mtybilly/Instruct2DS huggingface dataset:
Unifying Non-Maximum Likelihood Learning Objectives with Minimum KL Contraction
Authors: Siwei Lyu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: When used to learn high dimensional parametric probabilistic models, the clas- sical maximum likelihood (ML) learning often suffers from computational in- tractability, which motivates the active developments of non-ML learning meth- ods. Yet, because of their divergent motivations and forms, the objective func- tions of many non-ML learning methods are seemingly unrelated, and there lacks a unified framework to understand them. In this work, based on an information geometric view of parametric learning, we introduce a general non-ML learning principle termed as minimum KL contraction, where we seek optimal parameters that minimizes the contraction of the KL divergence between the two distributions after they are transformed with a KL contraction operator. We then show that the objective functions of several important or recently developed non-ML learn- ing methods, including contrastive divergence [12], noise-contrastive estimation [11], partial likelihood [7], non-local contrastive objectives [31], score match- ing [14], pseudo-likelihood [3], maximum conditional likelihood [17], maximum mutual information [2], maximum marginal likelihood [9], and conditional and marginal composite likelihood [24], can be unified under the minimum KL con- traction framework with different choices of the KL contraction operators.
Select and Sample - A Model of Efficient Neural Inference and Learning
Authors: Abdul S. Sheikh, Pietro Berkes, Joerg Bornschein, Jörg Lücke Jacquelyn A. Shelton
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: Jianhui Chen, Jieping Ye Jiayu Zhou
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: Christopher C. Johnson, Pradeep K. Ravikumar Ali Jalali
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: Josef Sivic, Ivan Laptev Vincent Delaitre
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: Christoph Lippert, Joris M. Mooij, Neil D. Lawrence, Karsten Borgwardt Oliver Stegle
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: Patrick J. Wolfe, Edoardo M. Airoldi David S. Choi
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: Aapo Hyvärinen Jun-ichiro Hirayama
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: Carl E. Rasmussen Andrew Mchutchon
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.
Unifying Framework for Fast Learning Rate of Non-Sparse Multiple Kernel Learning
Authors: Taiji Suzuki
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper, we give a new generalization error bound of Multiple Kernel Learning  (MKL) for a general class of regularizations. Our main target in this paper is  dense type regularizations including ℓp-MKL that imposes ℓp-mixed-norm regularization  instead of ℓ1-mixed-norm regularization. According to the recent numerical  experiments, the sparse regularization does not necessarily show a good  performance compared with dense type regularizations. Motivated by this fact,  this paper gives a general theoretical tool to derive fast learning rates that is applicable  to arbitrary monotone norm-type regularizations in a unifying manner. As  a by-product of our general result, we show a fast learning rate of ℓp-MKL that  is tightest among existing bounds. We also show that our general learning rate  achieves the minimax lower bound. Finally, we show that, when the complexities  of candidate reproducing kernel Hilbert spaces are inhomogeneous, dense type  regularization shows better learning rate compared with sparse ℓ1 regularization.
Speedy Q-Learning
Authors: Hilbert J. Kappen, Mohammad G. Azar, Rémi Munos Mohammad Ghavamzadeh
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: Martin J. Wainwright Po-ling Loh
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: Tong Zhang Dong Dai
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: Christian K. Widmer, Georg Zeller, Andre Kahles, Gunnar Rätsch, Sören Sonnenburg Nico Goernitz
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: Merlise Clyde, David B. Dunson Artin Armagan
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: Michalis K. Titsias, Neil D. Lawrence Andreas Damianou
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.
Statistical Tests for Optimization Efficiency
Authors: Anoop Korattikara, Deva Ramanan, Max Welling Levi Boyles
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Learning problems such as logistic regression are typically formulated as pure  optimization problems defined on some loss function. We argue that this view  ignores the fact that the loss function depends on stochastically generated data  which in turn determines an intrinsic scale of precision for statistical estimation.  By considering the statistical properties of the update variables used during  the optimization (e.g. gradients), we can construct frequentist hypothesis tests  to determine the reliability of these updates. We utilize subsets of the data  for computing updates, and use the hypothesis tests for determining when the  batch-size needs to be increased. This provides computational benefits and avoids  overfitting by stopping when the batch-size has become equal to size of the full  dataset. Moreover, the proposed algorithms depend on a single interpretable  parameter – the probability for an update to be in the wrong direction – which is  set to a single value across all algorithms and datasets. In this paper, we illustrate  these ideas on three L1 regularized coordinate algorithms: L1 -regularized L2 -loss  SVMs, L1 -regularized logistic regression, and the Lasso, but we emphasize that  the underlying methods are much more generally applicable.
Statistical Performance of Convex Tensor Decomposition
Authors: Taiji Suzuki, Kohei Hayashi, Hisashi Kashima Ryota Tomioka
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We analyze the statistical performance of a recently proposed convex tensor decomposition algorithm. Conventionally tensor decomposition has been formulated as non-convex optimization problems, which hindered the analysis of their performance. We show under some conditions that the mean squared error of the convex method scales linearly with the quantity we call the normalized rank of the true tensor. The current analysis naturally extends the analysis of convex low-rank matrix estimation to tensors. Furthermore, we show through numerical experiments that our theory can precisely predict the scaling behaviour in practice.
A Machine Learning Approach to Predict Chemical Reactions
Authors: Pierre F. Baldi Matthew A. Kayala
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Being able to predict the course of arbitrary chemical reactions is essential to the theory and applications of organic chemistry. Previous approaches are not high-throughput, are not generalizable or scalable, or lack sufficient data to be effective. We describe single mechanistic reactions as concerted electron movements from an electron orbital source to an electron orbital sink. We use an existing rule-based expert system to derive a dataset consisting of 2,989 productive mechanistic steps and 6.14 million non-productive mechanistic steps. We then pose identifying productive mechanistic steps as a ranking problem: rank potential orbital interactions such that the top ranked interactions yield the major products. The machine learning implementation follows a two-stage approach, in which we first train atom level reactivity filters to prune 94.0% of non-productive reactions with less than a 0.1% false negative rate. Then, we train an ensemble of ranking models on pairs of interacting orbitals to learn a relative productivity function over single mechanistic reactions in a given system. Without the use of explicit transformation patterns, the ensemble perfectly ranks the productive mechanisms at the top 89.1% of the time, rising to 99.9% of the time when top ranked lists with at most four non-productive reactions are considered. The final system allows multi-step reaction prediction. Furthermore, it is generalizable, making reasonable predictions over reactants and conditions which the rule-based expert system does not handle.
Sparse Features for PCA-Like Linear Regression
Authors: Petros Drineas, Malik Magdon-Ismail Christos Boutsidis
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Principal Components Analysis~(PCA) is often used as a feature extraction procedure. Given a matrix $X \in \mathbb{R}^{n \times d}$, whose rows represent $n$ data points with respect to $d$ features, the top $k$ right singular vectors of $X$ (the so-called \textit{eigenfeatures}), are arbitrary linear combinations of all available features. The eigenfeatures are very useful in data analysis, including the regularization of linear regression. Enforcing sparsity on the eigenfeatures, i.e., forcing them to be linear combinations of only a \textit{small} number of actual features (as opposed to all available features), can promote better generalization error and improve the interpretability of the eigenfeatures. We present deterministic and randomized algorithms that construct such sparse eigenfeatures while \emph{provably} achieving in-sample performance comparable to regularized linear regression. Our algorithms are relatively simple and practically efficient, and we demonstrate their performance on several data sets.
Spike and Slab Variational Inference for Multi-Task and Multiple Kernel Learning
Authors: Miguel Lázaro-Gredilla Michalis K. Titsias
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce a variational Bayesian inference algorithm which can be widely applied to sparse linear models. The algorithm is based on the spike and slab prior which, from a Bayesian perspective, is the golden standard for sparse inference. We apply the method to a general multi-task and multiple kernel learning model in which a common set of Gaussian process functions is linearly combined with task-specific sparse weights, thus inducing relation between tasks. This model unifies several sparse linear models, such as generalized linear models, sparse factor analysis and matrix factorization with missing values, so that the variational algorithm can be applied to all these cases. We demonstrate our approach in multi-output Gaussian process regression, multi-class classification, image processing applications and collaborative filtering.
Neuronal Adaptation for Sampling-Based Probabilistic Inference in Perceptual Bistability
Authors: Peggy Series, Amos J. Storkey David P. Reichert
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: It has been argued that perceptual multistability reflects probabilistic inference performed by the brain when sensory input is ambiguous. Alternatively, more traditional explanations of multistability refer to low-level mechanisms such as neuronal adaptation. We employ a Deep Boltzmann Machine (DBM) model of cortical processing to demonstrate that these two different approaches can be combined in the same framework. Based on recent developments in machine learning, we show how neuronal adaptation can be understood as a mechanism that improves probabilistic, sampling-based inference. Using the ambiguous Necker cube image, we analyze the perceptual switching exhibited by the model. We also examine the influence of spatial attention, and explore how binocular rivalry can be modeled with the same approach. Our work joins earlier studies in demonstrating how the principles underlying DBMs relate to cortical processing, and offers novel perspectives on the neural implementation of approximate probabilistic inference in the brain.
Reinforcement Learning using Kernel-Based Stochastic Factorization
Authors: Doina Precup, Joelle Pineau Andre Barreto
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Kernel-based reinforcement-learning (KBRL) is a method for learning a decision policy from a set of sample transitions which stands out for its strong theoretical guarantees. However, the size of the approximator grows with the number of transitions, which makes the approach impractical for large problems.  In this paper we introduce a novel algorithm to improve the scalability of KBRL. We resort to a special decomposition of a transition matrix, called stochastic factorization, to fix the size of the approximator while at the same time incorporating all the information contained in the data. The resulting algorithm, kernel-based stochastic factorization (KBSF), is much faster but still converges to a unique solution. We derive a theoretical upper bound for the distance between the value functions computed by KBRL and KBSF. The effectiveness of our method is illustrated with computational experiments on four reinforcement-learning problems, including a difficult task in which the goal is to learn a neurostimulation policy to suppress the occurrence of seizures in epileptic rat brains. We empirically demonstrate that the proposed approach is able to compress the information contained in KBRL's model. Also, on the tasks studied, KBSF outperforms two of the most prominent reinforcement-learning algorithms, namely least-squares policy iteration and fitted Q-iteration.
Better Mini-Batch Algorithms via Accelerated Gradient Methods
Authors: Ohad Shamir, Nati Srebro, Karthik Sridharan Andrew Cotter
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Mini-batch algorithms have recently received significant attention as a way to speed-up stochastic convex optimization problems. In this paper, we study how such algorithms can be improved using accelerated gradient methods. We provide a novel analysis, which shows how standard gradient methods may sometimes be insufficient to obtain a significant speed-up. We propose a novel accelerated gradient algorithm, which deals with this deficiency, and enjoys a uniformly superior guarantee. We conclude our paper with experiments  on real-world datasets, which validates our algorithm and  substantiates our theoretical insights.
Generalizing from Several Related Classification Tasks to a New Unlabeled Sample
Authors: Gyemin Lee, Clayton Scott Gilles Blanchard
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of assigning class labels to an unlabeled test  data set, given several labeled training data sets drawn from similar  distributions. This problem arises in several applications where data  distributions fluctuate because of biological, technical, or other sources  of variation. We develop a distribution-free, kernel-based approach to the  problem. This approach involves identifying an appropriate reproducing     kernel Hilbert space and optimizing a regularized empirical risk over the  space.  We present generalization error analysis, describe universal  kernels, and establish universal consistency of the proposed methodology.  Experimental results on flow cytometry data are presented.
Energetically Optimal Action Potentials
Authors: Biswa Sengupta, Simon Laughlin, Jeremy Niven Martin B. Stemmler
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Most action potentials in the nervous system take on the form of strong, rapid, and brief voltage deflections known as spikes, in stark contrast to other action potentials, such as in the heart, that are characterized by broad voltage plateaus. We derive the shape of the neuronal action potential from first principles, by postulating that action potential generation is strongly constrained by the brain's need to minimize energy expenditure. For a given height of an action potential, the least energy is consumed when the underlying currents obey the bang-bang principle: the currents giving rise to the spike should be intense, yet short-lived, yielding  spikes with sharp onsets and offsets. Energy optimality predicts features in the biophysics that are not per se required for producing the characteristic neuronal action potential:  sodium currents should be extraordinarily powerful and inactivate with voltage; both potassium and sodium currents should have kinetics that have a bell-shaped voltage-dependence; and the cooperative action of multiple `gates'  should start the flow of current.
Global Solution of Fully-Observed Variational Bayesian Matrix Factorization is Column-Wise Independent
Authors: Masashi Sugiyama, S. D. Babacan Shinichi Nakajima
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Variational Bayesian matrix factorization (VBMF) efficiently   approximates the posterior distribution of factorized matrices   by assuming matrix-wise independence of the two factors.  A recent study on fully-observed VBMF  showed that, under a stronger assumption that the two factorized matrices are  column-wise independent,  the global optimal solution can be analytically computed.  However, it was not clear how restrictive  the column-wise independence assumption is.  In this paper, we prove that the global solution under matrix-wise  independence is actually column-wise independent,  implying that the column-wise independence assumption is harmless.  A practical consequence of our theoretical finding is that  the global solution under matrix-wise independence (which is a standard setup)  can be obtained analytically in a computationally very efficient way  without any iterative algorithms.  We experimentally illustrate advantages of using our analytic solution  in probabilistic principal component analysis.
Algorithms and hardness results for parallel large margin learning
Authors: Rocco Servedio Phil Long
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study the fundamental problem of learning an unknown large-margin halfspace in the context of parallel computation.    Our main positive result is a parallel algorithm for learning a large-margin halfspace that is based on interior point methods from convex optimization and fast parallel algorithms for matrix computations. We show that this algorithm learns an unknown gamma-margin halfspace over n dimensions using poly(n,1/gamma) processors and runs in time ~O(1/gamma) + O(log n). In contrast, naive parallel algorithms that learn a gamma-margin halfspace in time that depends polylogarithmically on n have Omega(1/gamma^2) runtime dependence on gamma.     Our main negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We give an information-theoretic proof that in the original PAC framework, in which a weak learning algorithm is provided as an oracle that is called by the booster, boosting cannot be parallelized: the ability to  call the weak learner multiple times in parallel within a single boosting stage does not reduce the overall number of successive stages of boosting that are required.
Semi-supervised Regression via Parallel Field Regularization
Authors: Chiyuan Zhang, Xiaofei He Binbin Lin
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper studies the problem of semi-supervised learning from the vector field perspective. Many of the existing work use the graph Laplacian to ensure the smoothness of the prediction function on the data manifold. However, beyond smoothness, it is suggested by recent theoretical work that we should ensure second order smoothness for achieving faster rates of convergence for semi-supervised regression problems. To achieve this goal, we show that the second order smoothness measures the linearity of the function, and the gradient field of a linear function has to be a parallel vector field. Consequently, we propose to find a function which minimizes the empirical error, and simultaneously requires its gradient field to be as parallel as possible. We give a continuous objective function on the manifold and discuss how to discretize it by using random points. The discretized optimization problem turns out to be a sparse linear system which can be solved very efficiently. The experimental results have demonstrated the effectiveness of our proposed approach.
Thinning Measurement Models and Questionnaire Design
Authors: Ricardo Silva
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Inferring key unobservable features of individuals is an important task in the applied sciences. In particular, an important source of data in fields such as marketing, social sciences and medicine is questionnaires: answers in such questionnaires are noisy measures of target unobserved features. While comprehensive surveys help to better estimate the latent variables of interest, aiming at a high number of questions comes at a price: refusal to participate in surveys can go up, as well as the rate of missing data; quality of answers can decline; costs associated with applying such questionnaires can also increase. In this paper, we cast the problem of refining existing models for questionnaire data as follows: solve a constrained optimization problem of preserving the maximum amount of information found in a latent variable model using only a subset of existing questions. The goal is to find an optimal subset of a given size. For that, we first define an information theoretical measure for quantifying the quality of a reduced questionnaire. Three different approximate inference methods are introduced to solve this problem. Comparisons against a simple but powerful heuristic are presented.
Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials
Authors: Vladlen Koltun Philipp Krähenbühl
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Most state-of-the-art techniques for multi-class image segmentation and labeling use conditional random ﬁelds deﬁned over pixels or image regions. While region- level models often feature dense pairwise connectivity, pixel-level models are con- siderably larger and have only permitted sparse graph structures. In this paper, we consider fully connected CRF models deﬁned on the complete set of pixels in an image. The resulting graphs have billions of edges, making traditional inference algorithms impractical. Our main contribution is a highly efﬁcient approximate inference algorithm for fully connected CRF models in which the pairwise edge potentials are deﬁned by a linear combination of Gaussian kernels. Our experi- ments demonstrate that dense connectivity at the pixel level substantially improves segmentation and labeling accuracy.
Simultaneous Sampling and Multi-Structure Fitting with Adaptive Reversible Jump MCMC
Authors: Tat-jun Chin, Jin Yu, David Suter Trung T. Pham
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Multi-structure model fitting has traditionally taken a two-stage approach: First, sample a (large) number of model hypotheses, then select the subset of hypotheses that optimise a joint fitting and model selection criterion. This disjoint two-stage approach is arguably suboptimal and inefficient - if the random sampling did not retrieve a good set of hypotheses, the optimised outcome will not represent a good fit. To overcome this weakness we propose a new multi-structure fitting approach based on Reversible Jump MCMC. Instrumental in raising the effectiveness of our method is an adaptive hypothesis generator, whose proposal distribution is learned incrementally and online. We prove that this adaptive proposal satisfies the diminishing adaptation property crucial for ensuring ergodicity in MCMC. Our method effectively conducts hypothesis sampling and optimisation simultaneously, and gives superior computational efficiency over other methods.
Active dendrites: adaptation to spike-based communication
Authors: Máté Lengyel Balazs B. Ujfalussy
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Computational analyses of dendritic computations often assume stationary inputs to neurons, ignoring the pulsatile nature of spike-based communication between neurons and the moment-to-moment fluctuations caused by such spiking inputs. Conversely, circuit computations with spiking neurons are usually formalized without regard to the rich nonlinear nature of dendritic processing. Here we address the computational challenge faced by neurons that compute and represent analogue quantities but communicate with digital spikes, and show that reliable computation of even purely linear functions of inputs can require the interplay of strongly nonlinear subunits within the postsynaptic dendritic tree. Our theory predicts a matching of dendritic nonlinearities and synaptic weight distributions to the joint statistics of presynaptic inputs. This approach suggests normative roles for some puzzling forms of nonlinear dendritic dynamics and plasticity.
Shaping Level Sets with Submodular Functions
Authors: Francis R. Bach
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on  non-decreasing functions, we explore symmetric submodular functions and their \lova extensions. We show that the Lovasz extension may be seen as the convex envelope of a function that depends on level sets  (i.e., the set of indices whose corresponding components of the underlying predictor are greater than a given constant): this leads to a class of convex structured regularization terms that impose prior knowledge on the level sets, and not only on the supports of the underlying predictors. We provide a unified set of optimization algorithms, such as proximal operators, and theoretical guarantees (allowed level sets and recovery conditions). By selecting specific submodular functions,  we   give a new interpretation to known norms, such as the total variation; we also define new norms, in particular ones that are based on order statistics with application to clustering and outlier detection, and on noisy cuts in graphs with application to change point detection in the presence of outliers.
Probabilistic amplitude and frequency demodulation
Authors: Maneesh Sahani Richard Turner
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: A number of recent scientific and engineering problems require signals to be decomposed into a product of a slowly varying positive envelope and a quickly varying carrier whose instantaneous frequency also varies slowly over time. Although signal processing provides algorithms for so-called amplitude- and frequency-demodulation (AFD), there are well known problems with all of the existing methods. Motivated by the fact that AFD is ill-posed, we approach the problem using probabilistic inference. The new approach, called probabilistic amplitude and frequency demodulation (PAFD), models instantaneous frequency using an auto-regressive generalization of the von Mises distribution, and the envelopes using Gaussian auto-regressive dynamics with a positivity constraint. A novel form of expectation propagation is used for inference. We demonstrate that although PAFD is computationally demanding, it outperforms previous approaches on synthetic and real signals in clean, noisy and missing data settings.
Multi-Bandit Best Arm Identification
Authors: Mohammad Ghavamzadeh, Alessandro Lazaric, Sébastien Bubeck Victor Gabillon
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study the problem of identifying the best arm in each of the bandits in a multi-bandit multi-armed setting. We first propose an algorithm called Gap-based Exploration (GapE) that focuses on the arms whose mean is close to the mean of the best arm in the same bandit (i.e., small gap). We then introduce an algorithm, called GapE-V, which takes into account the variance of the arms in addition to their gap. We prove an upper-bound on the probability of error for both algorithms. Since GapE and GapE-V need to tune an exploration parameter that depends on the complexity of the problem, which is often unknown in advance, we also introduce variations of these algorithms that estimate this complexity online. Finally, we evaluate the performance of these algorithms and compare them to other allocation strategies on a number of synthetic problems.
Nonlinear Inverse Reinforcement Learning with Gaussian Processes
Authors: Zoran Popovic, Vladlen Koltun Sergey Levine
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a probabilistic algorithm for nonlinear inverse reinforcement learning. The goal of inverse reinforcement learning is to learn the reward function in a Markov decision process from expert demonstrations. While most prior inverse reinforcement learning algorithms represent the reward as a linear combination of a set of features, we use Gaussian processes to learn the reward as a nonlinear function, while also determining the relevance of each feature to the expert's policy. Our probabilistic algorithm allows complex behaviors to be captured from suboptimal stochastic demonstrations, while automatically balancing the simplicity of the learned reward structure against its consistency with the observed actions.