OpenRaiser/Intern-Atlas huggingface dataset:
Data-Driven Learning and Planning for Environmental Sampling
Venue: arXiv cs.RO 2018
Year: 2018

Robots such as autonomous underwater vehicles (AUVs) and autonomous surface vehicles (ASVs) have been used for sensing and monitoring aquatic environments such as oceans and lakes. Environmental sampling is a challenging task because the environmental attributes to be observed can vary both spatially and temporally, and the target environment is usually a large and continuous domain whereas the sampling data is typically sparse and limited. The challenges require that the sampling method must be informative and efficient enough to catch up with the environmental dynamics. In this paper we present a planning and learning method that enables a sampling robot to perform persistent monitoring tasks by learning and refining a dynamic "data map" that models a spatiotemporal environment attribute such as ocean salinity content. Our environmental sampling framework consists of two components: to maximize the information collected, we propose an informative planning component that efficiently generates sampling waypoints that contain the maximal information; To alleviate the computational bottleneck caused by large-scale data accumulated, we develop a component based on a sparse Gaussian Process whose hyperparameters are learned online by taking advantage of only a subset of data that provides the greatest contribution. We validate our method with both simulations running on real ocean data and field trials with an ASV in a lake environment. Our experiments show that the proposed framework is both accurate in learning the environmental data map and efficient in catching up with the dynamic environmental changes.
A one-shot achievability result for quantum state redistribution
Venue: arXiv cs.IT 2018
Year: 2018

We study the problem of entanglement-assisted quantum state redistribution in the one-shot setting and provide a new achievability result on the quantum communication required. Our bounds are in terms of the max-relative entropy and the hypothesis testing relative entropy. We use the techniques of convex split and position-based decoding to arrive at our result. We show that our result is upper bounded by the result obtained in Berta, Christandl, Touchette (2016).
A Complete Quantitative Deduction System for the Bisimilarity Distance on Markov Chains
Venue: arXiv cs.LO 2018
Year: 2018

