pwc-archive/papers-with-abstracts huggingface dataset:
No-Regret Algorithms for Unconstrained Online Convex Optimization
Authors: Brendan Mcmahan, Matthew Streeter
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification

Some of the most compelling applications of online convex optimization, including online prediction and classification, are unconstrained: the natural feasible set is R^n.  Existing algorithms fail to achieve sub-linear regret in this setting unless constraints on the comparator point x* are known in advance.  We present an algorithm that, without such prior knowledge, offers near-optimal regret bounds with respect to _any_ choice of x*.  In particular, regret with respect to x* = 0 is _constant_.  We then prove lower bounds showing that our algorithm's guarantees are optimal in this setting up to constant factors.
Bayesian models for Large-scale Hierarchical Classification
Authors: Siddharth Gopal, Yiming Yang, Bing Bai, Alexandru Niculescu-Mizil
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, General Classification

A challenging problem in hierarchical classification is to leverage the hierarchical relations among classes for  improving classification performance. An even greater challenge is to do so in a manner that is computationally feasible for the large scale problems usually encountered in practice. This paper proposes a set of Bayesian methods to model hierarchical dependencies among class labels using multivari- ate logistic regression. Specifically, the parent-child relationships are modeled by placing a hierarchical prior over the children nodes centered around the parame- ters of their parents; thereby encouraging classes nearby in the hierarchy to share similar model parameters. We present new, efficient variational algorithms for tractable posterior inference in these models, and provide a parallel implementa- tion that can comfortably handle large-scale problems with hundreds of thousands of dimensions and tens of thousands of classes. We run a comparative evaluation on multiple large-scale benchmark datasets that highlights the scalability of our approach, and shows a significant performance advantage over the other state-of- the-art hierarchical methods.
Recovery of Sparse Probability Measures via Convex Programming
Authors: Mert Pilanci, Laurent E. Ghaoui, Venkat Chandrasekaran
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering

We consider the problem of cardinality penalized optimization of a convex function over the probability simplex with additional convex constraints. It's well-known that the classical L1 regularizer fails to promote sparsity on the probability simplex since L1 norm on the probability simplex is trivially constant. We propose a direct relaxation of the minimum cardinality problem and show that it can be efficiently solved using convex programming. As a first application we consider recovering a sparse probability measure given moment constraints, in which our formulation becomes linear programming, hence can be solved very efficiently. A sufficient condition for exact recovery of the minimum cardinality solution is derived for arbitrary affine constraints. We then develop a penalized version for the noisy setting which can be solved using second order cone programs. The proposed method outperforms known heuristics based on L1 norm. As a second application we consider convex clustering using a sparse Gaussian mixture and compare our results with the well known soft k-means algorithm.
Multiple Operator-valued Kernel Learning
Authors: Hachem Kadri, Alain Rakotomamonjy, Philippe Preux, Francis R. Bach
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: regression

Positive definite operator-valued kernels generalize the well-known notion of reproducing kernels, and are naturally adapted to multi-output learning situations. This paper addresses the problem of learning a finite linear combination of infinite-dimensional operator-valued kernels which are suitable for extending functional data analysis methods to nonlinear contexts. We study this problem in the case of kernel ridge regression for functional responses with an lr-norm constraint on the combination coefficients. The resulting optimization problem is more involved than those of multiple scalar-valued kernel learning since operator-valued kernels pose more technical and theoretical issues. We propose a multiple operator-valued kernel learning algorithm based on solving a system of linear operator equations by using a block coordinate-descent procedure. We experimentally validate our approach on a functional regression task in the context of finger movement prediction in brain-computer interfaces.
Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning
Authors: Ulugbek Kamilov, Sundeep Rangan, Michael Unser, Alyson K. Fletcher
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: compressed sensing, parameter estimation, Sparse Learning

