pwc-archive/papers-with-abstracts huggingface dataset:
Learning a Distance Metric from a Network
Authors: Blake Shaw, Bert Huang, Tony Jebara
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Graph Embedding, Metric Learning

Many real-world networks are described by both connectivity information and features for every node.  To better model and understand these networks, we present structure preserving metric learning (SPML), an algorithm for learning a Mahalanobis distance metric from a network such that the learned distances are tied to the inherent connectivity structure of the network.  Like the graph embedding algorithm structure preserving embedding, SPML learns a metric which is structure preserving, meaning a connectivity algorithm such as k-nearest neighbors will yield the correct connectivity when applied using the distances from the learned metric.  We show a variety of synthetic and real-world experiments where SPML predicts link patterns from node features more accurately than standard techniques.  We further demonstrate a method for optimizing SPML based on stochastic gradient descent which removes the running-time dependency on the size of the network and allows the method to easily scale to networks of thousands of nodes and millions of edges.
Variance Penalizing AdaBoost
Authors: Pannagadatta K. Shivaswamy, Tony Jebara
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

This paper proposes a novel boosting algorithm called VadaBoost which is motivated by recent empirical Bernstein bounds.  VadaBoost iteratively minimizes a cost function that balances the sample mean and the sample variance of the exponential loss. Each step of the proposed algorithm minimizes the cost efficiently by providing weighted data to a weak learner rather than requiring a brute force evaluation of all possible weak learners. Thus, the proposed algorithm solves a key limitation of previous empirical Bernstein boosting methods which required brute force enumeration of all possible weak learners. Experimental results confirm that the new algorithm achieves the performance improvements of EBBoost yet goes beyond decision stumps to handle any weak learner. Significant performance gains are obtained over AdaBoost for arbitrary weak learners including decision trees (CART).
Efficient Offline Communication Policies for Factored Multiagent POMDPs
Authors: João V. Messias, Matthijs Spaan, Pedro U. Lima
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Form

Factored Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) form a powerful framework for multiagent planning under uncertainty, but optimal solutions require a rigid history-based policy representation. In this paper we allow inter-agent communication which turns the problem in a centralized Multiagent POMDP (MPOMDP). We map belief distributions over state factors to an agent's local actions by exploiting structure in the joint MPOMDP policy.  The key point is that when sparse dependencies between the agents' decisions exist, often the belief over its local state factors is sufficient for an agent to unequivocally identify the optimal action, and communication can be avoided. We formalize these notions by casting the problem into convex optimization form, and present experimental results illustrating the savings in communication that we can obtain.
Sparse recovery by thresholded non-negative least squares
Authors: Martin Slawski, Matthias Hein
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Non-negative data are commonly encountered in numerous fields, making non-negative least squares regression (NNLS) a frequently used tool.   At least relative to its simplicity, it often performs rather well in practice. Serious doubts about its usefulness arise for modern  high-dimensional linear models. Even in this setting - unlike first intuition may suggest - we show that for a broad class of designs, NNLS is resistant to overfitting and works excellently for sparse recovery when combined with thresholding, experimentally even outperforming L1-regularization.   Since NNLS also circumvents the delicate choice of a regularization parameter, our findings suggest that NNLS may be the method of choice.
On Learning Discrete Graphical Models using Greedy Methods
Authors: Ali Jalali, Christopher C. Johnson, Pradeep K. Ravikumar
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

In this paper, we address the problem of learning the structure of a pairwise graphical model from samples in a high-dimensional setting. Our first main result studies the sparsistency, or consistency in sparsity pattern recovery, properties of a forward-backward greedy algorithm as applied to general statistical models. As a special case, we then apply this algorithm to learn the structure of a discrete graphical model via neighborhood estimation. As a corollary of our general result, we derive sufficient conditions on the number of samples n, the maximum node-degree d and the problem size p, as well as other conditions on the model parameters, so that the algorithm recovers all the edges with high probability. Our result guarantees graph selection for samples scaling as n = Omega(d log(p)), in contrast to existing convex-optimization based algorithms that require a sample complexity of Omega(d^2 log(p)). Further, the greedy algorithm only requires a restricted strong convexity condition which is typically milder than irrepresentability assumptions. We corroborate these results using numerical simulations at the end.
Policy Gradient Coagent Networks
Authors: Philip S. Thomas
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We present a novel class of actor-critic algorithms for actors consisting of sets of interacting modules. We present, analyze theoretically, and empirically evaluate an update rule for each module, which requires only local information: the module's input, output, and the TD error broadcast by a critic. Such updates are necessary when computation of compatible features becomes prohibitively difficult and are also desirable to increase the biological plausibility of reinforcement learning methods.
Iterative Learning for Reliable Crowdsourcing Systems
Authors: David R. Karger, Sewoong Oh, Devavrat Shah
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: image-classification, Image Classification, Optical Character Recognition, Optical Character Recognition (OCR)

