pwc-archive/papers-with-abstracts huggingface dataset:
Information-theoretic lower bounds on the oracle complexity of convex optimization
Authors: Alekh Agarwal, Martin J. Wainwright, Peter L. Bartlett, Pradeep K. Ravikumar
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: BIG-bench Machine Learning

Despite the large amount of literature on upper bounds on complexity of convex analysis, surprisingly little is known about the fundamental hardness of these problems. The extensive use of convex optimization in machine learning and statistics makes such an understanding critical to understand fundamental computational limits of learning and estimation. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We improve upon known results and obtain tight minimax complexity estimates for some function classes. We also discuss implications of these results to the understanding the inherent complexity of large-scale learning and estimation problems.
Streaming k-means approximation
Authors: Nir Ailon, Ragesh Jaiswal, Claire Monteleoni
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering

We provide a clustering algorithm that approximately optimizes the k-means objective, in the one-pass streaming setting. We make no assumptions about the data, and  our algorithm is very light-weight in terms of memory, and computation. This setting is applicable to unsupervised learning on massive data sets, or resource-constrained devices. The two main ingredients of our theoretical work are:  a derivation of an extremely simple pseudo-approximation batch algorithm for k-means, in which the algorithm is allowed to output more than k centers (based on the recent k-means++"), and a streaming clustering algorithm in which batch clustering algorithms are performed on small inputs (fitting in memory) and combined in a hierarchical manner.  Empirical evaluations on real and simulated data reveal the practical utility of our method."
Complexity of Decentralized Control: Special Cases
Authors: Martin Allen, Shlomo Zilberstein
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

The worst-case complexity of general decentralized POMDPs, which are equivalent to partially observable stochastic games (POSGs) is very high, both for the cooperative and competitive cases.  Some reductions in complexity have been achieved by exploiting independence relations in some models.  We show that these results are somewhat limited:  when these independence assumptions are relaxed in very small ways, complexity returns to that of the general case.
Learning from Multiple Partially Observed Views - an Application to Multilingual Text Categorization
Authors: Massih Amini, Nicolas Usunier, Cyril Goutte
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Machine Translation, Text Categorization, Translation

We address the problem of learning classifiers when observations have multiple views, some of which may not be observed for all examples.  We assume the existence of view generating functions which may complete the missing views in an approximate way.  This situation corresponds for example to learning text classifiers from multilingual collections where documents are not available in all languages.  In that case, Machine Translation (MT) systems may be used to translate each document in the missing languages.  We derive a generalization error bound for classifiers learned on examples with multiple artificially created views. Our result uncovers a trade-off between the size of the training set, the number of views, and the quality of the view generating functions. As a consequence, we identify situations where it is more interesting to use multiple views for learning instead of classical single view learning.  An extension of this framework is a natural way to leverage unlabeled multi-view data in semi-supervised learning.  Experimental results on a subset of the Reuters RCV1/RCV2 collections support our findings by showing that additional views obtained from MT may significantly improve the classification performance in the cases identified by our trade-off.
Constructing Topological Maps using Markov Random Fields and Loop-Closure Detection
Authors: Roy Anati, Kostas Daniilidis
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Loop Closure Detection

We present a system which constructs a topological map of an environment given a sequence of images. This system includes a novel image similarity score which uses dynamic programming to match images using both the appearance and relative positions of local features simultaneously. Additionally an MRF is constructed to model the probability of loop-closures. A locally optimal labeling is found using Loopy-BP. Finally we outline a method to generate a topological map from loop closure data. Results are presented on four urban sequences and one indoor sequence.
Data-driven calibration of linear estimators with minimal penalties
Authors: Sylvain Arlot, Francis R. Bach
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Model Selection, regression

This paper tackles the problem of selecting among several linear estimators in non-parametric regression; this includes model selection for linear regression, the choice of a regularization parameter in kernel ridge regression or spline smoothing, and the choice of a kernel in multiple kernel learning. We propose a new algorithm which first estimates consistently the variance of the noise, based upon the concept of minimal penalty which was previously introduced in the context of model selection. Then, plugging our variance estimate in Mallows $C_L$ penalty is proved to lead to an algorithm satisfying an oracle inequality. Simulation experiments with kernel ridge regression and multiple kernel learning show that the proposed algorithm often improves significantly existing calibration procedures such as 10-fold cross-validation or generalized cross-validation.
On Learning Rotations
Authors: Raman Arora
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

An algorithm is presented for online learning of rotations. The proposed algorithm involves matrix exponentiated gradient updates and is motivated by the Von Neumann divergence. The additive updates are skew-symmetric matrices with trace zero which comprise the Lie algebra of the rotation group. The orthogonality and unit determinant of the matrix  parameter are preserved using matrix logarithms and exponentials and the algorithm lends itself to interesting interpretations in terms of the computational topology of the compact Lie groups. The stability and the computational complexity of the algorithm are discussed.
Polynomial Semantic Indexing
Authors: Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Kunihiko Sadamasa, Yanjun Qi, Corinna Cortes, Mehryar Mohri
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Retrieval

We present a class of nonlinear (polynomial) models that are discriminatively trained to directly map from the word content in a query-document or document-document pair to a ranking score. Dealing with polynomial models on word features is computationally challenging. We propose a low rank (but diagonal preserving) representation of our polynomial models to induce feasible memory and computation requirements. We provide an empirical study on retrieval tasks based on Wikipedia documents, where we obtain state-of-the-art performance while providing realistically scalable methods.
Nonparametric Bayesian Models for Unsupervised Event Coreference Resolution
Authors: Cosmin Bejan, Matthew Titsworth, Andrew Hickl, Sanda Harabagiu
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering, coreference-resolution, Coreference Resolution, Event Coreference Resolution

We present a sequence of unsupervised, nonparametric Bayesian models for clustering  complex linguistic objects. In this approach, we consider a potentially infinite number of features and categorical outcomes. We evaluate these models for the task  of within- and cross-document event coreference on two corpora.  All the models we investigated show significant improvements when compared against an existing baseline for this task.
Group Sparse Coding
Authors: Samy Bengio, Fernando Pereira, Yoram Singer, Dennis Strelow
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Computational Efficiency, General Classification, image-classification, Image Classification, Quantization

Bag-of-words document representations are often used in text, image and video processing. While it is relatively easy to determine a suitable word dictionary for text documents, there is no simple mapping from raw images or videos to dictionary terms. The classical approach builds a dictionary using vector quantization over a large set of useful visual descriptors extracted from a training set, and uses a nearest-neighbor algorithm to count the number of occurrences of each dictionary word in documents to be encoded. More robust approaches have been proposed recently that represent each visual descriptor as a sparse weighted combination of dictionary words. While favoring a sparse representation at the level of visual descriptors, those methods however do not ensure that images have sparse representation. In this work, we use mixed-norm regularization to achieve sparsity at the image level as well as a small overall dictionary. This approach can also be used to encourage using the same dictionary words for all the images in a class, providing a discriminative signal in the construction of image representations. Experimental results on a benchmark image classification dataset show that when compact image or dictionary representations are needed for computational efficiency, the proposed approach yields better mean average precision in classification.
Neurometric function analysis of population codes
Authors: Philipp Berens, Sebastian Gerwinn, Alexander Ecker, Matthias Bethge
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

The relative merits of different population coding schemes have mostly been analyzed in the framework of stimulus reconstruction using Fisher Information. Here, we consider the case of stimulus discrimination in a two alternative forced choice paradigm and compute neurometric functions in terms of the minimal discrimination error and the Jensen-Shannon information to study neural population codes. We first explore the relationship between minimum discrimination error, Jensen-Shannon Information and Fisher Information and show that the discrimination framework is more informative about the coding accuracy than Fisher Information as it defines an error for any pair of possible stimuli. In particular, it includes Fisher Information as a special case. Second, we use the framework to study population codes of angular variables. Specifically, we assess the impact of different noise correlations structures on coding accuracy in long versus short decoding time windows. That is, for long time window we use the common Gaussian noise approximation. To address the case of short time windows we analyze the Ising model with identical noise correlation structure. In this way, we provide a new rigorous framework for assessing the functional consequences of noise correlation structures for the representational accuracy of neural population codes that is in particular applicable to short-time population coding.
Slow, Decorrelated Features for Pretraining Complex Cell-like Networks
Authors: Yoshua Bengio, James S. Bergstra
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We introduce a new type of neural network activation function based on recent physiological rate models for complex cells in visual area V1.  A single-hidden-layer neural network of this kind of model achieves 1.5% error on MNIST.  We also introduce an existing criterion for learning slow, decorrelated features as a pretraining strategy for image models.  This pretraining strategy results in orientation-selective features, similar to the receptive fields of complex cells.  With this pretraining, the same single-hidden-layer model achieves better generalization error, even though the pretraining sample distribution is very different from the fine-tuning distribution.  To implement this pretraining strategy, we derive a fast algorithm for online learning of decorrelated features such that each iteration of the algorithm runs in linear time with respect to the number of features.
No evidence for active sparsification in the visual cortex
Authors: Pietro Berkes, Ben White, Jozsef Fiser
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

The proposal that cortical activity in the visual cortex is optimized for sparse neural activity is one of the most established ideas in computational neuroscience. However, direct experimental evidence for optimal sparse coding remains inconclusive, mostly due to the lack of reference values on which to judge the measured sparseness. Here we analyze neural responses to natural movies in the primary visual cortex of ferrets at different stages of development, and of rats while awake and under different levels of anesthesia. In contrast with prediction from a sparse coding model, our data shows that population and lifetime sparseness decrease with visual experience, and increase from the awake to anesthetized state. These results suggest that the representation in the primary visual cortex is not actively optimized to maximize sparseness.
Manifold Regularization for SIR with Rate Root-n Convergence
Authors: Wei Bian, DaCheng Tao
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

In this paper, we study the manifold regularization for the Sliced Inverse Regression (SIR). The manifold regularization improves the standard SIR in two aspects: 1) it encodes the local geometry for SIR and 2) it enables SIR to deal with transductive and semi-supervised learning problems. We prove that the proposed graph Laplacian based regularization is convergent at rate root-n. The projection directions of the regularized SIR are optimized by using a conjugate gradient method on the Grassmann manifold. Experimental results support our theory.
Augmenting Feature-driven fMRI Analyses: Semi-supervised learning and resting state activity
Authors: Andreas Bartels, Matthew Blaschko, Jacquelyn A. Shelton
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

