pwc-archive/papers-with-abstracts huggingface dataset:
Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction
Authors: Kwang I. Kim, Florian Steinke, Matthias Hein
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Dimensionality Reduction, regression, Supervised dimensionality reduction

Semi-supervised regression based on the graph Laplacian suffers from the fact that the solution is biased towards a constant and the lack of extrapolating power. Outgoing from these observations we propose to use the second-order Hessian energy for semi-supervised regression which overcomes both of these problems, in particular, if the data lies on or close to a low-dimensional submanifold in the feature space, the Hessian energy prefers functions which vary ``linearly with respect to the natural parameters in the data. This property makes it also particularly suited for the task of semi-supervised dimensionality reduction where the goal is to find the natural parameters in the data based on a few labeled points. The experimental result suggest that our method is superior to semi-supervised regression using Laplacian regularization and standard supervised methods and is particularly suited for semi-supervised dimensionality reduction.
Replacing supervised classification learning by Slow Feature Analysis in spiking neural networks
Authors: Stefan Klampfl, Wolfgang Maass
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification

Many models for computations in recurrent networks of neurons assume that the network state moves from some initial state to some fixed point attractor or limit cycle that represents the output of the computation. However experimental data show that in response to a sensory stimulus the network state moves from its initial state through a trajectory of network states and eventually returns to the initial state, without reaching an attractor or limit cycle in between. This type of network response, where salient information about external stimuli is encoded in characteristic trajectories of continuously varying network states, raises the question how a neural system could compute with such code, and arrive for example at a temporally stable classification of the external stimulus. We show that a known unsupervised learning algorithm, Slow Feature Analysis (SFA), could be an important ingredient for extracting stable information from these network trajectories. In fact, if sensory stimuli are more often followed by another stimulus from the same class than by a stimulus from another class, SFA approaches the classification capability of Fishers Linear Discriminant (FLD), a powerful algorithm for supervised learning. We apply this principle to simulated cortical microcircuits, and show that it enables readout neurons to learn discrimination of spoken digits and detection of repeating firing patterns within a stream of spike trains with the same firing statistics, without requiring any supervision for learning.
Efficient and Accurate Lp-Norm Multiple Kernel Learning
Authors: Marius Kloft, Ulf Brefeld, Pavel Laskov, Klaus-Robert Müller, Alexander Zien, Sören Sonnenburg
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Learning linear combinations of multiple kernels is an appealing strategy when the right choice of features is unknown. Previous approaches to multiple kernel learning (MKL) promote sparse kernel combinations and hence support interpretability. Unfortunately, L1-norm MKL is hardly observed to outperform trivial baselines in practical applications. To allow for robust kernel mixtures, we generalize MKL to arbitrary Lp-norms. We devise new insights on the connection between  several existing MKL formulations and develop two efficient interleaved optimization strategies for arbitrary p>1. Empirically, we demonstrate that the interleaved optimization strategies are much faster compared to the traditionally used wrapper approaches. Finally, we apply Lp-norm MKL to real-world problems from computational biology, showing that non-sparse MKL achieves accuracies that go beyond the state-of-the-art.
Sparsistent Learning of Varying-coefficient Models with Structural Changes
Authors: Mladen Kolar, Le Song, Eric P. Xing
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Brain Computer Interface, Model Selection

To estimate the changing structure of a varying-coefficient   varying-structure (VCVS) model remains an important and open problem   in dynamic system modelling, which includes learning trajectories of   stock prices, or uncovering the topology of an evolving gene   network. In this paper, we investigate sparsistent learning of a   sub-family of this model --- piecewise constant VCVS models. We   analyze two main issues in this problem: inferring time points where   structural changes occur and estimating model structure (i.e., model   selection) on each of the constant segments. We propose a two-stage   adaptive procedure, which first identifies jump points of structural   changes and then identifies relevant covariates to a response on   each of the segments. We provide an asymptotic analysis of the   procedure, showing that with the increasing sample size, number of   structural changes, and number of variables, the true model can be   consistently selected. We demonstrate the performance of the method   on synthetic data and apply it to the brain computer interface   dataset. We also consider how this applies to structure estimation   of time-varying probabilistic graphical models.
Skill Discovery in Continuous Reinforcement Learning Domains using Skill Chaining
Authors: George Konidaris, Andrew G. Barto
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We introduce skill chaining, a skill discovery method for reinforcement learning agents in continuous domains, that builds chains of skills leading to an end-of-task reward. We demonstrate experimentally that it creates skills that result in performance benefits in a challenging continuous domain.
Fast, smooth and adaptive regression in metric spaces
Authors: Samory Kpotufe
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

