pwc-archive/papers-with-abstracts huggingface dataset:
Approximate Dynamic Programming Finally Performs Well in the Game of Tetris
Authors: Victor Gabillon, Mohammad Ghavamzadeh, Bruno Scherrer
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Tetris is a popular video game that has been widely used as a benchmark for various optimization techniques including approximate dynamic programming (ADP) algorithms. A close look at the literature of this game shows that while ADP algorithms, that have been (almost) entirely based on approximating the value function (value function based), have performed poorly in Tetris, the methods that search directly in the space of policies by learning the policy parameters using an optimization black box, such as the cross entropy (CE) method, have achieved the best reported results. This makes us conjecture that Tetris is a game in which good policies are easier to represent, and thus, learn than their corresponding value functions. So, in order to obtain a good performance with ADP, we should use ADP algorithms that search in a policy space, instead of the more traditional ones that search in a value function space. In this paper, we put our conjecture to test by applying such an ADP algorithm, called classification-based modified policy iteration (CBMPI), to the game of Tetris. Our extensive experimental results show that for the first time an ADP algorithm, namely CBMPI, obtains the best results reported in the literature for Tetris in both small $10\times 10$ and large $10\times 20$ boards. Although the CBMPI's results are similar to those achieved by the CE method in the large board, CBMPI uses considerably fewer (almost 1/10) samples (call to the generative model of the game) than CE.
Third-Order Edge Statistics: Contour Continuation, Curvature, and Cortical Connections
Authors: Matthew Lawlor, Steven W. Zucker
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Association field models have been used to explain human contour grouping performance and to explain the mean frequency of long-range horizontal connections across cortical columns in V1. However, association fields essentially depend on pairwise statistics of edges in natural scenes. We develop a spectral test of the sufficiency of pairwise statistics and show that there is significant higher-order structure.  An analysis using a probabilistic spectral embedding reveals curvature-dependent components to the association field, and reveals a challenge for biological learning algorithms.
Matrix Completion From any Given Set of Observations
Authors: Troy Lee, Adi Shraibman
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Matrix Completion

In the matrix completion problem the aim is to recover an unknown real matrix from a subset of its entries.  This problem comes up in many application areas, and has received a great deal of attention in the context of the netflix prize.  A central approach to this problem is to output a matrix of lowest  possible complexity (e.g. rank or trace norm) that agrees with the partially  specified matrix.  The performance of this approach under the assumption that the revealed entries are sampled randomly   has received considerable attention. In practice, often the set of revealed entries is not chosen at random and these results do not apply. We are therefore left with no guarantees on the performance of the algorithm we are using.  We present a means to obtain performance guarantees with respect to any set of initial observations.  The first  step remains the same: find a matrix of lowest possible complexity that agrees with the partially specified matrix.   We give a new way to interpret the output of this algorithm by next finding a probability distribution over  the non-revealed entries with respect to which a bound on the generalization error can be proven.  The more  complex the set of revealed entries according to a certain measure, the better the bound on the generalization  error.
Regression-tree Tuning in a Streaming Setting
Authors: Samory Kpotufe, Francesco Orabona
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: regression

We consider the problem of maintaining the data-structures of a partition-based regression procedure in a setting where the training data arrives sequentially over time. We prove that it is possible to maintain such a structure in time $O(\log n)$ at any time step $n$ while achieving a nearly-optimal regression rate of $\tilde{O}(n^{-2/(2+d)})$ in terms of the unknown metric dimension $d$. Finally we prove a new regression lower-bound which is independent of a given data size, and hence is more appropriate for the streaming setting.
Dimension-Free Exponentiated Gradient
Authors: Francesco Orabona
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We present a new online learning algorithm that extends the exponentiated gradient to infinite dimensional spaces. Our analysis shows that the algorithm is implicitly able to estimate the $L_2$ norm of the unknown competitor, $U$, achieving a regret bound of the order of $O(U \log (U T+1))\sqrt{T})$, instead of the standard $O((U^2 +1) \sqrt{T})$, achievable without knowing $U$. For this analysis, we introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, we also show that the algorithm is optimal up to $\sqrt{\log T}$ term for linear and Lipschitz losses.
On Flat versus Hierarchical Classification in Large-Scale Taxonomies
Authors: Rohit Babbar, Ioannis Partalas, Eric Gaussier, Massih R. Amini
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Classification, General Classification

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.
Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies
Authors: Yangqing Jia, Joshua T. Abbott, Joseph L. Austerweil, Tom Griffiths, Trevor Darrell
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

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.
Robust Bloom Filters for Large MultiLabel Classification Tasks
Authors: Moustapha M. Cisse, Nicolas Usunier, Thierry Artières, Patrick Gallinari
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Binary Classification, Classification, General Classification

