pwc-archive/papers-with-abstracts huggingface dataset:
Estimation, Optimization, and Parallelism when Data is Sparse
Authors: John Duchi, Michael. I. Jordan, Brendan Mcmahan
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Stochastic Optimization

We study stochastic optimization problems when the \emph{data} is sparse,  which is in a sense dual to the current understanding of high-dimensional statistical learning and optimization. We highlight both the difficulties---in terms of increased sample complexity that sparse data necessitates---and the potential benefits, in terms of allowing parallelism and asynchrony in the design of algorithms. Concretely, we derive matching upper and lower bounds on the minimax rate for optimization and learning with sparse data, and we exhibit algorithms achieving these rates. Our algorithms are adaptive: they achieve the best possible rate for the data observed. We also show how leveraging sparsity leads to (still minimax optimal) parallel and asynchronous algorithms, providing experimental evidence complementing our theoretical results on medium to large-scale learning tasks.
A multi-agent control framework for co-adaptation in brain-computer interfaces
Authors: Josh S. Merel, Roy Fox, Tony Jebara, Liam Paninski
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Brain Computer Interface, Decoder

In a closed-loop brain-computer interface (BCI), adaptive decoders are used to learn parameters suited to decoding the user's neural response. Feedback to the user provides information which permits the neural tuning to also adapt. We present an approach to model this process of co-adaptation between the encoding model of the neural signal and the decoding algorithm as a multi-agent formulation of the linear quadratic Gaussian (LQG) control problem. In simulation we characterize how decoding performance improves as the neural encoding and adaptive decoder optimize, qualitatively resembling experimentally demonstrated closed-loop improvement. We then propose a novel, modified decoder update rule which is aware of the fact that the encoder is also changing and show it can improve simulated co-adaptation dynamics. Our modeling approach offers promise for gaining insights into co-adaptation as well as improving user learning of BCI control in practical settings.
Modeling Overlapping Communities with Node Popularities
Authors: Prem K. Gopalan, Chong Wang, David Blei
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Link Prediction, Variational Inference

We develop a probabilistic approach for accurate network modeling using node popularities within the framework of the mixed-membership stochastic blockmodel (MMSB). Our model integrates some of the basic properties of nodes in social networks: homophily and preferential connection to popular nodes. We develop a scalable algorithm for posterior inference, based on a novel nonconjugate variant of stochastic variational inference. We evaluate the link prediction accuracy of our algorithm on eight real-world networks with up to 60,000 nodes, and 24 benchmark networks. We demonstrate that our algorithm predicts better than the MMSB. Further, using benchmark networks we show that node popularities are essential to achieving high accuracy in the presence of skewed degree distribution and noisy links---both characteristics of real networks.
Learning from Limited Demonstrations
Authors: Beomjoon Kim, Amir-Massoud Farahmand, Joelle Pineau, Doina Precup
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: General Classification

We propose an approach to learning from demonstration (LfD) which leverages expert data, even if the expert examples are very few or inaccurate.  We achieve this by integrating LfD in an approximate policy iteration algorithm.  The key idea of our approach is that expert examples are used to generate linear constraints on the optimization, in a similar fashion to large-margin classification.  We prove an upper bound on the true Bellman error of the approximation computed by the algorithm at each iteration.  We show empirically that the algorithm outperforms both pure policy iteration, as well as DAgger (a state-of-art LfD algorithm) and supervised learning in a variety of scenarios, including when very few and/or imperfect demonstrations are available.  Our experiments include simulations as well as a real robotic navigation task.
On the Representational Efficiency of Restricted Boltzmann Machines
Authors: James Martens, Arkadev Chattopadhya, Toni Pitassi, Richard Zemel
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

This paper examines the question: What kinds of distributions can be efficiently represented by Restricted Boltzmann Machines (RBMs)?   We characterize the RBM's unnormalized log-likelihood function as a type of neural network (called an RBM network), and through a series of simulation results relate these networks to types that are better understood.  We show the surprising result that RBM networks can efficiently compute any function that depends on the number of 1's in the input, such as parity.  We also provide the first known example of a particular type of distribution which provably cannot be efficiently represented by an RBM (or equivalently, cannot be efficiently computed by an RBM network), assuming a realistic exponential upper bound on the size of the weights.  By formally demonstrating that a relatively simple distribution cannot be represented efficiently by an RBM our results provide a new rigorous justification for the use of potentially more expressive generative models, such as deeper ones.
An Approximate, Efficient LP Solver for LP Rounding
Authors: Srikrishna Sridhar, Stephen Wright, Christopher Re, Ji Liu, Victor Bittorf, Ce Zhang
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: BIG-bench Machine Learning