It was recently shown that certain nonparametric regressors can escape the curse of dimensionality in the sense that their convergence rates adapt to the intrinsic dimension of data (\cite{BL:65, SK:77}). We prove some stronger results in more general settings. In particular, we consider a regressor which, by combining aspects of both tree-based regression and kernel regression, operates on a general metric space, yields a smooth function, and evaluates in time $O(\log n)$. We derive a tight convergence rate of the form $n^{-2/(2+d)}$ where $d$ is the Assouad dimension of the input space.
Fast Image Deconvolution using Hyper-Laplacian Priors
Authors: Dilip Krishnan, Rob Fergus
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Deblurring, Denoising, Image Deconvolution, Super-Resolution

The heavy-tailed distribution of gradients in natural scenes have proven effective priors for a range of problems such as denoising, deblurring and super-resolution. However, the use of sparse distributions makes the problem non-convex and impractically slow to solve for multi-megapixel images. In this paper we describe a deconvolution approach that is several orders of magnitude faster than existing techniques that use hyper-Laplacian priors. We adopt an alternating minimization scheme where one of the two phases is a non-convex problem that is separable over pixels. This per-pixel sub-problem may be solved with a lookup table (LUT). Alternatively, for two specific values of α, 1/2 and 2/3 an analytic solution can be found, by finding the roots of a cubic and quartic polynomial, respectively. Our approach (using either LUTs or analytic formulae) is able to deconvolve a 1 megapixel image in less than ∼3 seconds, achieving comparable quality to existing methods such as iteratively reweighted least squares (IRLS) that take ∼20 minutes. Furthermore, our method is quite general and can easily be extended to related image processing problems, beyond the deconvolution application demonstrated.
Learning to Hash with Binary Reconstructive Embeddings
Authors: Brian Kulis, Trevor Darrell
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Retrieval

Fast retrieval methods are increasingly critical for many large-scale analysis tasks, and there have been several recent methods that attempt to learn hash functions for fast and accurate nearest neighbor searches.  In this paper, we develop an algorithm for learning hash functions based on explicitly minimizing the reconstruction error between the original distances and the Hamming distances of the corresponding binary embeddings.  We develop a scalable coordinate-descent algorithm for our proposed hashing objective that is able to efficiently learn hash functions in a variety of settings.  Unlike existing methods such as semantic hashing and spectral hashing, our method is easily kernelized and does not require restrictive assumptions about the underlying distribution of the data.  We present results over several domains to demonstrate that our method outperforms existing state-of-the-art techniques.
Learning a Small Mixture of Trees
Authors: M. P. Kumar, Daphne Koller
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Face Recognition, Variational Inference

The problem of approximating a given probability distribution using a simpler distribution plays an important role in several areas of machine learning, e.g. variational inference and classification. Within this context, we consider the task of learning a mixture of tree distributions. Although mixtures of trees can be learned by minimizing the KL-divergence using an EM algorithm, its success depends heavily on the initialization. We propose an efficient strategy for obtaining a good initial set of trees that attempts to cover the entire observed distribution by minimizing the $\alpha$-divergence with $\alpha = \infty$. We formulate the problem using the fractional covering framework and present a convergent sequential algorithm that only relies on solving a convex program at each iteration. Compared to previous methods, our approach results in a significantly smaller mixture of trees that provides similar or better accuracies. We demonstrate the usefulness of our approach by learning pictorial structures for face recognition.
Ensemble Nystrom Method
Authors: Sanjiv Kumar, Mehryar Mohri, Ameet Talwalkar
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

A crucial technique for scaling kernel methods to very large data sets reaching or exceeding millions of instances is based on low-rank approximation of kernel matrices. We introduce a new family of algorithms based on mixtures of Nystrom approximations, ensemble Nystrom algorithms, that yield more accurate low-rank approximations than the standard Nystrom method. We give a detailed study of multiple variants of these algorithms based on simple averaging, an exponential weight method, or regression-based methods. We also present a theoretical analysis of these algorithms, including novel error bounds guaranteeing a better convergence rate than the standard Nystrom method. Finally, we report the results of extensive experiments with several data sets containing up to 1M points demonstrating the signiﬁcant performance improvements gained over the standard Nystrom approximation.
Occlusive Components Analysis
Authors: Jörg Lücke, Richard Turner, Maneesh Sahani, Marc Henniges
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Object