Crowdsourcing systems, in which tasks are electronically distributed to numerous ``information piece-workers'', have emerged as an effective paradigm for human-powered solving of large scale problems in domains such as image classification, data entry, optical character recognition, recommendation, and proofreading. Because these low-paid workers can be unreliable, nearly all crowdsourcers must devise schemes to increase confidence in their answers, typically by assigning each task multiple times and combining the answers in some way such as majority voting. In this paper, we consider a general model of such  rowdsourcing tasks, and pose the problem of minimizing the total price (i.e., number of task assignments) that must be paid to achieve a target overall reliability. We give new algorithms for deciding which tasks to assign to which workers and for inferring correct answers from the workers’ answers. We show that our algorithm significantly outperforms majority voting and, in fact, are asymptotically optimal through comparison to an oracle that knows the reliability of every worker.
A Model for Temporal Dependencies in Event Streams
Authors: Asela Gunawardana, Christopher Meek, Puyang Xu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: model

We introduce the Piecewise-Constant Conditional Intensity Model, a model for learning temporal dependencies in event streams.  We describe a closed-form Bayesian approach to learning these models, and describe an importance sampling algorithm for forecasting future events using these models, using a proposal distribution based on Poisson superposition.  We then use synthetic data, supercomputer event logs, and web search query logs to illustrate that our learning algorithm can efficiently learn nonlinear temporal dependencies, and that our importance sampling algorithm can effectively forecast future events.
Unsupervised learning models of primary cortical receptive fields and receptive field plasticity
Authors: Maneesh Bhand, Ritvik Mudur, Bipin Suresh, Andrew Saxe, Andrew Y. Ng
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

The efficient coding hypothesis holds that neural receptive fields are adapted to the statistics of the environment, but is agnostic to the timescale of this adaptation, which occurs on both evolutionary and developmental timescales. In this work we focus on that component of adaptation which occurs during an organism's lifetime, and show that a number of unsupervised feature learning algorithms can account for features of normal receptive field properties across multiple primary sensory cortices. Furthermore, we show that the same algorithms account for altered receptive field properties in response to experimentally altered environmental statistics. Based on these modeling results we propose these models as phenomenological models of receptive field plasticity during an organism's lifetime. Finally, due to the success of the same models in multiple sensory areas, we suggest that these algorithms may provide a constructive realization of the theory, first proposed by Mountcastle (1978), that a qualitatively similar learning algorithm acts throughout primary sensory cortices.
The Doubly Correlated Nonparametric Topic Model
Authors: Dae I. Kim, Erik B. Sudderth
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: model, Topic Models

Topic models are learned via a statistical model of variation within document collections, but designed to extract meaningful semantic structure.  Desirable traits include the ability to incorporate annotations or metadata associated with documents; the discovery of correlated patterns of topic usage; and the avoidance of parametric assumptions, such as manual specification of the number of topics.  We propose a doubly correlated nonparametric topic (DCNT) model, the first model to simultaneously capture all three of these properties.  The DCNT models metadata via a flexible, Gaussian regression on arbitrary input features; correlations via a scalable square-root covariance representation; and nonparametric selection from an unbounded series of potential topics via a stick-breaking construction.  We validate the semantic structure and predictive performance of the DCNT using a corpus of NIPS documents annotated by various metadata.
MAP Inference for Bayesian Inverse Reinforcement Learning
Authors: Jaedeug Choi, Kee-Eung Kim
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

The difficulty in inverse reinforcement learning (IRL) arises in choosing the best reward function since there are typically an infinite number of reward functions that yield the given behaviour data as optimal. Using a Bayesian framework, we address this challenge by using the maximum a posteriori (MAP) estimation for the reward function, and show that most of the previous IRL algorithms can be modeled into our framework. We also present a gradient method for the MAP estimation based on the (sub)differentiability of the posterior distribution. We show the effectiveness of our approach by comparing the performance of the proposed method to those of the previous algorithms.
Similarity-based Learning via Data Driven Embeddings
Authors: Purushottam Kar, Prateek Jain
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Diversity

