OpenRaiser/Intern-Atlas huggingface dataset:
The Marriage of Incremental and Approximate Computing
Venue: arXiv cs.DC 2016
Year: 2016

Most data analytics systems that require low-latency execution and efficient utilization of computing resources, increasingly adopt two computational paradigms, namely, incremental and approximate computing. Incremental computation updates the output incrementally instead of re-computing everything from scratch for successive runs of a job with input changes. Approximate computation returns an approximate output for a job instead of the exact output. Both paradigms rely on computing over a subset of data items instead of computing over the entire dataset, but they differ in their means for skipping parts of the computation. Incremental computing relies on the memoization of intermediate results of sub-computations, and reusing these memoized results across jobs for sub-computations that are unaffected by the changed input. Approximate computing relies on representative sampling of the entire dataset to compute over a subset of data items. In this thesis, we make the observation that these two computing paradigms are complementary, and can be married together! The high level idea is to: design a sampling algorithm that biases the sample selection to the memoized data items from previous runs. To concretize this idea, we designed an online stratified sampling algorithm that uses self-adjusting computation to produce an incrementally updated approximate output with bounded error. We implemented our algorithm in a data analytics system called IncAppox based on Apache Spark Streaming. Our evaluation of the system shows that IncApprox achieves the benefits of both incremental and approximate computing.
PVANet: Lightweight Deep Neural Networks for Real-time Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

In object detection, reducing computational cost is as important as improving accuracy for most practical usages. This paper proposes a novel network structure, which is an order of magnitude lighter than other state-of-the-art networks while maintaining the accuracy. Based on the basic principle of more layers with less channels, this new deep neural network minimizes its redundancy by adopting recent innovations including C.ReLU and Inception structure. We also show that this network can be trained efficiently to achieve solid results on well-known object detection benchmarks: 84.9% and 84.2% mAP on VOC2007 and VOC2012 while the required compute is less than 10% of the recent ResNet-101.
Directional Mean Curvature for Textured Image Demixing
Venue: arXiv cs.CV 2016
Year: 2016

Approximation theory plays an important role in image processing, especially image deconvolution and decomposition. For piecewise smooth images, there are many methods that have been developed over the past thirty years. The goal of this study is to devise similar and practical methodology for handling textured images. This problem is motivated by forensic imaging, since fingerprints, shoeprints and bullet ballistic evidence are textured images. In particular, it is known that texture information is almost destroyed by a blur operator, such as a blurred ballistic image captured from a low-cost microscope. The contribution of this work is twofold: first, we propose a mathematical model for textured image deconvolution and decomposition into four meaningful components, using a high-order partial differential equation approach based on the directional mean curvature. Second, we uncover a link between functional analysis and multiscale sampling theory, e.g., harmonic analysis and filter banks. Both theoretical results and examples with natural images are provided to illustrate the performance of the proposed model.
Texture analysis using deterministic partially self-avoiding walk with thresholds
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a new texture analysis method using the deterministic partially self-avoiding walk performed on maps modified with thresholds. In this method, two pixels of the map are neighbors if the Euclidean distance between them is less than $\sqrt{2}$ and the weight (difference between its intensities) is less than a given threshold. The maps obtained by using different thresholds highlight several properties of the image that are extracted by the deterministic walk. To compose the feature vector, deterministic walks are performed with different thresholds and its statistics are concatenated. Thus, this approach can be considered as a multi-scale analysis. We validate our method on the Brodatz database, which is very well known public image database and widely used by texture analysis methods. Experimental results indicate that the proposed method presents a good texture discrimination, overcoming traditional texture methods.
Attention-based Memory Selection Recurrent Network for Language Modeling
Venue: arXiv cs.CL 2016
Year: 2016

Recurrent neural networks (RNNs) have achieved great success in language modeling. However, since the RNNs have fixed size of memory, their memory cannot store all the information about the words it have seen before in the sentence, and thus the useful long-term information may be ignored when predicting the next words. In this paper, we propose Attention-based Memory Selection Recurrent Network (AMSRN), in which the model can review the information stored in the memory at each previous time step and select the relevant information to help generate the outputs. In AMSRN, the attention mechanism finds the time steps storing the relevant information in the memory, and memory selection determines which dimensions of the memory are involved in computing the attention weights and from which the information is extracted.In the experiments, AMSRN outperformed long short-term memory (LSTM) based language models on both English and Chinese corpora. Moreover, we investigate using entropy as a regularizer for attention weights and visualize how the attention mechanism helps language modeling.
Training an Interactive Humanoid Robot Using Multimodal Deep Reinforcement Learning
Venue: arXiv cs.LG 2016
Year: 2016