This  paper presents an approach to multilabel classification (MLC) with a large number of labels. Our approach is a reduction to binary classification in which label sets are represented by low dimensional binary vectors. This representation follows the principle of Bloom filters, a space-efficient data structure originally designed for approximate membership testing. We show that a naive application of Bloom filters in MLC is not robust to individual binary classifiers' errors. We then present an approach that exploits a specific feature of real-world datasets when the number of labels is large: many labels (almost) never appear together.  Our approch is provably robust, has sublinear training and inference complexity with respect to the number of labels, and compares favorably to state-of-the-art algorithms on two large scale multilabel datasets.
Solving the multi-way matching problem by permutation synchronization
Authors: Deepti Pachauri, Risi Kondor, Vikas Singh
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

The problem of matching not just two, but m different sets of objects to each other arises in a variety of contexts, including finding the correspondence between feature points across multiple images in computer vision. At present it is usually solved by matching the sets pairwise, in series. In contrast, we propose a new method, permutation synchronization, which finds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efficient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods.
Generalizing Analytic Shrinkage for Arbitrary Covariance Structures
Authors: Daniel Bartz, Klaus-Robert Müller
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Optical Character Recognition, Optical Character Recognition (OCR)

Analytic shrinkage is a statistical technique that offers a fast alternative to cross-validation for the regularization of covariance matrices and has appealing consistency properties. We show that the proof of consistency implies bounds on the growth rates of eigenvalues and their dispersion, which are often violated in data. We prove consistency under assumptions which do not restrict the covariance structure and therefore better match real world data. In addition, we propose an extension of analytic shrinkage --orthogonal complement shrinkage-- which adapts to the covariance structure. Finally we demonstrate the superior performance of our novel approach on data from the domains of finance, spoken letter and optical character recognition, and neuroscience.
Top-Down Regularization of Deep Belief Networks
Authors: Hanlin Goh, Nicolas Thome, Matthieu Cord, Joo-Hwee Lim
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: global-optimization, Object Recognition

Designing a principled and effective algorithm for learning deep architectures is a challenging problem. The current approach involves two training phases: a fully unsupervised learning followed by a strongly discriminative optimization. We suggest a deep learning strategy that bridges the gap between the two phases, resulting in a three-phase learning procedure. We propose to implement the scheme using a method to regularize deep belief networks with top-down information. The network is constructed from building blocks of restricted Boltzmann machines learned by combining bottom-up and top-down sampled signals. A global optimization procedure that merges samples from a forward bottom-up pass and a top-down pass is used. Experiments on the MNIST dataset show improvements over the existing algorithms for deep belief networks. Object recognition results on the Caltech-101 dataset also yield competitive results.
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions
Authors: Tamir Hazan, Subhransu Maji, Joseph Keshet, Tommi Jaakkola
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

In this work we develop efficient methods for learning random MAP predictors for structured label problems. In particular, we construct posterior distributions over perturbations that can be adjusted via stochastic gradient methods. We show that every smooth posterior distribution would suffice to define a smooth PAC-Bayesian risk bound suitable for gradient methods. In addition, we relate the posterior distributions to computational properties of the MAP predictors. We suggest multiplicative posteriors to learn super-modular potential functions that accompany specialized MAP predictors such as graph-cuts. We also describe label-augmented posterior models that can use efficient MAP approximations, such as those arising from linear program relaxations.
Heterogeneous-Neighborhood-based Multi-Task Local Learning Algorithms
Authors: Yu Zhang
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: All, General Classification, regression

All the existing multi-task local learning methods are defined on homogeneous neighborhood which consists of all data points from only one task. In this paper, different from existing methods, we propose local learning methods for multi-task classification and regression problems based on heterogeneous neighborhood which is defined on data points from all tasks. Specifically, we extend the k-nearest-neighbor classifier by formulating the decision function for each data point as a weighted voting among the neighbors from all tasks where the weights are task-specific. By defining a regularizer to enforce the task-specific weight matrix to approach a symmetric one, a regularized objective function is proposed and an efficient coordinate descent method is developed to solve it. For regression problems, we extend the kernel regression to multi-task setting in a similar way to the classification case. Experiments on some toy data and real-world datasets demonstrate the effectiveness of our proposed methods.
Machine Teaching for Bayesian Learners in the Exponential Family
Authors: Jerry Zhu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

