pwc-archive/papers-with-abstracts huggingface dataset:
3D Object Recognition with Deep Belief Nets
Authors: Vinod Nair, Geoffrey E. Hinton
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: 3D Object Recognition, Object, Object Recognition, Translation

We introduce a new type of Deep Belief Net and evaluate it on a 3D object recognition task. The top-level model is a third-order Boltzmann machine, trained using a hybrid algorithm that combines both generative and discriminative gradients. Performance is evaluated on the NORB database(normalized-uniform version), which contains stereo-pair images of objects under different lighting conditions and viewpoints. Our model achieves 6.5% error on the test set, which is close to the best published result for NORB (5.9%) using a convolutional neural net that has built-in knowledge of translation invariance. It substantially outperforms shallow models such as SVMs (11.6%). DBNs are especially suited for semi-supervised learning, and to demonstrate this we consider a modified version of the NORB recognition task in which additional unlabeled images are created by applying small translations to the images in the database. With the extra unlabeled data (and the same amount of labeled data as before), our model achieves 5.2% error, making it the current best result for NORB.
A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
Authors: Sahand Negahban, Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

The estimation of high-dimensional parametric models requires imposing some structure on the models, for instance that they be sparse, or that matrix structured parameters have low rank. A general approach for such structured parametric model estimation is to use regularized M-estimation procedures, which regularize a loss function that measures goodness of fit of the parameters to the data with some regularization function that encourages the assumed structure. In this paper, we aim to provide a unified analysis of such regularized M-estimation procedures. In particular, we report the convergence rates of such estimators in any metric norm. Using just our main theorem, we are able to rederive some of the many existing results, but also obtain a wide range of novel convergence rates results. Our analysis also identifies key properties of loss and regularization functions such as restricted strong convexity, and decomposability, that ensure the corresponding regularized M-estimators have good convergence rates.
STDP enables spiking neurons to detect hidden causes of their inputs
Authors: Bernhard Nessler, Michael Pfeiffer, Wolfgang Maass
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Dimensionality Reduction

