mtybilly/Instruct2DS huggingface dataset:
Practical Variational Inference for Neural Networks
Authors: Alex Graves
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Variational methods have been previously explored as a tractable approximation to Bayesian inference for neural networks. However the approaches proposed so far have only been applicable to a few simple network architectures. This paper introduces an easy-to-implement stochastic variational method (or equivalently, minimum description length loss function) that can be applied to most neural networks. Along the way it revisits several common regularisers from a variational perspective. It also provides a simple pruning heuristic that can both drastically reduce the number of network weights and lead to improved generalisation. Experimental results are provided for a hierarchical multidimensional recurrent neural network applied to the TIMIT speech corpus.
Penalty Decomposition Methods for Rank Minimization
Authors: Zhaosong Lu Yong Zhang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper we consider general rank minimization problems with rank appearing in either objective function or constraint. We first show that a class of matrix optimization problems can be solved as lower dimensional vector optimization problems. As a consequence, we establish that a class of rank minimization problems have closed form solutions. Using this result, we then propose penalty decomposition methods for general rank minimization problems. The convergence results of the PD methods have been shown in the longer version of the paper. Finally, we test the performance of our methods by applying them to matrix completion and nearest low-rank correlation matrix problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed.
Accelerated Adaptive Markov Chain for Partition Function Computation
Authors: Carla P. Gomes, Ashish Sabharwal, Bart Selman Stefano Ermon
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose a novel Adaptive Markov Chain Monte Carlo algorithm to  compute the partition function. In particular, we show how to  accelerate a flat histogram sampling technique by significantly  reducing the number of ``null moves'' in the chain, while maintaining  asymptotic convergence properties. Our experiments show that our  method converges quickly to highly accurate solutions on a range of  benchmark instances, outperforming other state-of-the-art methods such  as IJGP, TRW, and Gibbs sampling both in run-time and accuracy. We  also show how obtaining a so-called density of states distribution  allows for efficient weight learning in Markov Logic theories.
On Strategy Stitching in Large Extensive Form Multiplayer Games
Authors: Duane Szafron Richard G. Gibson
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Computing a good strategy in a large extensive form game often demands an extraordinary amount of computer memory, necessitating the use of abstraction to reduce the game size.  Typically, strategies from abstract games perform better in the real game as the granularity of abstraction is increased.  This paper investigates two techniques for stitching a base strategy in a coarse abstraction of the full game tree, to expert strategies in fine abstractions of smaller subtrees.  We provide a general framework for creating static experts, an approach that generalizes some previous strategy stitching efforts.  In addition, we show that static experts can create strong agents for both 2-player and 3-player Leduc and Limit Texas Hold'em poker, and that a specific class of static experts can be preferred among a number of alternatives.  Furthermore, we describe a poker agent that used static experts and won the 3-player events of the 2010 Annual Computer Poker Competition.
Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity
Authors: Nir Ailon
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Given a set $V$ of  $n$ elements we wish to linearly order them using pairwise preference labels  which may be non-transitive (due to irrationality or arbitrary noise).  The goal is to linearly order the elements while disagreeing with  as few pairwise preference labels as possible.  Our performance is measured by two parameters:  The number of disagreements (loss) and the query complexity (number of pairwise preference labels).  Our algorithm adaptively queries  at most $O(n\poly(\log n,\eps^{-1}))$ preference labels for a regret of  $\eps$ times the optimal loss.  This is strictly better, and often significantly better than what  non-adaptive sampling could achieve.  Our main result helps settle an open problem posed by   learning-to-rank (from pairwise information) theoreticians and practitioners:  What is a provably correct way to sample preference labels?
Nonnegative dictionary learning in the exponential noise model for adaptive music signal representation
Authors: Cédric Févotte Onur Dikmen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper we describe a maximum likelihood likelihood approach for dictionary learning in the multiplicative exponential noise model. This model is prevalent in audio signal processing where it underlies a generative composite model of the power spectrogram. Maximum joint likelihood estimation of the dictionary and expansion coefficients leads to a nonnegative matrix factorization problem where the Itakura-Saito divergence is used. The optimality of this approach is in question because the number of parameters (which include the expansion coefficients) grows with the number of observations. In this paper we describe a variational procedure for optimization of the marginal likelihood, i.e., the likelihood of the dictionary where the activation coefficients have been integrated out (given a specific prior). We compare the output of both maximum joint likelihood estimation (i.e., standard Itakura-Saito NMF) and maximum marginal likelihood estimation (MMLE) on real and synthetical datasets. The MMLE approach is shown to embed automatic model order selection, akin to automatic relevance determination.
From Stochastic Nonlinear Integrate-and-Fire to Generalized Linear Models
Authors: Richard Naud, Wulfram Gerstner Skander Mensi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Variability in single neuron models is typically implemented either by a stochastic Leaky-Integrate-and-Fire model or by a model of the Generalized Linear Model (GLM) family. We use analytical and numerical methods to relate state-of-the-art models from both schools of thought. First we find the analytical expressions relating the subthreshold voltage from the Adaptive Exponential Integrate-and-Fire model (AdEx) to the Spike-Response Model with escape noise (SRM as an example of a GLM). Then we calculate numerically the link-function that provides the firing probability given a deterministic membrane potential. We find a mathematical expression for this link-function and test the ability of the GLM to predict the firing probability of a neuron receiving complex stimulation. Comparing the prediction performance of various link-functions, we find that a GLM with an exponential link-function provides an excellent approximation to the Adaptive Exponential Integrate-and-Fire with colored-noise input. These results help to understand the relationship between the different approaches to stochastic neuron models.
Generalised Coupled Tensor Factorisation
Authors: Ali T. Cemgil, Umut Simsekli Kenan Y. Yılmaz
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We derive algorithms for generalised tensor factorisation (GTF) by building upon the well-established theory of Generalised Linear Models. Our algorithms are general in the sense that we can compute arbitrary factorisations in a message passing framework, derived for a broad class of exponential family distributions including special cases such as Tweedie's distributions corresponding to $\beta$-divergences. By bounding the step size of the Fisher Scoring iteration of the GLM, we obtain general updates for real data and multiplicative updates for non-negative data. The GTF framework is, then extended easily to address the problems when multiple observed tensors are factorised simultaneously. We illustrate our coupled factorisation approach on synthetic data as well as on a musical audio restoration problem.
Prismatic Algorithm for Discrete D.C. Programming Problem
Authors: Takashi Washio Yoshinobu Kawahara
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), i.e., the discrete version of the D.C. programming problem. The developed algorithm is a branch-and-bound-based algorithm which responds to the structure of this problem through the relationship between submodularity and convexity. The D.S. programming problem covers a broad range of applications in machine learning because this generalizes the optimization of a wide class of set functions. We empirically investigate the performance of our algorithm, and illustrate the difference between exact and approximate solutions respectively obtained by the proposed and existing algorithms in feature selection and discriminative structure learning.
On the Completeness of First-Order Knowledge Compilation for Lifted Probabilistic Inference
Authors: Guy Broeck
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Probabilistic logics are receiving a lot of attention today because of their expressive power for knowledge representation and learning. However, this expressivity is detrimental to the tractability of inference, when done at the propositional level.  To solve this problem, various lifted inference algorithms have been proposed that reason at the first-order level, about groups of objects as a whole. Despite the existence of various lifted inference approaches, there are currently no completeness results about these algorithms.  The key contribution of this paper is that we introduce a formal definition of lifted inference that allows us to reason about the completeness of lifted inference algorithms relative to a particular class of probabilistic models.  We then show how to obtain a completeness result using a first-order knowledge compilation approach for theories of formulae containing up to two logical variables.
Analysis and Improvement of Policy Gradient Estimation
Authors: Hirotaka Hachiya, Gang Niu, Masashi Sugiyama Tingting Zhao
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Policy gradient is a useful model-free reinforcement learning approach,  but it tends to suffer from instability of gradient estimates.  In this paper, we analyze and improve the stability of policy gradient methods. We first prove that the variance of gradient estimates in the PGPE(policy gradients with parameter-based exploration) method is smaller than that of the classical REINFORCE method under a mild assumption.  We then derive the optimal baseline for PGPE, which contributes to further reducing the variance.  We also theoretically show that PGPE with the optimal baseline is more preferable than REINFORCE with the optimal baseline in terms of the variance of gradient estimates.  Finally, we demonstrate the usefulness of the improved PGPE method through experiments.
On Tracking The Partition Function
Authors: Yoshua Bengio, Aaron C. Courville Guillaume Desjardins
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Markov Random Fields (MRFs) have proven very powerful both as density estimators and feature extractors for classification. However, their use is often limited by an inability to estimate the partition function $Z$. In this paper, we exploit the gradient descent training procedure of restricted Boltzmann machines (a type of MRF) to {\bf track} the log partition function during learning. Our method relies on two distinct sources of information: (1) estimating the change $\Delta Z$ incurred by each gradient update, (2) estimating the difference in $Z$ over a small set of tempered distributions using bridge sampling. The two sources of information are then combined using an inference procedure similar to Kalman filtering.  Learning MRFs through Tempered Stochastic Maximum Likelihood, we can estimate $Z$ using no more temperatures than are required for learning. Comparing to both exact values and estimates using annealed importance sampling (AIS), we show on several datasets that our method is able to accurately track the log partition function. In contrast to AIS, our method provides this estimate at each time-step, at a computational cost similar to that required for training alone.
Portmanteau Vocabularies for Multi-Cue Image Representation
Authors: Joost Weijer, Andrew D. Bagdanov, Maria Vanrell Fahad S. Khan
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We describe a novel technique for feature combination in the bag-of-words model of image classification. Our approach builds discriminative compound words from primitive cues learned independently from training images. Our main observation is that modeling joint-cue distributions independently is more statistically robust for typical classification problems than attempting to empirically estimate the dependent, joint-cue distribution directly. We use Information theoretic vocabulary compression to find discriminative combinations of cues and the resulting vocabulary of portmanteau words is compact, has the cue binding property, and supports individual weighting of cues in the final image representation. State-of-the-art results on both the Oxford Flower-102 and Caltech-UCSD Bird-200 datasets demonstrate the effectiveness of our technique compared to other, significantly more complex approaches to multi-cue image representation
Algorithms for Hyper-Parameter Optimization
Authors: Rémi Bardenet, Yoshua Bengio, Balázs Kégl James S. Bergstra
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Several recent advances to the state of the art in image classification benchmarks have come from better configurations of existing techniques rather than novel approaches to feature learning. Traditionally, hyper-parameter optimization has been the job of humans because they can be very efficient in regimes where only a few trials are possible. Presently, computer clusters and GPU processors make it possible to run more trials and we show that algorithmic approaches can find better results. We present hyper-parameter optimization results on tasks of training neural networks and deep belief networks (DBNs). We optimize hyper-parameters using random search and two new greedy sequential methods based on the expected improvement criterion. Random search has been shown to be sufficiently efficient for learning neural networks for several datasets, but we show it is unreliable for training DBNs. The sequential algorithms are applied to the most difficult DBN learning problems from [Larochelle et al., 2007] and find significantly better results than the best previously reported. This work contributes novel techniques for making response surface models P (y|x) in which many elements of hyper-parameter assignment (x) are known to be irrelevant given particular values of other elements.
Finite Time Analysis of Stratified Sampling for Monte Carlo
Authors: Rémi Munos Alexandra Carpentier
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of stratified sampling for Monte-Carlo integration. We model this problem in a multi-armed bandit setting, where the arms represent the strata, and the goal is to estimate a weighted average of the mean values of the arms. We propose a strategy that samples the arms according to an upper bound on their standard deviations and compare its estimation quality to an ideal allocation that would know the standard deviations of the arms. We provide two regret analyses: a distribution-dependent bound O(n^{-3/2}) that depends on a measure of the disparity of the arms, and a distribution-free bound O(n^{-4/3}) that does not. To the best of our knowledge, such a finite-time analysis is new for this problem.
Online Submodular Set Cover, Ranking, and Repeated Active Learning
Authors: Jeff A. Bilmes Andrew Guillory
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose an online prediction version of submodular set cover with connections to ranking and repeated active learning.  In each round, the learning algorithm chooses a sequence of items.  The algorithm then receives a monotone submodular function and suffers loss equal to the cover time of the function: the number of items needed, when items are selected in order of the chosen sequence, to achieve a coverage constraint.  We develop an online learning algorithm whose loss converges to approximately that of the best sequence in hindsight.  Our proposed algorithm is readily extended to a setting where multiple functions are revealed at each round and to bandit and contextual bandit settings.
The Fast Convergence of Boosting
Authors: Matus J. Telgarsky
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: 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.
See the Tree Through the Lines: The Shazoo Algorithm
Authors: Nicolò Cesa-bianchi, Claudio Gentile, Giovanni Zappella Fabio Vitale
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: 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.
t-divergence Based Approximate Inference
Authors: Yuan Qi, S.v.n. Vishwanathan Nan Ding
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Approximate inference is an important technique for dealing with large, intractable graphical models based on the exponential family of distributions. We extend the idea of approximate inference to the t-exponential family by defining a new t-divergence. This divergence measure is obtained via convex duality between the log-partition function of the t-exponential family and a new t-entropy. We illustrate our approach on the Bayes Point Machine with a Student's t-prior.
Boosting with Maximum Adaptive Sampling
Authors: Francois Fleuret Charles Dubout
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Classical Boosting algorithms, such as AdaBoost, build a strong classifier without concern about the computational cost.  Some applications, in particular in computer vision, may involve up to millions of training examples and features.  In such contexts, the training time may become prohibitive.  Several methods exist to accelerate training, typically either by sampling the features, or the examples, used to train the weak learners.  Even if those methods can precisely quantify the speed improvement they deliver, they offer no guarantee of being more efficient than any other, given the same amount of time.    This paper aims at shading some light on this problem, i.e. given a fixed amount of time, for a particular problem, which strategy is optimal in order to reduce the training loss the most.  We apply this analysis to the design of new algorithms which estimate on the fly at every iteration the optimal trade-off between the number of samples and the number of features to look at in order to maximize the expected loss reduction.  Experiments in object recognition with two standard computer vision data-sets show that the adaptive methods we propose outperform basic sampling and state-of-the-art bandit methods.
Inverting Grice's Maxims to Learn Rules from Natural Language Extractions
Authors: Janardhan R. Doppa, Walker Orr, Prasad Tadepalli, Thomas G. Dietterich, Xiaoli Z. Fern Mohammad S. Sorower
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of learning rules from natural language text  sources. These sources, such as news articles and web texts, are  created by a writer to communicate information to a reader, where the  writer and reader share substantial domain knowledge.  Consequently,  the texts tend to be concise and mention the minimum information  necessary for the reader to draw the correct conclusions.  We study  the problem of learning domain knowledge from such concise texts,  which is an instance of the general problem of learning in the  presence of missing data.  However, unlike standard approaches to  missing data, in this setting we know that facts are more likely to be  missing from the text in cases where the reader can infer them from  the facts that are mentioned combined with the domain knowledge.  Hence, we can explicitly model this "missingness" process and invert  it via probabilistic inference to learn the underlying domain  knowledge.  This paper introduces a mention model that models  the probability of facts being mentioned in the text based on what  other facts have already been mentioned and domain knowledge in the  form of Horn clause rules.  Learning must simultaneously search the  space of rules and learn the parameters of the mention model.  We  accomplish this via an application of Expectation Maximization within  a Markov Logic framework.  An experimental evaluation on synthetic and  natural text data shows that the method can learn accurate rules and  apply them to new texts to make correct inferences.  Experiments also  show that the method out-performs the standard EM approach that  assumes mentions are missing at random.
Efficient anomaly detection using bipartite k-NN graphs
Authors: Alfred O. Hero Kumar Sricharan
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Learning minimum volume sets of an underlying nominal distribution is a very effective approach to anomaly detection. Several approaches to learning minimum volume sets have been proposed in the literature, including the K-point nearest neighbor graph (K-kNNG) algorithm based on the geometric entropy minimization (GEM) principle [4]. The K-kNNG detector, while possessing several desirable characteristics, suffers from high computation complexity, and in [4] a simpler heuristic approximation, the leave-one-out kNNG (L1O-kNNG) was proposed. In this paper, we propose a novel bipartite k-nearest neighbor graph (BP-kNNG) anomaly detection scheme for estimating minimum volume sets. Our bipartite estimator retains all the desirable theoretical properties of the K-kNNG, while being computationally simpler than the K-kNNG and the surrogate L1O-kNNG detectors. We show that BP-kNNG is asymptotically consistent in recovering the p-value of each test point. Experimental results are given that illustrate the superior performance of BP-kNNG as compared to the L1O-kNNG and other state of the art anomaly detection schemes.
Shallow vs. Deep Sum-Product Networks
Authors: Yoshua Bengio Olivier Delalleau
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We investigate the representational power of sum-product networks  (computation networks analogous to neural networks,  but whose individual units compute either products  or weighted sums), through a theoretical analysis that compares  deep (multiple hidden layers) vs. shallow (one hidden layer) architectures.  We prove there exist families of functions that can be represented  much more efficiently with a deep network than with a shallow one, i.e.  with substantially fewer hidden units.  Such results were not available until now, and  contribute to motivate recent research involving learning of deep  sum-product networks, and more generally motivate research in Deep  Learning.
Expressive Power and Approximation Errors of Restricted Boltzmann Machines
Authors: Johannes Rauh, Nihat Ay Guido F. Montufar
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present explicit classes of probability distributions that can be learned by Restricted Boltzmann Machines (RBMs) depending on the number of units that they contain, and which are representative for the expressive power of the model. We use this to show that the maximal Kullback-Leibler divergence to the RBM model with n visible and m hidden units is bounded from above by (n-1)-log(m+1). In this way we can specify the number of hidden units that guarantees a sufficiently rich model containing different classes of distributions and respecting a given error tolerance.
Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators
Authors: Marina Meila Dominique C. Perrault-joncas
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper considers the problem of embedding directed graphs in Euclidean space while retaining directional information. We model the observed graph as a sample from a manifold endowed with a vector field, and we design an algo- rithm that separates and recovers the features of this process: the geometry of the manifold, the data density and the vector field. The algorithm is motivated by our analysis of Laplacian-type operators and their continuous limit as generators of diffusions on a manifold. We illustrate the recovery algorithm on both artificially constructed and real data.
Information Rates and Optimal Decoding in Large Neural Populations
Authors: Liam Paninski Kamiar R. Rad
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many fundamental questions in theoretical neuroscience involve optimal  decoding and the computation of Shannon information rates in  populations of spiking neurons.  In this paper, we apply methods from  the asymptotic theory of statistical inference to obtain a clearer  analytical understanding of these quantities.  We find that for large  neural populations carrying a finite total amount of information, the  full spiking population response is asymptotically as informative as a  single observation from a Gaussian process whose mean and covariance  can be characterized explicitly in terms of network and single neuron  properties.  The Gaussian form of this asymptotic sufficient  statistic allows us in certain cases to perform optimal Bayesian  decoding by simple linear transformations, and to obtain closed-form  expressions of the Shannon information carried by the network.  One  technical advantage of the theory is that it may be applied easily  even to non-Poisson point process network models; for example, we find  that under some conditions, neural populations with strong  history-dependent (non-Poisson) effects carry exactly the same  information as do simpler equivalent populations of non-interacting  Poisson neurons with matched firing rates.  We argue that our findings  help to clarify some results from the recent literature on neural  decoding and neuroprosthetic design.
Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
Authors: Nicolas L. Roux, Francis R. Bach Mark Schmidt
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of optimizing the sum of a smooth convex function and a non-smooth convex function using proximal-gradient methods, where an error is present in the calculation of the gradient of the smooth term or in the proximity operator with respect to the second term. We show that the basic proximal-gradient method, the basic proximal-gradient method with a strong convexity assumption, and the accelerated proximal-gradient method achieve the same convergence rates as in the error-free case, provided the errors decrease at an appropriate rate.  Our experimental results on a structured sparsity problem indicate that sequences of errors with these appealing theoretical properties can lead to practical performance improvements.
Co-Training for Domain Adaptation
Authors: Kilian Q. Weinberger, John Blitzer Minmin Chen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Domain adaptation algorithms seek to generalize a model trained in a source domain to a new target domain.  In many  practical cases, the source and target distributions can differ substantially, and in some cases crucial target features may not have support in the source domain.  In this paper we introduce an algorithm that bridges the gap between source and target domains by slowly adding both the target features and instances in which the current  algorithm is the most confident.  Our algorithm is a variant of co-training, and we name it CODA (Co-training for domain adaptation).  Unlike the original co-training work, we do not assume a particular feature split.  Instead, for each iteration of co-training, we add target features and formulate a single optimization problem which simultaneously learns a target predictor, a split of the feature space into views, and a shared subset of source  and target features to include in the predictor.  CODA significantly out-performs the state-of-the-art on the 12-domain benchmark data set of Blitzer et al.. Indeed, over a wide range (65 of 84 comparisons) of target supervision, ranging from no labeled target data to a relatively large number of target labels, CODA achieves the best performance.
Learning to Agglomerate Superpixel Hierarchies
Authors: Srinivas C. Turaga, K Briggman, Moritz N. Helmstaedter, Winfried Denk, H. S. Seung Viren Jain
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: An agglomerative clustering algorithm merges the most similar pair of clusters at every iteration. The function that evaluates similarity is traditionally hand- designed, but there has been recent interest in supervised or semisupervised settings in which ground-truth clustered data is available for training. Here we show how to train a similarity function by regarding it as the action-value function of a reinforcement learning problem. We apply this general method to segment images by clustering superpixels, an application that we call Learning to Agglomerate Superpixel Hierarchies (LASH). When applied to a challenging dataset of brain images from serial electron microscopy, LASH dramatically improved segmentation accuracy when clustering supervoxels generated by state of the boundary detection algorithms. The naive strategy of directly training only supervoxel similarities and applying single linkage clustering produced less improvement.
Structured Learning for Cell Tracking
Authors: Fred A. Hamprecht Xinghua Lou
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study the problem of learning to track a large quantity of homogeneous objects such as cell tracking in cell culture study and developmental biology. Reliable cell tracking in time-lapse microscopic image sequences is important for modern biomedical research. Existing cell tracking methods are usually kept simple and use only a small number of features to allow for manual parameter tweaking or grid search. We propose a structured learning approach that allows to learn optimum parameters automatically from a training set. This allows for the use of a richer set of features which in turn affords improved tracking compared to recently reported methods on two public benchmark sequences.
Hierarchical Topic Modeling for Analysis of Time-Evolving Personal Choices
Authors: Lawrence Carin, David B. Dunson Xianxing Zhang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The nested Chinese restaurant process is extended to design a nonparametric  topic-model tree for representation of human choices. Each tree branch corresponds  to a type of person, and each node (topic) has a corresponding probability  vector over items that may be selected. The observed data are assumed to have  associated temporal covariates (corresponding to the time at which choices are  made), and we wish to impose that with increasing time it is more probable that  topics deeper in the tree are utilized. This structure is imposed by developing  a new “change point" stick-breaking model that is coupled with a Poisson and  product-of-gammas construction. To share topics across the tree nodes, topic distributions  are drawn from a Dirichlet process. As a demonstration of this concept,  we analyze real data on course selections of undergraduate students at Duke University,  with the goal of uncovering and concisely representing structure in the  curriculum and in the characteristics of the student body.
Selecting the State-Representation in Reinforcement Learning
Authors: Daniil Ryabko, Rémi Munos Odalric-ambrym Maillard
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The problem of selecting the right state-representation in a reinforcement learning problem is considered.   Several models (functions mapping past observations to a finite set) of the observations are given, and it is known   that for at least one of these models the resulting state dynamics are indeed Markovian. Without  knowing neither which of the models is the correct one, nor what are the probabilistic characteristics of the resulting   MDP, it is required to obtain as much reward as the optimal policy for the correct model (or for the best of the correct models, if there are several). We propose an algorithm that achieves that,   with a regret of order T^{2/3} where T is the horizon time.
A Reinforcement Learning Theory for Homeostatic Regulation
Authors: Boris S. Gutkin Mehdi Keramati
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Reinforcement learning models address animal's behavioral adaptation to its changing "external" environment, and are based on the assumption that Pavlovian, habitual and goal-directed responses seek to maximize reward acquisition. Negative-feedback models of homeostatic regulation, on the other hand, are concerned with behavioral adaptation in response to the "internal" state of the animal, and assume that animals' behavioral objective is to minimize deviations of some key physiological variables from their hypothetical setpoints. Building upon the drive-reduction theory of reward, we propose a new analytical framework that integrates learning and regulatory systems, such that the two seemingly unrelated objectives of reward maximization and physiological-stability prove to be identical. The proposed theory shows behavioral adaptation to both internal and external states in a disciplined way. We further show that the proposed framework allows for a unified explanation of some behavioral phenomenon like motivational sensitivity of different associative learning mechanism, anticipatory responses, interaction among competing motivational systems, and risk aversion.
Semantic Labeling of 3D Point Clouds for Indoor Scenes
Authors: Abhishek Anand, Thorsten Joachims, Ashutosh Saxena Hema S. Koppula
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Inexpensive RGB-D cameras that give an RGB image together with depth data have become widely available. In this paper, we use this data to build 3D point clouds of full indoor scenes such as an office and address the task of semantic labeling of these 3D point clouds. We propose a graphical model that captures various features and contextual relations, including the local visual appearance and shape cues, object co-occurence relationships and geometric relationships. With a large number of object classes and relations, the model’s parsimony becomes important and we address that by using multiple types of edge potentials. The model admits efficient approximate inference, and we train it using a maximum-margin learning approach. In our experiments over a total of 52 3D scenes of homes and offices (composed from about 550 views, having 2495 segments labeled with 27 object classes), we get a performance of 84.06% in labeling 17 object classes for offices, and 73.38% in labeling 17 object classes for home scenes. Finally, we applied these algorithms successfully on a mobile robot for the task of finding objects in large cluttered rooms.
Higher-Order Correlation Clustering for Image Segmentation
Authors: Sebastian Nowozin, Pushmeet Kohli, Chang D. Yoo Sungwoong Kim
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: 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.
Learning large-margin halfspaces with more malicious noise
Authors: Rocco Servedio Phil Long
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We describe a simple algorithm that runs in time  poly(n,1/gamma,1/eps) and learns an unknown n-dimensional  gamma-margin halfspace to accuracy 1-eps in the presence of  malicious noise, when the noise rate is allowed to be as high as  Theta(eps gamma sqrt(log(1/gamma))). Previous efficient  algorithms could only learn to accuracy eps in the presence of  malicious noise of rate at most Theta(eps gamma).    Our algorithm does not work by optimizing a convex loss function.  We  show that no algorithm for learning gamma-margin halfspaces that  minimizes a convex proxy for misclassification error can tolerate  malicious noise at a rate greater than Theta(eps gamma); this may  partially explain why previous algorithms could not achieve the higher  noise tolerance of our new algorithm.
The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning
Authors: Gilles Blanchard Marius Kloft
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We derive an upper bound on the local Rademacher complexity of Lp-norm multiple kernel learning, which yields a tighter excess risk bound than global approaches. Previous local approaches analyzed the case p=1 only while our analysis covers all cases $1\leq p\leq\infty$, assuming the different feature mappings corresponding to the different kernels to be uncorrelated. We also show a lower bound that shows that the bound is tight, and derive consequences regarding excess loss, namely fast convergence rates of the order $O(n^{-\frac{\alpha}{1+\alpha}})$, where $\alpha$ is the minimum eigenvalue decay rate of the individual kernels.
A Global Structural EM Algorithm for a Model of Cancer Progression
Authors: Erik Sj̦lund, Mattias H̦glund, Jens Lagergren Ali Tofigh
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Cancer has complex patterns of progression that include converging as  well as diverging progressional pathways. Vogelstein's path model of  colon cancer was a pioneering contribution to cancer research.  Since  then, several attempts have been made at obtaining mathematical models  of cancer progression, devising learning algorithms, and applying  these to cross-sectional data. Beerenwinkel {\em et al.}  provided,  what they coined, EM-like algorithms for Oncogenetic Trees (OTs) and  mixtures of such. Given the small size of current and future data  sets, it is important to minimize the number of parameters of a  model. For this reason, we too focus on tree-based models and  introduce Hidden-variable Oncogenetic Trees (HOTs). In contrast to  OTs, HOTs allow for errors in the data and thereby provide more  realistic modeling. We also design global structural EM algorithms for  learning HOTs and mixtures of HOTs (HOT-mixtures). The algorithms are  global in the sense that, during the M-step, they find a structure  that yields a global maximum of the expected complete log-likelihood  rather than merely one that improves it. The algorithm for single HOTs  performs very well on reasonable-sized data sets, while that for  HOT-mixtures requires data sets of sizes obtainable only with  tomorrow's more cost-efficient technologies.
Infinite Latent SVM for Classification and Multi-task Learning
Authors: Ning Chen, Eric P. Xing Jun Zhu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: 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.
On U-processes and clustering performance
Authors: Stéphan J. Clémençcon
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many clustering techniques aim at optimizing empirical criteria that are of the  form of a U-statistic of degree two. Given a measure of dissimilarity between  pairs of observations, the goal is to minimize the within cluster point scatter over  a class of partitions of the feature space. It is the purpose of this paper to define  a general statistical framework, relying on the theory of U-processes, for studying  the performance of such clustering methods. In this setup, under adequate  assumptions on the complexity of the subsets forming the partition candidates, the  excess of clustering risk is proved to be of the order O(1/\sqrt{n}). Based on recent  results related to the tail behavior of degenerate U-processes, it is also shown how  to establish tighter rate bounds. Model selection issues, related to the number of  clusters forming the data partition in particular, are also considered.
Robust Lasso with missing and grossly corrupted observations
Authors: Trac D. Tran, Nam Nguyen Nasser M. Nasrabadi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper studies the problem of accurately recovering a sparse vector $\beta^{\star}$ from highly corrupted linear measurements $y = X \beta^{\star} + e^{\star} + w$ where $e^{\star}$ is a sparse error vector whose nonzero entries may be unbounded and $w$ is a bounded noise. We propose a so-called extended Lasso optimization which takes into consideration sparse prior information of both $\beta^{\star}$ and $e^{\star}$. Our first result shows that the extended Lasso can faithfully recover both the regression and the corruption vectors. Our analysis is relied on a notion of extended restricted eigenvalue for the design matrix $X$. Our second set of results applies to a general class of Gaussian design matrix $X$ with i.i.d rows $\oper N(0, \Sigma)$, for which we provide a surprising phenomenon: the extended Lasso can recover exact signed supports of both $\beta^{\star}$ and $e^{\star}$ from only $\Omega(k \log p \log n)$ observations, even the fraction of corruption is arbitrarily close to one. Our analysis also shows that this amount of observations required to achieve exact signed support is optimal.