What if there is a teacher who knows the learning goal and wants to design good training data for a machine learner?  We propose an optimal teaching framework aimed at learners who employ Bayesian models.  Our framework is expressed as an optimization problem over teaching examples that balance the future loss of the learner and the effort of the teacher.  This optimization problem is in general hard.  In the case where the learner employs conjugate exponential family models, we present an approximate algorithm for finding the optimal teaching set.  Our algorithm optimizes the aggregate sufficient statistics, then unpacks them into actual teaching examples.  We give several examples to illustrate our framework.
Scoring Workers in Crowdsourcing: How Many Control Questions are Enough?
Authors: Qiang Liu, Alexander T. Ihler, Mark Steyvers
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

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.
Action from Still Image Dataset and Inverse Optimal Control to Learn Task Specific Visual Scanpaths
Authors: Stefan Mathe, Cristian Sminchisescu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Human eye movements provide a rich source of information into the human visual processing. The complex interplay between the task and the visual stimulus is believed to determine human eye movements, yet it is not fully understood. This has precluded the development of reliable dynamic eye movement prediction systems. Our work makes three contributions towards addressing this problem. First, we complement one of the largest and most challenging static computer vision datasets, VOC 2012 Actions, with human eye movement annotations collected under the task constraints of action and context recognition. Our dataset is unique among eyetracking datasets for still images in terms of its large scale (over 1 million fixations, 9157 images), task control and action from a single image emphasis. Second, we introduce models to automatically discover areas of interest (AOI) and introduce novel dynamic consistency metrics, based on them. Our method can automatically determine the number and spatial support of the AOIs, in addition to their locations. Based on such encodings, we show that, on unconstrained read-world stimuli, task instructions have significant influence on visual behavior. Finally, we leverage our large scale dataset in conjunction with powerful machine learning techniques and computer vision features, to introduce novel dynamic eye movement prediction methods which learn task-sensitive reward functions from eye movement data and efficiently integrate these rewards to plan future saccades based on inverse optimal control. We show that the propose methodology achieves state of the art scanpath modeling results.
A Determinantal Point Process Latent Variable Model for Inhibition in Neural Spiking Data
Authors: Jasper Snoek, Richard Zemel, Ryan P. Adams
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Hippocampus, Point Processes, Rhythm, Temporal Sequences

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.
Robust Sparse Principal Component Regression under the High Dimensional Elliptical Model
Authors: Fang Han, Han Liu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: regression, Vocal Bursts Intensity Prediction

In this paper we focus on the principal component regression and its application to high dimension non-Gaussian data. The major contributions are in two folds. First, in low dimensions and under a double asymptotic framework where both the dimension $d$ and sample size $n$ can increase, by borrowing the strength from recent development in minimax optimal principal component estimation, we first time sharply characterize the potential advantage of classical principal component regression over least square estimation under the Gaussian model. Secondly, we propose and analyze a new robust sparse principal component regression on high dimensional elliptically distributed data. The elliptical distribution is a semiparametric generalization of the Gaussian, including many well known distributions such as multivariate Gaussian, rank-deficient Gaussian, $t$, Cauchy, and logistic. It allows the random vector to be heavy tailed and have tail dependence. These extra flexibilities make it very suitable for modeling finance and biomedical imaging data. Under the elliptical model, we prove that our method can estimate the regression coefficients in the optimal parametric rate and therefore is a good alternative to the Gaussian based methods. Experiments on synthetic and real world data are conducted to illustrate the empirical usefulness of the proposed method.
Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation
Authors: Bogdan Savchynskyy, Jörg Hendrik Kappes, Paul Swoboda, Christoph Schnörr
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We consider energy minimization for undirected graphical models, also known as MAP-inference problem for Markov random fields. Although combinatorial methods, which return a provably optimal integral solution of the problem, made a big progress in the past decade, they are still typically unable to cope with large-scale datasets. On the other hand, large scale datasets are typically defined on sparse graphs, and convex relaxation methods, such as linear programming relaxations often provide good approximations to integral solutions.   We propose a novel method of combining combinatorial and convex programming techniques to obtain a global solution of the initial combinatorial problem. Based on the information obtained from the solution of the convex relaxation, our method confines application of the combinatorial solver to a small fraction of the initial graphical model, which allows to optimally solve big problems.   We demonstrate the power of our approach on a computer vision energy minimization benchmark.
Demixing odors - fast inference in olfaction
Authors: Agnieszka Grabska-Barwinska, Jeff Beck, Alexandre Pouget, Peter Latham
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

The olfactory system faces a difficult inference problem: it has to determine what odors are present based on the distributed activation of its receptor neurons. Here we derive neural implementations of two approximate inference algorithms that could be used by the brain. One is a variational algorithm (which builds on the work of Beck. et al., 2012), the other is based on sampling. Importantly, we use a more realistic prior distribution over odors than has been used in the past: we use a spike and slab'' prior, for which most odors have zero concentration. After mapping the two algorithms onto neural dynamics, we find that both can infer correct odors in less than 100 ms, although it takes ~500 ms to eliminate false positives. Thus, at the behavioral level, the two algorithms make very similar predictions. However, they make different assumptions about connectivity and neural computations, and make different predictions about neural activity. Thus, they should be distinguishable experimentally.  If so, that would provide insight into the mechanisms employed by the olfactory system, and, because the two algorithms use very different coding strategies, that would also provide insight into how networks represent probabilities."