pwc-archive/papers-with-abstracts huggingface dataset:
Submodular Multi-Label Learning
Authors: James Petterson, Tibério S. Caetano
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Multi-Label Learning

In this paper we present an algorithm to learn a multi-label classifier which attempts at directly optimising the F-score. The key novelty of our formulation is that we explicitly allow for assortative (submodular) pairwise label interactions, i.e., we can leverage the co-ocurrence of pairs of labels in order to improve the quality of prediction. Prediction in this model consists of minimising a particular submodular set function, what can be accomplished exactly and efficiently via graph-cuts. Learning however is substantially more involved and requires the solution of an intractable combinatorial optimisation problem. We present an approximate algorithm for this problem and prove that it is sound in the sense that it never predicts incorrect labels. We also present a nontrivial test of a sufficient condition for our algorithm to have found an optimal solution. We present experiments on benchmark multi-label datasets, which attest the value of our proposed technique. We also make available source code that enables the reproduction of our experiments.
Uniqueness of Belief Propagation on Signed Graphs
Authors: Yusuke Watanabe
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

While loopy Belief Propagation (LBP) has been utilized in a wide variety of applications with empirical success, it comes with few theoretical guarantees. Especially, if the interactions of random variables in a graphical model are strong, the behaviors of the algorithm can be difficult to analyze due to underlying phase transitions. In this paper, we develop a novel approach to the uniqueness problem of the LBP fixed point; our new “necessary and sufficient” condition is stated in terms of graphs and signs, where the sign denotes the types (attractive/repulsive) of the interaction (i.e., compatibility function) on the edge. In all previous works, uniqueness is guaranteed only in the situations where the strength of the interactions are “sufficiently” small in certain senses. In contrast, our condition covers arbitrary strong interactions on the specified class of signed graphs. The result of this paper is based on the recent theoretical advance in the LBP algorithm; the connection with the graph zeta function.
Higher-Order Correlation Clustering for Image Segmentation
Authors: Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, Chang D. Yoo
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering, graph partitioning, Image Segmentation, Segmentation, Semantic Segmentation, Superpixels

For many of the state-of-the-art computer vision algorithms, image segmentation is an important preprocessing step. As such, several image segmentation algorithms have been proposed, however, with certain reservation due to high computational load and many hand-tuning parameters. Correlation clustering, a graph-partitioning algorithm often used in natural language processing and document clustering, has the potential to perform better than previously proposed image segmentation algorithms. We improve the basic correlation clustering formulation by taking into account higher-order cluster relationships. This improves clustering in the presence of local boundary ambiguities. We first apply the pairwise correlation clustering to image segmentation over a pairwise superpixel graph and then develop higher-order correlation clustering over a hypergraph that considers higher-order relations among superpixels. Fast inference is possible by linear programming relaxation, and also effective parameter learning framework by structured support vector machine is possible. Experimental results on various datasets show that the proposed higher-order correlation clustering outperforms other state-of-the-art image segmentation algorithms.
Optimal learning rates for least squares SVMs using Gaussian kernels
Authors: Mona Eberts, Ingo Steinwart
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

We prove a new oracle inequality for support vector machines with Gaussian RBF kernels solving the regularized least squares regression problem. To this end, we apply the modulus of smoothness. With the help of the new oracle inequality we then derive learning rates that can also be achieved by a simple data-dependent parameter selection method. Finally, it turns out that our learning rates are asymptotically optimal for regression functions satisfying certain standard smoothness conditions.
Learning Auto-regressive Models from Sequence and Non-sequence Data
Authors: Tzu-Kuo Huang, Jeff G. Schneider
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Time Series, Time Series Analysis

