mtybilly/Instruct2DS huggingface dataset:
Online Submodular Set Cover, Ranking, and Repeated Active Learning
Authors: Andrew Guillory, Jeff A. Bilmes
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.
See the Tree Through the Lines: The Shazoo Algorithm
Authors: Fabio Vitale, Nicolò Cesa-bianchi, Claudio Gentile, Giovanni Zappella
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: Nan Ding, Yuan Qi, S.v.n. Vishwanathan
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: Charles Dubout, Francois Fleuret
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: Mohammad S. Sorower, Janardhan R. Doppa, Walker Orr, Prasad Tadepalli, Thomas G. Dietterich, Xiaoli Z. Fern
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: Kumar Sricharan, Alfred O. Hero
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: Olivier Delalleau, Yoshua Bengio
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: Guido F. Montufar, Johannes Rauh, Nihat Ay
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: Dominique C. Perrault-joncas, Marina Meila
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: Kamiar R. Rad, Liam Paninski
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: Mark Schmidt, Nicolas L. Roux, Francis R. Bach
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: Minmin Chen, Kilian Q. Weinberger, John Blitzer
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: Viren Jain, Srinivas C. Turaga, K Briggman, Moritz N. Helmstaedter, Winfried Denk, H. S. Seung
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: Xinghua Lou, Fred A. Hamprecht
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: Xianxing Zhang, Lawrence Carin, David B. Dunson
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: Odalric-ambrym Maillard, Daniil Ryabko, Rémi Munos
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: Mehdi Keramati, Boris S. Gutkin
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: Hema S. Koppula, Abhishek Anand, Thorsten Joachims, Ashutosh Saxena
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: Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, Chang D. Yoo
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: Phil Long, Rocco Servedio
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: Marius Kloft, Gilles Blanchard
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: Ali Tofigh, Erik Sj̦lund, Mattias H̦glund, Jens Lagergren
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: Jun Zhu, Ning Chen, Eric P. Xing
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.
Robust Lasso with missing and grossly corrupted observations
Authors: Nasser M. Nasrabadi, Trac D. Tran, Nam Nguyen
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.
Select and Sample - A Model of Efficient Neural Inference and Learning
Authors: Jacquelyn A. Shelton, Abdul S. Sheikh, Pietro Berkes, Joerg Bornschein, Jörg Lücke
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: An increasing number of experimental studies indicate that perception encodes a posterior probability distribution over possible causes of sensory stimuli, which is used to act close to optimally in the environment. One outstanding difficulty with this hypothesis is that the exact posterior will in general be too complex to be represented directly, and thus neurons will have to represent an approximation of this distribution. Two influential proposals of efficient posterior representation by neural populations are: 1) neural activity represents samples of the underlying distribution, or 2) they represent a parametric representation of a variational approximation of the posterior. We show that these approaches can be combined for an inference scheme that retains the advantages of both: it is able to represent multiple modes and arbitrary correlations, a feature of sampling methods, and it reduces the represented space to regions of high probability mass, a strength of variational approximations. Neurally, the combined method can be interpreted as a feed-forward preselection of the relevant state space, followed by a neural dynamics implementation of Markov Chain Monte Carlo (MCMC) to approximate the posterior over the relevant states. We demonstrate the effectiveness and efficiency of this approach on a sparse coding model. In numerical experiments on artificial data and image patches, we compare the performance of the algorithms to that of exact EM, variational state space selection alone, MCMC alone, and the combined select and sample approach. The select and sample approach integrates the advantages of the sampling and variational approximations, and forms a robust, neurally plausible, and very efficient model of processing and learning in cortical networks. For sparse coding we show applications easily exceeding a thousand observed and a thousand hidden dimensions.
Clustered Multi-Task Learning Via Alternating Structure Optimization
Authors: Jiayu Zhou, Jianhui Chen, Jieping Ye
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Multi-task learning (MTL) learns multiple related tasks simultaneously to improve generalization performance. Alternating structure optimization (ASO) is a popular MTL method that learns a shared low-dimensional predictive structure on hypothesis spaces from multiple related tasks. It has been applied successfully in many real world applications. As an alternative MTL approach, clustered multi-task learning (CMTL) assumes that multiple tasks follow a clustered structure, i.e., tasks are partitioned into a set of groups where tasks in the same group are similar to each other, and that such a clustered structure is unknown a priori. The objectives in ASO and CMTL differ in how multiple tasks are related. Interestingly, we show in this paper the equivalence relationship between ASO and CMTL, providing significant new insights into ASO and CMTL as well as their inherent relationship. The CMTL formulation is non-convex, and we adopt a convex relaxation to the CMTL formulation. We further establish the equivalence relationship between the proposed convex relaxation of CMTL and an existing convex relaxation of ASO, and show that the proposed convex CMTL formulation is significantly more efficient especially for high-dimensional data. In addition, we present three algorithms for solving the convex CMTL formulation. We report experimental results on benchmark datasets to demonstrate the efficiency of the proposed algorithms.
On Learning Discrete Graphical Models using Greedy Methods
Authors: Ali Jalali, Christopher C. Johnson, Pradeep K. Ravikumar
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper, we address the problem of learning the structure of a pairwise graphical model from samples in a high-dimensional setting. Our first main result studies the sparsistency, or consistency in sparsity pattern recovery, properties of a forward-backward greedy algorithm as applied to general statistical models. As a special case, we then apply this algorithm to learn the structure of a discrete graphical model via neighborhood estimation. As a corollary of our general result, we derive sufficient conditions on the number of samples n, the maximum node-degree d and the problem size p, as well as other conditions on the model parameters, so that the algorithm recovers all the edges with high probability. Our result guarantees graph selection for samples scaling as n = Omega(d log(p)), in contrast to existing convex-optimization based algorithms that require a sample complexity of Omega(d^2 log(p)). Further, the greedy algorithm only requires a restricted strong convexity condition which is typically milder than irrepresentability assumptions. We corroborate these results using numerical simulations at the end.
Learning person-object interactions for action recognition in still images
Authors: Vincent Delaitre, Josef Sivic, Ivan Laptev
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We investigate a discriminatively trained model of person-object interactions for recognizing common human actions in still images. We build on the locally order-less spatial pyramid bag-of-features model, which was shown to perform extremely well on a range of object, scene and human action recognition tasks. We introduce three principal contributions. First, we replace the standard quantized local HOG/SIFT features with stronger discriminatively trained body part and object detectors. Second, we introduce new person-object interaction features based on spatial co-occurrences of individual body parts and objects. Third, we address the combinatorial problem of a large number of possible interaction pairs and propose a discriminative selection procedure using a linear support vector machine (SVM) with a sparsity inducing regularizer. Learning of action-specific body part and object interactions bypasses the difficult problem of estimating the complete human body pose configuration. Benefits of the proposed model are shown on human action recognition in consumer photographs, outperforming the strong bag-of-features baseline.
Efficient inference in matrix-variate Gaussian models with \iid observation noise
Authors: Oliver Stegle, Christoph Lippert, Joris M. Mooij, Neil D. Lawrence, Karsten Borgwardt
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Inference in matrix-variate Gaussian models has major applications for multi- output prediction and joint learning of row and column covariances from matrix- variate data. Here, we discuss an approach for efﬁcient inference in such models that explicitly account for iid observation noise. Computational tractability can be retained by exploiting the Kronecker product between row and column covariance matrices. Using this framework, we show how to generalize the Graphical Lasso in order to learn a sparse inverse covariance between features while accounting for a low-rank confounding covariance between samples. We show practical utility on applications to biology, where we model covariances with more than 100,000 di- mensions. We ﬁnd greater accuracy in recovering biological network structures and are able to better reconstruct the confounders.
Confidence Sets for Network Structure
Authors: David S. Choi, Patrick J. Wolfe, Edoardo M. Airoldi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Latent variable models are frequently used to identify structure in dichotomous network data, in part because they give rise to a Bernoulli product likelihood that is both well understood and consistent with the notion of exchangeable random graphs.  In this article we propose conservative confidence sets that hold with respect to these underlying Bernoulli parameters as a function of any given partition of network nodes, enabling us to assess estimates of \emph{residual} network structure, that is, structure that cannot be explained by known covariates and thus cannot be easily verified by manual inspection. We demonstrate the proposed methodology by analyzing student friendship networks from the National Longitudinal Survey of Adolescent Health that include race, gender, and school year as covariates.  We employ a stochastic expectation-maximization algorithm to fit a logistic regression model that includes these explanatory variables as well as a latent stochastic blockmodel component and additional node-specific effects.  Although maximum-likelihood estimates do not appear consistent in this context, we are able to evaluate confidence sets as a function of different blockmodel partitions, which enables us to qualitatively assess the significance of estimated residual network structure relative to a baseline, which models covariates but lacks block structure.
Structural equations and divisive normalization for energy-dependent component analysis
Authors: Jun-ichiro Hirayama, Aapo Hyvärinen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Components estimated by independent component analysis and related methods  are typically not independent in real data. A very common form of nonlinear  dependency between the components is correlations in their variances or ener-  gies. Here, we propose a principled probabilistic model to model the energy-  correlations between the latent variables. Our two-stage model includes a linear  mixing of latent signals into the observed ones like in ICA. The main new fea-  ture is a model of the energy-correlations based on the structural equation model  (SEM), in particular, a Linear Non-Gaussian SEM. The SEM is closely related to  divisive normalization which effectively reduces energy correlation. Our new two-  stage model enables estimation of both the linear mixing and the interactions re-  lated to energy-correlations, without resorting to approximations of the likelihood  function or other non-principled approaches. We demonstrate the applicability of  our method with synthetic dataset, natural images and brain signals.
Gaussian Process Training with Input Noise
Authors: Andrew Mchutchon, Carl E. Rasmussen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In standard Gaussian Process regression input locations are assumed to be noise free. We present a simple yet effective GP model for training on input points corrupted by i.i.d. Gaussian noise. To make computations tractable we use a local linear expansion about each input point. This allows the input noise to be recast as output noise proportional to the squared gradient of the GP posterior mean. The input noise variances are inferred from the data as extra hyperparameters. They are trained alongside other hyperparameters by the usual method of maximisation of the marginal likelihood. Training uses an iterative scheme, which alternates between optimising the hyperparameters and calculating the posterior gradient. Analytic predictive moments can then be found for Gaussian distributed test points. We compare our model to others over a range of different regression problems and show that it improves over current methods.
Speedy Q-Learning
Authors: Mohammad Ghavamzadeh, Hilbert J. Kappen, Mohammad G. Azar, Rémi Munos
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce a new convergent variant of Q-learning, called speedy Q-learning, to address the problem of slow convergence in the standard form of the Q-learning algorithm. We prove a PAC bound on the performance of SQL, which shows that for an MDP with n state-action pairs  and the discount factor \gamma only T=O\big(\log(n)/(\epsilon^{2}(1-\gamma)^{4})\big) steps are required for the SQL algorithm to converge to an \epsilon-optimal action-value function with high probability. This bound has a better dependency on 1/\epsilon and 1/(1-\gamma), and thus, is tighter than the best available result for Q-learning. Our bound is also superior to the existing results for both model-free and model-based instances of batch Q-value iteration that are considered to be more efficient than the incremental methods like Q-learning.
High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity
Authors: Po-ling Loh, Martin J. Wainwright
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Although the standard formulations of prediction problems involve fully-observed and noiseless data drawn in an i.i.d. manner, many  applications involve noisy and/or missing data, possibly involving dependencies. We study these issues in the context of high-dimensional  sparse linear regression, and propose novel estimators for the cases of noisy, missing, and/or dependent data. Many standard approaches to noisy or missing data, such as those using the EM algorithm, lead to optimization problems that are inherently non-convex, and it is difficult to establish theoretical guarantees on practical algorithms. While our approach also involves optimizing non-convex programs, we are able to both analyze the statistical error associated with any global optimum, and prove that a simple projected gradient descent algorithm will converge in polynomial time to a small neighborhood of the set of global minimizers. On the statistical side, we provide non-asymptotic bounds that hold with high probability for the cases of noisy, missing, and/or dependent data. On the computational side, we prove that under the same types of conditions required for statistical consistency, the projected gradient descent algorithm will converge at geometric rates to a near-global minimizer. We illustrate these theoretical predictions with simulations, showing agreement with the predicted scalings.
Greedy Model Averaging
Authors: Dong Dai, Tong Zhang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper considers the problem of combining multiple models to achieve a prediction accuracy not much worse than that of the best single model for least squares regression.  It is known that if the models are mis-specified, model averaging is superior to model selection.  Specifically, let $n$ be the sample size, then the worst case regret of the former decays at the rate of $O(1/n)$   while the worst case regret of the latter decays at the rate of $O(1/\sqrt{n})$.  In the literature, the most important and widely studied model averaging method that achieves the optimal $O(1/n)$ average regret   is the exponential weighted model averaging (EWMA) algorithm. However this method suffers from several limitations.   The purpose of this paper is to present a new greedy model averaging procedure that improves EWMA.  We prove strong theoretical guarantees for the new procedure and illustrate our theoretical results with empirical examples.
Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation
Authors: Nico Goernitz, Christian K. Widmer, Georg Zeller, Andre Kahles, Gunnar Rätsch, Sören Sonnenburg
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a novel regularization-based Multitask Learning (MTL) formulation  for Structured Output (SO) prediction for the case of hierarchical task relations.  Structured output learning often results in difﬁcult inference problems and   requires large amounts of training data to obtain accurate models. We propose to  use MTL to exploit information available for related structured output learning  tasks by means of hierarchical regularization. Due to the combination of example   sets, the cost of training models for structured output prediction can easily  become infeasible for real world applications. We thus propose an efﬁcient   algorithm based on bundle methods to solve the optimization problems resulting from  MTL structured output learning. We demonstrate the performance of our approach  on gene ﬁnding problems from the application domain of computational biology.  We show that 1) our proposed solver achieves much faster convergence than previous   methods and 2) that the Hierarchical SO-MTL approach clearly outperforms  considered non-MTL methods.
Generalized Beta Mixtures of Gaussians
Authors: Artin Armagan, Merlise Clyde, David B. Dunson
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In recent years, a rich variety of shrinkage priors have been proposed that have great promise in addressing massive regression problems.  In general, these new priors can be expressed as scale mixtures of normals, but have more complex forms and better properties than traditional Cauchy and double exponential priors. We first propose a new class of normal scale mixtures through a novel generalized beta distribution that encompasses many interesting priors as special cases.  This encompassing framework should prove useful in comparing competing priors, considering properties and revealing close connections. We then develop a class of variational Bayes approximations through the new hierarchy presented that will scale more efficiently to the types of truly massive data sets that are now encountered routinely.
Variational Gaussian Process Dynamical Systems
Authors: Andreas Damianou, Michalis K. Titsias, Neil D. Lawrence
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: High dimensional time series are endemic in applications of machine learning  such as robotics (sensor data), computational biology (gene expression data), vision   (video sequences) and graphics (motion capture data). Practical nonlinear  probabilistic approaches to this data are required. In this paper we introduce  the variational Gaussian process dynamical system. Our work builds on recent  variational approximations for Gaussian process latent variable models to allow  for nonlinear dimensionality reduction simultaneously with learning a dynamical  prior in the latent space. The approach also allows for the appropriate dimensionality   of the latent space to be automatically determined. We demonstrate the  model on a human motion capture data set and a series of high resolution video  sequences.