Training robots to perceive, act and communicate using multiple modalities still represents a challenging problem, particularly if robots are expected to learn efficiently from small sets of example interactions. We describe a learning approach as a step in this direction, where we teach a humanoid robot how to play the game of noughts and crosses. Given that multiple multimodal skills can be trained to play this game, we focus our attention to training the robot to perceive the game, and to interact in this game. Our multimodal deep reinforcement learning agent perceives multimodal features and exhibits verbal and non-verbal actions while playing. Experimental results using simulations show that the robot can learn to win or draw up to 98% of the games. A pilot test of the proposed multimodal system for the targeted game---integrating speech, vision and gestures---reports that reasonable and fluent interactions can be achieved using the proposed approach.
Deep Reinforcement Learning for Multi-Domain Dialogue Systems
Venue: arXiv cs.AI 2016
Year: 2016

Standard deep reinforcement learning methods such as Deep Q-Networks (DQN) for multiple tasks (domains) face scalability problems. We propose a method for multi-domain dialogue policy learning---termed NDQN, and apply it to an information-seeking spoken dialogue system in the domains of restaurants and hotels. Experimental results comparing DQN (baseline) versus NDQN (proposed) using simulations report that our proposed method exhibits better scalability and is promising for optimising the behaviour of multi-domain dialogue systems.
Admissibility in Quantitative Graph Games
Venue: arXiv cs.LO 2016
Year: 2016

Admissibility has been studied for games of infinite duration with Boolean objectives. We extend here this study to games of infinite duration with quantitative objectives. First, we show that, un- der the assumption that optimal worst-case and cooperative strategies exist, admissible strategies are guaranteed to exist. Second, we give a characterization of admissible strategies using the no- tion of adversarial and cooperative values of a history, and we characterize the set of outcomes that are compatible with admissible strategies. Finally, we show how these characterizations can be used to design algorithms to decide relevant verification and synthesis problems.
Truthful Spectrum Auction for Efficient Anti-Jamming in Cognitive Radio Networks
Venue: arXiv cs.NI 2016
Year: 2016

One significant challenge in cognitive radio networks is to design a framework in which the selfish secondary users are obliged to interact with each other truthfully. Moreover, due to the vulnerability of these networks against jamming attacks, designing anti-jamming defense mechanisms is equally important. %providing the security defense is also of great importance. In this paper, we propose a truthful mechanism, robust against the jamming, for a dynamic stochastic cognitive radio network consisting of several selfish secondary users and a malicious user. In this model, each secondary user participates in an auction and wish to use the unjammed spectrum, and the malicious user aims at jamming a channel by corrupting the communication link. A truthful auction mechanism is designed among the secondary users. Furthermore, a zero-sum game is formulated between the set of secondary users and the malicious user. This joint problem is then cast as a randomized two-level auctions in which the first auction allocates the vacant channels, and then the second one assigns the remaining unallocated channels. We have also changed this solution to a trustful distributed scheme. Simulation results show that the distributed algorithm can achieve a performance that is close to the centralized algorithm, without the added overhead and complexity.
GSVD-Based Precoding in MIMO Systems With Integrated Services
Venue: arXiv cs.IT 2016
Year: 2016

This letter considers a two-receiver multiple-input multiple-output (MIMO) Gaussian broadcast channel model with integrated services. Specifically, we combine two sorts of service messages, and serve them simultaneously: one multicast message intended for both receivers and one confidential message intended for only one receiver. The confidential message is kept perfectly secure from the unauthorized receiver. Due to the coupling of service messages, it is intractable to seek capacity-achieving transmit covariance matrices. Accordingly, we propose a suboptimal precoding scheme based on the generalized singular value decomposition (GSVD). The GSVD produces several virtual orthogonal subchannels between the transmitter and the receivers. Subchannel allocation and power allocation between multicast message and confidential message are jointly optimized to maximize the secrecy rate in this letter, subject to the quality of multicast service (QoMS) constraints. Since this problem is inherently complex, a difference-of-concave (DC) algorithm, together with an exhaustive search, is exploited to handle the power allocation and subchannel allocation, respectively. Numerical results are presented to illustrate the efficacy of our proposed strategies.
Green Wireless Sensor Networks with Wireless Power Transfer
Venue: arXiv cs.NI 2016
Year: 2016

