OpenRaiser/Intern-Atlas huggingface dataset:
Fitted Learning: Models with Awareness of their Limits
Venue: arXiv cs.AI 2018
Year: 2018

Though deep learning has pushed the boundaries of classification forward, in recent years hints of the limits of standard classification have begun to emerge. Problems such as fooling, adding new classes over time, and the need to retrain learning models only for small changes to the original problem all point to a potential shortcoming in the classic classification regime, where a comprehensive a priori knowledge of the possible classes or concepts is critical. Without such knowledge, classifiers misjudge the limits of their knowledge and overgeneralization therefore becomes a serious obstacle to consistent performance. In response to these challenges, this paper extends the classic regime by reframing classification instead with the assumption that concepts present in the training set are only a sample of the hypothetical final set of concepts. To bring learning models into this new paradigm, a novel elaboration of standard architectures called the competitive overcomplete output layer (COOL) neural network is introduced. Experiments demonstrate the effectiveness of COOL by applying it to fooling, separable concept learning, one-class neural networks, and standard classification benchmarks. The results suggest that, unlike conventional classifiers, the amount of generalization in COOL networks can be tuned to match the problem.
Functorial Hierarchical Clustering with Overlaps
Venue: arXiv cs.LG 2018
Year: 2018

This work draws inspiration from three important sources of research on dissimilarity-based clustering and intertwines those three threads into a consistent principled functorial theory of clustering. Those three are the overlapping clustering of Jardine and Sibson, the functorial approach of Carlsson and Mémoli to partition-based clustering, and the Isbell/Dress school's study of injective envelopes. Carlsson and Mémoli introduce the idea of viewing clustering methods as functors from a category of metric spaces to a category of clusters, with functoriality subsuming many desirable properties. Our first series of results extends their theory of functorial clustering schemes to methods that allow overlapping clusters in the spirit of Jardine and Sibson. This obviates some of the unpleasant effects of chaining that occur, for example with single-linkage clustering. We prove an equivalence between these general overlapping clustering functors and projections of weight spaces to what we term clustering domains, by focusing on the order structure determined by the morphisms. As a specific application of this machinery, we are able to prove that there are no functorial projections to cut metrics, or even to tree metrics. Finally, although we focus less on the construction of clustering methods (clustering domains) derived from injective envelopes, we lay out some preliminary results, that hopefully will give a feel for how the third leg of the stool comes into play.
Generative Visual Manipulation on the Natural Image Manifold
Venue: arXiv cs.CV 2018
Year: 2018

Realistic image manipulation is challenging because it requires modifying the image appearance in a user-controlled way, while preserving the realism of the result. Unless the user has considerable artistic skill, it is easy to "fall off" the manifold of natural images while editing. In this paper, we propose to learn the natural image manifold directly from data using a generative adversarial neural network. We then define a class of image editing operations, and constrain their output to lie on that learned manifold at all times. The model automatically adjusts the output keeping all edits as realistic as possible. All our manipulations are expressed in terms of constrained optimization and are applied in near-real time. We evaluate our algorithm on the task of realistic photo manipulation of shape and color. The presented method can further be used for changing one image to look like the other, as well as generating novel imagery from scratch based on user's scribbles.
Toward an Algebraic Theory of Systems
Venue: arXiv cs.OH 2018
Year: 2018

We propose the concept of a system algebra with a parallel composition operation and an interface connection operation, and formalize composition-order invariance, which postulates that the order of composing and connecting systems is irrelevant, a generalized form of associativity. Composition-order invariance explicitly captures a common property that is implicit in any context where one can draw a figure (hiding the drawing order) of several connected systems, which appears in many scientific contexts. This abstract algebra captures settings where one is interested in the behavior of a composed system in an environment and wants to abstract away anything internal not relevant for the behavior. This may include physical systems, electronic circuits, or interacting distributed systems. One specific such setting, of special interest in computer science, are functional system algebras, which capture, in the most general sense, any type of system that takes inputs and produces outputs depending on the inputs, and where the output of a system can be the input to another system. The behavior of such a system is uniquely determined by the function mapping inputs to outputs. We consider several instantiations of this very general concept. In particular, we show that Kahn networks form a functional system algebra and prove their composition-order invariance. Moreover, we define a functional system algebra of causal systems, characterized by the property that inputs can only influence future outputs, where an abstract partial order relation captures the notion of "later". This system algebra is also shown to be composition-order invariant and appropriate instantiations thereof allow to model and analyze systems that depend on time.
PSI (Ψ): a Private data Sharing Interface
Venue: arXiv cs.CR 2018
Year: 2018

