pwc-archive/papers-with-abstracts huggingface dataset:
How Prior Probability Influences Decision Making: A Unifying Probabilistic Model
Authors: Yanping Huang, Timothy Hanks, Mike Shadlen, Abram L. Friesen, Rajesh P. Rao
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Decision Making, Descriptive

How does the brain combine prior knowledge with sensory evidence when making decisions under uncertainty? Two competing descriptive models have been proposed based on experimental data.  The first posits an additive offset to a decision variable, implying a static effect of the prior. However, this model is inconsistent with recent data from a motion discrimination task involving temporal integration of uncertain sensory evidence. To explain this data, a second model has been proposed which assumes a time-varying influence of the prior. Here we present a normative model of decision making that incorporates prior knowledge in a principled way.  We show that the additive offset model and the time-varying prior model emerge naturally when decision making is viewed within the framework of partially observable Markov decision processes (POMDPs).  Decision making in the model reduces to (1) computing beliefs given observations and prior information in a Bayesian manner, and (2) selecting actions based on these beliefs to maximize the  expected sum of future rewards. We show that the model can explain both  data previously explained using the additive offset model as well as more  recent data on the time-varying influence of prior knowledge on decision making.
High-Order Multi-Task Feature Learning to Identify Longitudinal Phenotypic Markers for Alzheimer's Disease Progression Prediction
Authors: Hua Wang, Feiping Nie, Heng Huang, Jingwen Yan, Sungeun Kim, Shannon Risacher, Andrew Saykin, Li Shen
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Multi-Task Learning, regression

Alzheimer disease (AD) is a neurodegenerative disorder characterized by progressive impairment of memory and other cognitive functions. Regression analysis has been studied to relate neuroimaging measures to cognitive status. However, whether these measures have further predictive power to infer a trajectory of cognitive performance over time is still an under-explored but important topic in AD research. We propose a novel high-order multi-task learning model to address this issue. The proposed model explores the temporal correlations existing in data features and regression tasks by the structured sparsity-inducing norms. In addition, the sparsity of the model enables the selection of a small number of MRI measures while maintaining high prediction accuracy. The empirical studies, using the baseline MRI and serial cognitive data of the ADNI cohort, have yielded promising results.
Symmetric Correspondence Topic Models for Multilingual Text Analysis
Authors: Kosuke Fukumasu, Koji Eguchi, Eric P. Xing
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Topic Models

Topic modeling is a widely used approach to analyzing large text collections. A small number of multilingual topic models have recently been explored to discover latent topics among parallel or comparable documents, such as in Wikipedia. Other topic models that were originally proposed for structured data are also applicable to multilingual documents. Correspondence Latent Dirichlet Allocation (CorrLDA) is one such model; however, it requires a pivot language to be specified in advance. We propose a new topic model, Symmetric Correspondence LDA (SymCorrLDA), that incorporates a hidden variable to control a pivot language, in an extension of CorrLDA. We experimented with two multilingual comparable datasets extracted from Wikipedia and demonstrate that SymCorrLDA is more effective than some other existing multilingual topic models.
Effective Split-Merge Monte Carlo Methods for Nonparametric Models of Sequential Data
Authors: Michael C. Hughes, Emily Fox, Erik B. Sudderth
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Time Series, Time Series Analysis

Applications of Bayesian nonparametric methods require learning and inference algorithms which efficiently explore models of unbounded complexity. We develop new Markov chain Monte Carlo methods for the beta process hidden Markov model (BP-HMM), enabling discovery of shared activity patterns in large video and motion capture databases. By introducing split-merge moves based on sequential allocation, we allow large global changes in the shared feature structure. We also develop data-driven reversible jump moves which more reliably discover rare or unique behaviors. Our proposals apply to any choice of conjugate likelihood for observed data, and we show success with multinomial, Gaussian, and autoregressive emission models. Together, these innovations allow tractable analysis of hundreds of time series, where previous inference required clever initialization and at least ten thousand burn-in iterations for just six sequences.
Efficient Sampling for Bipartite Matching Problems
Authors: Maksims Volkovs, Richard S. Zemel
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Information Retrieval, Retrieval