We consider the estimation of an i.i.d.\ vector $\xbf \in \R^n$ from measurements $\ybf \in \R^m$ obtained by a general cascade model consisting of a known linear transform followed by a probabilistic componentwise (possibly nonlinear) measurement channel. We present a method, called adaptive generalized approximate message passing (Adaptive GAMP), that enables joint learning of the statistics of the prior and measurement channel along with estimation of the unknown vector $\xbf$. The proposed algorithm is a generalization of a recently-developed method by Vila and Schniter that uses expectation-maximization (EM) iterations where the posteriors in the E-steps are computed via approximate message passing. The techniques can be applied to a large class of learning problems including the learning of sparse priors in compressed sensing or identification of linear-nonlinear cascade models in dynamical systems and neural spiking processes.  We prove that for large i.i.d.\ Gaussian transform matrices the asymptotic componentwise behavior of the adaptive GAMP algorithm is predicted by a simple set of scalar state evolution equations.  This analysis shows that the adaptive GAMP method can yield asymptotically consistent parameter estimates, which implies that the algorithm achieves a reconstruction quality equivalent to the oracle algorithm that knows the correct parameter values.  The adaptive GAMP methodology thus provides a systematic, general and computationally efficient method applicable to a large range of complex linear-nonlinear models with provable guarantees.
A Better Way to Pretrain Deep Boltzmann Machines
Authors: Geoffrey E. Hinton, Ruslan R. Salakhutdinov
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We describe how the pre-training algorithm for Deep Boltzmann Machines (DBMs) is related to the pre-training algorithm for Deep Belief Networks and we show that under certain conditions, the pre-training procedure improves the variational lower bound of a two-hidden-layer DBM. Based on this analysis, we develop a different method of pre-training DBMs that distributes the modelling work more evenly over the hidden layers. Our results on the MNIST and NORB datasets demonstrate that the new pre-training algorithm allows us to learn better generative models.
Towards a learning-theoretic analysis of spike-timing dependent plasticity
Authors: David Balduzzi, Michel Besserve
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

This paper suggests a learning-theoretic perspective on how synaptic plasticity benefits global brain functioning. We introduce a model, the selectron, that (i) arises as the fast time constant limit of leaky integrate-and-fire neurons equipped with spiking timing dependent plasticity (STDP) and (ii) is amenable to theoretical analysis. We show that the selectron encodes reward estimates into spikes and that an error bound on spikes is controlled by a spiking margin and the sum of synaptic weights. Moreover, the efficacy of spikes (their usefulness to other reward maximizing selectrons) also depends on total synaptic strength. Finally, based on our analysis, we propose a regularized version of STDP, and show the regularization improves the robustness of neuronal learning when faced with multiple stimuli.
Learning Manifolds with K-Means and K-Flats
Authors: Guillermo Canas, Tomaso Poggio, Lorenzo Rosasco
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by  k-means and k-ﬂats, and analyze their performance. We extend previous results  for k-means in two separate directions. First, we provide new results for k-means reconstruction on manifolds and, secondly, we prove reconstruction bounds for higher-order approximation (k-ﬂats), for which no known results were previously available. While the results for k-means are novel, some of the technical tools are well-established in the literature. In the case of k-ﬂats, both the results and the mathematical tools are  new.
Iterative ranking from pair-wise comparisons
Authors: Sahand Negahban, Sewoong Oh, Devavrat Shah
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR’s TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining ranking, finding ‘scores’ for each object (e.g. player’s rating) is of interest to understanding the intensity of the preferences.   In this paper, we propose a novel iterative rank aggregation algorithm for discovering scores for objects from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with edges present between two objects if they are compared; the scores turn out to be the stationary probability of this random walk. The algorithm is model independent. To establish the efficacy of our method, however, we consider the popular Bradley-Terry-Luce (BTL) model in which each object has an associated score which determines the probabilistic outcomes of pairwise comparisons between objects. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. This, in essence, leads to order-optimal dependence on the number of samples required to learn the scores well by our algorithm. Indeed, the experimental evaluation shows that our (model independent) algorithm performs as well as the Maximum Likelihood Estimator of the BTL model and outperforms a recently proposed algorithm by Ammar and Shah [1].
A Polynomial-time Form of Robust Regression
Authors: Yao-Liang Yu, Özlem Aslan, Dale Schuurmans
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Form, regression

Despite the variety of robust regression methods that have been developed, current regression formulations are either NP-hard, or allow unbounded response to even a single leverage point. We present a general formulation for robust regression --Variational M-estimation--that unifies a number of robust regression methods while allowing a tractable approximation strategy. We develop an estimator that requires only polynomial-time, while achieving certain robustness and consistency guarantees. An experimental evaluation demonstrates the effectiveness of the new estimation approach  compared to standard methods.
Learning Probability Measures with respect to Optimal Transport Metrics
Authors: Guillermo Canas, Lorenzo Rosasco
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Learning Theory, Quantization

