mtybilly/Instruct2DS huggingface dataset:
(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings
Authors: Adam Smith Abhradeep Guha Thakurta
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We provide a general technique for making online learning algorithms differentially private, in both the full information and bandit settings. Our technique applies to algorithms that aim to minimize a \emph{convex} loss function which is a sum of smaller convex loss terms, one for each data point. We modify the popular \emph{mirror descent} approach, or rather a variant called \emph{follow the approximate leader}.    The technique leads to the first nonprivate algorithms for private online learning in the bandit setting. In the full information setting, our algorithms improve over the regret bounds of previous work.  In many cases, our algorithms (in both settings) matching the dependence on the input length, $T$, of the \emph{optimal nonprivate} regret bounds up to logarithmic factors in $T$. Our algorithms require logarithmic space and update time.
The Fast Convergence of Incremental PCA
Authors: Sanjoy Dasgupta, Yoav Freund Akshay Balsubramani
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We prove the first finite-sample convergence rates for any incremental PCA algorithm using sub-quadratic time and memory per iteration. The algorithm analyzed is Oja's learning rule, an efficient and well-known scheme for estimating the top principal component. Our analysis of this non-convex problem yields expected and high-probability convergence rates of $\tilde{O}(1/n)$ through a novel technique. We relate our guarantees to existing rates for stochastic gradient descent on strongly convex functions, and extend those results. We also include experiments which demonstrate convergence behaviors predicted by our analysis.
Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs
Authors: Charles L Isbell Liam C MacDermed
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This paper presents four major results towards solving decentralized partially observable Markov decision problems (DecPOMDPs) culminating in an algorithm that outperforms all existing algorithms on all but one standard infinite-horizon benchmark problems. (1) We give an integer program that solves collaborative Bayesian games (CBGs). The program is notable because its linear relaxation is very often integral. (2) We show that a DecPOMDP with bounded belief can be converted to a POMDP (albeit with actions exponential in the number of beliefs). These actions correspond to strategies of a CBG. (3) We present a method to transform any DecPOMDP into a DecPOMDP with bounded beliefs (the number of beliefs is a free parameter) using optimal (not lossless) belief compression. (4) We show that the combination of these results opens the door for new classes of DecPOMDP algorithms based on previous POMDP algorithms. We choose one such algorithm, point-based valued iteration, and modify it to produce the first tractable value iteration method for DecPOMDPs which outperforms existing algorithms.
Summary Statistics for Partitionings and Feature Allocations
Authors: Taylan Cemgil Isik B Fidaner
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Infinite mixture models are commonly used for clustering. One can sample from the posterior of mixture assignments by Monte Carlo methods or find its maximum a posteriori solution by optimization. However, in some problems the posterior is diffuse and it is hard to interpret the sampled partitionings. In this paper, we introduce novel statistics based on block sizes for representing sample sets of partitionings and feature allocations. We develop an element-based definition of entropy to quantify segmentation among their elements. Then we propose a simple algorithm called entropy agglomeration (EA) to summarize and visualize this information. Experiments on various infinite mixture posteriors as well as a feature allocation dataset demonstrate that the proposed statistics are useful in practice.
Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition
Authors: Jeff Schneider Tzu-Kuo Huang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Learning dynamic models from observed data has been a central issue in many scientific  studies or engineering tasks. The usual setting is that data are collected sequentially  from trajectories of some dynamical system operation.   In quite a few modern scientific modeling tasks, however, it turns out that  reliable sequential data are rather difficult to gather, whereas out-of-order snapshots are much easier to obtain. Examples include the modeling of galaxies, chronic diseases such Alzheimer's, or certain biological processes.  Existing methods for learning dynamic model from non-sequence data are mostly based on Expectation-Maximization, which involves non-convex optimization and is thus hard to analyze.  Inspired by recent advances in spectral learning methods, we propose to study this problem  from a different perspective: moment matching and spectral decomposition. Under that framework,  we identify reasonable assumptions on the generative process of non-sequence data,  and propose learning algorithms based on the tensor decomposition method  \cite{anandkumar2012tensor} to \textit{provably} recover first-order Markov models and hidden Markov models. To the best of our knowledge, this is the first formal guarantee on learning from non-sequence data. Preliminary simulation results confirm our theoretical findings.
On Flat versus Hierarchical Classification in Large-Scale Taxonomies
Authors: Ioannis Partalas, Eric Gaussier, Massih R. Amini Rohit Babbar
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We study in this paper flat and hierarchical classification strategies in the context of large-scale taxonomies. To this end, we first propose a multiclass, hierarchical data dependent bound on the generalization error of classifiers deployed in large-scale taxonomies. This bound provides an explanation to several empirical results reported in the literature, related to the performance of flat and hierarchical classifiers. We then introduce another type of bounds targeting the approximation error of a family of classifiers, and derive from it features used in a meta-classifier to decide which nodes to prune (or flatten) in a large-scale taxonomy. We finally illustrate the theoretical developments through several experiments conducted on two widely used taxonomies.
Scoring Workers in Crowdsourcing: How Many Control Questions are Enough?
Authors: Alex Ihler, Mark Steyvers Qiang Liu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We study the problem of estimating continuous quantities, such as prices, probabilities, and point spreads, using a crowdsourcing approach.  A challenging aspect of combining the crowd's answers is that workers' reliabilities and biases are usually unknown and highly diverse.  Control items with known answers can be used to evaluate workers' performance, and hence improve the combined results on the target items with unknown answers.  This raises the problem of how many control items to use when the total number of items each workers can answer is limited: more control items evaluates the workers better, but leaves fewer resources for the target items that are of direct interest, and vice versa. We give theoretical results for this problem under different scenarios, and provide a simple rule of thumb for crowdsourcing practitioners.  As a byproduct, we also provide theoretical analysis of the accuracy of different consensus methods.
Cluster Trees on Manifolds
Authors: Srivatsan Narayanan, Alessandro Rinaldo, Aarti Singh, Larry Wasserman Sivaraman Balakrishnan
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We investigate the problem of estimating the cluster tree for a density $f$ supported on or near a smooth $d$-dimensional manifold $M$ isometrically embedded in $\mathbb{R}^D$. We study a $k$-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta. Under mild assumptions on $f$ and $M$, we obtain rates of convergence that depend on $d$ only but not on the ambient dimension $D$. We also provide a sample complexity lower bound for a natural class of clustering algorithms that use $D$-dimensional neighborhoods.
Bayesian inference as iterated random functions with  applications to sequential inference in graphical models
Authors: Xuanlong Nguyen Arash Amini
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We propose a general formalism of iterated random functions with semigroup property, under which exact and approximate Bayesian posterior updates can be viewed as specific instances. A convergence theory for iterated random functions is presented. As an application of the general theory we analyze convergence behaviors of exact and approximate message-passing algorithms that arise in a sequential change point detection problem formulated via a latent variable directed graphical model. The sequential inference algorithm and its supporting theory are  illustrated by simulated examples.
Recurrent networks of coupled Winner-Take-All oscillators for solving constraint satisfaction problems
Authors: Lorenz. K Mueller, Giacomo Indiveri Hesham Mostafa
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We present a recurrent neuronal network, modeled as a continuous-time dynamical system, that can solve constraint satisfaction problems. Discrete variables are represented by coupled Winner-Take-All (WTA) networks, and their values are encoded in localized patterns of oscillations that are learned by the recurrent weights in these networks. Constraints over the variables are encoded in the network connectivity. Although there are no sources of noise, the network can escape from local optima in its search for solutions that satisfy all constraints by modifying the effective network connectivity through oscillations. If there is no solution that satisfies all constraints, the network state changes in a pseudo-random manner and its trajectory approximates a sampling procedure that selects a variable assignment with a probability that increases with the fraction of constraints satisfied by this assignment. External evidence, or input to the network, can force variables to specific values. When new inputs are applied, the network re-evaluates the entire set of variables in its search for the states that satisfy the maximum number of constraints, while being consistent with the external input. Our results demonstrate that the proposed network architecture can perform a deterministic search for the optimal solution to problems with non-convex cost functions. The network is inspired by canonical microcircuit models of the cortex and suggests possible dynamical mechanisms to solve constraint satisfaction problems that can be present in biological networks, or implemented in neuromorphic electronic circuits.
Rapid Distance-Based Outlier Detection via Sampling
Authors: Karsten Borgwardt Mahito Sugiyama
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Distance-based approaches to outlier detection are popular in data mining, as they do not require to model the underlying probability distribution, which is particularly challenging for high-dimensional data. We present an empirical comparison of various approaches to distance-based outlier detection across a large number of datasets. We report the surprising observation that a simple, sampling-based scheme outperforms state-of-the-art techniques in terms of both efficiency and effectiveness. To better understand this phenomenon, we provide a theoretical analysis why the sampling-based approach outperforms alternative methods based on k-nearest neighbor search.
Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies
Authors: Joshua T. Abbott, Joseph L Austerweil, Tom Griffiths, Trevor Darrell Yangqing Jia
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Learning a visual concept from a small number of positive examples is a significant challenge for machine learning algorithms. Current methods typically fail to find the appropriate level of generalization in a concept hierarchy for a given set of visual examples. Recent work in cognitive science on Bayesian models of generalization addresses this challenge, but prior results assumed that objects were perfectly  recognized. We present an algorithm for learning visual concepts directly from images, using  probabilistic predictions generated by visual classifiers as the input to a Bayesian generalization model. As no existing challenge data tests this paradigm, we collect and make available a new, large-scale dataset for visual concept learning using the ImageNet hierarchy as the source of possible concepts, with human annotators to provide ground truth labels as to whether a new image is an instance of each concept using a paradigm similar to that used in experiments studying word learning in children.  We compare the performance of our system to several baseline algorithms, and show a significant advantage results from combining visual classifiers with the ability to identify an appropriate level of abstraction using Bayesian generalization.
Memoized Online Variational Inference for Dirichlet Process Mixture Models
Authors: Erik Sudderth Michael C Hughes
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Variational inference algorithms provide the most effective framework for large-scale training  of Bayesian nonparametric models. Stochastic online approaches are promising, but are sensitive to the chosen learning rate and often converge to poor local optima.  We present a new algorithm, memoized online variational inference, which scales to very large (yet finite) datasets while avoiding the complexities of stochastic gradient.  Our algorithm maintains finite-dimensional sufficient statistics from batches of the full dataset, requiring some additional memory but still scaling to millions of examples.  Exploiting nested families of variational bounds for infinite nonparametric models, we develop principled birth and merge moves allowing non-local optimization.  Births adaptively add components to the model to escape local optima, while merges remove redundancy and improve speed.  Using Dirichlet process mixture models for image clustering and denoising, we demonstrate major improvements in robustness and accuracy.
Locally Adaptive Bayesian Multivariate Time Series
Authors: Bruno Scarpa, David B Dunson Daniele Durante
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In modeling multivariate time series, it is important to allow time-varying smoothness in the mean and covariance process. In particular, there may be certain time intervals exhibiting rapid changes and others in which changes are slow. If such locally adaptive smoothness is not accounted for, one can obtain misleading inferences and predictions, with over-smoothing across erratic time intervals and under-smoothing across times exhibiting slow variation. This can lead to miscalibration of predictive intervals, which can be substantially too narrow or wide depending on the time. We propose a continuous multivariate stochastic process for time series having locally varying smoothness in both the mean and covariance matrix. This process is constructed utilizing latent dictionary functions in time, which are given nested Gaussian process priors and linearly related to the observed data through a sparse mapping. Using a differential equation representation, we bypass usual computational bottlenecks in obtaining MCMC and online algorithms for approximate Bayesian inference. The performance is assessed in simulations and illustrated in a financial application.
When in Doubt, SWAP: High-Dimensional Sparse Recovery from Correlated Measurements
Authors: Richard Baraniuk Divyanshu Vats
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider the problem of accurately estimating a high-dimensional sparse vector using a small number of linear measurements that are contaminated by noise.  It is well known that standard computationally tractable sparse recovery algorithms, such as the Lasso, OMP, and their various extensions, perform poorly when the measurement matrix contains highly correlated columns.  We develop a simple greedy algorithm, called SWAP, that iteratively swaps variables until a desired loss function cannot be decreased any further.  SWAP is surprisingly effective in handling measurement matrices with high correlations.  We prove that SWAP can be easily used as a wrapper around standard sparse recovery algorithms for improved performance.  We theoretically quantify the statistical guarantees of SWAP and complement our analysis with numerical results on synthetic and real data.
Information-theoretic lower bounds for distributed statistical estimation with communication constraints
Authors: John Duchi, Michael I Jordan, Martin J. Wainwright Yuchen Zhang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We establish minimax risk lower bounds for distributed statistical estimation given a budget $B$ of the total number of bits that may be communicated. Such lower bounds in turn reveal the minimum amount of communication required by any procedure to achieve the classical optimal rate for statistical estimation. We study two classes of protocols in which machines send messages either independently or interactively. The lower bounds are established for a variety of problems, from estimating the mean of a population to estimating parameters in linear regression or binary classification.
Learning Stochastic Feedforward Neural Networks
Authors: Ruslan Salakhutdinov Charlie Tang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Multilayer perceptrons (MLPs) or neural networks are popular models used for nonlinear regression and classification tasks. As regressors, MLPs model the conditional distribution of the predictor variables Y given the input variables X. However, this predictive distribution is assumed to be unimodal (e.g. Gaussian). For tasks such as structured prediction problems, the conditional distribution should be multimodal, forming one-to-many mappings. By using stochastic hidden variables rather than deterministic ones, Sigmoid Belief Nets (SBNs) can induce a rich multimodal distribution in the output space. However, previously proposed learning algorithms for SBNs are very slow and do not work well for real-valued data. In this paper, we propose a stochastic feedforward network with hidden layers having \emph{both deterministic and stochastic} variables. A new Generalized EM training procedure using importance sampling allows us to efficiently learn complicated conditional distributions. We demonstrate the superiority of our model to conditional Restricted Boltzmann Machines and Mixture Density Networks on synthetic datasets and on modeling facial expressions. Moreover, we show that latent features of our model improves classification and provide additional qualitative results on color images.
Robust Transfer Principal Component Analysis with Rank Constraints
Authors: Yuhong Guo
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Principal component analysis (PCA), a well-established technique for data analysis and processing, provides a convenient form of dimensionality reduction that is effective for cleaning small Gaussian noises presented in the data. However, the applicability of standard principal component analysis in real scenarios is limited by its sensitivity to large errors. In this paper, we tackle the challenge problem of recovering data corrupted with errors of high magnitude by developing a novel robust transfer principal component analysis method. Our method is based on the assumption that useful information for the recovery of a corrupted data matrix can be gained from an uncorrupted related data matrix. Speciﬁcally, we formulate the data recovery problem as a joint robust principal component analysis problem on the two data matrices, with shared common principal components across matrices and individual principal components speciﬁc to each data matrix. The formulated optimization problem is a minimization problem over a convex objective function but with non-convex rank constraints. We develop an efﬁcient proximal projected gradient descent algorithm to solve the proposed optimization problem with convergence guarantees. Our empirical results over image denoising tasks show the proposed method can effectively recover images with random large errors, and signiﬁcantly outperform both standard PCA and robust PCA.
A Determinantal Point Process Latent Variable Model for Inhibition in Neural Spiking Data
Authors: Richard Zemel, Ryan P. Adams Jasper Snoek
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Point processes are popular models of neural spiking behavior as they provide a statistical distribution over temporal sequences of spikes and help to reveal the complexities underlying a series of recorded action potentials.  However, the most common neural point process models, the Poisson process and the gamma renewal process, do not capture interactions and correlations that are critical to modeling populations of neurons.  We develop a novel model based on a determinantal point process over latent embeddings of neurons that effectively captures and helps visualize complex inhibitory and competitive interaction.  We show that this model is a natural extension of the popular generalized linear model to sets of interacting neurons.   The model is extended to incorporate gain control or divisive normalization, and the modulation of neural spiking based on periodic phenomena.  Applied to neural spike recordings from the rat hippocampus, we see that the model captures inhibitory relationships, a dichotomy of classes of neurons, and a periodic modulation by the theta rhythm known to be present in the data.
Reciprocally Coupled Local Estimators Implement Bayesian Information Integration Distributively
Authors: Si Wu Wen-Hao Zhang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Psychophysical experiments have demonstrated that the brain integrates information from multiple sensory cues in a near Bayesian optimal manner. The present study proposes a novel mechanism to achieve this. We consider two reciprocally connected networks, mimicking the integration of heading direction information between the dorsal medial superior temporal (MSTd) and the ventral intraparietal (VIP) areas. Each network serves as a local estimator and receives an independent cue, either the visual or the vestibular, as direct input for the external stimulus. We find that positive reciprocal interactions can improve the decoding accuracy of each individual network as if it implements Bayesian inference from two cues. Our model successfully explains the experimental finding that both MSTd and VIP achieve Bayesian multisensory integration, though each of them only receives a single cue as direct external input. Our result suggests that the brain may implement optimal information integration distributively at each local estimator through the reciprocal connections between cortical regions.
Structured Learning via Logistic Regression
Authors: Justin Domke
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: A successful approach to structured learning is to write the learning objective as a joint function of linear parameters and inference messages, and iterate between updates to each. This paper observes that if the inference problem is “smoothed” through the addition of entropy terms, for fixed messages, the learning objective reduces to a traditional (non-structured) logistic regression problem with respect to parameters. In these logistic regression problems, each training example has a bias term determined by the current set of messages. Based on this insight, the structured energy function can be extended from linear factors to any function class where an “oracle” exists to minimize a logistic loss.
Learning word embeddings efficiently with noise-contrastive estimation
Authors: Koray Kavukcuoglu Andriy Mnih
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Continuous-valued word embeddings learned by neural language models have recently been shown to capture semantic and syntactic information about words very well, setting performance records on several word similarity tasks.  The best results are obtained by learning high-dimensional embeddings from very large quantities of data, which makes scalability of the training method a critical factor.  We propose a simple and scalable new approach to learning word embeddings based on training log-bilinear models with noise-contrastive estimation.  Our approach is simpler, faster, and produces better results than the current state-of-the art method of Mikolov et al. (2013a). We achieve results comparable to the best ones reported, which were obtained on a cluster, using four times less data and more than an order of magnitude less computing time. We also investigate several model types and find that the embeddings learned by the simpler models perform at least as well as those learned by the more complex ones.
Generalized Method-of-Moments for Rank Aggregation
Authors: William Chen, David C. Parkes, Lirong Xia Hossein Azari Soufiani
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this paper we propose a class of efficient Generalized Method-of-Moments(GMM) algorithms for computing parameters of the Plackett-Luce model, where the data consists of full rankings over alternatives. Our technique is based on breaking the full rankings into pairwise comparisons, and then computing parameters that satisfy a set of generalized moment conditions. We identify conditions for the output of GMM to be unique, and identify a general class of consistent and inconsistent breakings. We then show by theory and experiments that our algorithms run significantly faster than the classical Minorize-Maximization (MM) algorithm, while achieving competitive statistical efficiency.
Reconciling "priors" & "priors" without prejudice?
Authors: Pierre Machart Remi Gribonval
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: There are two major routes to address linear inverse problems. Whereas regularization-based approaches build estimators as solutions of penalized regression optimization problems, Bayesian estimators rely on the posterior distribution of the unknown, given some assumed family of priors. While these may seem radically different approaches, recent results have shown that, in the context of additive white Gaussian denoising, the Bayesian conditional mean estimator is always the solution of a penalized regression problem. The contribution of this paper is twofold. First, we extend the additive white Gaussian denoising results to general linear inverse problems with colored Gaussian noise. Second, we characterize conditions under which the penalty function associated to the conditional mean estimator can satisfy certain popular properties such as convexity, separability, and smoothness. This sheds light on some tradeoff between computational efficiency and estimation accuracy in sparse regularization, and draws some connections between Bayesian estimation and proximal optimization.
Learning a Deep Compact Image Representation for Visual Tracking
Authors: Dit-Yan Yeung Naiyan Wang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this paper, we study the challenging problem of tracking the trajectory of a moving object in a video with possibly very complex background.  In contrast to most existing trackers which only learn the appearance of the tracked object online, we take a different approach, inspired by recent advances in deep learning architectures, by putting more emphasis on the (unsupervised) feature learning problem.  Specifically, by using auxiliary natural images, we train a stacked denoising autoencoder offline to learn generic image features that are more robust against variations.  This is then followed by knowledge transfer from offline training to the online tracking process.  Online tracking involves a classification neural network which is constructed from the encoder part of the trained autoencoder as a feature extractor and an additional classification layer.  Both the feature extractor and the classifier can be further tuned to adapt to appearance changes of the moving object.  Comparison with the state-of-the-art trackers on some challenging benchmark video sequences shows that our deep learning tracker is very efficient as well as more accurate.
Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent
Authors: Tianbao Yang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We present and study a distributed optimization algorithm by employing  a stochastic dual coordinate ascent method. Stochastic dual coordinate ascent methods enjoy strong theoretical guarantees and often have better performances than stochastic gradient descent methods in optimizing regularized loss minimization problems. It still lacks of efforts in studying them in a distributed framework. We make a progress along the line by presenting a distributed stochastic dual coordinate ascent algorithm in a star network, with an analysis of the tradeoff between  computation and  communication. We verify  our analysis by experiments on real data sets. Moreover, we compare the proposed algorithm with distributed stochastic gradient descent methods and distributed alternating direction methods of multipliers for optimizing SVMs in the same distributed framework, and observe competitive performances.
Projected Natural Actor-Critic
Authors: William C Dabney, Stephen Giguere, Sridhar Mahadevan Philip S. Thomas
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Natural actor-critics are a popular class of policy search algorithms for finding locally optimal policies for Markov decision processes. In this paper we address a drawback of natural actor-critics that limits their real-world applicability - their lack of safety guarantees. We present a principled algorithm for performing natural gradient descent over a constrained domain. In the context of reinforcement learning, this allows for natural actor-critic algorithms that are guaranteed to remain within a known safe region of policy space. While deriving our class of constrained natural actor-critic algorithms, which we call Projected Natural Actor-Critics (PNACs), we also elucidate the relationship between natural gradient descent and mirror descent.
Minimax Optimal Algorithms for Unconstrained Linear Optimization
Authors: Jacob Abernethy Brendan McMahan
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We design and analyze minimax-optimal algorithms for online linear   optimization games where the player's choice is unconstrained.  The   player strives to minimize regret, the difference between his loss   and the loss of a post-hoc benchmark strategy.  The standard   benchmark is the loss of the best strategy chosen from a bounded   comparator set, whereas we consider a broad range of benchmark   functions. We consider the problem as a sequential multi-stage   zero-sum game, and we give a thorough analysis of the minimax   behavior of the game, providing characterizations for the value of   the game, as well as both the player's and the adversary's optimal   strategy.  We show how these objects can be computed efficiently   under certain circumstances, and by selecting an appropriate   benchmark, we construct a novel hedging strategy for an   unconstrained betting game.
Policy Shaping: Integrating Human Feedback with Reinforcement Learning
Authors: Kaushik Subramanian, Jonathan Scholz, Charles L Isbell, Andrea L Thomaz Shane Griffith
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: A long term goal of Interactive Reinforcement Learning is to incorporate non-expert human feedback to solve complex tasks. State-of-the-art methods have approached this problem by mapping human information to reward and value signals to indicate preferences and then iterating over them to compute the necessary control policy. In this paper we argue for an alternate, more effective characterization of human feedback: Policy Shaping. We introduce Advise, a Bayesian approach that attempts to maximize the information gained from human feedback by utilizing it as direct labels on the policy. We compare Advise to state-of-the-art approaches and highlight scenarios where it outperforms them and importantly is robust to infrequent and inconsistent human feedback.
Regret based Robust Solutions for Uncertain Markov Decision Processes
Authors: Pradeep Varakantham, Yossiri Adulyasak, Patrick Jaillet Asrar Ahmed
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this paper, we seek robust policies for uncertain Markov Decision Processes (MDPs). Most robust optimization approaches for these problems have focussed on the computation of {\em maximin} policies which maximize the value corresponding to the worst realization of the uncertainty. Recent work has proposed {\em minimax} regret as a suitable alternative to the {\em maximin} objective for robust optimization.  However, existing algorithms for handling {\em minimax} regret are restricted to models with uncertainty over rewards only.  We provide algorithms that employ sampling to improve across multiple dimensions: (a) Handle uncertainties over both transition and reward models; (b) Dependence of model uncertainties across state, action pairs and decision epochs; (c) Scalability and quality bounds. Finally, to demonstrate the empirical effectiveness of our sampling approaches, we provide comparisons against benchmark algorithms on two domains from literature. We also provide a Sample Average Approximation (SAA) analysis to compute a posteriori error bounds.
Understanding variable importances in forests of randomized trees
Authors: Louis Wehenkel, Antonio Sutera, Pierre Geurts Gilles Louppe
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Despite growing interest and practical use in various scientific areas, variable importances derived from tree-based ensemble methods are not well understood from a theoretical point of view. In this work we characterize the Mean Decrease Impurity (MDI) variable importances as measured by an ensemble of totally randomized trees in asymptotic sample and ensemble size conditions. We derive a three-level decomposition of the  information jointly provided by all input variables about the output in terms of i) the MDI importance of each input variable, ii) the degree of interaction of a given input variable with the other input variables, iii) the different interaction terms of a given degree. We then show that this MDI importance of a variable is equal to zero if and only if the variable is irrelevant and that the MDI importance of a relevant variable is invariant with respect to the removal or the addition of irrelevant variables. We illustrate these properties on a simple example and discuss how they may change in the case of  non-totally randomized trees such as Random Forests and Extra-Trees.
Linear decision rule as aspiration for simple decision heuristics
Authors: Ozgur Simsek
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Many attempts to understand the success of simple decision heuristics have examined heuristics as an approximation to a linear decision rule. This research has identified three environmental structures that aid heuristics: dominance, cumulative dominance, and noncompensatoriness. Here, we further develop these ideas and examine their empirical relevance in 51 natural environments. We find that all three structures are prevalent, making it possible for some simple rules to reach the accuracy levels of the linear decision rule using less information.
Adaptive Multi-Column Deep Neural Networks with Application to Robust Image Denoising
Authors: Michael R Anderson, Honglak Lee Forest Agostinelli
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Stacked sparse denoising auto-encoders (SSDAs) have recently been shown to be successful at removing noise from corrupted images. However, like most denoising techniques, the SSDA is not robust to variation in noise types beyond what it has seen during training. We present the multi-column stacked sparse denoising autoencoder, a novel technique of combining multiple SSDAs into a multi-column SSDA (MC-SSDA) by combining the outputs of each SSDA. We eliminate the need to determine the type of noise, let alone its statistics, at test time. We show that good denoising performance can be achieved with a single system on a variety of different noise types, including ones not seen in the training set. Additionally, we experimentally demonstrate the efficacy of MC-SSDA denoising by achieving MNIST digit error rates on denoised images at close to that of the uncorrupted images.
Probabilistic Movement Primitives
Authors: Christian Daniel, Jan R Peters, Gerhard Neumann Alexandros Paraschos
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Movement Primitives (MP) are a well-established approach for representing modular and re-usable robot movement generators. Many state-of-the-art robot learning successes are based MPs, due to their compact representation of the inherently continuous and high dimensional robot movements. A major goal in robot learning is to combine multiple MPs as building blocks in a modular control architecture to solve complex tasks. To this effect, a MP representation has to allow for blending between motions, adapting to altered task variables, and co-activating multiple MPs in parallel. We present a probabilistic formulation of the MP concept that maintains a distribution over trajectories. Our probabilistic approach allows for the derivation of new operations which are essential for implementing all aforementioned properties in one framework. In order to use such a trajectory distribution for robot movement control, we analytically derive a stochastic feedback controller which reproduces the given trajectory distribution. We evaluate and compare our approach to existing methods on several simulated as well as real robot scenarios.
Speedup Matrix Completion with Side Information: Application to Multi-Label Learning
Authors: Rong Jin, Zhi-Hua Zhou Miao Xu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In standard matrix completion theory, it is required to have at least $O(n\ln^2 n)$ observed entries to perfectly recover a low-rank matrix $M$ of size $n\times n$, leading to a large number of observations when $n$ is large. In many real tasks, side information in addition to the observed entries is often available. In this work, we develop a novel theory of matrix completion that explicitly explore the side information to reduce the requirement on the number of observed entries. We show that, under appropriate conditions, with the assistance of side information matrices, the number of observed entries needed for a perfect recovery of matrix $M$ can be dramatically reduced to $O(\ln n)$. We demonstrate the effectiveness of the proposed approach for matrix completion in transductive incomplete multi-label learning.
Message Passing Inference with Chemical Reaction Networks
Authors: Ryan P. Adams Nils E Napp
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Recent work on molecular programming has explored new possibilities for computational abstractions with biomolecules, including logic gates, neural networks, and linear systems.  In the future such abstractions might enable nanoscale devices that can sense and control the world at a molecular scale.  Just as in macroscale robotics, it is critical that such devices can learn about their environment and reason under uncertainty. At this small scale, systems are typically modeled as chemical reaction networks. In this work, we develop a procedure that can take arbitrary probabilistic graphical models, represented as factor graphs over discrete random variables, and compile them into chemical reaction networks that implement inference.  In particular, we show that marginalization based on sum-product message passing can be implemented in terms of reactions between chemical species whose concentrations represent probabilities.  We show algebraically that the steady state concentration of these species correspond to the marginal distributions of the random variables in the graph and validate the results in simulations.  As with standard sum-product inference, this procedure yields exact results for tree-structured graphs, and approximate solutions for loopy graphs.
Binary to Bushy: Bayesian Hierarchical Clustering with the Beta Coalescent
Authors: Jordan L Ying, Hal Daume III, Z. Irene Ying Yuening Hu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Discovering hierarchical regularities in data is a key problem in interacting   with large datasets, modeling cognition, and encoding knowledge. A previous   Bayesian solution---Kingman's coalescent---provides a convenient probabilistic   model for data represented as a binary tree. Unfortunately, this is   inappropriate for data better described by bushier trees. We generalize an   existing belief propagation framework of Kingman's coalescent to the   beta coalescent, which models a wider range of tree structures.   Because of the complex combinatorial search over possible structures, we   develop new sampling schemes using sequential Monte Carlo and Dirichlet   process mixture models, which render inference efficient and tractable.     We present results on both synthetic and real data that show the beta coalescent      outperforms Kingman's coalescent on real datasets and is qualitatively better at    capturing data in bushy hierarchies.
A Stability-based Validation Procedure for Differentially Private Machine Learning
Authors: Staal A Vinterbo Kamalika Chaudhuri
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Differential privacy is a cryptographically motivated definition of privacy which has gained considerable attention in the algorithms, machine-learning and data-mining communities. While there has been an explosion of work on differentially private machine learning algorithms, a major barrier to achieving end-to-end differential privacy in practical machine learning applications is the lack of an effective procedure for differentially private parameter tuning, or, determining the parameter value, such as a bin size in a histogram, or a regularization parameter, that is suitable for a particular application.   In this paper, we introduce a generic validation procedure for differentially private machine learning algorithms that apply when a certain stability condition holds on the training algorithm and the validation performance metric. The training data size and the privacy budget used for training in our procedure is independent of the number of parameter values searched over. We apply our generic procedure to two fundamental tasks in statistics and machine-learning -- training a regularized linear classifier and building a histogram density estimator that result in end-to-end differentially private solutions for these problems.
Unsupervised Spectral Learning of Finite State Transducers
Authors: Xavier Carreras, Ariadna Quattoni Raphael Bailly
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Finite-State Transducers (FST) are a standard tool for modeling paired input-output sequences and are used in numerous applications, ranging from computational biology to natural language processing. Recently Balle et al. presented a spectral algorithm for learning FST from samples of aligned input-output sequences.  In this paper we address the more realistic, yet challenging setting where the alignments are unknown to the learning algorithm. We frame FST learning as finding a low rank Hankel matrix satisfying constraints derived from observable statistics. Under this formulation, we provide identifiability results for FST distributions. Then, following previous work on rank minimization, we propose a regularized convex relaxation of this objective which is based on minimizing a nuclear norm penalty subject to linear constraints and can be solved efficiently.
One-shot learning and big data with n=2
Authors: Dean P. Foster Lee H Dicker
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We model a one-shot learning" situation, where very few (scalar) observations $y_1,...,y_n$ are available. Associated with each observation $y_i$ is a very high-dimensional vector $x_i$, which provides context for $y_i$ and enables us to predict subsequent observations, given their own context. One of the salient features of our analysis is that the problems studied here are easier when the dimension of $x_i$ is large; in other words, prediction becomes easier when more context is provided. The proposed methodology is a variant of principal component regression (PCR). Our rigorous analysis sheds new light on PCR. For instance, we show that classical PCR estimators may be inconsistent in the specified setting, unless they are multiplied by a scalar $c > 1$; that is, unless the classical estimator is expanded. This expansion phenomenon appears to be somewhat novel and contrasts with shrinkage methods ($c < 1$), which are far more common in big data analyses. "