In this paper we propose a complete axiomatization of the bisimilarity distance of Desharnais et al. for the class of finite labelled Markov chains. Our axiomatization is given in the style of a quantitative extension of equational logic recently proposed by Mardare, Panangaden, and Plotkin (LICS 2016) that uses equality relations $t \equiv_\varepsilon s$ indexed by rationals, expressing that `$t$ is approximately equal to $s$ up to an error $\varepsilon$'. Notably, our quantitative deduction system extends in a natural way the equational system for probabilistic bisimilarity given by Stark and Smolka by introducing an axiom for dealing with the Kantorovich distance between probability distributions. The axiomatization is then used to propose a metric extension of a Kleene's style representation theorem for finite labelled Markov chains, that was proposed (in a more general coalgebraic fashion) by Silva et al. (Inf. Comput. 2011).
A Deterministic and Generalized Framework for Unsupervised Learning with Restricted Boltzmann Machines
Venue: arXiv cs.LG 2018
Year: 2018

Restricted Boltzmann machines (RBMs) are energy-based neural-networks which are commonly used as the building blocks for deep architectures neural architectures. In this work, we derive a deterministic framework for the training, evaluation, and use of RBMs based upon the Thouless-Anderson-Palmer (TAP) mean-field approximation of widely-connected systems with weak interactions coming from spin-glass theory. While the TAP approach has been extensively studied for fully-visible binary spin systems, our construction is generalized to latent-variable models, as well as to arbitrarily distributed real-valued spin systems with bounded support. In our numerical experiments, we demonstrate the effective deterministic training of our proposed models and are able to show interesting features of unsupervised learning which could not be directly observed with sampling. Additionally, we demonstrate how to utilize our TAP-based framework for leveraging trained RBMs as joint priors in denoising problems.
Enabling Robots to Communicate their Objectives
Venue: arXiv cs.RO 2018
Year: 2018

The overarching goal of this work is to efficiently enable end-users to correctly anticipate a robot's behavior in novel situations. Since a robot's behavior is often a direct result of its underlying objective function, our insight is that end-users need to have an accurate mental model of this objective function in order to understand and predict what the robot will do. While people naturally develop such a mental model over time through observing the robot act, this familiarization process may be lengthy. Our approach reduces this time by having the robot model how people infer objectives from observed behavior, and then it selects those behaviors that are maximally informative. The problem of computing a posterior over objectives from observed behavior is known as Inverse Reinforcement Learning (IRL), and has been applied to robots learning human objectives. We consider the problem where the roles of human and robot are swapped. Our main contribution is to recognize that unlike robots, humans will not be exact in their IRL inference. We thus introduce two factors to define candidate approximate-inference models for human learning in this setting, and analyze them in a user study in the autonomous driving domain. We show that certain approximate-inference models lead to the robot generating example behaviors that better enable users to anticipate what it will do in novel situations. Our results also suggest, however, that additional research is needed in modeling how humans extrapolate from examples of robot behavior.
Random walk based in-network computation of arbitrary functions
Venue: arXiv cs.DC 2018
Year: 2018

We study in-network computation on general network topologies. Specifically, we are given the description of a function, and a network with distinct nodes at which the operands of the function are made available, and a designated sink where the computed value of the function is to be consumed. We want to compute the function during the process of moving the data towards the sink. Such settings have been studied in the literature, but mainly for symmetric functions, e.g. average, parity etc., which have the specific property that the output is invariant to permutation of the operands. To the best of our knowledge, we present the first fully decentralised algorithms for arbitrary functions, which we model as those functions whose computation schema is structured as a binary tree. We propose two algorithms, Fixed Random-Compute and Flexible Random-Compute, for this problem, both of which use simple random walks on the network as their basic primitive. Assuming a stochastic model for the generation of streams of data at each source, we provide a lower and an upper bound on the rate at which Fixed Random-Compute can compute the stream of associated function values. Note that the lower bound on rate though computed for our algorithm serves as a general lower bound for the function computation problem and to the best of our knowledge is first such lower bound for asymmetric functions. We also provide upper bounds on the average time taken to compute the function, characterising this time in terms of the fundamental parameters of the random walk on the network: the hitting time in the case of Fixed Random-Compute, and the mixing time in the case of Flexible Random-Compute.
A $(2+ε)$-Approximation for Maximum Weight Matching in the Semi-Streaming Model
Venue: arXiv cs.DS 2018
Year: 2018

We present a simple deterministic single-pass $(2+ε)$-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of $(4+ε)$. Our algorithm uses $O(n\log^2 n)$ bits of space for constant values of $ε$. It relies on a variation of the local-ratio theorem, which may be of use for other algorithms in the semi-streaming model as well.
Characterizing the Rate-Memory Tradeoff in Cache Networks within a Factor of 2
Venue: arXiv cs.IT 2018
Year: 2018

We consider a basic caching system, where a single server with a database of $N$ files (e.g. movies) is connected to a set of $K$ users through a shared bottleneck link. Each user has a local cache memory with a size of $M$ files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of $2.00884$ for both the peak rate and the average rate (under uniform file popularity), improving state of the arts that are within a factor of $4$ and $4.7$ respectively. Moreover, in a practically important case where the number of files ($N$) is large, we exactly characterize the tradeoff for systems with no more than $5$ users, and characterize the tradeoff within a factor of $2$ otherwise. To establish these results, we develop two new converse bounds that improve over the state of the art.
Solving Equations of Random Convex Functions via Anchored Regression
Venue: arXiv cs.LG 2018
Year: 2018

We consider the question of estimating a solution to a system of equations that involve convex nonlinearities, a problem that is common in machine learning and signal processing. Because of these nonlinearities, conventional estimators based on empirical risk minimization generally involve solving a non-convex optimization program. We propose anchored regression, a new approach based on convex programming that amounts to maximizing a linear functional (perhaps augmented by a regularizer) over a convex set. The proposed convex program is formulated in the natural space of the problem, and avoids the introduction of auxiliary variables, making it computationally favorable. Working in the native space also provides great flexibility as structural priors (e.g., sparsity) can be seamlessly incorporated. For our analysis, we model the equations as being drawn from a fixed set according to a probability law. Our main results provide guarantees on the accuracy of the estimator in terms of the number of equations we are solving, the amount of noise present, a measure of statistical complexity of the random equations, and the geometry of the regularizer at the true solution. We also provide recipes for constructing the anchor vector (that determines the linear functional to maximize) directly from the observed data.
Learning to Detect Human-Object Interactions
Venue: arXiv cs.CV 2018
Year: 2018

We study the problem of detecting human-object interactions (HOI) in static images, defined as predicting a human and an object bounding box with an interaction class label that connects them. HOI detection is a fundamental problem in computer vision as it provides semantic information about the interactions among the detected objects. We introduce HICO-DET, a new large benchmark for HOI detection, by augmenting the current HICO classification benchmark with instance annotations. To solve the task, we propose Human-Object Region-based Convolutional Neural Networks (HO-RCNN). At the core of our HO-RCNN is the Interaction Pattern, a novel DNN input that characterizes the spatial relations between two bounding boxes. Experiments on HICO-DET demonstrate that our HO-RCNN, by exploiting human-object spatial relations through Interaction Patterns, significantly improves the performance of HOI detection over baseline approaches.
Playing Games with Bounded Entropy
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we consider zero-sum repeated games in which the maximizer is restricted to strategies requiring no more than a limited amount of randomness. Particularly, we analyze the maxmin payoff of the maximizer in two models: the first model forces the maximizer to randomize her action in each stage just by conditioning her decision to outcomes of a given sequence of random source, whereas, in the second model, the maximizer is a team of players who are free to privately randomize their corresponding actions but do not have access to any explicit source of shared randomness needed for cooperation. The works of Gossner and Vieille, and Gossner and Tomala adopted the method of types to establish their results; however, we utilize the idea of random hashing which is the core of randomness extractors in the information theory literature. In addition, we adopt the well-studied tool of simulation of a source from another source. By utilizing these tools, we are able to simplify the prior results and generalize them as well. We characterize the maxmin payoff of the maximizer in the repeated games under study. Particularly, the maxmin payoff of the first model is fully described by the function $J(h)$ which is the maximum payoff that the maximizer can secure in a one-shot game by choosing mixed strategies of entropy at most $h$. In the second part of the paper, we study the computational aspects of $J(h)$. We offer three explicit lower bounds on the entropy-payoff trade-off curve. To do this, we provide and utilize new results for the set of distributions that guarantee a certain payoff for Alice. In particular, we study how this set of distributions shrinks as we increase the security level. While the use of total variation distance is common in game theory, our derivation indicates the suitability of utilizing the Renyi-divergence of order two.
Modeling of power distribution systems with solar generation: A case study
Venue: arXiv cs.SY 2018
Year: 2018

This document presents the data for a single-phase distribution bus (based on IEEE 37 bus) together with the model and data for a PV inverter and active and reactive power loads.
Generalized Deterministic Perturbations For Stochastic Gradient Search
Venue: arXiv cs.SY 2018
Year: 2018

Stochastic optimization (SO) considers the problem of optimizing an objective function in the presence of noise. Most of the solution techniques in SO estimate gradients from the noise corrupted observations of the objective and adjust parameters of the objective along the direction of the estimated gradients to obtain locally optimal solutions. Two prominent algorithms in SO namely Random Direction Kiefer-Wolfowitz (RDKW) and Simultaneous Perturbation Stochastic Approximation (SPSA) obtain noisy gradient estimate by randomly perturbing all the parameters simultaneously. This forces the search direction to be random in these algorithms and causes them to suffer additional noise on top of the noise incurred from the samples of the objective. Owing to this additional noise, the idea of using deterministic perturbations instead of random perturbations for gradient estimation has also been studied. Two specific constructions of the deterministic perturbation sequence using lexicographical ordering and Hadamard matrices have been explored and encouraging results have been reported in the literature. In this paper, we characterize the class of deterministic perturbation sequences that can be utilized in the RDKW algorithm. This class expands the set of known deterministic perturbation sequences available in the literature. Using our characterization we propose a construction of a deterministic perturbation sequence that has the least possible cycle length among all deterministic perturbations. Through simulations we illustrate the performance gain of the proposed deterministic perturbation sequence in the RDKW algorithm over the Hadamard and the random perturbation counterparts. We establish the convergence of the RDKW algorithm for the generalized class of deterministic perturbations.
Online Representation Learning with Single and Multi-layer Hebbian Networks for Image Classification
Venue: arXiv cs.NE 2018
Year: 2018

Unsupervised learning permits the development of algorithms that are able to adapt to a variety of different data sets using the same underlying rules thanks to the autonomous discovery of discriminating features during training. Recently, a new class of Hebbian-like and local unsupervised learning rules for neural networks have been developed that minimise a similarity matching cost-function. These have been shown to perform sparse representation learning. This study tests the effectiveness of one such learning rule for learning features from images. The rule implemented is derived from a nonnegative classical multidimensional scaling cost-function, and is applied to both single and multi-layer architectures. The features learned by the algorithm are then used as input to an SVM to test their effectiveness in classification on the established CIFAR-10 image dataset. The algorithm performs well in comparison to other unsupervised learning algorithms and multi-layer networks, thus suggesting its validity in the design of a new class of compact, online learning networks.
Bounding the inefficiency of compromise in opinion formation
Venue: arXiv cs.GT 2018
Year: 2018

Social networks on the Internet have seen an enormous growth recently and play a crucial role in different aspects of today's life. They have facilitated information dissemination in ways that have been beneficial for their users but they are often used strategically in order to spread information that only serves the objectives of particular users. These properties have inspired a revision of classical opinion formation models from sociology using game-theoretic notions and tools. We follow the same modeling approach, focusing on scenarios where the opinion expressed by each user is a compromise between her internal belief and the opinions of a small number of neighbors among her social acquaintances. We formulate simple games that capture this behavior and quantify the inefficiency of equilibria using the well-known notion of the price of anarchy. Our results indicate that compromise comes at a cost that strongly depends on the neighborhood size.
On the Optimality of Secret Key Agreement via Omniscience
Venue: arXiv cs.IT 2018
Year: 2018

For the multiterminal secret key agreement problem under a private source model, it is known that the maximum key rate, i.e., the secrecy capacity, can be achieved through communication for omniscience, but the omniscience strategy can be strictly suboptimal in terms of minimizing the public discussion rate. While a single-letter characterization is not known for the minimum discussion rate needed for achieving the secrecy capacity, we derive single-letter lower and upper bounds that yield some simple conditions for omniscience to be discussion-rate optimal. These conditions turn out to be enough to deduce the optimality of omniscience for a large class of sources including the hypergraphical sources. Through conjectures and examples, we explore other source models to which our methods do not easily extend.
Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret
Venue: arXiv cs.LG 2018
Year: 2018

We present an efficient second-order algorithm with $\tilde{O}(\frac{1}η\sqrt{T})$ regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by $η$, for a range of $η$ restricted by the norm of the competitor. The family of loss functions ranges from hinge loss ($η=0$) to squared hinge loss ($η=1$). This provides a solution to the open problem of (J. Abernethy and A. Rakhlin. An efficient bandit algorithm for $\sqrt{T}$-regret in online multiclass prediction? In COLT, 2009). We test our algorithm experimentally, showing that it also performs favorably against earlier algorithms.
Selective Video Object Cutout
Venue: arXiv cs.CV 2018
Year: 2018

Conventional video segmentation approaches rely heavily on appearance models. Such methods often use appearance descriptors that have limited discriminative power under complex scenarios. To improve the segmentation performance, this paper presents a pyramid histogram based confidence map that incorporates structure information into appearance statistics. It also combines geodesic distance based dynamic models. Then, it employs an efficient measure of uncertainty propagation using local classifiers to determine the image regions where the object labels might be ambiguous. The final foreground cutout is obtained by refining on the uncertain regions. Additionally, to reduce manual labeling, our method determines the frames to be labeled by the human operator in a principled manner, which further boosts the segmentation performance and minimizes the labeling effort. Our extensive experimental analyses on two big benchmarks demonstrate that our solution achieves superior performance, favorable computational efficiency, and reduced manual labeling in comparison to the state-of-the-art.
Nash and Wardrop equilibria in aggregative games with coupling constraints
Venue: arXiv cs.SY 2018
Year: 2018

We consider the framework of aggregative games, in which the cost function of each agent depends on his own strategy and on the average population strategy. As first contribution, we investigate the relations between the concepts of Nash and Wardrop equilibrium. By exploiting a characterization of the two equilibria as solutions of variational inequalities, we bound their distance with a decreasing function of the population size. As second contribution, we propose two decentralized algorithms that converge to such equilibria and are capable of coping with constraints coupling the strategies of different agents. Finally, we study the applications of charging of electric vehicles and of route choice on a road network.
Iterative Bayesian Learning for Crowdsourced Regression
Venue: arXiv cs.LG 2018
Year: 2018

Crowdsourcing platforms emerged as popular venues for purchasing human intelligence at low cost for large volume of tasks. As many low-paid workers are prone to give noisy answers, a common practice is to add redundancy by assigning multiple workers to each task and then simply average out these answers. However, to fully harness the wisdom of the crowd, one needs to learn the heterogeneous quality of each worker. We resolve this fundamental challenge in crowdsourced regression tasks, i.e., the answer takes continuous labels, where identifying good or bad workers becomes much more non-trivial compared to a classification setting of discrete labels. In particular, we introduce a Bayesian iterative scheme and show that it provably achieves the optimal mean squared error. Our evaluations on synthetic and real-world datasets support our theoretical results and show the superiority of the proposed scheme.