We study unsupervised learning in a probabilistic generative model for occlusion. The model uses two types of latent variables: one indicates which objects are present in the image, and the other how they are ordered in depth. This depth order then determines how the positions and appearances of the objects present, specified in the model parameters, combine to form the image. We show that the object parameters can be learnt from an unlabelled set of images in which objects occlude one another. Exact maximum-likelihood learning is intractable. However, we show that tractable approximations to Expectation Maximization (EM) can be found if the training images each contain only a small number of objects on average. In numerical experiments it is shown that these approximations recover the correct set of object parameters. Experiments on a novel version of the bars test using colored bars, and experiments on more realistic data, show that the algorithm performs well in extracting the generating causes. Experiments based on the standard bars benchmark test for object learning show that the algorithm performs well in comparison to other recent component extraction approaches. The model and the learning algorithm thus connect research on occlusion with the research field of multiple-cause component extraction methods.
Monte Carlo Sampling for Regret Minimization in Extensive Games
Authors: Marc Lanctot, Kevin Waugh, Martin Zinkevich, Michael Bowling
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: counterfactual, Decision Making, Sequential Decision Making

Sequential decision-making with multiple agents and imperfect information is commonly modeled as an extensive game.  One efficient method for computing Nash equilibria in large, zero-sum, imperfect information games is counterfactual regret minimization (CFR). In the domain of poker, CFR has proven effective, particularly when using a domain-specific augmentation involving chance outcome sampling.  In this paper, we describe a general family of domain independent CFR sample-based algorithms called Monte Carlo counterfactual regret minimization (MCCFR) of which the original and poker-specific versions are special cases. We start by showing that MCCFR performs the same regret updates as CFR on expectation. Then, we introduce two sampling schemes: {\it outcome sampling} and {\it external sampling}, showing that both have bounded overall regret with high  probability. Thus, they can compute an approximate equilibrium using self-play. Finally, we prove a new tighter bound on the regret for the original CFR algorithm and relate this new bound to MCCFRs bounds. We show empirically that, although the sample-based algorithms require more iterations, their lower cost per iteration can lead to dramatically faster convergence in various games.
Inter-domain Gaussian Processes for Sparse Inference using Inducing Features
Authors: Miguel Lázaro-Gredilla, Aníbal Figueiras-Vidal
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Computational Efficiency, Gaussian Processes, Model Selection

We present a general inference framework for inter-domain Gaussian Processes (GPs), focusing on its usefulness to build sparse GP models. The state-of-the-art sparse GP model introduced by Snelson and Ghahramani in [1] relies on finding a small, representative pseudo data set of m elements (from the same domain as the n available data elements) which is able to explain existing data well, and then uses it to perform inference. This reduces inference and model selection computation time from O(n^3) to O(m^2n), where m << n. Inter-domain GPs can be used to find a (possibly more compact) representative set of features lying in a different domain, at the same computational cost. Being able to specify a different domain for the representative features allows to incorporate prior knowledge about relevant characteristics of data and detaches the functional form of the covariance and basis functions. We will show how previously existing models fit into this framework and will use it to develop two new sparse GP models. Tests on large, representative regression data sets suggest that significant improvement can be achieved, while retaining computational efficiency.
Unsupervised feature learning for audio classification using convolutional deep belief networks
Authors: Honglak Lee, Peter Pham, Yan Largman, Andrew Y. Ng
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Audio Classification, Deep Learning, General Classification

In recent years, deep learning approaches have gained significant interest as a way of building hierarchical representations from unlabeled data. However, to our knowledge, these deep learning approaches have not been extensively studied for auditory data. In this paper, we apply convolutional deep belief networks to audio data and empirically evaluate them on various audio classification tasks. For the case of speech data, we show that the learned features correspond to phones/phonemes. In addition, our feature representations trained from unlabeled audio data show very good performance for multiple audio classification tasks. We hope that this paper will inspire more research on deep learning approaches applied to a wide range of audio recognition tasks.
Functional network reorganization in motor cortex can be explained by reward-modulated Hebbian learning
Authors: Steven Chase, Andrew Schwartz, Wolfgang Maass, Robert A. Legenstein
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