We provide an overview of PSI ("a Private data Sharing Interface"), a system we are developing to enable researchers in the social sciences and other fields to share and explore privacy-sensitive datasets with the strong privacy protections of differential privacy.
Probabilistic Feature Selection and Classification Vector Machine
Venue: arXiv cs.LG 2018
Year: 2018

Sparse Bayesian learning is a state-of-the-art supervised learning algorithm that can choose a subset of relevant samples from the input data and make reliable probabilistic predictions. However, in the presence of high-dimensional data with irrelevant features, traditional sparse Bayesian classifiers suffer from performance degradation and low efficiency by failing to eliminate irrelevant features. To tackle this problem, we propose a novel sparse Bayesian embedded feature selection method that adopts truncated Gaussian distributions as both sample and feature priors. The proposed method, called probabilistic feature selection and classification vector machine (PFCVMLP ), is able to simultaneously select relevant features and samples for classification tasks. In order to derive the analytical solutions, Laplace approximation is applied to compute approximate posteriors and marginal likelihoods. Finally, parameters and hyperparameters are optimized by the type-II maximum likelihood method. Experiments on three datasets validate the performance of PFCVMLP along two dimensions: classification performance and effectiveness for feature selection. Finally, we analyze the generalization performance and derive a generalization error bound for PFCVMLP . By tightening the bound, the importance of feature selection is demonstrated.
A Variation on Chip-Firing: the diffusion game
Venue: arXiv cs.DM 2018
Year: 2018

We introduce a natural variant of the parallel chip-firing game, called the diffusion game. Chips are initially assigned to vertices of a graph. At every step, all vertices simultaneously send one chip to each neighbour with fewer chips. As the dynamics of the parallel chip-firing game occur on a finite set the process is inherently periodic. However the diffusion game is not obviously periodic: even if $2|E(G)|$ chips are assigned to vertices of graph G, there may exist time steps where some vertices have a negative number of chips. We investigate the process, prove periodicity for a number of graph classes, and pose some questions for future research.
Production-Driven Patch Generation and Validation
Venue: arXiv cs.SE 2018
Year: 2018

We envision a world where the developer would receive each morning in her GitHub dashboard a list of potential patches that fix certain production failures. For this, we propose a novel program repair scheme, with the unique feature of being applicable to production directly. We present the design and implementation of a prototype system for Java, called Itzal, that performs patch generation for uncaught exceptions in production. We have performed two empirical experiments to validate our system: the first one on 34 failures from 14 different software applications, the second one on 16 seeded failures in 3 real open-source e-commerce applications for which we have set up a realistic user traffic. This validates the novel and disruptive idea of using program repair directly in production.
PIR schemes with small download complexity and low storage requirements
Venue: arXiv cs.IT 2018
Year: 2018

In the classical model for (information theoretically secure) Private Information Retrieval (PIR), a user wishes to retrieve one bit of a database that is stored on a set of $n$ servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into $R$-bit records with $R>1$, and the user wishes to retrieve one record rather than one bit. When $R$ is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Shah, Rashmi and Ramchandran show that at least $R+1$ bits must be downloaded from servers in the worst case, and provide PIR schemes meeting this bound. Sun and Jafar determine the best asymptotic download cost of a PIR scheme (as $R\rightarrow\infty$), where this cost is defined as the ratio of the message length $R$ and the total number of bits downloaded. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number $n$ of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes, including explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average.
Commonsense Reasoning, Commonsense Knowledge, and The SP Theory of Intelligence
Venue: arXiv cs.AI 2018
Year: 2018

This paper describes how the "SP Theory of Intelligence" with the "SP Computer Model", outlined in an Appendix, may throw light on aspects of commonsense reasoning (CSR) and commonsense knowledge (CSK), as discussed in another paper by Ernest Davis and Gary Marcus (DM). In four main sections, the paper describes: 1) The main problems to be solved; 2) Other research on CSR and CSK; 3) Why the SP system may prove useful with CSR and CSK 4) How examples described by DM may be modelled in the SP system. With regard to successes in the automation of CSR described by DM, the SP system's strengths in simplification and integration may promote seamless integration across these areas, and seamless integration of those area with other aspects of intelligence. In considering challenges in the automation of CSR described by DM, the paper describes in detail, with examples of SP-multiple-alignments. how the SP system may model processes of interpretation and reasoning arising from the horse's head scene in "The Godfather" film. A solution is presented to the 'long tail' problem described by DM. The SP system has some potentially useful things to say about several of DM's objectives for research in CSR and CSK.
K-Regret Queries Using Multiplicative Utility Functions
Venue: arXiv cs.DB 2018
Year: 2018