An energy cooperation policy for energy harvesting wireless sensor networks (WSNs) with wireless power transfer is proposed in this paper to balance the energy at each sensor node and increase the total energy utilization ratio of the whole WSNs. Considering the unbalanced spatio-temporal properties of the energy supply across the deployment terrain of energy harvesting WSNs and the dynamic traffic load at each sensor node, the energy cooperation problem among sensor nodes is decomposed into two steps: the local energy storage at each sensor node based on its traffic load to meet its own needs; within the energy storage procedure sensor nodes with excess energy transmit a part of their energy to nodes with energy shortage through the energy trading. Inventory theory and game theory are respectively applied to solving the local energy storage problem at each sensor node and the energy trading problem among multiple sensor nodes. Numerical results show that compared with the static energy cooperation method without energy trading, the Stackelberg Model based Game we design in this paper can significantly improve the trading volume of energy thereby increasing the utilization ratio of the harvested energy which is unevenly distributed in the WSNs.
Variational inequality approach to enforce the non-negative constraint for advection-diffusion equations
Venue: arXiv cs.CE 2016
Year: 2016

Predictive simulations are crucial for the success of many subsurface applications, and it is highly desirable to obtain accurate non-negative solutions for transport equations in these numerical simulations. In this paper, we propose a computational framework based on the variational inequality (VI) which can also be used to enforce important mathematical properties (e.g., maximum principles) and physical constraints (e.g., the non-negative constraint). We demonstrate that this framework is not only applicable to diffusion equations but also to non-symmetric advection-diffusion equations. An attractive feature of the proposed framework is that it works with with any weak formulation for the advection-diffusion equations, including single-field formulations, which are computationally attractive. A particular emphasis is placed on the parallel and algorithmic performance of the VI approach across large-scale and heterogeneous problems. It is also shown that QP and VI are equivalent under certain conditions. State-of-the-art QP and VI solvers available from the PETSc library are used on a variety of steady-state 2D and 3D benchmarks, and a comparative study on the scalability between the QP and VI solvers is presented. We then extend the proposed framework to transient problems by simulating the miscible displacement of fluids in a heterogeneous porous medium and illustrate the importance of enforcing maximum principles for these types of coupled problems. Our numerical experiments indicate that VIs are indeed a viable approach for enforcing the maximum principles and the non-negative constraint in a large-scale computing environment. Also provided are Firedrake project files as well as a discussion on the computer implementation to help facilitate readers in understanding the proposed framework.
A Linear-time Algorithm for Integral Multiterminal Flows in Trees
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we study the problem of finding an integral multiflow which maximizes the sum of flow values between every two terminals in an undirected tree with a nonnegative integer edge capacity and a set of terminals. In general, it is known that the flow value of an integral multiflow is bounded by the cut value of a cut-system which consists of disjoint subsets each of which contains exactly one terminal or has an odd cut value, and there exists a pair of an integral multiflow and a cut-system whose flow value and cut value are equal; i.e., a pair of a maximum integral multiflow and a minimum cut. In this paper, we propose an $O(n)$-time algorithm that finds such a pair of an integral multiflow and a cut-system in a given tree instance with $n$ vertices. This improves the best previous results by a factor of $Ω(n)$. Regarding a given tree in an instance as a rooted tree, we define $O(n)$ rooted tree instances taking each vertex as a root, and establish a recursive formula on maximum integral multiflow values of these instances to design a dynamic programming that computes the maximum integral multiflow values of all $O(n)$ rooted instances in linear time. We can prove that the algorithm implicitly maintains a cut-system so that not only a maximum integral multiflow but also a minimum cut-system can be constructed in linear time for any rooted instance whenever it is necessary. The resulting algorithm is rather compact and succinct.
A Low Complexity Detection Algorithm for SCMA
Venue: arXiv cs.IT 2016
Year: 2016

Sparse code multiple access (SCMA) is a new multiple access technique which supports massive connectivity. Compared with the current Long Term Evolution (LTE) system, it enables the overloading of active users on limited orthogonal resources and thus meets the requirement of the fifth generation (5G) wireless networks. However, the computation complexity of existing detection algorithms increases exponentially with $d_f$ (the degree of the resource nodes). Although the codebooks are designed to have low density, the detection still takes considerable time. The parameter $d_f$ must be designed to be very small, which largely limits the choice of codebooks. In this paper, a new detection algorithm is proposed by discretizing the probability distribution functions (PDFs) in the layer nodes (variable nodes). Given $M$ as the size of one codebook, the detection complexity of each resource node (function node) is reduced from $O(d_f M^{d_f})$ to $O(d_f^3 \ln (d_f))$. Its detection accuracy can quickly approach that of the previous detection algorithms with the decrease of sampling interval in discretization.
Uniform Information Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Size uniformity is one of the main criteria of superpixel methods. But size uniformity rarely conforms to the varying content of an image. The chosen size of the superpixels therefore represents a compromise - how to obtain the fewest superpixels without losing too much important detail. We propose that a more appropriate criterion for creating image segments is information uniformity. We introduce a novel method for segmenting an image based on this criterion. Since information is a natural way of measuring image complexity, our proposed algorithm leads to image segments that are smaller and denser in areas of high complexity and larger in homogeneous regions, thus simplifying the image while preserving its details. Our algorithm is simple and requires just one input parameter - a threshold on the information content. On segmentation comparison benchmarks it proves to be superior to the state-of-the-art. In addition, our method is computationally very efficient, approaching real-time performance, and is easily extensible to three-dimensional image stacks and video volumes.
Nonparametric General Reinforcement Learning
Venue: arXiv cs.AI 2016
Year: 2016