Resting state activity is brain activation that arises in the absence of any task, and is usually measured in awake subjects during prolonged fMRI scanning sessions where the only instruction given is to close the eyes and do nothing.  It has been recognized in recent years that resting state activity is implicated in a wide variety of brain function.  While certain networks of brain areas have different levels of activation at rest and during a task, there is nevertheless significant similarity between activations in the two cases.  This suggests that recordings of resting state activity can be used as a source of unlabeled data to augment discriminative regression techniques in a semi-supervised setting.  We evaluate this setting empirically yielding three main results: (i) regression tends to be improved by the use of Laplacian regularization even when no additional unlabeled data are available, (ii) resting state data may have a similar marginal distribution to that recorded during the execution of a visual processing task reinforcing the hypothesis that these conditions have similar types of activation, and (iii) this source of information can be broadly exploited to improve the robustness of empirical inference in fMRI studies, an inherently data poor domain.
Efficient Match Kernel between Sets of Features for Visual Recognition
Authors: Liefeng Bo, Cristian Sminchisescu
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Quantization

In visual recognition, the images are frequently modeled as sets of local features (bags). We show that bag of words, a common method to handle such cases, can be viewed as a special match kernel, which counts 1 if two local features fall into the same regions partitioned by visual words and 0 otherwise. Despite its simplicity, this quantization is too coarse. It is, therefore, appealing to design match kernels that more accurately measure the similarity between local features. However, it is impractical to use such kernels on large datasets due to their significant computational cost. To address this problem, we propose an efficient match kernel (EMK), which maps local features to a low dimensional feature space, average the resulting feature vectors to form a set-level feature, then apply a linear classifier. The local feature maps are learned so that their inner products preserve, to the best possible, the values of the specified kernel function. EMK is linear both in the number of images and in the number of local features. We demonstrate that EMK is extremely efficient and achieves the current state of the art performance on three difficult real world datasets: Scene-15, Caltech-101 and Caltech-256.
Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs
Authors: Alexandre Bouchard-Côté, Slav Petrov, Dan Klein
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Pruning can massively accelerate the computation of feature expectations in large models.  However, any single pruning mask will introduce bias.  We present a novel approach which employs a randomized sequence of pruning masks. Formally, we apply auxiliary variable MCMC sampling to generate this sequence of masks, thereby gaining theoretical guarantees about convergence. Because each mask is generally able to skip large portions of an underlying dynamic program, our approach is particularly compelling for high-degree algorithms.  Empirically, we demonstrate our method on bilingual parsing, showing decreasing bias as more masks are incorporated, and outperforming fixed tic-tac-toe pruning.
Unsupervised Feature Selection for the k-means Clustering Problem
Authors: Christos Boutsidis, Petros Drineas, Michael W. Mahoney
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering, feature selection