Bipartite matching problems characterize many situations, ranging from ranking in information retrieval to correspondence in vision. Exact inference in real-world applications of these problems is intractable, making efficient approximation methods essential for learning and inference. In this paper we propose a novel {\it sequential matching} sampler based on the generalization of the Plackett-Luce model, which can effectively make large moves in the space of matchings. This allows the sampler to match the difficult target distributions common in these problems: highly multimodal distributions with well separated modes. We present experimental results with bipartite matching problems - ranking and image correspondence - which show that the sequential matching sampler efficiently approximates the target distribution, significantly outperforming other sampling approaches.
Learning visual motion in recurrent neural networks
Authors: Marius Pachitariu, Maneesh Sahani
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We present a dynamic nonlinear generative model for visual motion based on a latent representation of binary-gated Gaussian variables. Trained on sequences of images, the model learns to represent different movement directions in different variables. We use an online approximate-inference scheme that can be mapped to the dynamics of networks of neurons. Probed with drifting grating stimuli and moving bars of light, neurons in the model show patterns of responses analogous to those of direction-selective simple cells in primary visual cortex. Most model neurons also show speed tuning and respond equally well to a range of motion directions and speeds aligned to the constraint line of their respective preferred speed. We show how these computations are enabled by a specific pattern of recurrent connections learned by the model.
Learned Prioritization for Trading Off Accuracy and Speed
Authors: Jiarong Jiang, Adam Teichert, Jason Eisner, Hal Daume
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Imitation Learning, Reinforcement Learning

Users want natural language processing (NLP) systems to be both fast and accurate, but quality often comes at the cost of speed. The field has been manually exploring various speed-accuracy tradeoffs (for particular problems and datasets).  We aim to explore this space automatically, focusing here on the case of agenda-based syntactic parsing \cite{kay-1986}. Unfortunately, off-the-shelf reinforcement learning techniques fail to learn good policies: the state space is simply too large to explore naively. An attempt to counteract this by applying imitation learning algorithms also fails: the ``teacher'' is far too good to successfully imitate with our inexpensive features.  Moreover, it is not specifically tuned for the known reward function.  We propose a hybrid reinforcement/apprenticeship learning algorithm that, even with only a few inexpensive features, can automatically learn weights that achieve competitive accuracies at significant improvements in speed over state-of-the-art baselines.
Value Pursuit Iteration
Authors: Amir M. Farahmand, Doina Precup
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Reinforcement Learning, Reinforcement Learning (RL)

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.
Compressive neural representation of sparse, high-dimensional probabilities
Authors: Zachary Pitkow
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Compressive Sensing, Vocal Bursts Intensity Prediction

This paper shows how sparse, high-dimensional probability distributions could be represented by neurons with exponential compression. The representation is a novel application of compressive sensing to sparse probability distributions rather than to the usual sparse signals. The compressive measurements correspond to expected values of nonlinear functions of the probabilistically distributed variables. When these expected values are estimated by sampling, the quality of the compressed representation is limited only by the quality of sampling. Since the compression preserves the geometric structure of the space of sparse probability distributions, probabilistic computation can be performed in the compressed domain. Interestingly, functions satisfying the requirements of compressive sensing can be implemented as simple perceptrons. If we use perceptrons as a simple model of feedforward computation by neurons, these results show that the mean activity of a relatively small number of neurons can accurately represent a high-dimensional joint distribution implicitly, even without accounting for any noise correlations. This comprises a novel hypothesis for how neurons could encode probabilities in the brain.
Graphical Models via Generalized Linear Models
Authors: Eunho Yang, Genevera Allen, Zhandong Liu, Pradeep K. Ravikumar
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Undirected graphical models, or Markov networks, such as Gaussian graphical models and Ising models enjoy popularity in a variety of applications.  In many settings, however, data may not follow a Gaussian or binomial distribution assumed by these models. We introduce a new class of graphical models based on generalized linear models (GLM) by assuming that node-wise conditional distributions arise from exponential families.  Our models allow one to estimate networks for a wide class of exponential distributions, such as the Poisson, negative binomial, and exponential, by fitting penalized GLMs to select the neighborhood for each node. A major contribution of this paper is the rigorous statistical analysis showing that with high probability, the neighborhood of our graphical models can be recovered exactly. We provide examples of high-throughput genomic networks learned via our GLM graphical models for multinomial and Poisson distributed data.
CPRL -- An Extension of Compressive Sensing to the Phase Retrieval Problem
Authors: Henrik Ohlsson, Allen Yang, Roy Dong, Shankar Sastry
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Compressive Sensing, Retrieval

