pwc-archive/papers-with-abstracts huggingface dataset:
On the Sample Complexity of Robust PCA
Authors: Matthew Coudron, Gilad Lerman
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We estimate the sample complexity of a recent robust estimator for a generalized version of the inverse covariance matrix. This estimator is used in a convex algorithm for robust subspace recovery (i.e., robust PCA). Our model assumes a sub-Gaussian underlying distribution and an i.i.d.~sample from it. Our main result shows with high probability that the norm of the difference between the generalized inverse covariance of the underlying distribution and its estimator from an i.i.d.~sample of size $N$ is of order $O(N^{-0.5+\eps})$ for arbitrarily small $\eps>0$ (affecting the probabilistic estimate); this rate of convergence is close to one of direct covariance and inverse covariance estimation, i.e., $O(N^{-0.5})$. Our precise probabilistic estimate implies for some natural settings that the sample complexity of the generalized inverse covariance estimation when using the Frobenius norm is $O(D^{2+\delta})$ for arbitrarily small $\delta>0$ (whereas the sample complexity of direct covariance estimation with Frobenius norm is $O(D^{2})$). These results provide similar rates of convergence and sample complexity for the corresponding robust subspace recovery algorithm, which are close to those of PCA. To the best of our knowledge, this is the only work analyzing the sample complexity of any robust PCA algorithm.
Latent Coincidence Analysis: A Hidden Variable Model for Distance Metric Learning
Authors: Matthew Der, Lawrence K. Saul
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Dimensionality Reduction, Metric Learning, parameter estimation, Supervised dimensionality reduction

We describe a latent variable model for supervised dimensionality reduction and distance metric learning. The model discovers linear projections of high dimensional data that shrink the distance between similarly labeled inputs and expand the distance between differently labeled ones. The model’s continuous latent variables locate pairs of examples in a latent space of lower dimensionality. The model differs significantly from classical factor analysis in that the posterior distribution over these latent variables is not always multivariate Gaussian. Nevertheless we show that inference is completely tractable and derive an Expectation-Maximization (EM) algorithm for parameter estimation. We also compare the model to other approaches in distance metric learning. The model’s main advantage is its simplicity: at each iteration of the EM algorithm, the distance metric is re-estimated by solving an unconstrained least-squares problem. Experiments show that these simple updates are highly effective.
Trajectory-Based Short-Sighted Probabilistic Planning
Authors: Felipe Trevizan, Manuela Veloso
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Probabilistic planning captures the uncertainty of plan execution by probabilistically modeling the effects of actions in the environment, and therefore the probability of reaching different states from a given state and action. In order to compute a solution for a probabilistic planning problem, planners need to manage the uncertainty associated with the different paths from the initial state to a goal state. Several approaches to manage uncertainty were proposed, e.g., consider all paths at once, perform determinization of actions, and sampling. In this paper, we introduce trajectory-based short-sighted Stochastic Shortest Path Problems (SSPs), a novel approach to manage uncertainty for probabilistic planning problems in which states reachable with low probability are substituted by artificial goals that heuristically estimate their cost to reach a goal state. We also extend the theoretical results of Short-Sighted Probabilistic Planner (SSiPP) [ref] by proving that SSiPP always finishes and is asymptotically optimal under sufficient conditions on the structure of short-sighted SSPs.  We empirically compare SSiPP using trajectory-based short-sighted SSPs with the winners of the previous probabilistic planning competitions and other state-of-the-art planners in the triangle tireworld problems. Trajectory-based SSiPP outperforms all the competitors and is the only planner able to scale up to problem number 60, a problem in which the optimal solution contains approximately $10^{70}$ states.
Interpreting prediction markets: a stochastic approach
Authors: Rafael M. Frongillo, Nicholás Della Penna, Mark D. Reid
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Prediction

We strengthen recent connections between prediction markets and learning by showing that a natural class of market makers can be understood as performing stochastic mirror descent when trader demands are sequentially drawn from a fixed distribution. This provides new insights into how market prices (and price paths) may be interpreted as a summary of the market's belief distribution by relating them to the optimization problem being solved. In particular, we show that the stationary point of the stochastic process of prices generated by the market is equal to the market's Walrasian equilibrium of classic market analysis. Together, these results suggest how traditional market making mechanisms might be replaced with general purpose learning algorithms while still retaining guarantees about their behaviour.
Risk-Aversion in Multi-armed Bandits
Authors: Amir Sani, Alessandro Lazaric, Rémi Munos
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Multi-Armed Bandits

