mtybilly/Instruct2DS huggingface dataset:
Exploration in Model-based Reinforcement Learning by Empirically Estimating Learning Progress
Authors: Tobias Lang, Marc Toussaint, Pierre-yves Oudeyer Manuel Lopes
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Formal exploration approaches in model-based reinforcement learning estimate the accuracy of the currently learned model without consideration of the empirical prediction error. For example, PAC-MDP approaches such as Rmax base their model certainty on the amount of collected data, while Bayesian approaches assume a prior over the transition dynamics. We propose extensions to such approaches which drive exploration solely based on empirical estimates of the learner's accuracy and learning progress. We provide a ``sanity check'' theoretical analysis, discussing the behavior of our extensions in the standard stationary finite state-action case. We then provide experimental studies demonstrating the robustness of these exploration measures in cases of non-stationary environments or where original approaches are misled by wrong domain assumptions.
From Deformations to Parts: Motion-based Segmentation of 3D Objects
Authors: Matthew Loper, Erik B. Sudderth, Michael J. Black Soumya Ghosh
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop a method for discovering the parts of an articulated object from aligned meshes capturing various three-dimensional (3D) poses.  We adapt the distance dependent Chinese restaurant process (ddCRP) to allow nonparametric discovery of a potentially unbounded number of parts, while simultaneously guaranteeing a spatially connected segmentation.  To allow analysis of datasets in which object instances have varying shapes, we model part variability across poses via affine transformations.  By placing a matrix normal-inverse-Wishart prior on these affine transformations, we develop a ddCRP Gibbs sampler which tractably marginalizes over transformation uncertainty.  Analyzing a dataset of humans captured in dozens of poses, we infer parts which provide quantitatively better motion predictions than conventional clustering methods.
Bayesian models for Large-scale Hierarchical Classification
Authors: Yiming Yang, Bing Bai, Alexandru Niculescu-mizil Siddharth Gopal
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: A challenging problem in hierarchical classification is to leverage the hierarchical relations among classes for  improving classification performance. An even greater challenge is to do so in a manner that is computationally feasible for the large scale problems usually encountered in practice. This paper proposes a set of Bayesian methods to model hierarchical dependencies among class labels using multivari- ate logistic regression. Specifically, the parent-child relationships are modeled by placing a hierarchical prior over the children nodes centered around the parame- ters of their parents; thereby encouraging classes nearby in the hierarchy to share similar model parameters. We present new, efficient variational algorithms for tractable posterior inference in these models, and provide a parallel implementa- tion that can comfortably handle large-scale problems with hundreds of thousands of dimensions and tens of thousands of classes. We run a comparative evaluation on multiple large-scale benchmark datasets that highlights the scalability of our approach, and shows a significant performance advantage over the other state-of- the-art hierarchical methods.
Efficient Spike-Coding with Multiplicative Adaptation in a Spike Response Model
Authors: Sander M. Bohte
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Neural adaptation underlies the ability of neurons to maximize encoded information over a wide dynamic range of input stimuli. While adaptation is an intrinsic feature of neuronal models like the Hodgkin-Huxley model, the challenge is to integrate adaptation in models of neural computation.  Recent computational models like the Adaptive Spike Response Model implement adaptation as spike-based addition of fixed-size fast spike-triggered threshold dynamics and slow spike-triggered currents. Such adaptation has been shown to accurately model neural spiking behavior over a limited dynamic range. Taking a cue from kinetic models of adaptation, we propose a multiplicative Adaptive Spike Response Model where the spike-triggered adaptation dynamics are scaled multiplicatively by the adaptation state at the time of spiking. We show that unlike the additive adaptation model, the firing rate in the multiplicative adaptation model saturates to a maximum spike-rate. When simulating variance switching experiments, the model also quantitatively fits the experimental data over a wide dynamic range. Furthermore, dynamic threshold models of adaptation suggest a straightforward interpretation of neural activity in terms of dynamic signal encoding with shifted and weighted exponential kernels. We show that when thus encoding rectified filtered stimulus signals, the multiplicative Adaptive Spike Response Model achieves a high coding efficiency and maintains this efficiency over changes in the dynamic signal range of several orders of magnitude, without changing model parameters.
Forging The Graphs: A Low Rank and Positive Semidefinite Graph Learning Approach
Authors: Heng Huang, Feiping Nie, Chris H. Ding Dijun Luo
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In many graph-based machine learning and data mining approaches, the quality of the graph is critical. However, in real-world applications, especially in semi-supervised learning and unsupervised learning, the evaluation of the quality of a graph is often expensive and sometimes even impossible, due the cost or the unavailability of ground truth. In this paper, we proposed a robust approach with convex optimization to ``forge'' a graph: with an input of a graph, to learn a graph with higher quality. Our major concern is that an ideal graph shall satisfy all the following constraints: non-negative, symmetric, low rank, and positive semidefinite. We develop a graph learning algorithm by solving a convex optimization problem and further develop an efficient optimization to obtain global optimal solutions with theoretical guarantees. With only one non-sensitive parameter, our method is shown by experimental results to be robust and achieve higher accuracy in semi-supervised learning and clustering under various settings. As a preprocessing of graphs, our method has a wide range of potential applications machine learning and data mining.
Random Utility Theory for Social Choice
Authors: David Parks, Lirong Xia Hossein Azari
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Random utility theory models an agents preferences on alternatives by drawing a real-valued score on each alternative (typically independently) from a parameterized distribution, and then ranking the alternatives according to scores. A special case that has received signicant attention is the Plackett-Luce model, for which fast inference methods for maximum likelihood estimators are available. This paper develops conditions on general random utility models that enable fast inference within a Bayesian framework through MC-EM, providing concave loglikelihood functions and bounded sets of global maxima solutions. Results on both real-world and simulated data provide support for the scalability of the approach and capability for model selection among general random utility models including Plackett-Luce.
Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs
Authors: Shay B. Cohen Michael Collins
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We describe an approach to speed-up inference with latent variable PCFGs, which have been shown to  be highly effective for natural language parsing. Our approach is based on a tensor formulation recently introduced for spectral estimation of latent-variable PCFGs coupled with a tensor decomposition algorithm well-known in the multilinear algebra literature.  We also describe an error bound for this approximation, which bounds the difference between the probabilities calculated by the algorithm and the true probabilities that the approximated model gives. Empirical evaluation on real-world natural language parsing data demonstrates a significant speed-up at minimal cost for parsing performance.
Action-Model Based Multi-agent Plan Recognition
Authors: Qiang Yang, Subbarao Kambhampati Hankz H. Zhuo
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Multi-Agent Plan Recognition (MAPR) aims to recognize dynamic team structures and team behaviors from the observed team traces (activity sequences) of a set of intelligent agents. Previous MAPR approaches required a library of team activity sequences (team plans) be given as input. However, collecting a library of team plans to ensure adequate coverage is often difficult and costly. In this paper, we relax this constraint, so that team plans are not required to be provided beforehand. We assume instead that a set of action models are available. Such models are often already created to describe domain physics; i.e., the  preconditions and effects of effects actions. We propose a novel approach for recognizing multi-agent team plans based on such action models rather than libraries of team plans. We encode the resulting MAPR problem as a \emph{satisfiability problem} and solve the problem using a state-of-the-art weighted MAX-SAT solver. Our approach also allows for incompleteness in the observed plan traces. Our empirical studies demonstrate that our algorithm is both effective and efficient in comparison to state-of-the-art MAPR methods based on plan libraries.
Semiparametric Principal Component Analysis
Authors: Han Liu Fang Han
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We propose two new principal component analysis methods in this paper utilizing a semiparametric model. The according methods are named Copula Component Analysis (COCA) and Copula PCA. The semiparametric model assumes that, af- ter unspeciﬁed marginally monotone transformations, the distributions are multi- variate Gaussian. The COCA and Copula PCA accordingly estimate the leading eigenvectors of the correlation and covariance matrices of the latent Gaussian dis- tribution. The robust nonparametric rank-based correlation coefﬁcient estimator, Spearman’s rho, is exploited in estimation. We prove that, under suitable condi- tions, although the marginal distributions can be arbitrarily continuous, the COCA and Copula PCA estimators obtain fast estimation rates and are feature selection consistent in the setting where the dimension is nearly exponentially large relative to the sample size. Careful numerical experiments on the synthetic and real data are conducted to back up the theoretical results. We also discuss the relationship with the transelliptical component analysis proposed by Han and Liu (2012).
Multi-task Vector Field Learning
Authors: Sen Yang, Chiyuan Zhang, Jieping Ye, Xiaofei He Binbin Lin
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Multi-task learning (MTL) aims to improve generalization performance by learning multiple related tasks simultaneously and identifying the shared information among tasks. Most of existing MTL methods focus on learning linear models under the supervised setting. We propose a novel semi-supervised and nonlinear approach for MTL using vector fields. A vector field is a smooth mapping from the manifold to the tangent spaces which can be viewed as a directional derivative of functions on the manifold. We argue that vector fields provide a natural way to exploit the geometric structure of data as well as the shared differential structure of tasks, both are crucial for semi-supervised multi-task learning. In this paper, we develop multi-task vector field learning (MTVFL) which learns the prediction functions and the vector fields simultaneously. MTVFL has the following key properties: (1) the vector fields we learned are close to the gradient fields of the prediction functions; (2) within each task, the vector field is required to be as parallel as possible which is expected to span a low dimensional subspace; (3) the vector fields from all tasks share a low dimensional subspace. We formalize our idea in a regularization framework and also provide a convex relaxation method to solve the original non-convex problem. The experimental results on synthetic and real data demonstrate the effectiveness of our proposed approach.
Local Supervised Learning through Space Partitioning
Authors: Venkatesh Saligrama Joseph Wang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop a novel approach for supervised learning based on adaptively partitioning the feature space into different regions and learning local region-specific classifiers. We formulate an empirical risk minimization problem that incorporates both partitioning and classification in to a single global objective. We show that space partitioning can be equivalently reformulated as a supervised learning problem and consequently any discriminative learning method can be utilized in conjunction with our approach. Nevertheless, we consider locally linear schemes by learning linear partitions and linear region classifiers. Locally linear schemes can not only approximate complex decision boundaries and ensure low training error but also provide tight control on over-fitting and generalization error. We train locally linear classifiers by using LDA, logistic regression and perceptrons, and so our scheme is scalable to large data sizes and high-dimensions. We present experimental results demonstrating improved performance over state of the art classification techniques on benchmark datasets. We also show improved robustness to label noise.
Dip-means: an incremental clustering method for estimating the number of clusters
Authors: Aristidis Likas Argyris Kalogeratos
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Learning the number of clusters is a key problem in data clustering. We present dip-means, a novel robust incremental method to learn the number of data clusters that may be used as a wrapper around any iterative clustering algorithm of the k-means family. In contrast to many popular methods which make assumptions about the underlying cluster distributions, dip-means only assumes a fundamental cluster property: each cluster to admit a unimodal distribution. The proposed algorithm considers each cluster member as a ''viewer'' and applies a univariate statistic hypothesis test for unimodality (dip-test) on the distribution of the distances between the viewer and the cluster members. Two important advantages are: i) the unimodality test is applied on univariate distance vectors, ii) it can be directly applied with kernel-based methods, since only the pairwise distances are involved in the computations. Experimental results on artificial and real datasets indicate the effectiveness of our method and its superiority over analogous approaches.
Unsupervised Template Learning for Fine-Grained Object Recognition
Authors: Liefeng Bo, Jue Wang, Linda G. Shapiro Shulin Yang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Fine-grained recognition refers to a subordinate level of recognition, such are recognizing different species of birds, animals or plants. It differs from recognition of basic categories, such as humans, tables, and computers, in that there are global similarities in shape or structure shared within a category, and the differences are in the details of the object parts. We suggest that the key to identifying the fine-grained differences lies in finding the right alignment of image regions that contain the same object parts. We propose a template model for the purpose, which captures common shape patterns of object parts, as well as the co-occurence relation of the shape patterns. Once the image regions are aligned, extracted features are used for classification. Learning of the template model is efficient, and the recognition results we achieve significantly outperform the state-of-the-art algorithms.
A Nonparametric Conjugate Prior Distribution for the Maximizing Argument of a Noisy Function
Authors: Jordi Grau-moya, Tim Genewein, David Balduzzi, Daniel Braun Pedro Ortega
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We propose a novel Bayesian approach to solve stochastic optimization problems that involve ﬁnding extrema of noisy, nonlinear functions. Previous work has focused on representing possible functions explicitly, which leads to a two-step procedure of ﬁrst, doing inference over the function space and second, ﬁnding the extrema of these functions. Here we skip the representation step and directly model the distribution over extrema. To this end, we devise a non-parametric conjugate prior where the natural parameter corresponds to a given kernel function and the sufﬁcient statistic is composed of the observed function values. The resulting posterior distribution directly captures the uncertainty over the maximum of the unknown function.
Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems
Authors: Adel Javanmard, Benjamin V. Roy Morteza Ibrahimi
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study the problem of adaptive control of a high dimensional linear quadratic (LQ) system.  Previous work established the asymptotic convergence to an optimal controller for various adaptive control schemes. More recently, an asymptotic regret bound of $\tilde{O}(\sqrt{T})$ was shown for $T \gg p$ where $p$ is the dimension of the state space. In this work we consider the case where the matrices describing the dynamic of the LQ system are sparse and their dimensions are large. We present an adaptive control scheme that for $p \gg 1$ and $T \gg \polylog(p)$ achieves a regret bound of $\tilde{O}(p \sqrt{T})$. In particular, our algorithm has an average cost of $(1+\eps)$ times the optimum cost after $T = \polylog(p) O(1/\eps^2)$. This is in comparison to previous work on the dense dynamics where the algorithm needs $\Omega(p)$ samples before it can estimate the unknown dynamic with any significant accuracy. We believe our result has prominent applications in the emerging area of computational advertising, in particular targeted online advertising and advertising in social networks.
A Conditional Multinomial Mixture Model for Superset Label Learning
Authors: Thomas G. Dietterich Liping Liu
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In the superset label learning problem (SLL), each training instance provides a set of candidate labels of which one is the true label of the instance. As in ordinary regression, the candidate label set is a noisy version of the true label. In this work, we solve the problem by maximizing the likelihood of the candidate label sets of training instances. We propose a probabilistic model, the Logistic Stick- Breaking Conditional Multinomial Model (LSB-CMM), to do the job. The LSB- CMM is derived from the logistic stick-breaking process. It ﬁrst maps data points to mixture components and then assigns to each mixture component a label drawn from a component-speciﬁc multinomial distribution. The mixture components can capture underlying structure in the data, which is very useful when the model is weakly supervised. This advantage comes at little cost, since the model introduces few additional parameters. Experimental tests on several real-world problems with superset labels show results that are competitive or superior to the state of the art. The discovered underlying structures also provide improved explanations of the classiﬁcation predictions.
Value Pursuit Iteration
Authors: Doina Precup Amir M. Farahmand
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Value Pursuit Iteration (VPI) is an approximate value iteration algorithm that finds a close to optimal policy for  reinforcement learning and planning problems with large state spaces. VPI has two main features: First, it is a nonparametric algorithm that finds a good sparse approximation of the optimal value function given a dictionary of features. The algorithm is almost insensitive to the number of irrelevant features. Second, after each iteration of VPI, the algorithm adds a set of functions based on the currently learned value function to the dictionary. This increases the representation power of the dictionary in a way that is directly relevant to the goal of having a good approximation of the optimal value function. We theoretically study VPI and provide a finite-sample error upper bound for it.
Latent Coincidence Analysis: A Hidden Variable Model for Distance Metric Learning
Authors: Lawrence K. Saul Matthew Der
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We describe a latent variable model for supervised dimensionality reduction and distance metric learning. The model discovers linear projections of high dimensional data that shrink the distance between similarly labeled inputs and expand the distance between differently labeled ones. The model’s continuous latent variables locate pairs of examples in a latent space of lower dimensionality. The model differs significantly from classical factor analysis in that the posterior distribution over these latent variables is not always multivariate Gaussian. Nevertheless we show that inference is completely tractable and derive an Expectation-Maximization (EM) algorithm for parameter estimation. We also compare the model to other approaches in distance metric learning. The model’s main advantage is its simplicity: at each iteration of the EM algorithm, the distance metric is re-estimated by solving an unconstrained least-squares problem. Experiments show that these simple updates are highly effective.
Identification of Recurrent Patterns in the Activation of Brain Networks
Authors: Weichang Li, Niranjan Subrahmanya, Istvan Morocz, William Wells Firdaus Janoos
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Identifying patterns from the neuroimaging recordings of brain activity  related to the unobservable psychological or mental state of an individual can be treated as a unsupervised pattern recognition problem. The main challenges, however, for such an analysis of fMRI data are: a) defining a physiologically meaningful feature-space for representing the spatial patterns across time; b) dealing with the high-dimensionality of the data; and c) robustness to the various artifacts and confounds in the fMRI time-series.  In this paper, we present a network-aware feature-space to represent the states of a general network, that enables  comparing and clustering such states in a manner that is a) meaningful in terms of the network connectivity structure; b)computationally efficient; c) low-dimensional; and d) relatively robust to structured and random noise artifacts. This feature-space is obtained from a spherical relaxation of the transportation distance metric which measures the cost of transporting ``mass'' over the network to transform one function into another. Through theoretical and empirical assessments, we demonstrate the accuracy and efficiency of the approximation, especially for large problems.  While the application presented here is for identifying distinct brain activity patterns from fMRI, this feature-space can be applied to the problem of identifying recurring patterns and detecting outliers in measurements on many different types of networks, including sensor, control and social networks.
Hierarchical spike coding of sound
Authors: Chaitanya Ekanadham, Eero P. Simoncelli Yan Karklin
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop a probabilistic generative model for representing acoustic event structure at multiple scales via a two-stage hierarchy. The first stage consists of a spiking representation which encodes a sound with a sparse set of kernels at different frequencies positioned precisely in time. The coarse time and frequency statistical structure of the first-stage spikes is encoded by a second stage spiking representation, while fine-scale statistical regularities are encoded by recurrent interactions within the first-stage.  When fitted to speech data, the model encodes acoustic features such as harmonic stacks, sweeps, and frequency modulations, that can be composed to represent complex acoustic events. The model is also able to synthesize sounds from the higher-level representation and provides significant improvement over wavelet thresholding techniques on a denoising task.
A Polynomial-time Form of Robust Regression
Authors: Özlem Aslan, Dale Schuurmans Yao-liang Yu
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Despite the variety of robust regression methods that have been developed, current regression formulations are either NP-hard, or allow unbounded response to even a single leverage point. We present a general formulation for robust regression --Variational M-estimation--that unifies a number of robust regression methods while allowing a tractable approximation strategy. We develop an estimator that requires only polynomial-time, while achieving certain robustness and consistency guarantees. An experimental evaluation demonstrates the effectiveness of the new estimation approach  compared to standard methods.
Multimodal Learning with Deep Boltzmann Machines
Authors: Ruslan Salakhutdinov Nitish Srivastava
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We propose a Deep Boltzmann Machine for learning a generative model of multimodal data. We show how to use the model to extract a meaningful representation of multimodal data. We find that the learned representation is useful for classification and information retreival tasks, and hence conforms to some notion of semantic similarity. The model defines a probability density over the space of multimodal inputs. By sampling from the conditional distributions over each data modality, it possible to create the representation even when some data modalities are missing. Our experimental results on bi-modal data consisting of images and text show that the Multimodal DBM can learn a good generative model of the joint space of image and text inputs that is useful for information retrieval from both unimodal and multimodal queries. We further demonstrate that our model can significantly outperform SVMs and LDA on discriminative tasks. Finally, we compare our model to other deep learning methods, including autoencoders and deep belief networks, and show that it achieves significant gains.
A nonparametric variable clustering model
Authors: Zoubin Ghahramani, David A. Knowles Konstantina Palla
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Factor analysis models effectively summarise the covariance structure of high dimensional data, but the solutions are typically hard to interpret. This motivates attempting to find a disjoint partition, i.e. a clustering, of observed variables so that variables in a cluster are highly correlated. We introduce a Bayesian non-parametric approach to this problem, and demonstrate advantages over heuristic methods proposed to date.
Transelliptical Graphical Models
Authors: Fang Han, Cun-hui Zhang Han Liu
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We advocate the use of a new distribution family—the transelliptical—for robust inference of high dimensional graphical models. The transelliptical family is an extension of the nonparanormal family proposed by Liu et al. (2009). Just as the nonparanormal extends the normal by transforming the variables using univariate functions, the transelliptical extends the elliptical family in the same way. We propose a nonparametric rank-based regularization estimator which achieves the parametric rates of convergence for both graph recovery and parameter estima- tion. Such a result suggests that the extra robustness and ﬂexibility obtained by the semiparametric transelliptical modeling incurs almost no efﬁciency loss. We also discuss the relationship between this work with the transelliptical component analysis proposed by Han and Liu (2012).
Collaborative Gaussian Processes for Preference Learning
Authors: Ferenc Huszar, Zoubin Ghahramani, Jose M. Hernández-lobato Neil Houlsby
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present a new model based on Gaussian processes (GPs) for learning pairwise preferences expressed by multiple users. Inference is simplified by using a \emph{preference kernel} for GPs which allows us to combine supervised GP learning of user preferences with unsupervised dimensionality reduction for multi-user systems. The model not only exploits collaborative information from the shared structure in user behavior, but may also incorporate user features if they are available. Approximate inference is implemented using a combination of expectation propagation and variational Bayes. Finally, we present an efficient active learning strategy for querying preferences. The proposed technique performs favorably on real-world data against state-of-the-art multi-user preference learning algorithms.
Smooth-projected Neighborhood Pursuit for High-dimensional Nonparanormal Graph Estimation
Authors: Kathryn Roeder, Han Liu Tuo Zhao
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Many statistical methods gain robustness and exibility by sacricing convenient computational structure. In this paper, we illustrate this fundamental tradeoff by studying a semiparametric graphical model estimation problem. We explain how new computational techniques help to solve this type of problem. In particularly, we propose a smooth-projected neighborhood pursuit method for efciently estimating high dimensional nonparanormal graphs with theoretical guarantees. Besides new computational and theoretical analysis, we also provide an alternative view to analyze the tradeoff between computational efciency and statistical error under a smoothing optimization framework. We also report experimental results on text and stock datasets.
Learning Manifolds with K-Means and K-Flats
Authors: Tomaso Poggio, Lorenzo Rosasco Guillermo Canas
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by  k-means and k-ﬂats, and analyze their performance. We extend previous results  for k-means in two separate directions. First, we provide new results for k-means reconstruction on manifolds and, secondly, we prove reconstruction bounds for higher-order approximation (k-ﬂats), for which no known results were previously available. While the results for k-means are novel, some of the technical tools are well-established in the literature. In the case of k-ﬂats, both the results and the mathematical tools are  new.
Newton-Like Methods for Sparse Inverse Covariance Estimation
Authors: Jorge Nocedal, Steven Rennie, Peder A. Olsen Figen Oztoprak
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We propose two classes of second-order optimization methods for solving the sparse inverse covariance estimation problem. The first approach, which we call the Newton-LASSO method, minimizes a piecewise quadratic model of the objective function at every iteration to generate a step. We employ the fast iterative shrinkage thresholding method (FISTA) to solve this subproblem. The second approach, which we call the Orthant-Based Newton method, is a two-phase algorithm that first identifies an orthant face and then minimizes a smooth quadratic approximation of the objective function using the conjugate gradient method.  These methods exploit the structure of the Hessian to efficiently compute the search direction and to avoid explicitly storing the Hessian.  We show that quasi-Newton methods are also effective in this context, and describe a limited memory BFGS variant of the orthant-based Newton method.  We present numerical results that suggest that all the techniques described in this paper have attractive properties and constitute useful tools for solving the sparse inverse covariance estimation problem. Comparisons with the method implemented in the QUIC software package are presented.
A Neural Autoregressive Topic Model
Authors: Stanislas Lauly Hugo Larochelle
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We describe a new model for learning meaningful representations of text documents from an unlabeled collection of documents. This model is inspired by the recently proposed Replicated Softmax, an undirected graphical model of word counts that was shown to learn a better generative model and more meaningful document representations. Specifically, we take inspiration from the conditional mean-field recursive equations of the Replicated Softmax in order to define a neural network architecture that estimates the probability of observing a new word in a given document given the previously observed words. This paradigm also allows us to replace the expensive softmax distribution over words with a hierarchical distribution over paths in a binary tree of words. The end result is a model whose training complexity scales logarithmically with the vocabulary size instead of linearly as in the Replicated Softmax. Our experiments show that our model is competitive both as a generative model of documents and as a document representation learning algorithm.
Active Learning of Multi-Index Function Models
Authors: Volkan Cevher Tyagi Hemant
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We consider the problem of actively learning \textit{multi-index} functions of the form $f(\vecx) = g(\matA\vecx)= \sum_{i=1}^k g_i(\veca_i^T\vecx)$ from point evaluations of $f$. We assume that the function $f$ is defined on an $\ell_2$-ball in $\Real^d$, $g$ is twice continuously differentiable almost everywhere, and $\matA \in \mathbb{R}^{k \times d}$ is a rank $k$ matrix, where $k \ll d$.  We propose a randomized, active sampling scheme for estimating such functions with uniform approximation guarantees. Our theoretical developments leverage recent techniques from low rank matrix recovery, which enables us to derive an estimator of the function $f$ along with sample complexity bounds. We also characterize the noise robustness of the scheme, and provide empirical evidence that the high-dimensional scaling of our sample complexity bounds are quite accurate.
Probabilistic Low-Rank Subspace Clustering
Authors: Shinichi Nakajima, Minh Do S. D. Babacan
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper, we consider the problem of clustering data points into low-dimensional subspaces in the presence of outliers. We pose the problem using a density estimation formulation with an associated generative model. Based on this probability model, we first develop an iterative expectation-maximization (EM) algorithm and then derive its global solution. In addition, we develop two Bayesian methods based on variational Bayesian (VB) approximation, which are capable of automatic dimensionality selection. While the first method is based on an alternating optimization scheme for all unknowns, the second method makes use of recent results in VB matrix factorization leading to fast and effective estimation. Both methods are extended to handle sparse outliers for robustness and can handle missing values. Experimental results suggest that proposed methods are very effective in clustering and identifying outliers.
Fully Bayesian inference for neural models with negative-binomial spiking
Authors: James Scott Jonathan W. Pillow
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Characterizing the information carried by neural populations in the brain requires accurate statistical models of neural spike responses.  The negative-binomial distribution provides a convenient model for over-dispersed spike counts, that is, responses with greater-than-Poisson variability.  Here we describe a powerful data-augmentation framework for fully Bayesian inference in neural models with negative-binomial spiking. Our approach relies on a recently described latent-variable representation of the negative-binomial distribution, which equates it to a Polya-gamma mixture of normals.  This framework provides a tractable, conditionally Gaussian representation of the posterior that can be used to design efficient EM and Gibbs sampling based algorithms for inference in regression and dynamic factor models.  We apply the model to neural data from primate retina and show that it substantially outperforms Poisson regression on held-out data, and reveals latent structure underlying spike count correlations in simultaneously recorded spike trains.
Adaptive Learning of Smoothing Functions: Application to Electricity Load Forecasting
Authors: Mathieu Sinn, Yannig Goude, Pascal Pompey Amadou Ba
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper proposes an efficient online learning algorithm to track the smoothing functions of Additive Models. The key idea is to combine the linear representation of Additive Models with a Recursive Least Squares (RLS) filter. In order to quickly track changes in the model and put more weight on recent data, the RLS filter uses a forgetting factor which exponentially weights down observations by the order of their arrival. The tracking behaviour is further enhanced by using an adaptive forgetting factor which is updated based on the gradient of the a priori errors. Using results from Lyapunov stability theory, upper bounds for the learning rate are analyzed. The proposed algorithm is applied to 5 years of electricity load data provided by the French utility company Electricite de France (EDF). Compared to state-of-the-art methods, it achieves a superior performance in terms of model tracking and prediction accuracy.
Complex Inference in Neural Circuits with Probabilistic Population Codes and Topic Models
Authors: Alexandre Pouget, Katherine A. Heller Jeff Beck
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Recent experiments have demonstrated that humans and animals typically reason probabilistically about their environment. This ability requires a neural code that represents probability distributions and neural circuits that are capable of implementing the operations of probabilistic inference. The proposed probabilistic population coding (PPC) framework provides a statistically efficient neural representation of probability distributions that is both broadly consistent with physiological measurements and capable of implementing some of the basic operations of probabilistic inference in a biologically plausible way. However, these experiments and the corresponding neural models have largely focused on simple (tractable) probabilistic computations such as cue combination, coordinate transformations, and decision making. As a result it remains unclear how to generalize this framework to more complex probabilistic computations. Here we address this short coming by showing that a very general approximate inference algorithm known as Variational Bayesian Expectation Maximization can be implemented within the linear PPC framework. We apply this approach to a generic problem faced by any given layer of cortex, namely the identification of latent causes of complex mixtures of spikes. We identify a formal equivalent between this spike pattern demixing problem and topic models used for document classification, in particular Latent Dirichlet Allocation (LDA). We then construct a neural network implementation of variational inference and learning for LDA that utilizes a linear PPC. This network relies critically on two non-linear operations: divisive normalization and super-linear facilitation, both of which are ubiquitously observed in neural circuits. We also demonstrate how online learning can be achieved using a variation of Hebb’s rule and describe an extesion of this work which allows us to deal with time varying and correlated latent causes.
Clustering by Nonnegative Matrix Factorization Using Graph Random Walk
Authors: Tele Hao, Onur Dikmen, Xi Chen, Erkki Oja Zhirong Yang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Nonnegative Matrix Factorization (NMF) is a promising relaxation technique for clustering analysis.  However, conventional NMF methods that directly approximate the pairwise similarities using the least square error often yield mediocre performance for data in curved manifolds because they can capture only the immediate similarities between data samples.  Here we propose a new NMF clustering method which replaces the approximated matrix with its smoothed version using random walk.  Our method can thus accommodate farther relationships between data samples.  Furthermore, we introduce a novel regularization in the proposed objective function in order to improve over spectral clustering.  The new learning objective is optimized by a multiplicative Majorization-Minimization algorithm with a scalable implementation for learning the factorizing matrix.  Extensive experimental results on real-world datasets show that our method has strong performance in terms of cluster purity.
Graphical Gaussian Vector for Image Categorization
Authors: Yasuo Kuniyoshi Tatsuya Harada
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper proposes a novel image representation called a Graphical Gaussian Vector, which is a counterpart of the codebook and local feature matching approaches. In our method, we model the distribution of local features as a Gaussian Markov Random Field (GMRF) which can efficiently represent the spatial relationship among local features. We consider the parameter of GMRF as a feature vector of the image. Using concepts of information geometry, proper parameters and a metric from the GMRF can be obtained. Finally we define a new image feature by embedding the metric into the parameters, which can be directly applied to scalable linear classifiers. Our method obtains superior performance over the state-of-the-art methods in the standard object recognition datasets and comparable performance in the scene dataset. As the proposed method simply calculates the local auto-correlations of local features, it is able to achieve both high classification accuracy and high efficiency.
Convergence Rate Analysis of MAP Coordinate Minimization Algorithms
Authors: Amir Globerson, Tommi S. Jaakkola Ofer Meshi
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Finding maximum aposteriori (MAP) assignments in graphical models is an important task in many applications. Since the problem is generally hard, linear programming (LP) relaxations are often used. Solving these relaxations efficiently is thus an important practical problem. In recent years, several authors have proposed message passing updates corresponding to coordinate descent in the dual LP. However,these are generally not guaranteed to converge to a global optimum. One approach to remedy this is to smooth the LP, and perform coordinate descent on the smoothed dual. However, little is known about the convergence rate of this procedure. Here we perform a thorough rate analysis of such schemes and derive primal and dual convergence rates. We also provide a simple dual to primal mapping that yields feasible primal solutions with a guaranteed rate of convergence. Empirical evaluation supports our theoretical claims and shows that the method is highly competitive with state of the art approaches that yield global optima.
Distributed Probabilistic Learning for Camera Networks with Missing Data
Authors: Vladimir Pavlovic Sejong Yoon
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Probabilistic approaches to computer vision typically assume a centralized setting, with the algorithm granted access to all observed data points.  However, many problems in wide-area surveillance can benefit from distributed modeling, either because of physical or computational constraints.  Most distributed models to date use algebraic approaches (such as distributed SVD) and as a result cannot explicitly deal with missing data.  In this work we present an approach to estimation and learning of generative probabilistic models in a distributed context where certain sensor data can be missing.  In particular, we show how traditional centralized models, such as probabilistic PCA and missing-data PPCA, can be learned when the data is distributed across a network of sensors.  We demonstrate the utility of this approach on the problem of distributed affine structure from motion.  Our experiments suggest that the accuracy of the learned probabilistic structure and motion models rivals that of traditional centralized factorization methods while being able to handle challenging situations such as missing or noisy observations.
Confusion-Based Online Learning and a Passive-Aggressive Scheme
Authors: Liva Ralaivola
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper provides the first ---to the best of our knowledge--- analysis of online learning algorithms for multiclass problems when the {\em confusion} matrix is taken as a performance measure. The work builds upon recent and elegant results on noncommutative concentration inequalities, i.e. concentration inequalities that apply to matrices, and more precisely to matrix martingales.  We do establish generalization bounds for online learning algorithm and show how the theoretical study motivate the proposition of a new confusion-friendly learning procedure. This learning algorithm, called \copa (for COnfusion Passive-Aggressive) is a passive-aggressive learning algorithm; it is shown that the update equations for \copa can be computed analytically, thus allowing the user from having to recours to any optimization package to implement it.