Reinforcement learning (RL) problems are often phrased in terms of Markov decision processes (MDPs). In this thesis we go beyond MDPs and consider RL in environments that are non-Markovian, non-ergodic and only partially observable. Our focus is not on practical algorithms, but rather on the fundamental underlying problems: How do we balance exploration and exploitation? How do we explore optimally? When is an agent optimal? We follow the nonparametric realizable paradigm. We establish negative results on Bayesian RL agents, in particular AIXI. We show that unlucky or adversarial choices of the prior cause the agent to misbehave drastically. Therefore Legg-Hutter intelligence and balanced Pareto optimality, which depend crucially on the choice of the prior, are entirely subjective. Moreover, in the class of all computable environments every policy is Pareto optimal. This undermines all existing optimality properties for AIXI. However, there are Bayesian approaches to general RL that satisfy objective optimality guarantees: We prove that Thompson sampling is asymptotically optimal in stochastic environments in the sense that its value converges to the value of the optimal policy. We connect asymptotic optimality to regret given a recoverability assumption on the environment that allows the agent to recover from mistakes. Hence Thompson sampling achieves sublinear regret in these environments. Our results culminate in a formal solution to the grain of truth problem: A Bayesian agent acting in a multi-agent environment learns to predict the other agents' policies if its prior assigns positive probability to them (the prior contains a grain of truth). We construct a large but limit computable class containing a grain of truth and show that agents based on Thompson sampling over this class converge to play Nash equilibria in arbitrary unknown computable multi-agent environments.
Online tools for public engagement: case studies from Reykjavik
Venue: arXiv cs.CY 2016
Year: 2016

With the ubiquity of Internet technologies and growing demands for transparency and open data policies, the role of social networking and online deliberation tools for public engagement in decision-making has increased substantially in the last decades. In this paper, we present the analysis of how social media are used by different public bodies to enhance public participation in deliberative democracy. We collected and reviewed published information on the subject and carried out a field base assessment, involving structured interviews with different government representatives and urban policymakers. In order to compare collected data, we used a framework for systematic analysis and comparison of e-participation platforms called the participatory cube. The results we got were the following. Participatory decision-making on matters of public concern justly consumes time and resources, therefore online tools should be applied with consideration of scale and efficiency, i.e. on burning issues for a majority of citizens or small-scale local platforms, and in combination with meetings in real time and space. The budget and workforce allocated to managing online engagement tools should be proportionate to other political and administrative efforts to bring to execution proposed ideas and act on collected feedback in order to satisfy the needs expressed by the communities and not undermine their beliefs about their power to influence decisions.
Improving Fully Convolution Network for Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Fully Convolution Networks (FCN) have achieved great success in dense prediction tasks including semantic segmentation. In this paper, we start from discussing FCN by understanding its architecture limitations in building a strong segmentation network. Next, we present our Improved Fully Convolution Network (IFCN). In contrast to FCN, IFCN introduces a context network that progressively expands the receptive fields of feature maps. In addition, dense skip connections are added so that the context network can be effectively optimized. More importantly, these dense skip connections enable IFCN to fuse rich-scale context to make reliable predictions. Empirically, those architecture modifications are proven to be significant to enhance the segmentation performance. Without engaging any contextual post-processing, IFCN significantly advances the state-of-the-arts on ADE20K (ImageNet scene parsing), Pascal Context, Pascal VOC 2012 and SUN-RGBD segmentation datasets.
Relational Logic with Framing and Hypotheses: Technical Report
Venue: arXiv cs.LO 2016
Year: 2016

Relational properties arise in many settings: relating two versions of a program that use different data representations, noninterference properties for security, etc. The main ingredient of relational verification, relating aligned pairs of intermediate steps, has been used in numerous guises, but existing relational program logics are narrow in scope. This paper introduces a logic based on novel syntax that weaves together product programs to express alignment of control flow points at which relational formulas are asserted. Correctness judgments feature hypotheses with relational specifications, discharged by a rule for the linking of procedure implementations. The logic supports reasoning about program-pairs containing both similar and dissimilar control and data structures. Reasoning about dynamically allocated objects is supported by a frame rule based on frame conditions amenable to SMT provers. We prove soundness and sketch how the logic can be used for data abstraction, loop optimizations, and secure information flow.