We study the problem of estimating, in the sense of optimal transport metrics, a measure which is assumed supported on a manifold embedded in a Hilbert space. By establishing a precise connection between optimal transport metrics, optimal quantization, and learning theory, we derive new probabilistic bounds for the performance of a classic algorithm in unsupervised learning (k-means), when used to produce a probability measure derived from the data. In the course of the analysis, we arrive at new lower bounds, as well as probabilistic bounds on the convergence rate of the empirical law of large numbers, which, unlike existing bounds, are applicable to a wide class of measures.
Label Ranking with Partial Abstention based on Thresholded Probabilistic Models
Authors: Weiwei Cheng, Eyke Hüllermeier, Willem Waegeman, Volkmar Welker
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification, Learning-To-Rank

Several machine learning methods allow for abstaining from uncertain predictions. While being common for settings like conventional classification, abstention has been studied much less in learning to rank. We address abstention for the label ranking setting, allowing the learner to declare certain pairs of labels as being incomparable and, thus, to predict partial instead of total orders. In our method, such predictions are produced via thresholding the probabilities of pairwise preferences between labels, as induced by a predicted probability distribution on the set of all rankings. We formally analyze this approach for the Mallows and the Plackett-Luce model, showing that it produces proper partial orders as predictions and characterizing the expressiveness of the induced class of partial orders. These theoretical results are complemented by experiments demonstrating the practical usefulness of the approach.
Adaptive Learning of Smoothing Functions: Application to Electricity Load Forecasting
Authors: Amadou Ba, Mathieu Sinn, Yannig Goude, Pascal Pompey
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Additive models, Load Forecasting

This paper proposes an efficient online learning algorithm to track the smoothing functions of Additive Models. The key idea is to combine the linear representation of Additive Models with a Recursive Least Squares (RLS) filter. In order to quickly track changes in the model and put more weight on recent data, the RLS filter uses a forgetting factor which exponentially weights down observations by the order of their arrival. The tracking behaviour is further enhanced by using an adaptive forgetting factor which is updated based on the gradient of the a priori errors. Using results from Lyapunov stability theory, upper bounds for the learning rate are analyzed. The proposed algorithm is applied to 5 years of electricity load data provided by the French utility company Electricite de France (EDF). Compared to state-of-the-art methods, it achieves a superior performance in terms of model tracking and prediction accuracy.
Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs
Authors: Michael Collins, Shay B. Cohen
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Tensor Decomposition

We describe an approach to speed-up inference with latent variable PCFGs, which have been shown to  be highly effective for natural language parsing. Our approach is based on a tensor formulation recently introduced for spectral estimation of latent-variable PCFGs coupled with a tensor decomposition algorithm well-known in the multilinear algebra literature.  We also describe an error bound for this approximation, which bounds the difference between the probabilities calculated by the algorithm and the true probabilities that the approximated model gives. Empirical evaluation on real-world natural language parsing data demonstrates a significant speed-up at minimal cost for parsing performance.
Semi-supervised Eigenvectors for Locally-biased Learning
Authors: Toke Hansen, Michael W. Mahoney
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: BIG-bench Machine Learning

In many applications, one has information, e.g., labels that are  provided in a semi-supervised manner, about a specific target region of a  large data set, and one wants to perform machine learning and data analysis  tasks nearby that pre-specified target region.   Locally-biased problems of this sort are particularly challenging for  popular eigenvector-based machine learning and data analysis tools. At root, the reason is that eigenvectors are inherently global quantities. In this paper, we address this issue by providing a methodology to construct  semi-supervised eigenvectors of a graph Laplacian, and we illustrate  how these locally-biased eigenvectors can be used to perform  locally-biased machine learning. These semi-supervised eigenvectors capture successively-orthogonalized  directions of maximum variance, conditioned on being well-correlated with an  input seed set of nodes that is assumed to be provided in a semi-supervised  manner. We also provide several empirical examples demonstrating how these  semi-supervised eigenvectors can be used to perform locally-biased learning.
Exponential Concentration for Mutual Information Estimation with Application to Forests
Authors: Han Liu, Larry Wasserman, John D. Lafferty
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Mutual Information Estimation

We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.
Augment-and-Conquer Negative Binomial Processes
Authors: Mingyuan Zhou, Lawrence Carin
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Data Augmentation