While compressive sensing (CS) has been one of the most vibrant and active research fields in the past few years, most development only applies to linear models. This limits its application and excludes many areas where CS ideas could make a difference. This paper presents a novel extension of CS to the phase retrieval problem, where intensity measurements of a linear system are used to recover a complex sparse signal. We propose a novel solution using a lifting technique -- CPRL, which relaxes the NP-hard problem to a nonsmooth semidefinite program. Our analysis shows that CPRL inherits many desirable properties from CS, such as guarantees for exact recovery. We further provide scalable numerical solvers to accelerate its implementation. The source code of our algorithms will be provided to the public.
Co-Regularized Hashing for Multimodal Data
Authors: Yi Zhen, Dit-yan Yeung
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Hashing-based methods provide a very promising approach to large-scale similarity search.  To obtain compact hash codes, a recent trend seeks to learn the hash functions from data automatically.  In this paper, we study hash function learning in the context of multimodal data.  We propose a novel multimodal hash function learning method, called Co-Regularized Hashing (CRH), based on a boosted co-regularization framework.  The hash functions for each bit of the hash codes are learned by solving DC (difference of convex functions) programs, while the learning for multiple bits proceeds via a boosting procedure so that the bias introduced by the hash functions can be sequentially minimized.  We empirically compare CRH with two state-of-the-art multimodal hash function learning methods on two publicly available data sets.
Convergence and Energy Landscape for Cheeger Cut Clustering
Authors: Xavier Bresson, Thomas Laurent, David Uminsky, James V. Brecht
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering

Unsupervised clustering of scattered, noisy and high-dimensional data points is an important and difficult problem. Continuous relaxations of balanced cut problems  yield excellent clustering results. This paper provides rigorous convergence results for two algorithms that solve the relaxed Cheeger Cut minimization.  The first algorithm is a new steepest descent algorithm and the second one is a slight modification of the Inverse Power Method algorithm \cite{pro:HeinBuhler10OneSpec}. While the steepest descent algorithm has better theoretical convergence properties,  in practice both algorithm perform equally.  We also completely characterize the local minima of the relaxed problem in terms of the original balanced cut problem, and relate this characterization to the convergence of the algorithms.
Symbolic Dynamic Programming for Continuous State and Observation POMDPs
Authors: Zahra Zamani, Scott Sanner, Pascal Poupart, Kristian Kersting
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Decision Making, Sequential Decision Making

Partially-observable Markov decision processes (POMDPs) provide a powerful model for real-world sequential decision-making problems. In recent years, point- based value iteration methods have proven to be extremely effective techniques for ﬁnding (approximately) optimal dynamic programming solutions to POMDPs when an initial set of belief states is known. However, no point-based work has provided exact point-based backups for both continuous state and observation spaces, which we tackle in this paper. Our key insight is that while there may be an inﬁnite number of possible observations, there are only a ﬁnite number of observation partitionings that are relevant for optimal decision-making when a ﬁnite, ﬁxed set of reachable belief states is known. To this end, we make two important contributions: (1) we show how previous exact symbolic dynamic pro- gramming solutions for continuous state MDPs can be generalized to continu- ous state POMDPs with discrete observations, and (2) we show how this solution can be further extended via recently developed symbolic methods to continuous state and observations to derive the minimal relevant observation partitioning for potentially correlated, multivariate observation spaces. We demonstrate proof-of- concept results on uni- and multi-variate state and observation steam plant control.
Bayesian Probabilistic Co-Subspace Addition
Authors: Lei Shi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Missing Values, Variational Inference

For modeling data matrices, this paper introduces Probabilistic Co-Subspace Addition (PCSA) model by simultaneously capturing the dependent structures among both rows and columns. Briefly, PCSA assumes that each entry of a matrix is generated by the additive combination of the linear mappings of two features, which distribute in the row-wise and column-wise latent subspaces. Consequently, it captures the dependencies among entries intricately, and is able to model the non-Gaussian and heteroscedastic density. Variational inference is proposed on PCSA for  approximate Bayesian learning, where the updating for posteriors is formulated into the problem of solving Sylvester equations. Furthermore, PCSA is extended to tackling and filling missing values, to adapting its sparseness, and to modelling tensor data. In comparison with several state-of-art approaches, experiments demonstrate the effectiveness and efficiency of Bayesian (sparse) PCSA on modeling matrix (tensor) data and filling missing values.
Scaled Gradients on Grassmann Manifolds for Matrix Completion
Authors: Thanh Ngo, Yousef Saad
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Low-Rank Matrix Completion, Matrix Completion