The k-regret query aims to return a size-k subset S of a database D such that, for any query user that selects a data object from this size-k subset S rather than from database D, her regret ratio is minimized. The regret ratio here is modeled by the relative difference in the optimality between the locally optimal object in S and the globally optimal object in D. The optimality of a data object in turn is modeled by a utility function of the query user. Unlike traditional top-k queries, the k-regret query does not minimize the regret ratio for a specific utility function. Instead, it considers a family of infinite utility functions F, and aims to find a size-k subset that minimizes the maximum regret ratio of any utility function in F. Studies on k-regret queries have focused on the family of additive utility functions, which have limitations in modeling individuals' preferences and decision making processes, especially for a common observation called the diminishing marginal rate of substitution (DMRS). We introduce k-regret queries with multiplicative utility functions, which are more expressive in modeling the DMRS, to overcome those limitations. We propose a query algorithm with bounded regret ratios. To showcase the applicability of the algorithm, we apply it to a special family of multiplicative utility functions, the Cobb-Douglas family of utility functions, and a closely related family of utility functions, the Constant Elasticity of Substitution family of utility functions, both of which are frequently used utility functions in microeconomics. After a further study of the query properties, we propose a heuristic algorithm that produces even smaller regret ratios in practice. Extensive experiments on the proposed algorithms confirm that they consistently achieve small maximum regret ratios.
Exponential Separations in the Energy Complexity of Leader Election
Venue: arXiv cs.DC 2018
Year: 2018

Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), not on computation. In this paper we study the energy complexity of LeaderElection and ApproximateCounting in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions. We consider four collision-detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD and Receiver-CD (in which only transmitters or only listeners detect collisions), and No-CD (in which no one detects collisions.) The take-away message of our results is quite surprising. For randomized LeaderElection algorithms, there is an exponential gap between the energy complexity of Sender-CD and Receiver-CD, and for deterministic LeaderElection algorithms there is another exponential gap, but in the reverse direction. In particular, the randomized energy complexity of LeaderElection is $Θ(\log^* n)$ in Sender-CD but $Θ(\log(\log^* n))$ in Receiver-CD, where $n$ is the (unknown) number of devices. Its deterministic complexity is $Θ(\log N)$ in Receiver-CD but $Θ(\log\log N)$ in Sender-CD, where $N$ is the (known) size of the devices' ID space. There is a tradeoff between time and energy. We give a new upper bound on the time-energy tradeoff curve for randomized LeaderElection and ApproximateCounting. A critical component of this algorithm is a new deterministic LeaderElection algorithm for dense instances, when $n=Θ(N)$, with inverse-Ackermann-type ($O(α(N))$) energy complexity.
Median-of-k Jumplists and Dangling-Min BSTs
Venue: arXiv cs.DS 2018
Year: 2018

We extend randomized jumplists introduced by Brönnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomized algorithms with expected $O(\log n)$ time complexity that maintain the probability distribution of jump pointers upon insertions and deletions. We analyze the expected costs to search, insert and delete a random element, and we show that omitting jump pointers in small sublists hardly affects search costs, but significantly reduces the memory consumption. We use a bijection between jumplists and "dangling-min BSTs", a variant of (fringe-balanced) binary search trees for the analysis. Despite their similarities, some standard analysis techniques for search trees fail for dangling-min trees (and hence for jumplists).
Global Constraint Catalog, Volume II, Time-Series Constraints
Venue: arXiv cs.AI 2018
Year: 2018

First this report presents a restricted set of finite transducers used to synthesise structural time-series constraints described by means of a multi-layered function composition scheme. Second it provides the corresponding synthesised catalogue of structural time-series constraints where each constraint is explicitly described in terms of automata with registers.
Path Integral Guided Policy Search
Venue: arXiv cs.RO 2018
Year: 2018

