pwc-archive/papers-with-abstracts huggingface dataset:
MAP Inference in Chains using Column Generation
Authors: David Belanger, Alexandre Passos, Sebastian Riedel, Andrew McCallum
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), Part-Of-Speech Tagging

Linear chains and trees are basic building blocks in many applications of graphical models.  Although exact inference in these models can be performed by dynamic programming, this computation can still be prohibitively expensive with non-trivial target variable domain sizes due to the quadratic dependence on this size.  Standard message-passing algorithms for these problems are inefficient because they compute scores on hypotheses for which there is strong negative local evidence.  For this reason there has been significant previous interest in beam search and its variants; however, these methods provide only approximate inference.  This paper presents new efficient exact inference algorithms based on the combination of it column generation and pre-computed bounds on the model's cost structure.  Improving worst-case performance is impossible. However, our method substantially speeds real-world, typical-case inference in chains and trees.  Experiments show our method to be twice as fast as exact Viterbi for Wall Street Journal part-of-speech tagging and over thirteen times faster for a joint part-of-speed and named-entity-recognition task.  Our algorithm is also extendable to new techniques for approximate inference, to faster two-best inference, and new opportunities for connections between inference and learning.
Bayesian Nonparametric Modeling of Suicide Attempts
Authors: Francisco Ruiz, Isabel Valera, Carlos Blanco, Fernando Pérez-Cruz
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The National Epidemiologic Survey on Alcohol and Related Conditions (NESARC) database contains a large amount of information, regarding the way of life, medical conditions, depression, etc., of a representative sample of the U.S. population. In the present paper, we are interested in seeking the hidden causes behind the suicide attempts, for which we propose to model the subjects using a nonparametric latent model based on the Indian Buffet Process (IBP). Due to the nature of the data, we need to adapt the observation model for discrete random variables. We propose a generative model in which the observations are drawn from a multinomial-logit distribution given the IBP matrix. The implementation of an efficient Gibbs sampler is accomplished using the Laplace approximation, which allows us to integrate out the weighting factors of the  multinomial-logit likelihood model. Finally, the experiments over the NESARC database show that our model properly captures some of the hidden causes that model suicide attempts.
Fiedler Random Fields: A Large-Scale Spectral Approach to Statistical Network Modeling
Authors: Antonino Freno, Mikaela Keller, Marc Tommasi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Statistical models for networks have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are explicitly designed for capturing some specific graph properties (such as power-law degree distributions), which makes them unsuitable for application to domains where the behavior of the target quantities is not known a priori. The key contribution of this paper is twofold. First, we introduce the Fiedler delta statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random field model, which allows for efficient estimation of edge distributions over large-scale random networks. After analyzing the dependence structure involved in Fiedler random fields, we estimate them over several real-world networks, showing that they achieve a much higher modeling accuracy than other well-known statistical approaches.
Neurally Plausible Reinforcement Learning of Working Memory Tasks
Authors: Jaldert Rombouts, Pieter Roelfsema, Sander M. Bohte
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Decision Making, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

A key function of brains is undoubtedly the abstraction and maintenance of information from the environment for later use. Neurons in association cortex play an important role in this process: during learning these neurons become tuned to relevant features and represent the information that is required later as a persistent elevation of their activity. It is however not well known how these neurons acquire their task-relevant tuning. Here we introduce a biologically plausible learning scheme that explains how neurons become selective for relevant information when animals learn by trial and error. We propose that the action selection stage feeds back attentional signals to earlier processing levels. These feedback signals interact with feedforward signals to form synaptic tags at those connections that are responsible for the stimulus-response mapping. A globally released neuromodulatory signal interacts with these tagged synapses to determine the sign and strength of plasticity. The learning scheme is generic because it can train networks in different tasks, simply by varying inputs and rewards. It explains how neurons in association cortex learn to (1) temporarily store task-relevant information in non-linear stimulus-response mapping tasks and (2) learn to optimally integrate probabilistic evidence for perceptual decision making.
Efficient Monte Carlo Counterfactual Regret Minimization in Games with Many Player Actions
Authors: Neil Burch, Marc Lanctot, Duane Szafron, Richard G. Gibson
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: counterfactual