The principles by which spiking neurons contribute to the astounding computational power of generic cortical microcircuits, and how spike-timing-dependent plasticity (STDP) of synaptic weights could generate and maintain  this computational function, are unknown. We show here that STDP, in conjunction with a stochastic soft winner-take-all (WTA) circuit, induces spiking neurons to generate through their synaptic weights implicit internal models for subclasses (or causes") of the high-dimensional spike patterns of hundreds of pre-synaptic neurons. Hence these  neurons will fire after learning whenever the current input best matches their internal model. The resulting computational function of soft WTA circuits, a common network motif of cortical microcircuits, could therefore be a drastic dimensionality reduction of information streams, together with the autonomous creation of internal models for the probability distributions of their input patterns. We show that the autonomous generation and maintenance of this computational function can be explained on the basis of rigorous mathematical principles. In particular, we show that STDP is able to approximate a stochastic online Expectation-Maximization (EM) algorithm for modeling the input data. A corresponding result is shown for Hebbian learning in artificial neural networks."
Noisy Generalized Binary Search
Authors: Robert Nowak
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Active Learning, Scheduling

This paper addresses the problem of noisy Generalized Binary Search (GBS).  GBS is a well-known greedy algorithm for determining a binary-valued hypothesis through a sequence of strategically selected queries.  At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search.  GBS is used in many applications, including fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and active learning. In most of these cases, the responses to queries can be noisy.  Past work has provided a partial characterization of GBS, but existing noise-tolerant versions of GBS are suboptimal in terms of sample complexity.  This paper presents the first optimal algorithm for noisy GBS and demonstrates its application to learning multidimensional threshold functions.
Submanifold density estimation
Authors: Arkadas Ozakin, Alexander G. Gray
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Density Estimation

Kernel density estimation is the most widely-used practical method for accurate nonparametric density estimation. However, long-standing worst-case theoretical results showing that its performance worsens exponentially with the dimension of the data have quashed its application to modern high-dimensional datasets for decades. In practice, it has been recognized that often such data have a much lower-dimensional intrinsic structure. We propose a small modification to kernel density estimation for estimating probability density functions on Riemannian submanifolds of Euclidean space. Using ideas from Riemannian geometry, we prove the consistency of this modified estimator and show that the convergence rate is determined by the intrinsic dimension of the submanifold. We conclude with empirical results demonstrating the behavior predicted by our theory.
Correlation Coefficients are Insufficient for Analyzing Spike Count Dependencies
Authors: Arno Onken, Steffen Grünewälder, Klaus Obermayer
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

The linear correlation coefficient is typically used to characterize and analyze dependencies of neural spike counts. Here, we show that the correlation coefficient is in general insufficient to characterize these dependencies. We construct two neuron spike count models with Poisson-like marginals and vary their dependence structure using copulas. To this end, we construct a copula that allows to keep the spike counts uncorrelated while varying their dependence strength. Moreover, we employ a network of leaky integrate-and-fire neurons to investigate whether weakly correlated spike counts with strong dependencies are likely to occur in real networks. We find that the entropy of uncorrelated but dependent spike count distributions can deviate from the corresponding distribution with independent components by more than 25% and that weakly correlated but strongly dependent spike counts are very likely to occur in biological networks. Finally, we introduce a test for deciding whether the dependence structure of distributions with Poisson-like marginals is well characterized by the linear correlation coefficient and verify it for different copula-based models.
Construction of Nonparametric Bayesian Models from Parametric Bayes Equations
Authors: Peter Orbanz
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We consider the general problem of constructing nonparametric   Bayesian models on infinite-dimensional random objects, such   as functions, infinite graphs or infinite permutations.   The problem has generated much interest in machine learning,   where it is treated heuristically, but has not been    studied in full generality in nonparametric Bayesian statistics, which tends to   focus on models over probability distributions.    Our approach applies a standard tool of stochastic process   theory, the construction of stochastic processes from their   finite-dimensional marginal distributions.    The main contribution of the paper is a generalization   of the classic Kolmogorov extension theorem to conditional   probabilities.   This extension allows a rigorous construction of nonparametric Bayesian models   from systems of finite-dimensional, parametric Bayes equations.   Using this approach, we show (i)   how existence of a conjugate posterior for    the nonparametric model can be guaranteed by choosing   conjugate finite-dimensional models in the construction, (ii) how the   mapping to the posterior parameters of the nonparametric   model can be explicitly determined, and (iii) that   the construction of conjugate models in essence requires the   finite-dimensional models to be in the exponential family.   As an application of our constructive framework,    we derive a model on infinite   permutations, the nonparametric Bayesian analogue of a model   recently proposed for the analysis of rank data.
Learning from Neighboring Strokes: Combining Appearance and Context for Multi-Domain Sketch Recognition
Authors: Tom Ouyang, Randall Davis
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Sketch Recognition

We propose a new sketch recognition framework that combines a rich representation of low level visual appearance with a graphical model for capturing high level relationships between symbols. This joint model of appearance and context allows our framework to be less sensitive to noise and drawing variations, improving accuracy and robustness. The result is a recognizer that is better able to handle the wide range of drawing styles found in messy freehand sketches. We evaluate our work on two real-world domains, molecular diagrams and electrical circuit diagrams, and show that our combined approach significantly improves recognition performance.
Zero-shot Learning with Semantic Output Codes
Authors: Mark Palatucci, Dean Pomerleau, Geoffrey E. Hinton, Tom M. Mitchell
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Zero-Shot Learning

We consider the problem of zero-shot learning, where the goal is to learn a classifier $f: X \rightarrow Y$ that must predict novel values of $Y$ that were omitted from the training set. To achieve this, we define the notion of a semantic output code classifier (SOC) which utilizes a knowledge base of semantic properties of $Y$ to extrapolate to novel classes. We provide a formalism for this type of classifier and study its theoretical properties in a PAC framework, showing conditions under which the classifier can accurately predict novel classes.  As a case study, we build a SOC classifier for a neural decoding task and show that it can often predict words that people are thinking about from functional magnetic resonance images (fMRI) of their neural activity, even without training examples for those words.
Conditional Neural Fields
Authors: Jian Peng, Liefeng Bo, Jinbo Xu
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Handwriting Recognition, Hyperparameter Optimization, Protein Structure Prediction

Conditional random fields (CRF) are quite successful on sequence labeling tasks such as natural language processing and biological sequence analysis. CRF models use linear potential functions to represent the relationship between input features and outputs. However, in many real-world applications such as protein structure prediction and handwriting recognition, the relationship between input features and outputs is highly complex and nonlinear, which cannot be accurately modeled by a linear function. To model the nonlinear relationship between input features and outputs we propose Conditional Neural Fields (CNF), a new conditional probabilistic graphical model for sequence labeling. Our CNF model extends CRF by adding one (or possibly several) middle layer between input features and outputs. The middle layer consists of a number of hidden parameterized gates, each acting as a local neural network node or feature extractor to capture the nonlinear relationship between input features and outputs. Therefore, conceptually this CNF model is much more expressive than the linear CRF model. To better control the complexity of the CNF model, we also present a hyperparameter optimization procedure within the evidence framework. Experiments on two widely-used benchmarks indicate that this CNF model performs significantly better than a number of popular methods. In particular, our CNF model is the best among about ten machine learning methods for protein secondary tructure prediction and also among a few of the best methods for handwriting recognition.
Free energy score space
Authors: Alessandro Perina, Marco Cristani, Umberto Castellani, Vittorio Murino, Nebojsa Jojic
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification

Score functions induced by generative models extract fixed-dimension feature vectors from different-length data observations by subsuming the process of data generation, projecting them in highly informative spaces called score spaces. In this way, standard discriminative classifiers are proved to achieve higher performances than a solely generative or discriminative approach. In this paper, we present a novel score space that exploits the free energy associated to a generative model through a score function. This function aims at capturing both the uncertainty of the model learning and ``local compliance  of data observations with respect to the generative process. Theoretical justifications and convincing comparative classification results on various generative models prove the goodness of the proposed strategy.
Maximum likelihood trajectories for continuous-time Markov chains
Authors: Theodore J. Perkins
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: parameter estimation

Continuous-time Markov chains are used to model systems in which transitions between states as well as the time the system spends in each state are random.  Many computational problems related to such chains have been solved, including determining state distributions as a function of time, parameter estimation, and control.  However, the problem of inferring most likely trajectories, where a trajectory is a sequence of states as well as the amount of time spent in each state, appears unsolved.  We study three versions of this problem: (i) an initial value problem, in which an initial state is given and we seek the most likely trajectory until a given final time, (ii) a boundary value problem, in which initial and final states and times are given, and we seek the most likely trajectory connecting them, and (iii) trajectory inference under partial observability, analogous to finding maximum likelihood trajectories for hidden Markov models.  We show that maximum likelihood trajectories are not always well-defined, and describe a polynomial time test for well-definedness.  When well-definedness holds, we show that each of the three problems can be solved in polynomial time, and we develop efficient dynamic programming algorithms for doing so.
Robust Value Function Approximation Using Bilinear Programming
Authors: Marek Petrik, Shlomo Zilberstein
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose approximate bilinear programming, a new formulation of value function approximation that provides strong a priori guarantees. In particular, it provably finds an approximate value function that minimizes the Bellman residual. Solving a bilinear program optimally is NP hard, but this is unavoidable because the Bellman-residual minimization itself is NP hard. We, therefore, employ and analyze a common approximate algorithm for bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on a simple benchmark problem.
Exponential Family Graph Matching and Ranking
Authors: James Petterson, Jin Yu, Julian J. McAuley, Tibério S. Caetano
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Document Ranking, Graph Matching

We present a method for learning max-weight matching predictors in bipartite graphs. The method consists of performing maximum a posteriori estimation in exponential families with sufficient statistics that encode permutations and data features. Although inference is in general hard, we show that for one very relevant application - document ranking - exact inference is efficient. For general model instances, an appropriate sampler is readily available. Contrary to existing max-margin matching models, our approach is statistically consistent and, in addition, experiments with increasing sample sizes indicate superior improvement over such models. We apply the method to graph matching in computer vision as well as to a standard benchmark dataset for learning document ranking, in which we obtain state-of-the-art results, in particular improving on max-margin variants. The drawback of this method with respect to max-margin alternatives is its runtime for large graphs, which is high comparatively.
Know Thy Neighbour: A Normative Theory of Synaptic Depression
Authors: Jean-Pascal Pfister, Peter Dayan, Máté Lengyel
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Synapses exhibit an extraordinary degree of short-term malleability, with release probabilities and effective synaptic strengths changing markedly over multiple timescales. From the perspective of a fixed computational operation in a network, this seems like a most unacceptable degree of added noise. We suggest an alternative theory according to which short term synaptic plasticity plays a normatively-justifiable role. This theory starts from the commonplace observation that the spiking of a neuron is an incomplete, digital, report of the analog quantity that contains all the critical information, namely its membrane potential. We suggest that one key task for a synapse is to solve the inverse problem of estimating the pre-synaptic membrane potential from the spikes it receives and prior  expectations, as in a recursive filter. We show that short-term synaptic depression has canonical dynamics which closely resemble those required for optimal estimation, and that it indeed supports high quality estimation. Under this account, the local postsynaptic potential and the level of synaptic resources track the (scaled) mean and variance of the estimated presynaptic membrane potential. We make  experimentally testable predictions for how the statistics of subthreshold membrane potential fluctuations and the form of spiking non-linearity should be related to the properties of short-term plasticity in any particular cell type.
Time-rescaling methods for the estimation and assessment of non-Poisson neural encoding models
Authors: Jonathan W. Pillow
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Recent work on the statistical modeling of neural responses has focused on modulated renewal processes in which the spike rate is a function of the stimulus and recent spiking history. Typically, these models incorporate spike-history dependencies via either: (A) a conditionally-Poisson process with rate dependent on a linear projection of the spike train history (e.g., generalized linear model); or (B) a modulated non-Poisson renewal process (e.g., inhomogeneous gamma process). Here we show that the two approaches can be combined, resulting in a {\it conditional renewal} (CR) model for neural spike trains. This model captures both real and rescaled-time effects, and can be fit by maximum likelihood using a simple application of the time-rescaling theorem [1]. We show that for any modulated renewal process model, the log-likelihood is concave in the linear filter parameters only under certain restrictive conditions on the renewal density (ruling out many popular choices, e.g. gamma with $\kappa \neq1$), suggesting that real-time history effects are easier to estimate than non-Poisson renewal properties. Moreover, we show that goodness-of-fit tests based on the time-rescaling theorem [1] quantify relative-time effects, but do not reliably assess accuracy in spike prediction or stimulus-response modeling. We illustrate the CR model with applications to both real and simulated neural data.
Bilinear classifiers for visual recognition
Authors: Hamed Pirsiavash, Deva Ramanan, Charless C. Fowlkes
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Action Classification, General Classification, Transfer Learning

We describe an algorithm for learning bilinear SVMs. Bilinear classifiers are a discriminative variant of bilinear models, which capture the dependence of data on multiple factors. Such models are particularly appropriate for visual data that is better represented as a matrix or tensor, rather than a vector. Matrix encodings allow for more natural regularization through rank restriction. For example, a rank-one scanning-window classifier yields a separable filter. Low-rank models have fewer parameters and so are easier to regularize and faster to score at run-time. We learn low-rank models with bilinear classifiers. We also use bilinear classifiers for transfer learning by sharing linear factors between different classification tasks. Bilinear classifiers are trained with biconvex programs. Such programs are optimized with coordinate descent, where each coordinate step requires solving a convex program - in our case, we use a standard off-the-shelf SVM solver. We demonstrate bilinear SVMs on difficult problems of people detection in video sequences and action classification of video sequences, achieving state-of-the-art results in both.
Convex Relaxation of Mixture Regression with Efficient Algorithms
Authors: Novi Quadrianto, John Lim, Dale Schuurmans, Tibério S. Caetano
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Motion Segmentation, regression

We develop a convex relaxation of maximum a posteriori estimation of a mixture of regression models. Although our relaxation involves a semidefinite matrix variable, we reformulate the problem to eliminate the need for general semidefinite programming. In particular, we provide two reformulations that admit fast algorithms. The first is a max-min spectral reformulation exploiting quasi-Newton descent. The second is a min-min reformulation consisting of fast alternating steps of closed-form updates. We evaluate the methods against Expectation-Maximization in a real problem of motion segmentation from video data.
Distribution Matching for Transduction
Authors: Novi Quadrianto, James Petterson, Alex J. Smola
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification, regression

Many transductive inference algorithms assume that distributions over training and test estimates should be related, e.g. by providing a large margin of separation on both sets. We use this idea to design a transduction algorithm which can be used without modification for classification, regression, and structured estimation. At its heart we exploit the fact that for a good learner the distributions over the outputs on training and test sets should match. This is a classical two-sample problem which can be solved efficiently in its most general form by using distance measures in Hilbert Space. It turns out that a number of existing heuristics can be viewed as special cases of our approach.