We consider the problem of classification using similarity/distance functions over data. Specifically, we propose a framework for defining the goodness of a (dis)similarity function with respect to a given learning task and propose algorithms that have guaranteed generalization properties when working with such good functions. Our framework unifies and generalizes the frameworks proposed by (Balcan-Blum 2006) and (Wang et al 2007). An attractive feature of our framework is its adaptability to data - we do not promote a fixed notion of goodness but rather let data dictate it. We show, by giving theoretical guarantees that the goodness criterion best suited to a problem can itself be learned which makes our approach applicable to a variety of domains and problems. We propose a landmarking-based approach to obtaining a classifier from such learned goodness criteria. We then provide a novel diversity based heuristic to perform task-driven selection of landmark points instead of random selection. We demonstrate the effectiveness of our goodness criteria learning method as well as the landmark selection heuristic on a variety of similarity-based learning datasets and benchmark UCI datasets on which our method consistently outperforms existing approaches by a significant margin.
Predicting Dynamic Difficulty
Authors: Olana Missura, Thomas Gärtner
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Motivated by applications in electronic games as well as teaching systems, we investigate the problem of dynamic difficulty adjustment. The task here is to repeatedly find a game difficulty setting that is neither `too easy' and bores the player, nor `too difficult' and overburdens the player.  The contributions of this paper are ($i$) formulation of difficulty adjustment as an online learning problem on partially ordered sets, ($ii$) an exponential update algorithm for dynamic difficulty adjustment, ($iii$) a bound on the number of wrong difficulty settings relative to the best static setting chosen in hindsight, and ($iv$) an empirical investigation of the algorithm when playing against adversaries.
Sparse Estimation with Structured Dictionaries
Authors: David P. Wipf
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Compressive Sensing, Model Selection

In the vast majority of recent work on sparse estimation algorithms, performance has been evaluated using ideal or quasi-ideal dictionaries (e.g., random Gaussian or Fourier) characterized by unit $\ell_2$ norm, incoherent columns or features.  But in reality, these types of dictionaries represent only a subset of the dictionaries that are actually used in practice (largely restricted to idealized compressive sensing applications).  In contrast, herein sparse estimation is considered in the context of structured dictionaries possibly exhibiting high coherence between arbitrary groups of columns and/or rows.  Sparse penalized regression models are analyzed with the purpose of finding, to the extent possible, regimes of dictionary invariant performance.  In particular, a Type II Bayesian estimator with a dictionary-dependent sparsity penalty is shown to have a number of desirable invariance properties leading to provable advantages over more conventional penalties such as the $\ell_1$ norm, especially in areas where existing theoretical recovery guarantees no longer hold.  This can translate into improved performance in applications such as model selection with correlated features, source localization, and compressive sensing with constrained measurement directions.
Spectral Methods for Learning Multivariate Latent Tree Structure
Authors: Animashree Anandkumar, Kamalika Chaudhuri, Daniel J. Hsu, Sham M. Kakade, Le Song, Tong Zhang
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

This work considers the problem of learning the structure of multivariate linear tree models, which include a variety of directed tree graphical models with continuous, discrete, and mixed latent variables such as linear-Gaussian models, hidden Markov models, Gaussian mixture models, and Markov evolutionary trees.  The setting is one where we only have samples from certain observed variables in the tree, and our goal is to estimate the tree structure (i.e., the graph of how the underlying hidden variables are connected to each other and to the observed variables).  We propose the Spectral Recursive Grouping algorithm, an efficient and simple bottom-up procedure for recovering the tree structure from independent samples of the observed variables.  Our finite sample size bounds for exact recovery of the tree structure  reveal certain natural dependencies on underlying statistical and structural properties of the underlying joint distribution.  Furthermore, our sample complexity guarantees have no explicit dependence on the dimensionality of the observed variables, making the algorithm applicable to many high-dimensional settings.  At the heart of our algorithm is a spectral quartet test for determining the relative topology of a quartet of variables from second-order statistics.
How biased are maximum entropy models?
Authors: Jakob H. Macke, Iain Murray, Peter E. Latham
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Small Data Image Classification