Counterfactual Regret Minimization (CFR) is a popular, iterative algorithm for computing strategies in extensive-form games. The Monte Carlo CFR (MCCFR) variants reduce the per iteration time cost of CFR by traversing a sampled portion of the tree. The previous most effective instances of MCCFR can still be very slow in games with many player actions since they sample every action for a given player. In this paper, we present a new MCCFR algorithm, Average Strategy Sampling (AS), that samples a subset of the player's actions according to the player's average strategy. Our new algorithm is inspired by a new, tighter bound on the number of iterations required by CFR to converge to a given solution quality. In addition, we prove a similar, tighter bound for AS and other popular MCCFR variants. Finally, we validate our work by demonstrating that AS converges faster than previous MCCFR algorithms in both no-limit poker and Bluff.
Repulsive Mixtures
Authors: Francesca Petralia, Vinayak Rao, David B. Dunson
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Multi-Task Learning

Discrete mixtures are used routinely in broad sweeping applications ranging from unsupervised settings to fully supervised multi-task learning.  Indeed, finite mixtures and infinite mixtures, relying on Dirichlet processes and modifications, have become a standard tool.  One important issue that arises in using discrete mixtures is low separation in the components; in particular, different components can be introduced that are very similar and hence redundant.   Such redundancy leads to too many clusters that are too similar, degrading performance in unsupervised learning and leading to computational problems and an unnecessarily complex model in supervised settings.  Redundancy can arise in the absence of a penalty on components placed close together even when a Bayesian approach is used to learn the number of components.  To solve this problem, we propose a novel prior that generates components from a repulsive process, automatically penalizing redundant components.  We characterize this repulsive prior theoretically and propose a Markov chain Monte Carlo sampling algorithm for posterior computation.  The methods are illustrated using synthetic examples and an iris data set.
Fully Bayesian inference for neural models with negative-binomial spiking
Authors: James Scott, Jonathan W. Pillow
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Bayesian Inference, Data Augmentation, regression

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.
Slice Normalized Dynamic Markov Logic Networks
Authors: Tivadar Papai, Henry Kautz, Daniel Stefankovic
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Relational Reasoning, Rolling Shutter Correction

Markov logic is a widely used tool in statistical relational learning, which uses a weighted first-order logic knowledge base to specify a Markov random field (MRF) or a conditional random field (CRF). In many applications, a Markov logic network (MLN) is trained in one domain, but used in a different one. This paper focuses on dynamic Markov logic networks, where the domain of time points typically varies between training and testing. It has been previously pointed out that the marginal probabilities of truth assignments to ground atoms can change if one extends or reduces the domains of predicates in an MLN. We show that in addition to this problem, the standard way of unrolling a Markov logic theory into a MRF may result in time-inhomogeneity of the underlying Markov chain. Furthermore, even if these representational problems are not significant for a given domain, we show that the more practical problem of generating samples in a sequential conditional random field for the next slice relying on the samples from the previous slice has high computational cost in the general case, due to the need to estimate a normalization factor for each sample. We propose a new discriminative model, slice normalized dynamic Markov logic networks (SN-DMLN), that suffers from none of these issues. It supports efficient online inference, and can directly model influences between variables within a time slice that do not have a causal direction, in contrast with fully directed models (e.g., DBNs). Experimental results show an improvement in accuracy over previous approaches to online inference in dynamic Markov logic networks.
Meta-Gaussian Information Bottleneck
Authors: Melanie Rey, Volker Roth
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We present a reformulation of the information bottleneck (IB) problem in terms of copula, using the equivalence between mutual information and negative copula  entropy. Focusing on the Gaussian copula we extend the analytical IB solution available for the multivariate Gaussian case to distributions with a Gaussian dependence structure but arbitrary marginal densities, also called meta-Gaussian distributions. This opens new possibles applications of IB to continuous data and provides a solution more robust to outliers.
Diffusion Decision Making for Adaptive k-Nearest Neighbor Classification
Authors: Yung-Kyun Noh, Frank Park, Daniel D. Lee
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, Decision Making, General Classification