We present a novel feature selection algorithm for the $k$-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter $\epsilon \in (0,1)$, selects and appropriately rescales in an unsupervised manner $\Theta(k \log(k / \epsilon) / \epsilon^2)$ features from a dataset of arbitrary dimensions. We prove that, if we run any $\gamma$-approximate $k$-means algorithm ($\gamma \geq 1$) on the features selected using our method, we can find a $(1+(1+\epsilon)\gamma)$-approximate partition with high probability.
On Invariance in Hierarchical Models
Authors: Jake Bouvrie, Lorenzo Rosasco, Tomaso Poggio
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Object Recognition

A goal of central importance in the study of hierarchical models for object recognition -- and indeed the visual cortex -- is that of understanding quantitatively the trade-off between invariance and selectivity, and how invariance and discrimination properties contribute towards providing an improved representation useful for learning from data. In this work we provide a general group-theoretic framework for characterizing and understanding invariance in a family of hierarchical models.  We show that by taking an algebraic perspective, one can provide a concise set of conditions which must be met to establish invariance, as well as a constructive prescription for meeting those conditions. Analyses in specific cases of particular relevance to computer vision and text processing are given, yielding insight into how and when invariance can be achieved. We find that the minimal sets of transformations intrinsic to the hierarchical model needed to support a particular invariance can be clearly described, thereby encouraging efficient computational implementations.
Nash Equilibria of Static Prediction Games
Authors: Michael Brückner, Tobias Scheffer
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Prediction