Many problems in machine learning can be solved by rounding the solution of an appropriate linear program. We propose a scheme that is based on a quadratic program relaxation which allows us to use parallel stochastic-coordinate-descent to approximately solve large linear programs efficiently. Our software is an order of magnitude faster than Cplex (a commercial linear programming solver) and yields similar solution quality. Our results include a novel perturbation analysis of a quadratic-penalty formulation of linear programming and a convergence result, which we use to derive running time and quality guarantees.
Linear decision rule as aspiration for simple decision heuristics
Authors: Özgür Şimşek
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

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.
On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation
Authors: Harikrishna Narasimhan, Shivani Agarwal
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Binary Classification, Classification, General Classification

We investigate the relationship between three fundamental problems in machine learning: binary classification, bipartite ranking, and binary class probability estimation (CPE). It is known that a good binary CPE model can be used to obtain a good binary classification model (by thresholding at 0.5), and also to obtain a good bipartite ranking model (by using the CPE model directly as a ranking model); it is also known that a binary classification model does not necessarily yield a CPE model. However, not much is known about other directions. Formally, these relationships involve regret transfer bounds. In this paper, we introduce the notion of weak regret transfer bounds, where the mapping needed to transform a model from one problem to another depends on the underlying probability distribution (and in practice, must be estimated from data). We then show that, in this weaker sense, a good bipartite ranking model can be used to construct a good classification model (by thresholding at a suitable point), and more surprisingly, also to construct a good binary CPE model (by calibrating the scores of the ranking model).
Compressive Feature Learning
Authors: Hristo S. Paskov, Robert West, John C. Mitchell, Trevor Hastie
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Dimensionality Reduction, Text Categorization

This paper addresses the problem of unsupervised feature learning for text data. Our method is grounded in the principle of minimum description length and uses a dictionary-based compression scheme to extract a succinct feature set. Specifically, our method finds a set of word $k$-grams that minimizes the cost of reconstructing the text losslessly. We formulate document compression as a binary optimization task and show how to solve it approximately via a sequence of reweighted linear programs that are efficient to solve and parallelizable. As our method is unsupervised, features may be extracted once and subsequently used in a variety of tasks. We demonstrate the performance of these features over a range of scenarios including unsupervised exploratory analysis and supervised text categorization. Our compressed feature space is two orders of magnitude smaller than the full $k$-gram space and matches the text categorization accuracy achieved in the full feature space. This dimensionality reduction not only results in faster training times, but it can also help elucidate structure in unsupervised learning tasks and reduce the amount of training data necessary for supervised learning.
Moment-based Uniform Deviation Bounds for k-means and Friends
Authors: Matus J. Telgarsky, Sanjoy Dasgupta
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Clustering

Suppose $k$ centers are fit to $m$ points by heuristically minimizing the $k$-means cost; what is the corresponding fit over the source distribution?  This question is resolved here for distributions with $p\geq 4$ bounded moments; in particular, the difference between the sample cost and distribution cost decays with $m$ and $p$ as $m^{\min\{-1/4, -1/2+2/p\}}$.  The essential technical contribution is a mechanism to uniformly control deviations in the face of unbounded parameter sets, cost functions, and source distributions.  To further demonstrate this mechanism, a soft clustering variant of $k$-means cost is also considered, namely the log likelihood of a Gaussian mixture, subject to the constraint that all covariance matrices have bounded spectrum.  Lastly, a rate with refined constants is provided for $k$-means instances possessing some cluster structure.
Fast Template Evaluation with Vector Quantization
Authors: Mohammad Amin Sadeghi, David Forsyth
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: object-detection, Object Detection, Quantization