In stochastic multi--armed bandits the objective is to solve the exploration--exploitation dilemma and ultimately maximize the expected reward. Nonetheless, in many practical problems, maximizing the expected reward is not the most desirable objective. In this paper, we introduce a novel setting based on the principle of risk--aversion where the objective is to compete against the arm with the best risk--return trade--off. This setting proves to be intrinsically more difficult than the standard multi-arm bandit setting due in part to an exploration risk which introduces a regret associated to the variability of an algorithm. Using variance as a measure of risk, we introduce two new algorithms, we investigate their theoretical guarantees, and we report preliminary empirical results.
Confusion-Based Online Learning and a Passive-Aggressive Scheme
Authors: Liva Ralaivola
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Generalization Bounds

This paper provides the first ---to the best of our knowledge--- analysis of online learning algorithms for multiclass problems when the {\em confusion} matrix is taken as a performance measure. The work builds upon recent and elegant results on noncommutative concentration inequalities, i.e. concentration inequalities that apply to matrices, and more precisely to matrix martingales.  We do establish generalization bounds for online learning algorithm and show how the theoretical study motivate the proposition of a new confusion-friendly learning procedure. This learning algorithm, called \copa (for COnfusion Passive-Aggressive) is a passive-aggressive learning algorithm; it is shown that the update equations for \copa can be computed analytically, thus allowing the user from having to recours to any optimization package to implement it.
Cardinality Restricted Boltzmann Machines
Authors: Kevin Swersky, Ilya Sutskever, Daniel Tarlow, Richard S. Zemel, Ruslan R. Salakhutdinov, Ryan P. Adams
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The Restricted Boltzmann Machine (RBM) is a popular density model that is also good for extracting features. A main source of tractability in RBM models is the model's assumption that given an input, hidden units activate independently from one another. Sparsity and competition in the hidden representation is believed to be beneficial, and while an RBM with competition among its hidden units would acquire some of the attractive properties of sparse coding, such constraints are not added  due to the widespread belief that the resulting model would become intractable.  In this work, we show how a dynamic programming algorithm developed in 1981 can be used to implement exact sparsity in the RBM's hidden units. We then expand on this and show how to pass derivatives through a layer of exact sparsity, which makes it possible to fine-tune a deep belief network (DBN) consisting of RBMs with sparse hidden layers.  We show that sparsity in the RBM's hidden layer improves the performance of both the pre-trained representations and of the fine-tuned model.
Shaping Level Sets with Submodular Functions
Authors: Francis R. Bach
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Change Point Detection, Clustering, Outlier Detection

We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on  non-decreasing functions, we explore symmetric submodular functions and their \lova extensions. We show that the Lovasz extension may be seen as the convex envelope of a function that depends on level sets  (i.e., the set of indices whose corresponding components of the underlying predictor are greater than a given constant): this leads to a class of convex structured regularization terms that impose prior knowledge on the level sets, and not only on the supports of the underlying predictors. We provide a unified set of optimization algorithms, such as proximal operators, and theoretical guarantees (allowed level sets and recovery conditions). By selecting specific submodular functions,  we   give a new interpretation to known norms, such as the total variation; we also define new norms, in particular ones that are based on order statistics with application to clustering and outlier detection, and on noisy cuts in graphs with application to change point detection in the presence of outliers.
Nonlinear Inverse Reinforcement Learning with Gaussian Processes
Authors: Sergey Levine, Zoran Popovic, Vladlen Koltun
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Gaussian Processes, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We present a probabilistic algorithm for nonlinear inverse reinforcement learning. The goal of inverse reinforcement learning is to learn the reward function in a Markov decision process from expert demonstrations. While most prior inverse reinforcement learning algorithms represent the reward as a linear combination of a set of features, we use Gaussian processes to learn the reward as a nonlinear function, while also determining the relevance of each feature to the expert's policy. Our probabilistic algorithm allows complex behaviors to be captured from suboptimal stochastic demonstrations, while automatically balancing the simplicity of the learned reward structure against its consistency with the observed actions.
Video Annotation and Tracking with Active Learning
Authors: Carl Vondrick, Deva Ramanan
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Active Learning

We introduce a novel active learning framework for video annotation. By  judiciously choosing which frames a user should annotate, we can obtain highly  accurate tracks with minimal user effort.  We cast this problem as one of  active learning, and show that we can obtain excellent performance by querying  frames that, if annotated, would produce a large expected change in the  estimated object track. We implement a constrained tracker and compute the  expected change for putative annotations with efficient dynamic programming  algorithms.  We demonstrate our framework on four datasets, including two  benchmark datasets constructed with key frame annotations obtained by Amazon  Mechanical Turk. Our results indicate that we could obtain equivalent labels  for a small fraction of the original cost.
On U-processes and clustering performance
Authors: Stéphan J. Clémençcon
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering, Model Selection