This paper sheds light on some fundamental connections of the diffusion decision making model of neuroscience and cognitive psychology with k-nearest neighbor classification.  We show that conventional k-nearest neighbor classification can be viewed as a special problem of the diffusion decision model in the asymptotic situation.  Applying the optimal strategy associated with the diffusion decision model, an adaptive rule is developed for determining appropriate values of k in k-nearest neighbor classification.  Making use of the sequential probability ratio test (SPRT) and Bayesian analysis, we propose five different criteria for adaptively acquiring nearest neighbors.  Experiments with both synthetic and real datasets demonstrate the effectivness of our classification criteria.
The Perturbed Variation
Authors: Maayan Harel, Shie Mannor
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Two-sample testing

We introduce a new discrepancy score between two distributions that gives an indication on their \emph{similarity}. While much research has been done to determine if two samples come from exactly the same distribution, much less research considered the problem of determining if two finite samples come from similar distributions. The new score gives an intuitive interpretation of similarity;  it optimally perturbs the distributions so that they best fit each other. The score is defined between distributions, and can be efficiently estimated from samples. We provide convergence bounds of the estimated score, and develop hypothesis testing procedures that test if two data sets come from similar distributions. The statistical power of this procedures is presented in simulations. We also compare the score's capacity to detect similarity with that of other known measures on real data.
Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization
Authors: Konstantinos Tsianos, Sean Lawlor, Michael G. Rabbat
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Distributed Optimization, Metric Learning

We study the scalability of consensus-based distributed optimization algorithms by considering two questions: How many processors should we use for a given problem, and how often should they communicate when communication is not free? Central to our analysis is a problem-specific value $r$ which quantifies the communication/computation tradeoff. We show that organizing the communication among nodes as a $k$-regular expander graph~\cite{kRegExpanders} yields speedups, while when all pairs of nodes communicate (as in a complete graph), there is an optimal number of processors that depends on $r$. Surprisingly, a speedup can be obtained, in terms of the time to reach a fixed level of accuracy, by communicating less and less frequently as the computation progresses. Experiments on a real cluster solving metric learning and non-smooth convex minimization tasks demonstrate strong agreement between theory and practice.
The Coloured Noise Expansion and Parameter Estimation of Diffusion Processes
Authors: Simon Lyons, Amos J. Storkey, Simo Särkkä
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: parameter estimation

Stochastic differential equations (SDE) are a natural tool for modelling systems that are inherently noisy or contain uncertainties that can be modelled as stochastic processes. Crucial to the process of using SDE to build mathematical models is the ability to estimate parameters of those models from observed data. Over the past few decades, significant progress has been made on this problem, but we are still far from having a definitive solution. We describe a novel method of approximating a diffusion process that we show to be useful in Markov chain Monte-Carlo (MCMC) inference algorithms. We take the ‘white’ noise that drives a diffusion process and decompose it into two terms. The first is a ‘coloured noise’ term that can be deterministically controlled by a set of auxilliary variables. The second term is small and enables us to form a linear Gaussian ‘small noise’ approximation. The decomposition allows us to take a diffusion process of interest and cast it in a form that is amenable to sampling by MCMC methods. We explain why many state-of-the-art inference methods fail on highly nonlinear inference problems. We demonstrate experimentally that our method performs well in such situations. Our results show that this method is a promising new tool for use in inference and parameter estimation problems.
Online allocation and homogeneous partitioning for piecewise constant mean-approximation
Authors: Alexandra Carpentier, Odalric-Ambrym Maillard
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Active Learning