Applying linear templates is an integral part of many object detection systems and accounts for a significant portion of computation time. We describe a method that achieves a substantial end-to-end speedup over the best current methods, without loss of accuracy. Our method is a combination of approximating scores by vector quantizing feature windows and a number of speedup techniques including cascade. Our procedure allows speed and accuracy to be traded off in two ways: by choosing the number of Vector Quantization levels, and by choosing to rescore windows or not. Our method can be directly plugged into any recognition system that relies on linear templates. We demonstrate our method to speed up the original Exemplar SVM detector [1] by an order of magnitude and Deformable Part models [2] by two orders of magnitude with no loss of accuracy.
Context-sensitive active sensing in humans
Authors: Sheeraz Ahmad, He Huang, Angela J. Yu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Humans and animals readily utilize active sensing, or the use of self-motion, to focus sensory and cognitive resources on the behaviorally most relevant stimuli and events in the environment. Understanding the computational basis of natural active sensing is important both for advancing brain sciences and for developing more powerful artificial systems. Recently, a goal-directed, context-sensitive, Bayesian control strategy for active sensing, termed C-DAC (Context-Dependent Active Controller), was proposed (Ahmad & Yu, 2013). In contrast to previously proposed algorithms for human active vision, which tend to optimize abstract statistical objectives and therefore cannot adapt to changing behavioral context or task goals, C-DAC directly minimizes behavioral costs and thus, automatically adapts itself to different task conditions. However, C-DAC is limited as a model of human active sensing, given its computational/representational requirements, especially for more complex, real-world situations. Here, we propose a myopic approximation to C-DAC, which also takes behavioral costs into account, but achieves a significant reduction in complexity by looking only one step ahead. We also present data from a human active visual search experiment, and compare the performance of the various models against human behavior. We find that C-DAC and its myopic variant both achieve better fit to human data than Infomax (Butko & Movellan, 2010), which maximizes expected cumulative future information gain. In summary, this work provides novel experimental results that differentiate theoretical models for human active sensing, as well as a novel active sensing algorithm that retains the context-sensitivity of the optimal controller while achieving significant computational savings.
Variational Planning for Graph-based MDPs
Authors: Qiang Cheng, Qiang Liu, Feng Chen, Alexander T. Ihler
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Decision Making, Sequential Decision Making

Markov Decision Processes (MDPs) are extremely useful for modeling and solving sequential decision making problems. Graph-based MDPs provide a compact representation for MDPs with large numbers of random variables. However, the complexity of exactly solving a graph-based MDP usually grows exponentially in the number of variables, which limits their application. We present a new variational framework to describe and solve the planning problem of MDPs, and derive both exact and approximate planning algorithms. In particular, by exploiting the graph structure of graph-based MDPs, we propose a factored variational value iteration algorithm in which the value function is first approximated by the multiplication of local-scope value functions, then solved by minimizing a Kullback-Leibler (KL) divergence. The KL divergence is optimized using the belief propagation algorithm, with complexity exponential in only the cluster size of the graph. Experimental comparison on different models shows that our algorithm outperforms existing approximation algorithms at finding good policies.
Convex Two-Layer Modeling
Authors: Özlem Aslan, Hao Cheng, Xinhua Zhang, Dale Schuurmans
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Vocal Bursts Valence Prediction

Latent variable prediction models, such as multi-layer networks, impose auxiliary latent variables between inputs and outputs to allow automatic inference of implicit features useful for prediction.  Unfortunately, such models are difficult to train because inference over latent variables must be performed concurrently with parameter optimization---creating a highly non-convex problem.  Instead of proposing another local training method, we develop a convex relaxation of hidden-layer conditional models that admits global training.  Our approach extends current convex modeling approaches to handle two nested nonlinearities separated by a non-trivial adaptive latent layer.  The resulting methods are able to acquire two-layer models that cannot be represented by any single-layer model over the same features, while improving training quality over local heuristics.
Sketching Structured Matrices for Faster Nonlinear Regression
Authors: Haim Avron, Vikas Sindhwani, David Woodruff
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: regression