Vector Auto-regressive models (VAR) are useful tools for analyzing time series  data. In quite a few modern time series modelling tasks, the collection of reliable  time series turns out to be a major challenge, either due to the slow progression of  the dynamic process of interest, or inaccessibility of repetitive measurements of  the same dynamic process over time. In those situations, however, we observe that  it is often easier to collect a large amount of non-sequence samples, or snapshots  of the dynamic process of interest. In this work, we assume a small amount of time  series data are available, and propose methods to incorporate non-sequence data  into penalized least-square estimation of VAR models. We consider non-sequence  data as samples drawn from the stationary distribution of the underlying VAR  model, and devise a novel penalization scheme based on the discrete-time Lyapunov  equation concerning the covariance of the stationary distribution. Experiments  on synthetic and video data demonstrate the effectiveness of the proposed  methods.
Committing Bandits
Authors: Loc X. Bui, Ramesh Johari, Shie Mannor
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We consider a multi-armed bandit problem where there are two phases. The first phase is an experimentation phase where the decision maker is free to explore multiple options. In the second phase the decision maker has to commit to one of the arms and stick with it. Cost is incurred during both phases with a higher cost during the experimentation phase. We analyze the regret in this setup, and both propose algorithms and provide upper and lower bounds that depend on the ratio of the duration of the experimentation phase to the duration of the commitment phase. Our analysis reveals that if given the choice, it is optimal to experiment $\Theta(\ln T)$ steps and then commit, where $T$ is the time horizon.
Energetically Optimal Action Potentials
Authors: Martin B. Stemmler, Biswa Sengupta, Simon Laughlin, Jeremy Niven
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Most action potentials in the nervous system take on the form of strong, rapid, and brief voltage deflections known as spikes, in stark contrast to other action potentials, such as in the heart, that are characterized by broad voltage plateaus. We derive the shape of the neuronal action potential from first principles, by postulating that action potential generation is strongly constrained by the brain's need to minimize energy expenditure. For a given height of an action potential, the least energy is consumed when the underlying currents obey the bang-bang principle: the currents giving rise to the spike should be intense, yet short-lived, yielding  spikes with sharp onsets and offsets. Energy optimality predicts features in the biophysics that are not per se required for producing the characteristic neuronal action potential:  sodium currents should be extraordinarily powerful and inactivate with voltage; both potassium and sodium currents should have kinetics that have a bell-shaped voltage-dependence; and the cooperative action of multiple `gates'  should start the flow of current.
Unifying Framework for Fast Learning Rate of Non-Sparse Multiple Kernel Learning
Authors: Taiji Suzuki
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Vocal Bursts Type Prediction

In this paper, we give a new generalization error bound of Multiple Kernel Learning  (MKL) for a general class of regularizations. Our main target in this paper is  dense type regularizations including ℓp-MKL that imposes ℓp-mixed-norm regularization  instead of ℓ1-mixed-norm regularization. According to the recent numerical  experiments, the sparse regularization does not necessarily show a good  performance compared with dense type regularizations. Motivated by this fact,  this paper gives a general theoretical tool to derive fast learning rates that is applicable  to arbitrary monotone norm-type regularizations in a unifying manner. As  a by-product of our general result, we show a fast learning rate of ℓp-MKL that  is tightest among existing bounds. We also show that our general learning rate  achieves the minimax lower bound. Finally, we show that, when the complexities  of candidate reproducing kernel Hilbert spaces are inhomogeneous, dense type  regularization shows better learning rate compared with sparse ℓ1 regularization.
See the Tree Through the Lines: The Shazoo Algorithm
Authors: Fabio Vitale, Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Predicting the nodes of a given graph is a fascinating   theoretical problem with applications in several domains.   Since graph sparsification via spanning trees   retains enough information while making the task much easier,   trees are an important special case of this problem.   Although it is known how to predict the nodes of an unweighted tree   in a nearly optimal way, in the weighted case a fully satisfactory   algorithm is not available yet. We fill this hole and introduce an efficient node predictor,   Shazoo, which is nearly optimal on any weighted tree. Moreover, we show that Shazoo can   be viewed as a common nontrivial generalization of both previous approaches for   unweighted trees and weighted lines.   Experiments on real-world datasets confirm that Shazoo performs well in that   it fully exploits the structure of the input tree,   and gets very close to (and sometimes better than)   less scalable energy minimization methods.
The Fast Convergence of Boosting
Authors: Matus J. Telgarsky
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

This manuscript considers the convergence rate of boosting under a large class of losses, including the exponential and logistic losses, where the best previous rate of convergence was O(exp(1/ε²)).  First, it is established that the setting of weak learnability aids the entire class, granting a rate O(ln(1/ε)).  Next, the (disjoint) conditions under which the infimal empirical risk is attainable are characterized in terms of the sample and weak learning class, and a new proof is given for the known rate O(ln(1/ε)).  Finally, it is established that any instance can be decomposed into two smaller instances resembling the two preceding special cases, yielding a rate O(1/ε), with a matching lower bound for the logistic loss.  The principal technical hurdle throughout this work is the potential unattainability of the infimal empirical risk; the technique for overcoming this barrier may be of general interest.
Multi-armed bandits on implicit metric spaces
Authors: Aleksandrs Slivkins
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: General Classification, Multi-Armed Bandits