Many clustering techniques aim at optimizing empirical criteria that are of the  form of a U-statistic of degree two. Given a measure of dissimilarity between  pairs of observations, the goal is to minimize the within cluster point scatter over  a class of partitions of the feature space. It is the purpose of this paper to define  a general statistical framework, relying on the theory of U-processes, for studying  the performance of such clustering methods. In this setup, under adequate  assumptions on the complexity of the subsets forming the partition candidates, the  excess of clustering risk is proved to be of the order O(1/\sqrt{n}). Based on recent  results related to the tail behavior of degenerate U-processes, it is also shown how  to establish tighter rate bounds. Model selection issues, related to the number of  clusters forming the data partition in particular, are also considered.
Penalty Decomposition Methods for Rank Minimization
Authors: Yong Zhang, Zhaosong Lu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Matrix Completion

In this paper we consider general rank minimization problems with rank appearing in either objective function or constraint. We first show that a class of matrix optimization problems can be solved as lower dimensional vector optimization problems. As a consequence, we establish that a class of rank minimization problems have closed form solutions. Using this result, we then propose penalty decomposition methods for general rank minimization problems. The convergence results of the PD methods have been shown in the longer version of the paper. Finally, we test the performance of our methods by applying them to matrix completion and nearest low-rank correlation matrix problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed.
Sparse Manifold Clustering and Embedding
Authors: Ehsan Elhamifar, René Vidal
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering, Dimensionality Reduction

We propose an algorithm called Sparse Manifold Clustering and Embedding (SMCE) for simultaneous clustering and dimensionality reduction of data lying in multiple nonlinear manifolds. Similar to most dimensionality reduction methods, SMCE finds a small neighborhood around each data point and connects each point to its neighbors with appropriate weights. The key difference is that SMCE finds both the neighbors and the weights automatically. This is done by solving a sparse optimization problem, which encourages selecting nearby points that lie in the same manifold and approximately span a low-dimensional affine subspace. The optimal solution encodes information that can be used for clustering and dimensionality reduction using spectral clustering and embedding. Moreover, the size of the optimal neighborhood of a data point, which can be different for different points, provides an estimate of the dimension of the manifold to which the point belongs. Experiments demonstrate that our method can effectively handle multiple manifolds that are very close to each other, manifolds with non-uniform sampling and holes, as well as estimate the intrinsic dimensions of the manifolds.
Unifying Non-Maximum Likelihood Learning Objectives with Minimum KL Contraction
Authors: Siwei Lyu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

When used to learn high dimensional parametric probabilistic models, the clas- sical maximum likelihood (ML) learning often suffers from computational in- tractability, which motivates the active developments of non-ML learning meth- ods. Yet, because of their divergent motivations and forms, the objective func- tions of many non-ML learning methods are seemingly unrelated, and there lacks a unified framework to understand them. In this work, based on an information geometric view of parametric learning, we introduce a general non-ML learning principle termed as minimum KL contraction, where we seek optimal parameters that minimizes the contraction of the KL divergence between the two distributions after they are transformed with a KL contraction operator. We then show that the objective functions of several important or recently developed non-ML learn- ing methods, including contrastive divergence [12], noise-contrastive estimation [11], partial likelihood [7], non-local contrastive objectives [31], score match- ing [14], pseudo-likelihood [3], maximum conditional likelihood [17], maximum mutual information [2], maximum marginal likelihood [9], and conditional and marginal composite likelihood [24], can be unified under the minimum KL con- traction framework with different choices of the KL contraction operators.
Image Parsing with Stochastic Scene Grammar
Authors: Yibiao Zhao, Song-Chun Zhu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering, Scene Labeling, Scene Understanding