In the setting of active learning for the multi-armed bandit, where the goal of a learner is to estimate with equal precision the mean of a finite number of arms, recent results show that it is possible to derive strategies based on finite-time confidence bounds that are competitive with the best possible strategy. We here consider an extension of this problem to the case when the arms are the cells of a finite partition P of a continuous sampling space X \subset \Real^d. Our goal is now to build a piecewise constant approximation of a noisy function (where each piece is one region of P and P is fixed beforehand) in order to maintain the local quadratic error of approximation on each cell equally low. Although this extension is not trivial, we show that a simple algorithm based on upper confidence bounds can be proved to be adaptive to the function itself in a near-optimal way, when |P| is chosen to be of minimax-optimal order  on the class of \alpha-Hölder functions.
Learning as MAP Inference in Discrete Graphical Models
Authors: Xianghang Liu, James Petterson, Tibério S. Caetano
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Binary Classification, feature selection

We present a new formulation for attacking binary classification problems. Instead of relying on convex losses and regularisers such as in SVMs, logistic regression and boosting, or instead non-convex but continuous formulations such as those encountered in neural networks and deep belief networks, our framework entails a non-convex but \emph{discrete} formulation, where estimation amounts to finding a MAP configuration in a graphical model whose potential functions are low-dimensional discrete surrogates for the misclassification loss. We argue that such a discrete formulation can naturally account for a number of issues that are typically encountered in either the convex or the continuous non-convex paradigms, or both. By reducing the learning problem to a MAP inference problem, we can immediately translate the guarantees available for many inference settings to the learning problem itself. We empirically demonstrate in a number of experiments that this approach is promising in dealing with issues such as severe label noise, while still having global optimality guarantees. Due to the discrete nature of the formulation, it also allows for \emph{direct} regularisation through cardinality-based penalties, such as the $\ell_0$ pseudo-norm, thus providing the ability to perform feature selection and trade-off interpretability and predictability in a principled manner. We also outline a number of open problems arising from the formulation.
A mechanistic model of early sensory processing based on subtracting sparse representations
Authors: Shaul Druckmann, Tao Hu, Dmitri B. Chklovskii
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Early stages of sensory systems face the challenge of compressing information from numerous receptors onto a much smaller number of projection neurons, a so called communication bottleneck. To make more efficient use of limited bandwidth, compression may be achieved using predictive coding, whereby predictable, or redundant, components of the stimulus are removed. In the case of the retina, Srinivasan et al. (1982) suggested that feedforward inhibitory connections subtracting a linear prediction generated from nearby receptors implement such compression, resulting in biphasic center-surround receptive fields. However, feedback inhibitory circuits are common in early sensory circuits and furthermore their dynamics may be nonlinear. Can such circuits implement predictive coding as well? Here, solving the transient dynamics of nonlinear reciprocal feedback circuits through analogy to a signal-processing algorithm called linearized Bregman iteration we show that nonlinear predictive coding can be implemented in an inhibitory feedback circuit. In response to a step stimulus, interneuron activity in time constructs progressively less sparse but more accurate representations of the stimulus, a temporally evolving prediction. This analysis provides a powerful theoretical framework to interpret and understand the dynamics of early sensory processing in a variety of physiological experiments and yields novel predictions regarding the relation between activity and stimulus statistics.
Multi-Stage Multi-Task Feature Learning
Authors: Pinghua Gong, Jieping Ye, Chang-Shui Zhang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: parameter estimation

Multi-task sparse feature learning aims to improve the generalization performance by exploiting the shared features among tasks. It has been successfully applied to many applications including computer vision and biomedical informatics. Most of the existing multi-task sparse feature learning algorithms are formulated as a convex sparse regularization problem, which is usually suboptimal, due to its looseness for approximating an $\ell_0$-type regularizer. In this paper, we propose a non-convex formulation for multi-task sparse feature learning based on a novel regularizer. To solve the non-convex optimization problem, we propose a Multi-Stage Multi-Task Feature Learning (MSMTFL) algorithm. Moreover, we present a detailed theoretical analysis showing that MSMTFL achieves a better parameter estimation error bound than the convex formulation. Empirical studies on both synthetic and real-world data sets demonstrate the effectiveness of MSMTFL in comparison with the state of the art multi-task sparse feature learning algorithms.
From Deformations to Parts: Motion-based Segmentation of 3D Objects
Authors: Soumya Ghosh, Matthew Loper, Erik B. Sudderth, Michael J. Black
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, Object

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.