We present a policy search method for learning complex feedback control policies that map from high-dimensional sensory inputs to motor torques, for manipulation tasks with discontinuous contact dynamics. We build on a prior technique called guided policy search (GPS), which iteratively optimizes a set of local policies for specific instances of a task, and uses these to train a complex, high-dimensional global policy that generalizes across task instances. We extend GPS in the following ways: (1) we propose the use of a model-free local optimizer based on path integral stochastic optimal control (PI2), which enables us to learn local policies for tasks with highly discontinuous contact dynamics; and (2) we enable GPS to train on a new set of task instances in every iteration by using on-policy sampling: this increases the diversity of the instances that the policy is trained on, and is crucial for achieving good generalization. We show that these contributions enable us to learn deep neural network policies that can directly perform torque control from visual input. We validate the method on a challenging door opening task and a pick-and-place task, and we demonstrate that our approach substantially outperforms the prior LQR-based local policy optimizer on these tasks. Furthermore, we show that on-policy sampling significantly increases the generalization ability of these policies.
Fast Cosine Similarity Search in Binary Space with Angular Multi-index Hashing
Venue: arXiv cs.DB 2018
Year: 2018

Given a large dataset of binary codes and a binary query point, we address how to efficiently find $K$ codes in the dataset that yield the largest cosine similarities to the query. The straightforward answer to this problem is to compare the query with all items in the dataset, but this is practical only for small datasets. One potential solution to enhance the search time and achieve sublinear cost is to use a hash table populated with binary codes of the dataset and then look up the nearby buckets to the query to retrieve the nearest neighbors. However, if codes are compared in terms of cosine similarity rather than the Hamming distance, then the main issue is that the order of buckets to probe is not evident. To examine this issue, we first elaborate on the connection between the Hamming distance and the cosine similarity. Doing this allows us to systematically find the probing sequence in the hash table. However, solving the nearest neighbor search with a single table is only practical for short binary codes. To address this issue, we propose the angular multi-index hashing search algorithm which relies on building multiple hash tables on binary code substrings. The proposed search algorithm solves the exact angular $K$ nearest neighbor problem in a time that is often orders of magnitude faster than the linear scan baseline and even approximation methods.
A Survey of Multi-View Representation Learning
Venue: arXiv cs.LG 2018
Year: 2018

Recently, multi-view representation learning has become a rapidly growing direction in machine learning and data mining areas. This paper introduces two categories for multi-view representation learning: multi-view representation alignment and multi-view representation fusion. Consequently, we first review the representative methods and theories of multi-view representation learning based on the perspective of alignment, such as correlation-based alignment. Representative examples are canonical correlation analysis (CCA) and its several extensions. Then from the perspective of representation fusion we investigate the advancement of multi-view representation learning that ranges from generative methods including multi-modal topic learning, multi-view sparse coding, and multi-view latent space Markov networks, to neural network-based methods including multi-modal autoencoders, multi-view convolutional neural networks, and multi-modal recurrent neural networks. Further, we also investigate several important applications of multi-view representation learning. Overall, this survey aims to provide an insightful overview of theoretical foundation and state-of-the-art developments in the field of multi-view representation learning and to help researchers find the most appropriate tools for particular applications.
Small Variance Asymptotics for Non-Parametric Online Robot Learning
Venue: arXiv cs.RO 2018
Year: 2018

Small variance asymptotics is emerging as a useful technique for inference in large scale Bayesian non-parametric mixture models. This paper analyses the online learning of robot manipulation tasks with Bayesian non-parametric mixture models under small variance asymptotics. The analysis yields a scalable online sequence clustering (SOSC) algorithm that is non-parametric in the number of clusters and the subspace dimension of each cluster. SOSC groups the new datapoint in its low dimensional subspace by online inference in a non-parametric mixture of probabilistic principal component analyzers (MPPCA) based on Dirichlet process, and captures the state transition and state duration information online in a hidden semi-Markov model (HSMM) based on hierarchical Dirichlet process. A task-parameterized formulation of our approach autonomously adapts the model to changing environmental situations during manipulation. We apply the algorithm in a teleoperation setting to recognize the intention of the operator and remotely adjust the movement of the robot using the learned model. The generative model is used to synthesize both time-independent and time-dependent behaviours by relying on the principles of shared and autonomous control. Experiments with the Baxter robot yield parsimonious clusters that adapt online with new demonstrations and assist the operator in performing remote manipulation tasks.