By developing data augmentation methods unique to the negative binomial (NB) distribution, we unite seemingly disjoint count and mixture models  under the  NB process framework. We develop fundamental properties of the models and derive efficient Gibbs sampling inference. We show that the  gamma-NB process can be reduced to the hierarchical Dirichlet process with normalization, highlighting its unique theoretical, structural and computational advantages. A variety of NB processes with distinct sharing mechanisms are constructed and applied to topic modeling, with connections to existing algorithms, showing the importance of inferring both the NB dispersion and probability parameters.
Transferring Expectations in Model-based Reinforcement Learning
Authors: Trung Nguyen, Tomi Silander, Tze Y. Leong
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: model, Model-based Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Transfer Learning

We study how to automatically select and adapt multiple abstractions or representations of the world to support model-based reinforcement learning. We address the challenges of transfer learning in heterogeneous environments with varying tasks. We present an efficient, online framework that, through a sequence of tasks, learns a set of relevant representations to be used in future tasks. Without pre-defined mapping strategies, we introduce a general approach to support transfer learning across different state spaces. We demonstrate the potential impact of our system through improved jumpstart and faster convergence to near optimum policy in two benchmark domains.
Minimization of Continuous Bethe Approximations: A Positive Variation
Authors: Jason Pacheco, Erik B. Sudderth
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: valid

We develop convergent minimization algorithms for Bethe variational approximations which explicitly constrain marginal estimates to families of valid distributions.  While existing message passing algorithms define fixed point iterations corresponding to stationary points of the Bethe free energy, their greedy dynamics do not distinguish between local minima and maxima, and can fail to converge. For continuous estimation problems, this instability is linked to the creation of invalid marginal estimates, such as Gaussians with negative variance. Conversely, our approach leverages multiplier methods with well-understood convergence properties, and uses bound projection methods to ensure that marginal approximations are valid at all iterations. We derive general algorithms for discrete and Gaussian pairwise Markov random fields, showing improvements over standard loopy belief propagation. We also apply our method to a hybrid model with both discrete and continuous variables, showing improvements over expectation propagation.
Non-linear Metric Learning
Authors: Dor Kedem, Stephen Tyree, Fei Sha, Gert R. Lanckriet, Kilian Q. Weinberger
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Metric Learning

In this paper, we introduce two novel metric learning algorithms, χ2-LMNN and GB-LMNN, which are explicitly designed to be non-linear and  easy-to-use. The two approaches achieve this goal in fundamentally different ways: χ2-LMNN inherits the computational benefits of a linear mapping from linear metric learning, but uses a non-linear χ2-distance to explicitly capture similarities within histogram data sets; GB-LMNN applies gradient-boosting to learn non-linear mappings directly in function space and takes advantage of this approach's robustness, speed, parallelizability and insensitivity towards the single additional hyper-parameter. On various benchmark data sets, we demonstrate these methods not only match the current state-of-the-art in terms of kNN classification error, but in the case of χ2-LMNN, obtain best results in 19 out of 20 learning settings.
Factorial LDA: Sparse Multi-Dimensional Text Models
Authors: Michael Paul, Mark Dredze
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Multi-dimensional latent variable models can capture the many latent factors in a text corpus, such as topic, author perspective and sentiment. We introduce factorial LDA, a multi-dimensional latent variable model in which a document is influenced by K different factors, and each word token depends on a K-dimensional vector of latent variables. Our model incorporates structured word priors and learns a sparse product of factors. Experiments on research abstracts show that our model can learn latent factors such as research topic, scientific discipline, and focus (e.g. methods vs. applications.) Our modeling improvements reduce test perplexity and improve human interpretability of the discovered factors.
Ancestor Sampling for Particle Gibbs
Authors: Fredrik Lindsten, Thomas Schön, Michael. I. Jordan
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: State Space Models

We present a novel method in the family of particle MCMC methods that we refer to as particle Gibbs with ancestor sampling (PG-AS). Similarly to the existing PG with backward simulation (PG-BS) procedure, we use backward sampling to (considerably) improve the mixing of the PG kernel. Instead of using separate forward and backward sweeps as in PG-BS, however, we achieve the same effect in a single forward sweep. We apply the PG-AS framework to the challenging class of non-Markovian state-space models. We develop a truncation strategy of these models that is applicable in principle to any backward-simulation-based method, but which is particularly well suited to the PG-AS framework. In particular, as we show in a simulation study, PG-AS can yield an order-of-magnitude improved accuracy relative to PG-BS due to its robustness to the truncation error. Several application examples are discussed, including Rao-Blackwellized particle smoothing and inference in degenerate state-space models.