mtybilly/Instruct2DS huggingface dataset:
Dynamical segmentation of single trials from population neural data
Authors: Byron M. Yu, John P. Cunningham, Gopal Santhanam, Stephen I. Ryu, Krishna V. Shenoy, Maneesh Sahani Biljana Petreska
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Simultaneous recordings of many neurons embedded within a  recurrently-connected cortical network may provide concurrent views into the dynamical processes of that network, and thus its computational function.  In principle, these dynamics might be identified by purely unsupervised, statistical means.  Here, we show that a Hidden Switching Linear Dynamical Systems (HSLDS) model---in which multiple linear dynamical laws approximate a nonlinear and potentially non-stationary dynamical process---is able to distinguish different dynamical regimes within single-trial motor cortical activity associated with the preparation and initiation of hand movements.  The regimes are identified without reference to behavioural or experimental epochs, but nonetheless transitions between them correlate strongly with external events whose timing may vary from trial to trial.  The HSLDS model also performs better than recent comparable models in predicting the firing rate of an isolated neuron based on the firing rates of others, suggesting that it  captures more of the "shared variance" of the data.  Thus, the method is able to trace the dynamical processes underlying the coordinated evolution of network activity in a way that appears to reflect its computational role.
Approximating Semidefinite Programs in Sublinear Time
Authors: Elad Hazan Dan Garber
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In recent years semidefinite optimization has become a tool of major importance in various optimization and machine learning problems. In many of these problems the amount of data in practice is so large that there is a constant need for faster algorithms. In this work we present the first  sublinear time approximation algorithm for semidefinite programs which we believe may be useful for such problems in which the size of data may cause even linear time algorithms to have prohibitive running times in practice. We present the algorithm and its analysis alongside with some theoretical lower bounds and an improved algorithm for the special problem of supervised learning of a distance metric.
Active Classification based on Value of Classifier
Authors: Daphne Koller Tianshi Gao
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Modern classification tasks usually involve many class labels and can be informed by a broad range of features. Many of these tasks are tackled by constructing a set of classifiers, which are then applied at test time and then pieced together in a fixed procedure determined in advance or at training time. We present an active classification process at the test time, where each classifier in a large ensemble is viewed as a potential observation that might inform our classification process. Observations are then selected dynamically based on previous observations, using a value-theoretic computation that balances an estimate of the expected classification gain from each observation as well as its computational cost. The expected classification gain is computed using a probabilistic model that uses the outcome from previous observations. This active classification process is applied at test time for each individual test instance, resulting in an efficient instance-specific decision path. We demonstrate the benefit of the active scheme on various real-world datasets, and show that it can achieve comparable or even higher classification accuracy at a fraction of the computational costs of traditional methods.
Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
Authors: Varun Kanade, Ohad Shamir, Adam Kalai Sham M. Kakade
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Generalized Linear Models (GLMs) and Single Index Models (SIMs) provide powerful generalizations of linear regression, where the target variable is assumed to be a (possibly unknown) 1-dimensional function of a linear predictor. In general, these problems entail non-convex estimation procedures, and, in practice, iterative local search heuristics are often used.  Kalai and Sastry (2009) provided the first provably efficient method, the \emph{Isotron} algorithm, for learning SIMs and GLMs, under the assumption that the data is in fact generated under a GLM and under certain monotonicity and Lipschitz (bounded slope) constraints. The Isotron algorithm interleaves steps of perceptron-like updates with isotonic regression (fitting a one-dimensional non-decreasing function). However, to obtain provable performance, the method requires a fresh sample every iteration. In this paper, we provide algorithms for learning GLMs and SIMs, which are both computationally and statistically efficient. We modify the isotonic regression step in Isotron to fit a Lipschitz monotonic function, and also provide an efficient $O(n \log(n))$ algorithm for this step, improving upon the previous $O(n^2)$ algorithm. We provide a brief empirical study, demonstrating the feasibility of our algorithms in practice.
Co-regularized Multi-view Spectral Clustering
Authors: Piyush Rai, Hal Daume Abhishek Kumar
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In many clustering problems, we have access to multiple views of the data each  of which could be individually used for clustering. Exploiting information from  multiple views, one can hope to find a clustering that is more accurate than the  ones obtained using the individual views. Since the true clustering would assign  a point to the same cluster irrespective of the view, we can approach this problem  by looking for clusterings that are consistent across the views, i.e., corresponding  data points in each view should have same cluster membership. We propose a  spectral clustering framework that achieves this goal by co-regularizing the clustering  hypotheses, and propose two co-regularization schemes to accomplish this.  Experimental comparisons with a number of baselines on two synthetic and three  real-world datasets establish the efficacy of our proposed approaches.
A concave regularization technique for sparse mixture models
Authors: Johan Ugander Martin O. Larsson
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Latent variable mixture models are a powerful tool for exploring the structure in large datasets. A common challenge for interpreting such models is a desire to impose sparsity, the natural assumption that each data point only contains few latent features. Since mixture distributions are constrained in their L1 norm, typical sparsity techniques based on L1 regularization become toothless, and concave regularization becomes necessary. Unfortunately concave regularization typically results in EM algorithms that must perform problematic non-concave M-step maximizations. In this work, we introduce a technique for circumventing this difficulty, using the so-called Mountain Pass Theorem to provide easily verifiable conditions under which the M-step is well-behaved despite the lacking concavity. We also develop a correspondence between logarithmic regularization and what we term the pseudo-Dirichlet distribution, a generalization of the ordinary Dirichlet distribution well-suited for inducing sparsity. We demonstrate our approach on a text corpus, inferring a sparse topic mixture model for 2,406 weblogs.
Image Parsing with Stochastic Scene Grammar
Authors: Song-chun Zhu Yibiao Zhao
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper proposes a parsing algorithm for scene understanding which includes four aspects: computing 3D scene layout, detecting 3D objects (e.g. furniture), detecting 2D faces (windows, doors etc.), and segmenting background. In contrast to previous scene labeling work that applied discriminative classifiers to pixels (or super-pixels), we use a generative Stochastic Scene Grammar (SSG). This grammar represents the compositional structures of visual entities from scene categories, 3D foreground/background, 2D faces, to 1D lines. The grammar includes three types of production rules and two types of contextual relations. Production rules: (i) AND rules represent the decomposition of an entity into sub-parts; (ii) OR rules represent the switching among sub-types of an entity; (iii) SET rules rep- resent an ensemble of visual entities. Contextual relations: (i) Cooperative “+” relations represent positive links between binding entities, such as hinged faces of a object or aligned boxes; (ii) Competitive “-” relations represents negative links between competing entities, such as mutually exclusive boxes. We design an efficient MCMC inference algorithm, namely Hierarchical cluster sampling, to search in the large solution space of scene configurations. The algorithm has two stages: (i) Clustering: It forms all possible higher-level structures (clusters) from lower-level entities by production rules and contextual relations. (ii) Sampling: It jumps between alternative structures (clusters) in each layer of the hierarchy to find the most probable configuration (represented by a parse tree). In our experiment, we demonstrate the superiority of our algorithm over existing methods on public dataset. In addition, our approach achieves richer structures in the parse tree.
Dynamic Pooling and Unfolding Recursive Autoencoders for Paraphrase Detection
Authors: Eric H. Huang, Jeffrey Pennin, Christopher D. Manning, Andrew Y. Ng Richard Socher
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Paraphrase detection is the task of examining two sentences and determining whether they have the same meaning. In order to obtain high accuracy on this task, thorough syntactic and semantic analysis of the two statements is needed. We introduce a method for paraphrase detection based on recursive autoencoders (RAE). Our unsupervised RAEs are based on a novel unfolding objective and learn feature vectors for phrases in syntactic trees. These features are used to measure the word- and phrase-wise similarity between two sentences. Since sentences may be of arbitrary length, the resulting matrix of similarity measures is of variable size. We introduce a novel dynamic pooling layer which computes a fixed-sized representation from the variable-sized matrices. The pooled representation is then used as input to a classifier. Our method outperforms other state-of-the-art approaches on the challenging MSRP paraphrase corpus.
Trace Lasso: a trace norm regularization for correlated designs
Authors: Guillaume R. Obozinski, Francis R. Bach Edouard Grave
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Using the $\ell_1$-norm to regularize the estimation of  the parameter vector of a linear model leads to an unstable estimator when covariates are highly correlated. In this paper, we introduce a new penalty function which takes into account the correlation of the design matrix to stabilize the estimation. This norm, called the trace Lasso, uses the trace norm of the selected covariates, which is a convex surrogate of their rank, as the criterion of model complexity. We analyze the properties of our norm, describe an optimization algorithm based on reweighted least-squares, and illustrate the behavior of this norm on synthetic data, showing that it is more adapted to strong correlations than competing methods such as the elastic net.
Linear Submodular Bandits and their Application to Diversified Retrieval
Authors: Carlos Guestrin Yisong Yue
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Diversified retrieval and online learning are two core research areas in the design of modern information retrieval systems.In this paper, we propose the linear submodular bandits problem, which is an online learning setting for optimizing a general class of feature-rich submodular utility models for diversified retrieval. We present an algorithm, called LSBGREEDY, and prove that it efficiently converges to a near-optimal model. As a case study, we applied our approach to the setting of personalized news recommendation, where the system must recommend small sets of news articles selected from tens of thousands of available articles each day. In a live user study, we found that LSBGREEDY significantly outperforms existing online learning approaches.
Learning Eigenvectors for Free
Authors: Wojciech Kotlowski, Manfred K. Warmuth Wouter M. Koolen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We extend the classical problem of predicting a sequence  of outcomes from a finite alphabet to the matrix domain.   In this extension, the alphabet of $n$ outcomes is replaced by the set of all dyads, i.e.   outer products $\u\u^\top$ where $\u$ is a vector in $\R^n$ of unit length.  Whereas in the classical case the goal is to learn   (i.e. sequentially predict as well as) the best multinomial distribution,  in the matrix case we desire to learn the density matrix  that best explains the observed sequence of dyads. We show  how popular online algorithms for learning a multinomial  distribution can be extended to learn density matrices.  Intuitively, learning the $n^2$ parameters of a density matrix is much harder than learning the $n$ parameters of a multinomial distribution. Completely surprisingly, we prove that the worst-case regrets of   certain classical algorithms and   their matrix generalizations are identical.   The reason is that the worst-case sequence of dyads share a common   eigensystem, i.e. the worst case regret is achieved in the  classical case. So these matrix algorithms learn the eigenvectors  without any regret.
Neural Reconstruction with Approximate Message Passing (NeuRAMP)
Authors: Sundeep Rangan, Lav R. Varshney, Aniruddha Bhargava Alyson K. Fletcher
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many functional descriptions of spiking neurons assume a cascade structure where inputs are passed through an initial linear filtering stage that produces a low-dimensional signal that drives subsequent nonlinear stages.  This paper presents a novel and systematic parameter estimation procedure for such models and applies the method to two neural estimation problems: (i) compressed-sensing based neural mapping from multi-neuron excitation, and (ii) estimation of neural receptive yields in sensory neurons.  The proposed estimation algorithm models the neurons via a graphical model and then estimates the parameters in the model using a recently-developed generalized approximate message passing (GAMP) method.  The GAMP method is based on Gaussian approximations of loopy belief propagation.  In the neural connectivity problem, the GAMP-based   method is shown to be computational efficient, provides a more exact modeling of the sparsity, can incorporate nonlinearities in the output and significantly outperforms previous compressed-sensing methods.  For the receptive field estimation, the GAMP method can also exploit inherent structured sparsity in the linear weights.  The method is validated on estimation of linear nonlinear Poisson (LNP) cascade models for receptive fields of salamander retinal ganglion cells.
Bayesian Partitioning of Large-Scale Distance Data
Authors: Volker Roth David Adametz
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: A Bayesian approach to partitioning distance matrices is presented. It is inspired by the 'Translation-Invariant Wishart-Dirichlet' process (TIWD) in (Vogt et al., 2010) and shares a number of advantageous properties like the fully probabilistic nature of the inference model, automatic selection of the number of clusters and applicability in semi-supervised settings. In addition, our method (which we call 'fastTIWD') overcomes the main shortcoming of the original TIWD, namely its high computational costs. The fastTIWD reduces the workload in each iteration of a Gibbs sampler from O(n^3) in the TIWD to O(n^2). Our experiments show that this cost reduction does not compromise the quality of the inferred partitions. With this new method it is now possible to 'mine' large relational datasets with a probabilistic model, thereby automatically detecting new and potentially interesting clusters.
Dimensionality Reduction Using the Sparse Linear Model
Authors: Todd Zickler Ioannis A. Gkioulekas
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose an approach for linear unsupervised dimensionality reduction, based on the sparse linear model that has been used to probabilistically interpret sparse coding. We formulate an optimization problem for learning a linear projection from the original signal domain to a lower-dimensional one in a way that approximately preserves, in expectation, pairwise inner products in the sparse domain. We derive solutions to the problem, present nonlinear extensions, and discuss relations to compressed sensing. Our experiments using facial images, texture patches, and images of object categories suggest that the approach can improve our ability to recover meaningful structure in many classes of signals.
RTRMC: A Riemannian trust-region method for low-rank matrix completion
Authors: Pierre-antoine Absil Nicolas Boumal
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider large matrices of low rank. We address the problem of recovering such matrices when most of the entries are unknown. Matrix completion finds applications in recommender systems. In this setting, the rows of the matrix may correspond to items and the columns may correspond to users. The known entries are the ratings given by users to some items. The aim is to predict the unobserved ratings. This problem is commonly stated in a constrained optimization framework. We follow an approach that exploits the geometry of the low-rank constraint to recast the problem as an unconstrained optimization problem on the Grassmann manifold. We then apply first- and second-order Riemannian trust-region methods to solve it. The cost of each iteration is linear in the number of known entries. Our methods, RTRMC 1 and 2, outperform state-of-the-art algorithms on a wide range of problem instances.
Complexity of Inference in Latent Dirichlet Allocation
Authors: Dan Roy David Sontag
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the computational complexity of probabilistic inference in Latent Dirichlet Allocation (LDA).  First, we study the problem of finding the maximum a posteriori (MAP) assignment of topics to words, where the document's topic distribution is integrated out.  We show that, when the effective number of topics per document is small, exact inference takes polynomial time. In contrast, we show that, when a document has a large number of topics, finding the MAP assignment of topics to words in LDA is NP-hard.  Next, we consider the problem of finding the MAP topic distribution for a document, where the topic-word assignments are integrated out.  We show that this problem is also NP-hard.  Finally, we briefly discuss the problem of sampling from the posterior, showing that this is NP-hard in one restricted setting, but leaving open the general question.
A Denoising View of Matrix Completion
Authors: Miguel Á. Carreira-Perpiñán, Zhengdong Lu Weiran Wang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In matrix completion, we are given a matrix where the values of only some of the entries are present, and we want to reconstruct the missing ones. Much work has focused on the assumption that the data matrix has low rank. We propose a more general assumption based on denoising, so that we expect that the value of a missing entry can be predicted from the values of neighboring points. We propose a nonparametric version of denoising based on local, iterated averaging with mean-shift, possibly constrained to preserve local low-rank manifold structure. The few user parameters required (the denoising scale, number of neighbors and local dimensionality) and the number of iterations can be estimated by cross-validating the reconstruction error. Using our algorithms as a postprocessing step on an initial reconstruction (provided by e.g. a low-rank method), we show consistent improvements with synthetic, image and motion-capture data.
Generalization Bounds and Consistency for Latent Structural Probit and Ramp Loss
Authors: David A. McAllester Joseph Keshet
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider latent structural versions of probit loss and ramp loss. We show that  these surrogate loss functions are consistent in the strong sense that for any feature map  (finite or infinite dimensional) they yield predictors approaching the infimum  task loss achievable by any linear predictor over the given features.  We also give  finite sample generalization bounds (convergence rates) for these loss functions.  These bounds suggest that probit loss converges more rapidly.  However, ramp loss is more easily optimized and may ultimately  be more practical.
Budgeted Optimization with Concurrent Stochastic-Duration Experiments
Authors: Alan Fern, Xiaoli Z. Fern Javad Azimi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Budgeted optimization involves optimizing an unknown function that is costly to evaluate by requesting a limited number of function evaluations at intelligently selected inputs. Typical problem formulations assume that experiments are selected one at a time with a limited total number of experiments, which fail to capture important aspects of many real-world problems. This paper defines a novel problem formulation with the following important extensions: 1) allowing for concurrent experiments; 2) allowing for stochastic experiment durations; and 3) placing constraints on both the total number of experiments and the total experimental time. We develop both offline and online algorithms for selecting concurrent experiments in this new setting and provide experimental results on a number of optimization benchmarks. The results show that our algorithms produce highly effective schedules compared to natural baselines.
Data Skeletonization via Reeb Graphs
Authors: Issam I. Safa, Mikhail Belkin, Yusu Wang Xiaoyin Ge
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Recovering hidden structure from complex and noisy non-linear data is one of the most fundamental problems in machine learning and statistical inference. While such data is often high-dimensional, it is of interest to approximate it with a low-dimensional or even one-dimensional space, since  many important aspects of  data are often intrinsically low-dimensional.   Furthermore, there are many scenarios where the underlying structure is graph-like, e.g, river/road networks or various trajectories.   In this paper, we develop a framework to extract, as well as to simplify, a one-dimensional "skeleton" from unorganized data using the Reeb graph.   Our algorithm is very simple, does not require complex optimizations and can be easily applied to unorganized high-dimensional data such as point clouds or  proximity graphs.   It can also represent arbitrary graph structures in the data.  We also give  theoretical results to justify our method.  We  provide a number of experiments to demonstrate the effectiveness and generality of our algorithm, including comparisons to existing methods, such as principal curves.  We believe that the simplicity and practicality of our algorithm will help to promote skeleton graphs as a data analysis tool for a broad range of applications.
MAP Inference for Bayesian Inverse Reinforcement Learning
Authors: Kee-eung Kim Jaedeug Choi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The difficulty in inverse reinforcement learning (IRL) arises in choosing the best reward function since there are typically an infinite number of reward functions that yield the given behaviour data as optimal. Using a Bayesian framework, we address this challenge by using the maximum a posteriori (MAP) estimation for the reward function, and show that most of the previous IRL algorithms can be modeled into our framework. We also present a gradient method for the MAP estimation based on the (sub)differentiability of the posterior distribution. We show the effectiveness of our approach by comparing the performance of the proposed method to those of the previous algorithms.
Learning Sparse Representations of High Dimensional Data on Large Scale Dictionaries
Authors: Hao Xu, Peter J. Ramadge Zhen J. Xiang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Learning sparse representations on data adaptive dictionaries is a state-of-the-art method for modeling data. But when the dictionary is large and the data dimension is high, it is a computationally challenging problem. We explore three aspects of the problem. First, we derive new, greatly improved screening tests that quickly identify codewords that are guaranteed to have zero weights. Second, we study the properties of random projections in the context of learning sparse representations. Finally, we develop a hierarchical framework that uses incremental random projections and screening to learn, in small stages, a hierarchically structured dictionary for sparse representations. Empirical results show that our framework can learn informative hierarchical sparse representations more efficiently.
Efficient Online Learning via Randomized Rounding
Authors: Ohad Shamir Nicolò Cesa-bianchi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Most online algorithms used in machine learning today are based on variants of mirror descent or follow-the-leader. In this paper, we present an online algorithm based on a completely different approach, which combines ``random playout'' and randomized rounding of loss subgradients. As an application of our approach, we provide the first computationally efficient online algorithm for collaborative filtering with trace-norm constrained matrices. As a second application, we solve an open question linking batch learning and transductive online learning.
Spatial distance dependent Chinese restaurant processes for image segmentation
Authors: Andrei B. Ungureanu, Erik B. Sudderth, David M. Blei Soumya Ghosh
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The distance dependent Chinese restaurant process (ddCRP) was recently introduced to accommodate random partitions of non-exchangeable data.  The ddCRP clusters data in a biased way: each data point is more likely to be clustered with other data that are near it in an external sense.  This paper examines the ddCRP in a spatial setting with the goal of natural image segmentation.  We explore the biases of the spatial ddCRP model and propose a novel hierarchical extension better suited for producing "human-like" segmentations. We then study the sensitivity of the models to various distance and appearance hyperparameters, and provide the first rigorous comparison of nonparametric Bayesian models in the image segmentation domain. On unsupervised image segmentation, we demonstrate that similar performance to existing nonparametric Bayesian models is possible with substantially simpler models and algorithms.
History distribution matching method for predicting effectiveness of HIV combination therapies
Authors: Jasmina Bogojeska
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper presents an approach that predicts the effectiveness of HIV combination therapies by simultaneously addressing several problems affecting the available HIV clinical data sets: the different treatment backgrounds of the samples, the uneven representation of the levels of therapy experience, the missing treatment history information, the uneven therapy representation and the unbalanced therapy outcome representation. The computational validation on clinical data shows that, compared to the most commonly used approach that does not account for the issues mentioned above, our model has significantly higher predictive power. This is especially true for samples stemming from patients with longer treatment history and samples associated with rare therapies. Furthermore, our approach is at least as powerful for the remaining samples.
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
Authors: Francis R. Bach Eric Moulines
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the minimization of a convex objective function defined on a Hilbert space, which is only available through unbiased estimates of  its gradients.  This problem includes  standard machine learning algorithms such as kernel logistic regression and least-squares regression, and is commonly referred to as a stochastic approximation problem in the operations research community. We provide a non-asymptotic analysis of the  convergence of two well-known algorithms, stochastic gradient descent (a.k.a.~Robbins-Monro algorithm) as well as a simple modification where iterates are averaged (a.k.a.~Polyak-Ruppert averaging). Our analysis suggests that a learning rate proportional to the inverse of the number of iterations, while leading to the optimal convergence rate in the strongly convex case, is not robust to the lack of strong convexity or the setting of the proportionality constant. This situation is remedied when using slower decays together with averaging, robustly leading to the optimal rate of convergence. We illustrate our theoretical results with simulations on synthetic and standard datasets.
A Non-Parametric Approach to Dynamic Programming
Authors: Jan R. Peters Oliver B. Kroemer
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper, we consider the problem of policy evaluation for continuous-state systems. We present a non-parametric approach to policy evaluation, which uses kernel density estimation to represent the system. The true form of the value function for this model can be determined, and can be computed using Galerkin's method. Furthermore, we also present a unified view of several well-known policy evaluation methods. In particular, we show that the same Galerkin method can be used to derive Least-Squares Temporal Difference learning, Kernelized Temporal Difference learning, and a discrete-state Dynamic Programming solution, as well as our proposed method. In a numerical evaluation of these algorithms, the proposed approach performed better than the other methods.
Extracting Speaker-Specific Information with a Regularized Siamese Deep Network
Authors: Ahmad Salman Ke Chen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Speech conveys different yet mixed information ranging from linguistic to speaker-specific components, and each of them should be exclusively used in a specific task. However, it is extremely difficult to extract a specific information component given the fact that nearly all existing acoustic representations carry all types of speech information. Thus, the use of the same representation in both speech and speaker recognition hinders a system from producing better performance due to interference of irrelevant information. In this paper, we present a deep neural architecture to extract speaker-specific information from MFCCs. As a result, a multi-objective loss function is proposed for learning speaker-specific characteristics and regularization via normalizing interference of non-speaker related information and avoiding information loss. With LDC benchmark corpora and a Chinese speech corpus, we demonstrate that a resultant speaker-specific representation is insensitive to text/languages spoken and environmental mismatches and hence outperforms MFCCs and other state-of-the-art techniques in speaker recognition. We discuss relevant issues and relate our approach to previous work.
Variance Penalizing AdaBoost
Authors: Tony Jebara Pannagadatta K. Shivaswamy
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper proposes a novel boosting algorithm called VadaBoost which is motivated by recent empirical Bernstein bounds.  VadaBoost iteratively minimizes a cost function that balances the sample mean and the sample variance of the exponential loss. Each step of the proposed algorithm minimizes the cost efficiently by providing weighted data to a weak learner rather than requiring a brute force evaluation of all possible weak learners. Thus, the proposed algorithm solves a key limitation of previous empirical Bernstein boosting methods which required brute force enumeration of all possible weak learners. Experimental results confirm that the new algorithm achieves the performance improvements of EBBoost yet goes beyond decision stumps to handle any weak learner. Significant performance gains are obtained over AdaBoost for arbitrary weak learners including decision trees (CART).
Autonomous Learning of Action Models for Planning
Authors: Prasad Tadepalli, Alan Fern Neville Mehta
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper introduces two new frameworks for learning action models for planning.  In the mistake-bounded planning framework, the learner has access to a planner for the given model representation, a simulator, and a planning problem generator, and aims to learn a model with at most a polynomial number of faulty plans.  In the planned exploration framework, the learner does not have access to a problem generator and must instead design its own problems, plan for them, and converge with at most a polynomial number of planning attempts.  The paper reduces learning in these frameworks to concept learning with one-sided error and provides algorithms for successful learning in both frameworks.  A specific family of hypothesis spaces is shown to be efficiently learnable in both the frameworks.
Hierarchically Supervised Latent Dirichlet Allocation
Authors: Frank Wood, Noemie Elhadad, Nicholas Bartlett Adler J. Perotte
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce hierarchically supervised latent Dirichlet allocation (HSLDA), a model for hierarchically and multiply labeled bag-of-word data. Examples of such data include web pages and their placement in directories, product descriptions and associated categories from product hierarchies, and free-text clinical records and their assigned diagnosis codes. Out-of-sample label prediction is the primary goal of this work, but improved lower-dimensional representations of the bag-of-word data are also of interest. We demonstrate HSLDA on large-scale data from clinical document labeling and retail product categorization tasks. We show that leveraging the structure from hierarchical labels improves out-of-sample label prediction substantially when compared to models that do not.
Agnostic Selective Classification
Authors: Ran El-Yaniv Yair Wiener
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: For a learning problem whose associated excess loss class is $(\beta,B)$-Bernstein, we show that it is theoretically possible to track the same classification performance  of the best (unknown) hypothesis in our class, provided that we are free to abstain from prediction in some region of our choice. The (probabilistic) volume of this rejected region of the domain is shown to be diminishing at rate $O(B\theta (\sqrt{1/m}))^\beta)$, where $\theta$ is Hanneke's disagreement coefficient. The strategy achieving this performance has computational barriers because it requires empirical error minimization in an agnostic setting. Nevertheless, we heuristically approximate this strategy and develop a novel selective classification algorithm  using constrained SVMs. We show empirically that the resulting algorithm consistently outperforms  the traditional rejection mechanism based on distance from decision boundary.
Additive Gaussian Processes
Authors: Hannes Nickisch, Carl E. Rasmussen David K. Duvenaud
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce a Gaussian process model of functions which are additive.  An additive function is one which decomposes into a sum of low-dimensional functions, each depending on only a subset of the input variables. Additive GPs generalize both Generalized Additive Models, and the standard GP models which use squared-exponential kernels.  Hyperparameter learning in this model can be seen as Bayesian Hierarchical Kernel Learning (HKL).  We introduce an expressive but tractable parameterization of the kernel function, which allows efficient evaluation of all input interaction terms, whose number is exponential in the input dimension.  The additional structure discoverable by this model results in increased interpretability, as well as state-of-the-art predictive power in regression tasks.
A Collaborative Mechanism for Crowdsourcing Prediction Problems
Authors: Rafael M. Frongillo Jacob D. Abernethy
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Machine Learning competitions such as the Netflix Prize have proven reasonably successful as a method of “crowdsourcing” prediction tasks. But these compe- titions have a number of weaknesses, particularly in the incentive structure they create for the participants. We propose a new approach, called a Crowdsourced Learning Mechanism, in which participants collaboratively “learn” a hypothesis for a given prediction task. The approach draws heavily from the concept of a prediction market, where traders bet on the likelihood of a future event. In our framework, the mechanism continues to publish the current hypothesis, and par- ticipants can modify this hypothesis by wagering on an update. The critical in- centive property is that a participant will profit an amount that scales according to how much her update improves performance on a released test set.
Sparse Bayesian Multi-Task Learning
Authors: Onno Zoeter, Cédric Archambeau Shengbo Guo
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose a new sparse Bayesian model for multi-task regression and classification. The model is able to capture correlations between tasks, or more specifically a low-rank approximation of the covariance matrix, while being sparse in the features. We introduce a general family of group sparsity inducing priors based on matrix-variate Gaussian scale mixtures. We show the amount of sparsity can be learnt from the data by combining an approximate inference approach with type II maximum likelihood estimation of the hyperparameters. Empirical evaluations on data sets from biology and vision demonstrate the applicability of the model, where on both regression and classification tasks it achieves competitive predictive performance compared to previously proposed methods.
Orthogonal Matching Pursuit with Replacement
Authors: Ambuj Tewari, Inderjit S. Dhillon Prateek Jain
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper, we consider the problem of compressed sensing where the goal is to recover almost all the sparse vectors using a small number of fixed linear measurements. For this problem, we propose a novel partial hard-thresholding operator leading to a general family of iterative algorithms. While one extreme of the family yields well known hard thresholding algorithms like ITI and HTP, the other end of the spectrum leads to a novel algorithm that we call  Orthogonal Matching Pursuit with Replacement (OMPR). OMPR, like the classic greedy algorithm OMP, adds exactly one coordinate to the support at each iteration, based on the correlation with the current residual. However, unlike OMP, OMPR also removes one coordinate from the support. This simple change allows us to prove the best known guarantees for OMPR in terms of the Restricted Isometry Property (a condition on the measurement matrix). In contrast, OMP is known to have very weak performance guarantees under RIP.  We also extend OMPR using locality sensitive hashing to get OMPR-Hash, the first provably sub-linear (in dimensionality) algorithm for sparse recovery. Our  proof techniques are novel and flexible enough to also permit the tightest known analysis of popular iterative algorithms such as CoSaMP and Subspace Pursuit.  We provide experimental results on large problems providing  recovery for vectors of size up to million dimensions.  We demonstrate that for large-scale problems our proposed methods are more robust and faster than the existing  methods.
High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions
Authors: Vincent Tan, Alan S. Willsky Animashree Anandkumar
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm   for structure estimation based known as  conditional mutual information test. This simple local algorithm    requires only low-order statistics of the data and decides    whether  two nodes   are neighbors in the unknown graph. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent)  when the number of samples scales as n= Omega(J{min}^{-4} log p), where p is the number of nodes and J{min} is the minimum edge potential.  We also prove novel non-asymptotic necessary conditions for graphical model selection.
Optimal learning rates for least squares SVMs using Gaussian kernels
Authors: Ingo Steinwart Mona Eberts
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We prove a new oracle inequality for support vector machines with Gaussian RBF kernels solving the regularized least squares regression problem. To this end, we apply the modulus of smoothness. With the help of the new oracle inequality we then derive learning rates that can also be achieved by a simple data-dependent parameter selection method. Finally, it turns out that our learning rates are asymptotically optimal for regression functions satisfying certain standard smoothness conditions.
Fast and Accurate k-means For Large Datasets
Authors: Alex Wong, Adam W. Meyerson Michael Shindler
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Clustering is a popular problem with many applications. We consider the k-means problem in the situation where the data is too large to be stored in main memory and must be accessed sequentially, such as from a disk, and where we must use as little memory as possible. Our algorithm is based on recent theoretical results, with significant improvements to make it practical. Our approach greatly simpli(cid:173) fies a recently developed algorithm, both in design and in analysis, and eliminates large constant factors in the approximation guarantee, the memory requirements, and the running time. We then incorporate approximate nearest neighbor search to compute k-means in o(nk) (where n is the number of data points; note that com(cid:173) puting the cost, given a solution, takes 8(nk) time). We show that our algorithm compares favorably to existing algorithms - both theoretically and experimentally, thus providing state-of-the-art performance in both theory and practice.
Message-Passing for Approximate MAP Inference with Latent Variables
Authors: Piyush Rai, Hal Daume Jiarong Jiang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider a general inference setting for discrete probabilistic graphical models where we seek maximum a posteriori (MAP) estimates for a subset of the random variables (max nodes), marginalizing over the rest (sum nodes). We present a hybrid message-passing algorithm to accomplish this.  The hybrid algorithm passes a mix of sum and max messages depending on the type of source node (sum or max). We derive our algorithm by showing that it falls out as the solution of a particular relaxation of a variational framework.  We further show that the Expectation Maximization algorithm can be seen as an approximation to our algorithm. Experimental results on synthetic and real-world datasets, against several baselines, demonstrate the efficacy of our proposed algorithm.
A More Powerful Two-Sample Test in High Dimensions using Random Projection
Authors: Laurent Jacob, Martin J. Wainwright Miles Lopes
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the hypothesis testing problem of detecting a shift between the means of two multivariate normal distributions in the high-dimensional setting, allowing for the data dimension p to exceed the sample size n. Our contribution is a new test statistic for the two-sample test of means that integrates a random projection with the classical Hotelling T squared statistic. Working within a high- dimensional framework that allows (p,n) to tend to infinity, we first derive an asymptotic power function for our test, and then provide sufficient conditions for it to achieve greater power than other  state-of-the-art tests. Using ROC curves generated from simulated data, we demonstrate superior performance against competing tests in the parameter regimes anticipated by our theoretical results. Lastly, we illustrate an advantage of our procedure with comparisons on a high-dimensional gene expression dataset involving the discrimination of different types of cancer.
Kernel Bayes' Rule
Authors: Le Song, Arthur Gretton Kenji Fukumizu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: A nonparametric kernel-based method for realizing Bayes' rule is proposed, based on kernel representations of probabilities in reproducing kernel Hilbert spaces. The prior and conditional probabilities are expressed as empirical kernel mean and covariance operators, respectively, and the kernel mean of the posterior distribution is computed in the form of a weighted sample.  The kernel Bayes' rule can be applied to a wide variety of Bayesian inference problems: we demonstrate Bayesian computation without likelihood, and filtering with a nonparametric state-space model. A consistency rate for the posterior estimate is established.