This paper proposes a parsing algorithm for scene understanding which includes four aspects: computing 3D scene layout, detecting 3D objects (e.g. furniture), detecting 2D faces (windows, doors etc.), and segmenting background. In contrast to previous scene labeling work that applied discriminative classifiers to pixels (or super-pixels), we use a generative Stochastic Scene Grammar (SSG). This grammar represents the compositional structures of visual entities from scene categories, 3D foreground/background, 2D faces, to 1D lines. The grammar includes three types of production rules and two types of contextual relations. Production rules: (i) AND rules represent the decomposition of an entity into sub-parts; (ii) OR rules represent the switching among sub-types of an entity; (iii) SET rules rep- resent an ensemble of visual entities. Contextual relations: (i) Cooperative “+” relations represent positive links between binding entities, such as hinged faces of a object or aligned boxes; (ii) Competitive “-” relations represents negative links between competing entities, such as mutually exclusive boxes. We design an efficient MCMC inference algorithm, namely Hierarchical cluster sampling, to search in the large solution space of scene configurations. The algorithm has two stages: (i) Clustering: It forms all possible higher-level structures (clusters) from lower-level entities by production rules and contextual relations. (ii) Sampling: It jumps between alternative structures (clusters) in each layer of the hierarchy to find the most probable configuration (represented by a parse tree). In our experiment, we demonstrate the superiority of our algorithm over existing methods on public dataset. In addition, our approach achieves richer structures in the parse tree.
A Reinforcement Learning Theory for Homeostatic Regulation
Authors: Mehdi Keramati, Boris S. Gutkin
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Learning Theory, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Reinforcement learning models address animal's behavioral adaptation to its changing "external" environment, and are based on the assumption that Pavlovian, habitual and goal-directed responses seek to maximize reward acquisition. Negative-feedback models of homeostatic regulation, on the other hand, are concerned with behavioral adaptation in response to the "internal" state of the animal, and assume that animals' behavioral objective is to minimize deviations of some key physiological variables from their hypothetical setpoints. Building upon the drive-reduction theory of reward, we propose a new analytical framework that integrates learning and regulatory systems, such that the two seemingly unrelated objectives of reward maximization and physiological-stability prove to be identical. The proposed theory shows behavioral adaptation to both internal and external states in a disciplined way. We further show that the proposed framework allows for a unified explanation of some behavioral phenomenon like motivational sensitivity of different associative learning mechanism, anticipatory responses, interaction among competing motivational systems, and risk aversion.
Learning large-margin halfspaces with more malicious noise
Authors: Phil Long, Rocco Servedio
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We describe a simple algorithm that runs in time  poly(n,1/gamma,1/eps) and learns an unknown n-dimensional  gamma-margin halfspace to accuracy 1-eps in the presence of  malicious noise, when the noise rate is allowed to be as high as  Theta(eps gamma sqrt(log(1/gamma))). Previous efficient  algorithms could only learn to accuracy eps in the presence of  malicious noise of rate at most Theta(eps gamma).    Our algorithm does not work by optimizing a convex loss function.  We  show that no algorithm for learning gamma-margin halfspaces that  minimizes a convex proxy for misclassification error can tolerate  malicious noise at a rate greater than Theta(eps gamma); this may  partially explain why previous algorithms could not achieve the higher  noise tolerance of our new algorithm.
On Strategy Stitching in Large Extensive Form Multiplayer Games
Authors: Richard G. Gibson, Duane Szafron
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Form

Computing a good strategy in a large extensive form game often demands an extraordinary amount of computer memory, necessitating the use of abstraction to reduce the game size.  Typically, strategies from abstract games perform better in the real game as the granularity of abstraction is increased.  This paper investigates two techniques for stitching a base strategy in a coarse abstraction of the full game tree, to expert strategies in fine abstractions of smaller subtrees.  We provide a general framework for creating static experts, an approach that generalizes some previous strategy stitching efforts.  In addition, we show that static experts can create strong agents for both 2-player and 3-player Leduc and Limit Texas Hold'em poker, and that a specific class of static experts can be preferred among a number of alternatives.  Furthermore, we describe a poker agent that used static experts and won the 3-player events of the 2010 Annual Computer Poker Competition.
Environmental statistics and the trade-off between model-based and TD learning in humans
Authors: Dylan A. Simon, Nathaniel D. Daw
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Decision Making, Incremental Learning

There is much evidence that humans and other animals utilize a combination of model-based and model-free RL methods.  Although it has been proposed that these systems may dominate according to their relative statistical efficiency in different circumstances, there is little specific evidence -- especially in humans -- as to the details of this trade-off.  Accordingly, we examine the relative performance of different RL approaches under situations in which the statistics of reward are differentially noisy and volatile.  Using theory and simulation, we show that model-free TD learning is relatively most disadvantaged in cases of high volatility and low noise.  We present data from a decision-making experiment manipulating these parameters, showing that humans shift learning strategies in accord with these predictions.  The statistical circumstances favoring model-based RL are also those that promote a high learning rate, which helps explain why, in psychology, the distinction between these strategies is traditionally conceived in terms of rule-based vs. incremental learning.