The multi-armed bandit (MAB) setting is a useful abstraction of many online learning tasks which focuses on the trade-off between exploration and exploitation. In this setting, an online algorithm has a fixed set of alternatives ("arms"), and in each round it selects one arm and then observes the corresponding reward. While the case of small number of arms is by now well-understood, a lot of recent work has focused on multi-armed bandits with (infinitely) many arms, where one needs to assume extra structure in order to make the problem tractable. In particular, in the Lipschitz MAB problem there is an underlying similarity metric space, known to the algorithm, such that any two arms that are close in this metric space have similar payoffs.  In this paper we consider the more realistic scenario in which the metric space is *implicit* -- it is defined by the available structure but not revealed to the algorithm directly. Specifically, we assume that an algorithm is given a tree-based classification of arms. For any given problem instance such a classification implicitly defines a similarity metric space, but the numerical similarity information is not available to the algorithm. We provide an algorithm for this setting, whose performance guarantees (almost) match the best known guarantees for the corresponding instance of the Lipschitz MAB problem.
Learning Anchor Planes for Classification
Authors: Ziming Zhang, Lubor Ladicky, Philip Torr, Amir Saffari
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Classification, General Classification

Local Coordinate Coding (LCC) [18] is a method for modeling functions of data lying on non-linear manifolds. It provides a set of anchor points which form a local coordinate system, such that each data point on the manifold can be approximated by a linear combination of its anchor points, and the linear weights become the local coordinate coding. In this paper we propose encoding data using orthogonal  anchor planes, rather than anchor points. Our method needs only a few orthogonal anchor planes for coding, and it can linearize any (\alpha,\beta,p)-Lipschitz smooth nonlinear  function with a fixed expected value of the upper-bound approximation error on any high dimensional data. In practice, the orthogonal coordinate system can be easily learned by minimizing this upper bound using singular value decomposition (SVD). We apply our method to model the coordinates locally in linear SVMs for classification tasks, and our experiment on MNIST shows that using only 50 anchor planes our method achieves 1.72% error rate, while LCC achieves 1.90% error rate using 4096 anchor points.
Infinite Latent SVM for Classification and Multi-task Learning
Authors: Jun Zhu, Ning Chen, Eric P. Xing
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Bayesian Inference, Classification, General Classification, Multi-Task Learning

Unlike existing nonparametric Bayesian models, which rely solely on specially conceived priors to incorporate domain knowledge for discovering improved latent representations, we study nonparametric Bayesian inference with regularization on the desired posterior distributions. While priors can indirectly affect posterior distributions through Bayes' theorem, imposing posterior regularization is arguably more direct and in some cases can be much easier. We particularly focus on developing infinite latent support vector machines (iLSVM) and multi-task infinite latent support vector machines (MT-iLSVM), which explore the large-margin idea in combination with a nonparametric Bayesian model for discovering predictive latent features for classification and multi-task learning, respectively. We present efficient inference methods and report empirical studies on several benchmark datasets. Our results appear to demonstrate the merits inherited from both large-margin learning and Bayesian nonparametrics.
Facial Expression Transfer with Input-Output Temporal Restricted Boltzmann Machines
Authors: Matthew D. Zeiler, Graham W. Taylor, Leonid Sigal, Iain Matthews, Rob Fergus
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We present a type of Temporal Restricted Boltzmann Machine that defines a probability distribution over an output sequence conditional on an input sequence. It shares the desirable properties of RBMs: efficient exact inference, an exponentially more expressive latent state than HMMs, and the ability to model nonlinear structure and dynamics. We apply our model to a challenging real-world graphics problem: facial expression transfer. Our results demonstrate improved performance over several baselines modeling high-dimensional 2D and 3D data.
Universal low-rank matrix recovery from Pauli measurements
Authors: Yi-Kai Liu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: compressed sensing, Gaussian Processes, Quantum State Tomography

We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd polylog d) Pauli measurements.  This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing:  recovering a sparse vector from a few of its Fourier coefficients.      We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP).  This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error.  A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm.  Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
Better Mini-Batch Algorithms via Accelerated Gradient Methods
Authors: Andrew Cotter, Ohad Shamir, Nati Srebro, Karthik Sridharan
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Mini-batch algorithms have recently received significant attention as a way to speed-up stochastic convex optimization problems. In this paper, we study how such algorithms can be improved using accelerated gradient methods. We provide a novel analysis, which shows how standard gradient methods may sometimes be insufficient to obtain a significant speed-up. We propose a novel accelerated gradient algorithm, which deals with this deficiency, and enjoys a uniformly superior guarantee. We conclude our paper with experiments  on real-world datasets, which validates our algorithm and  substantiates our theoretical insights.
Adaptive Hedge
Authors: Tim V. Erven, Wouter M. Koolen, Steven D. Rooij, Peter Grünwald
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Most methods for decision-theoretic online learning are based on the Hedge algorithm, which takes a parameter called the learning rate. In most previous analyses the learning rate was carefully tuned to obtain optimal worst-case performance, leading to suboptimal performance on easy instances, for example when there exists an action that is significantly better than all others. We propose a new way of setting the learning rate, which adapts to the difficulty of the learning problem: in the worst case our procedure still guarantees optimal performance, but on easy instances it achieves much smaller regret. In particular, our adaptive method achieves constant regret in a probabilistic setting, when there exists an action that on average obtains strictly smaller loss than all other actions. We also provide a simulation study comparing our approach to existing methods.
Agnostic Selective Classification
Authors: Yair Wiener, Ran El-Yaniv
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Classification, General Classification