Maximum entropy models have become popular statistical models in neuroscience and other areas in biology, and can be useful tools for obtaining estimates of mu- tual information in biological systems. However, maximum entropy models fit to small data sets can be subject to sampling bias; i.e. the true entropy of the data can be severely underestimated. Here we study the sampling properties of estimates of the entropy obtained from maximum entropy models. We show that if the data is generated by a distribution that lies in the model class, the bias is equal to the number of parameters divided by twice the number of observations. However, in practice, the true distribution is usually outside the model class, and we show here that this misspecification can lead to much larger bias. We provide a perturba- tive approximation of the maximally expected bias when the true model is out of model class, and we illustrate our results using numerical simulations of an Ising model; i.e. the second-order maximum entropy distribution on binary data.
Active learning of neural response functions with Gaussian processes
Authors: Mijung Park, Greg Horwitz, Jonathan W. Pillow
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Active Learning, Experimental Design, Gaussian Processes

A sizable literature has focused on the problem of estimating a low-dimensional feature space capturing a neuron's stimulus sensitivity.  However, comparatively little work has addressed the problem of estimating the nonlinear function from feature space to a neuron's output spike rate. Here, we use a Gaussian process (GP) prior over the infinite-dimensional space of nonlinear functions to obtain Bayesian estimates of the "nonlinearity" in the linear-nonlinear-Poisson (LNP) encoding model. This offers flexibility, robustness, and computational tractability compared to traditional methods (e.g., parametric forms, histograms, cubic splines).  Most importantly, we develop a framework for optimal experimental design based on uncertainty sampling.  This involves adaptively selecting stimuli to characterize the nonlinearity with as little experimental data as possible, and relies on a method for rapidly updating hyperparameters using the Laplace approximation.  We apply these methods to data from color-tuned neurons in macaque V1.  We estimate nonlinearities in the 3D space of cone contrasts, which reveal that V1 combines cone inputs in a highly nonlinear manner. With simulated experiments, we show that optimal design substantially reduces the amount of data required to estimate this nonlinear combination rule.
Learning to Learn with Compound HD Models
Authors: Antonio Torralba, Joshua B. Tenenbaum, Ruslan R. Salakhutdinov
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Novel Concepts, Object Recognition

We introduce HD (or ``Hierarchical-Deep'') models, a new compositional learning architecture that integrates deep learning models with structured hierarchical Bayesian models. Specifically we show how we can learn a hierarchical Dirichlet process (HDP) prior over the activities of the top-level features in a Deep Boltzmann Machine (DBM).  This compound HDP-DBM model learns to learn novel concepts from very few training examples, by learning low-level generic features, high-level features that capture correlations among low-level features, and a category hierarchy for sharing priors over the high-level features that are typical of different kinds of concepts.  We present efficient learning and inference algorithms for the HDP-DBM model and show that it is able to learn new concepts from very few examples on CIFAR-100 object recognition, handwritten character recognition, and human motion capture datasets.
Active Learning with a Drifting Distribution
Authors: Liu Yang
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Active Learning

We study the problem of active learning in a stream-based setting, allowing the distribution of the examples to change over time.  We prove upper bounds on the number of prediction mistakes and number of label requests for established disagreement-based active learning algorithms, both in the realizable case and under Tsybakov noise.  We further prove minimax lower bounds for this problem.
PiCoDes: Learning a Compact Code for Novel-Category Recognition
Authors: Alessandro Bergamo, Lorenzo Torresani, Andrew W. Fitzgibbon
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Object, Object Recognition

We introduce PiCoDes: a very compact image descriptor which nevertheless allows high performance on object category recognition. In particular, we address novel-category recognition: the task of defining indexing structures and image representations which enable a large collection of images to be searched for an object category that was not known when the index was built. Instead, the training images defining the category are supplied at query time. We explicitly learn descriptors of a given length (from as small as 16 bytes per image) which have good object-recognition performance. In contrast to previous work in the domain of object recognition, we do not choose an arbitrary intermediate representation, but explicitly learn short codes. In contrast to previous approaches to learn compact codes, we optimize explicitly for (an upper bound on) classification performance. Optimization directly for binary features is difficult and nonconvex, but we present an alternation scheme and convex upper bound which demonstrate excellent performance in practice. PiCoDes of 256 bytes match the accuracy of the current best known classifier for the Caltech256 benchmark, but they decrease the database storage size by a factor of 100 and speed-up the training and testing of novel classes by orders of magnitude.