Motivated by the desire to extend fast randomized techniques to nonlinear $l_p$ regression, we consider a class of structured regression problems. These problems involve Vandermonde matrices which arise naturally in various statistical modeling settings, including classical polynomial fitting problems and recently developed randomized techniques for scalable kernel methods. We show that this structure can be exploited to further accelerate the solution of the regression problem, achieving running times that are faster than input sparsity''. We present empirical results confirming both the practical value of our modeling framework, as well as speedup benefits of randomized regression."
Efficient Exploration and Value Function Generalization in Deterministic Systems
Authors: Zheng Wen, Benjamin Van Roy
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Efficient Exploration, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system  and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function lies within the given hypothesis class, OCP selects optimal actions over all but at most K episodes, where K is the eluder dimension of the given hypothesis class. We establish further efficiency and asymptotic performance guarantees that apply even if the true value function does not lie in the given hypothesis space, for  the special case where the hypothesis space is the span of pre-specified indicator functions over disjoint sets.
Bellman Error Based Feature Generation using Random Projections on Sparse Spaces
Authors: Mahdi Milani Fard, Yuri Grinberg, Amir-Massoud Farahmand, Joelle Pineau, Doina Precup
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This paper addresses the problem of automatic generation of features for value function approximation in reinforcement learning.  Bellman Error Basis Functions (BEBFs) have been shown to improve the error of policy evaluation with function approximation, with a convergence rate similar to that of value iteration. We propose a simple, fast and robust algorithm based on random projections, which generates BEBFs for sparse feature spaces. We provide a finite sample analysis of the proposed method, and prove that projections logarithmic in the dimension of the original space guarantee a contraction in the error.  Empirical results demonstrate the strength of this method in domains in which choosing a good state representation is challenging.
Learning and using language via recursive pragmatic reasoning about other agents
Authors: Nathaniel J. Smith, Noah Goodman, Michael Frank
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Language users are remarkably good at making inferences about speakers' intentions in context, and children learning their native language also display substantial skill in acquiring the meanings of unknown words. These two cases are deeply related: Language users invent new terms in conversation, and language learners learn the literal meanings of words based on their pragmatic inferences about how those words are used.  While pragmatic inference and word learning have both been independently characterized in probabilistic terms, no current work unifies these two. We describe a model in which language learners assume that they jointly approximate a shared, external lexicon and reason recursively about the goals of others in using this lexicon. This model captures phenomena in word learning and pragmatic inference; it additionally leads to insights about the emergence of communicative systems in conversation and the mechanisms by which pragmatic inferences become incorporated into word meanings.
Learning Stochastic Inverses
Authors: Andreas Stuhlmüller, Jacob Taylor, Noah Goodman
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We describe a class of algorithms for amortized inference in Bayesian networks. In this setting, we invest computation upfront to support rapid online inference for a wide range of queries. Our approach is based on learning an inverse factorization of a model's joint distribution: a factorization that turns observations into root nodes.  Our algorithms accumulate information to estimate the local conditional distributions that constitute such a factorization. These stochastic inverses can be used to invert each of the computation steps leading to an observation, sampling backwards in order to quickly find a likely explanation. We show that estimated inverses converge asymptotically in number of (prior or posterior) training samples.  To make use of inverses before convergence, we describe the Inverse MCMC algorithm, which uses stochastic inverses to make block proposals for a Metropolis-Hastings sampler.  We explore the efficiency of this sampler for a variety of parameter regimes and Bayes nets.
Learning invariant representations and applications to face verification
Authors: Qianli Liao, Joel Z. Leibo, Tomaso Poggio
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Face Verification, Object Recognition

One approach to computer object recognition and modeling the brain's ventral stream involves unsupervised learning of representations that are invariant to common transformations. However, applications of these ideas have usually been limited to 2D affine transformations, e.g., translation and scaling, since they are easiest to solve via convolution. In accord with a recent theory of transformation-invariance, we propose a model that, while capturing other common convolutional networks as special cases, can also be used with arbitrary identity-preserving transformations. The model's wiring can be learned from videos of transforming objects---or any other grouping of images into sets by their depicted object. Through a series of successively more complex empirical tests, we study the invariance/discriminability properties of this model with respect to different transformations. First, we empirically confirm theoretical predictions for the case of 2D affine transformations. Next, we apply the model to non-affine transformations: as expected, it performs well on face verification tasks requiring invariance to the relatively smooth transformations of 3D rotation-in-depth and changes in illumination direction. Surprisingly, it can also tolerate clutter transformations'' which map an image of a face on one background to an image of the same face on a different background. Motivated by these empirical findings, we tested the same model on face verification benchmark tasks from the computer vision literature: Labeled Faces in the Wild, PubFig and a new dataset we gathered---achieving strong performance in these highly unconstrained cases as well."
Adaptivity to Local Smoothness and Dimension in Kernel Regression
Authors: Samory Kpotufe, Vikas Garg
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: regression

We present the first result for kernel regression where the procedure adapts locally at a point $x$ to both the unknown local dimension of the metric and the unknown H\{o}lder-continuity of the regression function at $x$. The result holds with high probability simultaneously at all points $x$ in a metric space of unknown structure."