This paper describes gradient methods based on a scaled metric on the Grassmann manifold for low-rank matrix completion. The proposed methods significantly improve canonical gradient methods especially on ill-conditioned matrices, while maintaining established global convegence and exact recovery guarantees. A connection between a form of subspace iteration for matrix completion and the scaled gradient descent procedure is also established. The proposed conjugate gradient method based on the scaled gradient outperforms several existing algorithms for matrix completion and is competitive with recently proposed methods.
Q-MKL: Matrix-induced Regularization in Multi-Kernel Learning with Applications to Neuroimaging
Authors: Chris Hinrichs, Vikas Singh, Jiming Peng, Sterling Johnson
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Inductive Bias

Multiple Kernel Learning (MKL) generalizes SVMs to the setting where one simultaneously trains a linear classifier and chooses an optimal combination of given base kernels. Model complexity is typically controlled using various norm regularizations on the vector of base kernel mixing coefficients. Existing methods, however, neither regularize nor exploit potentially useful information pertaining to how kernels in the input set 'interact'; that is, higher order kernel-pair relationships that can be easily obtained via unsupervised (similarity, geodesics), supervised (correlation in errors), or domain knowledge driven mechanisms (which features were used to construct the kernel?). We show that by substituting the norm penalty with an arbitrary quadratic function Q \succeq 0, one can impose a desired covariance structure on mixing coefficient selection, and use this as an inductive bias when learning the concept. This formulation significantly generalizes the widely used 1- and 2-norm MKL objectives. We explore the model’s utility via experiments on a challenging Neuroimaging problem, where the goal is to predict a subject’s conversion to Alzheimer’s Disease (AD) by exploiting aggregate information from several distinct imaging modalities. Here, our new model outperforms the state of the art (p-values << 10−3 ). We briefly discuss ramifications in terms of learning bounds (Rademacher complexity).
Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods
Authors: Andre Wibisono, Martin J. Wainwright, Michael. I. Jordan, John C. Duchi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Stochastic Optimization

We consider derivative-free algorithms for stochastic optimization problems that use only noisy function values rather than gradients, analyzing their finite-sample convergence rates. We show that if pairs of function values are available, algorithms that use gradient estimates based on random perturbations suffer a factor of at most $\sqrt{\dim}$ in convergence rate over traditional stochastic gradient methods, where $\dim$ is the dimension of the problem. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, which show that our bounds are sharp with respect to all problem-dependent quantities: they cannot be improved by more than constant factors.
Hierarchical Optimistic Region Selection driven by Curiosity
Authors: Odalric-Ambrym Maillard
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Active Learning, Multi-Armed Bandits, Reinforcement Learning

This paper aims to take a step forwards making the term ``intrinsic motivation'' from reinforcement learning theoretically well founded, focusing on curiosity-driven learning. To that end, we consider the setting where, a fixed partition P of a continuous space X being given, and a process \nu defined on X being unknown, we are asked to sequentially decide which cell of the partition to select as well as where to sample \nu in that cell, in order to minimize a loss function that is inspired from previous work on curiosity-driven learning. The loss on each cell consists of one term measuring a simple worst case quadratic sampling error, and a penalty term proportional to the range of the variance in that cell. The corresponding problem formulation extends the setting known as active learning for multi-armed bandits to the case when each arm is a continuous region, and we show how an adaptation of recent algorithms for that problem and of hierarchical optimistic sampling algorithms for optimization can be used in order to solve this problem. The resulting procedure, called Hierarchical Optimistic Region SElection driven by Curiosity (HORSE.C) is provided together with a finite-time regret analysis.
Sparse Prediction with the k-Support Norm
Authors: Andreas Argyriou, Rina Foygel, Nathan Srebro
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Prediction

We derive a novel norm that corresponds to the tightest convex   relaxation of sparsity combined with an $\ell_2$ penalty. We show   that this new norm provides a tighter relaxation than the elastic   net, and is thus a good replacement for the Lasso or the elastic net   in sparse prediction problems.  But through studying our new norm,   we also bound the looseness of the elastic net, thus shedding new   light on it and providing justification for its use.
Active Learning of Multi-Index Function Models
Authors: Tyagi Hemant, Volkan Cevher
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Active Learning

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.