The standard assumption of identically distributed training and test data can be violated when an adversary can exercise some control over the generation of the test data. In a prediction game, a learner produces a predictive model while an adversary may alter the distribution of input data. We study single-shot prediction games in which the cost functions of learner and adversary are not necessarily antagonistic. We identify conditions under which the prediction game has a unique Nash equilibrium, and derive algorithms that will find the equilibrial prediction models. In a case study, we explore properties of Nash-equilibrial prediction models for email spam filtering empirically.
Optimal context separation of spiking haptic signals by second-order somatosensory neurons
Authors: Romain Brasselet, Roland Johansson, Angelo Arleo
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We study an encoding/decoding mechanism accounting for the relative spike timing of the signals propagating from peripheral nerve fibers to second-order somatosensory neurons in the cuneate nucleus (CN). The CN is modeled as a population of spiking neurons receiving as inputs the spatiotemporal responses of real mechanoreceptors obtained via microneurography recordings in humans. The efficiency of the haptic discrimination process is quantified by a novel definition of entropy that takes into full account the metrical properties of the spike train space. This measure proves to be a suitable decoding scheme for generalizing the classical Shannon entropy to spike-based neural codes. It permits an assessment of neurotransmission in the presence of a large output space (i.e. hundreds of spike trains) with 1 ms temporal precision. It is shown that the CN population code performs a complete discrimination of 81 distinct stimuli already within 35 ms of the first afferent spike, whereas a partial discrimination (80% of the maximum information transmission) is possible as rapidly as 15 ms. This study suggests that the CN may not constitute a mere synaptic relay along the somatosensory pathway but, rather, it may convey optimal contextual accounts (in terms of fast and reliable information transfer) of peripheral tactile inputs to downstream structures of the central nervous system.
Manifold Embeddings for Model-Based Reinforcement Learning under Partial Observability
Authors: Keith Bush, Joelle Pineau
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Model-based Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Interesting real-world datasets often exhibit nonlinear, noisy, continuous-valued states that are unexplorable, are poorly described by first principles, and are only partially observable. If partial observability can be overcome, these constraints suggest the use of model-based reinforcement learning.  We experiment with manifold embeddings as the reconstructed observable state-space of an off-line, model-based reinforcement learning approach to control. We demonstrate the embedding of a system changes as a result of learning and that the best performing embeddings well-represent the dynamics of both the uncontrolled and adaptively controlled system.  We apply this approach in simulation to learn a neurostimulation policy that is more efficient in treating epilepsy than conventional policies.  We then demonstrate the learned policy completely suppressing seizures in real-world neurostimulation experiments on actual animal brain slices.