For a learning problem whose associated excess loss class is $(\beta,B)$-Bernstein, we show that it is theoretically possible to track the same classification performance  of the best (unknown) hypothesis in our class, provided that we are free to abstain from prediction in some region of our choice. The (probabilistic) volume of this rejected region of the domain is shown to be diminishing at rate $O(B\theta (\sqrt{1/m}))^\beta)$, where $\theta$ is Hanneke's disagreement coefficient. The strategy achieving this performance has computational barriers because it requires empirical error minimization in an agnostic setting. Nevertheless, we heuristically approximate this strategy and develop a novel selective classification algorithm  using constrained SVMs. We show empirically that the resulting algorithm consistently outperforms  the traditional rejection mechanism based on distance from decision boundary.
PAC-Bayesian Analysis of Contextual Bandits
Authors: Yevgeny Seldin, Peter Auer, John S. Shawe-Taylor, Ronald Ortner, François Laviolette
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Multi-Armed Bandits

We derive an instantaneous (per-round) data-dependent regret bound for stochastic multiarmed bandits with side information (also known as contextual bandits). The scaling of our regret bound with the number of states (contexts) $N$ goes as $\sqrt{N I_{\rho_t}(S;A)}$, where $I_{\rho_t}(S;A)$ is the mutual information between states and actions (the side information) used by the algorithm at round $t$. If the algorithm uses all the side information, the regret bound scales as $\sqrt{N \ln K}$, where $K$ is the number of actions (arms). However, if the side information $I_{\rho_t}(S;A)$ is not fully used, the regret bound is significantly tighter. In the extreme case, when $I_{\rho_t}(S;A) = 0$, the dependence on the number of states reduces from linear to logarithmic. Our analysis allows to provide the algorithm large amount of side information, let the algorithm to decide which side information is relevant for the task, and penalize the algorithm only for the side information that it is using de facto. We also present an algorithm for multiarmed bandits with side information with computational complexity that is a linear in the number of actions.
Bayesian Spike-Triggered Covariance Analysis
Authors: Il Memming Park, Jonathan W. Pillow
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Neurons typically respond to a restricted number of stimulus features within the high-dimensional space of natural stimuli. Here we describe an explicit model-based interpretation of traditional estimators for a neuron's multi-dimensional feature space, which allows for several important generalizations and extensions. First, we show that traditional estimators based on the spike-triggered average (STA) and spike-triggered covariance (STC) can be formalized in terms of the "expected log-likelihood" of a Linear-Nonlinear-Poisson (LNP) model with Gaussian stimuli. This model-based formulation allows us to define maximum-likelihood and Bayesian estimators that are statistically consistent and efficient in a wider variety of settings, such as with naturalistic (non-Gaussian) stimuli. It also allows us to employ Bayesian methods for regularization, smoothing, sparsification, and model comparison, and provides Bayesian confidence intervals on model parameters. We describe an empirical Bayes method for selecting the number of features, and extend the model to accommodate an arbitrary elliptical nonlinear response function, which results in a more powerful and more flexible model for feature space inference. We validate these methods using neural data recorded extracellularly from macaque primary visual cortex.
Non-conjugate Variational Message Passing for Multinomial and Binary Regression
Authors: David A. Knowles, Tom Minka
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Variational Message Passing (VMP) is an algorithmic implementation of the Variational Bayes (VB) method which applies only in the special case of conjugate exponential family models. We propose an extension to VMP, which we refer to as Non-conjugate Variational Message Passing (NCVMP) which aims to alleviate this restriction while maintaining modularity, allowing choice in how expectations are calculated, and integrating into an existing message-passing framework: Infer.NET. We demonstrate NCVMP on logistic binary and multinomial regression. In the multinomial case we introduce a novel variational bound for the softmax factor which is tighter than other commonly used bounds whilst maintaining computational tractability.