The control of neuroprosthetic devices from the activity of motor cortex neurons benefits from learning effects where the function of these neurons is adapted to the control task. It was recently shown that tuning properties of neurons in monkey motor cortex are adapted selectively in order to compensate for an erroneous interpretation of their activity. In particular, it was shown that the tuning curves of those neurons whose preferred directions had been misinterpreted changed more than those of other neurons. In this article, we show that the experimentally observed self-tuning properties of the system can be explained on the basis of a simple learning rule. This learning rule utilizes neuronal noise for exploration and performs Hebbian weight updates that are modulated by a global reward signal. In contrast to most previously proposed reward-modulated Hebbian learning rules, this rule does not require extraneous knowledge about what is noise and what is signal. The learning rule is able to optimize the performance of the model system within biologically realistic periods of time and under high noise levels. When the neuronal noise is fitted to experimental data, the model produces learning effects similar to those found in monkey experiments.
An Integer Projected Fixed Point Method for Graph Matching and MAP Inference
Authors: Marius Leordeanu, Martial Hebert, Rahul Sukthankar
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Graph Matching

Graph matching and MAP inference are essential problems in computer vision and machine learning. We introduce a novel algorithm that can accommodate both problems and solve them efficiently. Recent graph matching algorithms are based on a general quadratic programming formulation, that takes in consideration both unary and second-order terms reflecting the similarities in local appearance as well as in the pairwise geometric relationships between the matched features. In this case the problem is NP-hard and a lot of effort has been spent in finding efficiently approximate solutions by relaxing the constraints of the original problem. Most algorithms find optimal continuous solutions of the modified problem, ignoring during the optimization the original discrete constraints. The continuous solution is quickly binarized at the end, but very little attention is put into this final discretization step. In this paper we argue that the stage in which a discrete solution is found is crucial for good performance. We propose an efficient algorithm, with climbing and convergence properties, that optimizes in the discrete domain the quadratic score, and it gives excellent results either by itself or by starting from the solution returned by any graph matching algorithm. In practice it outperforms state-or-the art algorithms and it also significantly improves their performance if used in combination. When applied to MAP inference, the algorithm is a parallel extension of Iterated Conditional Modes (ICM) with climbing and convergence properties that make it a compelling alternative to the sequential ICM. In our experiments on MAP inference our algorithm proved its effectiveness by outperforming ICM and Max-Product Belief Propagation.
Probabilistic Relational PCA
Authors: Wu-Jun Li, Dit-yan Yeung, Zhihua Zhang
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Dimensionality Reduction

One crucial assumption made by both principal component analysis (PCA) and probabilistic PCA (PPCA) is that the instances are independent and identically distributed (i.i.d.). However, this common i.i.d. assumption is unreasonable for relational data. In this paper, by explicitly modeling covariance between instances as derived from the relational information, we propose a novel probabilistic dimensionality reduction method, called probabilistic relational PCA (PRPCA), for relational data analysis. Although the i.i.d. assumption is no longer adopted in PRPCA, the learning algorithms for PRPCA can still be devised easily like those for PPCA which makes explicit use of the i.i.d. assumption. Experiments on real-world data sets show that PRPCA can effectively utilize the relational information to dramatically outperform PCA and achieve state-of-the-art performance.
Asymptotically Optimal Regularization in Smooth Parametric Models
Authors: Percy S. Liang, Guillaume Bouchard, Francis R. Bach, Michael. I. Jordan
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Multi-Task Learning

Many types of regularization schemes have been employed in statistical learning, each one motivated by some assumption about the problem domain.  In this paper, we present a unified asymptotic analysis of smooth regularizers, which allows us to see how the validity of these assumptions impacts the success of a particular regularizer.  In addition, our analysis motivates an algorithm for optimizing regularization parameters, which in turn can be analyzed within our framework.  We apply our analysis to several examples, including hybrid generative-discriminative learning and multi-task learning.
Nonparametric Greedy Algorithms for the Sparse Learning Problem
Authors: Han Liu, Xi Chen
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Additive models, regression, Sparse Learning, Variable Selection

This paper studies the forward greedy strategy in sparse nonparametric regression. For additive models, we propose an algorithm called additive forward regression; for general multivariate regression, we propose an algorithm called generalized forward regression. Both of them simultaneously conduct estimation and variable selection in nonparametric settings for the high dimensional sparse learning problem. Our main emphasis is empirical: on both simulated and real data, these two simple greedy methods can clearly outperform several state-of-the-art competitors, including the LASSO, a nonparametric version of the LASSO called the sparse additive model (SpAM) and a recently proposed adaptive parametric forward-backward algorithm called the Foba. Some theoretical justifications are also provided.