pwc-archive/papers-with-abstracts huggingface dataset:
A Nonparametric Conjugate Prior Distribution for the Maximizing Argument of a Noisy Function
Authors: Pedro Ortega, Jordi Grau-Moya, Tim Genewein, David Balduzzi, Daniel Braun
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Stochastic Optimization

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.
Convergence Rate Analysis of MAP Coordinate Minimization Algorithms
Authors: Ofer Meshi, Amir Globerson, Tommi S. Jaakkola
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

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.
Projection Retrieval for Classification
Authors: Madalina Fiterau, Artur Dubrawski
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, General Classification, regression, Retrieval

In many applications classification systems often require in the loop human intervention. In such cases the decision process must be transparent and comprehensible simultaneously requiring minimal assumptions on the underlying data distribution. To tackle this problem, we formulate it as an axis-alligned subspacefinding task under the assumption that query specific information dictates the complementary use of the subspaces. We develop a regression-based approach called RECIP that efficiently solves this problem by finding projections that minimize a nonparametric conditional entropy estimator. Experiments show that the method is accurate in identifying the informative projections of the dataset, picking the correct ones to classify query points and facilitates visual evaluation by users.
Hierarchical spike coding of sound
Authors: Yan Karklin, Chaitanya Ekanadham, Eero P. Simoncelli
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Denoising

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.
Human memory search as a random walk in a semantic network
Authors: Joseph L. Austerweil, Joshua T. Abbott, Thomas L. Griffiths
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Information Retrieval, Retrieval

The human mind has a remarkable ability to store a vast amount of information in memory, and an even more remarkable ability to retrieve these experiences when needed. Understanding the representations and algorithms that underlie human memory search could potentially be useful in other information retrieval settings, including internet search. Psychological studies have revealed clear regularities in how people search their memory, with clusters of semantically related items tending to be retrieved together. These findings have recently been taken as evidence that human memory search is similar to animals foraging for food in patchy environments, with people making a rational decision to switch away from a cluster of related information as it becomes depleted. We demonstrate that the results that were taken as evidence for this account also emerge from a random walk on a semantic network, much like the random web surfer model used in internet search engines. This offers a simpler and more unified account of how people search their memory, postulating a single process rather than one process for exploring a cluster and one process for switching between clusters.
Complex Inference in Neural Circuits with Probabilistic Population Codes and Topic Models
Authors: Jeff Beck, Alexandre Pouget, Katherine A. Heller
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Decision Making, Document Classification, Topic Models, Variational Inference

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.
Cost-Sensitive Exploration in Bayesian Reinforcement Learning
Authors: Dongho Kim, Kee-Eung Kim, Pascal Poupart
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In this paper, we consider Bayesian reinforcement learning (BRL) where actions incur costs in addition to rewards, and thus exploration has to be constrained in terms of the expected total cost while learning to maximize the expected long-term total reward. In order to formalize cost-sensitive exploration, we use the constrained Markov decision process (CMDP) as the model of the environment, in which we can naturally encode exploration requirements using the cost function. We extend BEETLE, a model-based BRL method, for learning in the environment with cost constraints. We demonstrate the cost-sensitive exploration behaviour in a number of simulated problems.
Learning with Partially Absorbing Random Walks
Authors: Xiao-Ming Wu, Zhenguo Li, Anthony M. So, John Wright, Shih-Fu Chang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We propose a novel stochastic process that is with probability $\alpha_i$ being absorbed at current state $i$, and with probability $1-\alpha_i$ follows a random edge out of it. We analyze its properties and show its potential for exploring graph structures. We prove that under proper absorption rates, a random walk starting from a set $\mathcal{S}$ of low conductance will be mostly absorbed in $\mathcal{S}$. Moreover, the absorption probabilities vary slowly inside $\mathcal{S}$, while dropping sharply outside $\mathcal{S}$, thus implementing the desirable cluster assumption for graph-based learning. Remarkably, the partially absorbing process unifies many popular models arising in a variety of contexts, provides new insights into them, and makes it possible for transferring findings from one paradigm to another. Simulation results demonstrate its promising applications in graph-based learning.
Locating Changes in Highly Dependent Data with Unknown Number of Change Points
Authors: Azadeh Khaleghi, Daniil Ryabko
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Time Series, Time Series Analysis

The problem of multiple change point estimation is  considered for sequences  with unknown number of change points.  A consistency framework is suggested that is suitable for highly dependent time-series, and an asymptotically consistent algorithm is proposed.   In order for the consistency to be established the only assumption  required is that the data is generated by stationary ergodic time-series distributions. No modeling, independence or parametric assumptions are made; the data are allowed to be dependent and the dependence can be of arbitrary form.  The theoretical results are complemented with experimental evaluations.
Probabilistic Event Cascades for Alzheimer's disease
Authors: Jonathan Huang, Daniel Alexander
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Accurate and detailed models of the progression of neurodegenerative diseases such as  Alzheimer's (AD) are crucially important for reliable early diagnosis and the determination and deployment of effective treatments. In this paper, we introduce the ALPACA (Alzheimer's disease Probabilistic Cascades) model, a generative model linking latent Alzheimer's progression dynamics to observable biomarker data. In contrast with previous works which model disease progression as a fixed ordering of events, we explicitly model the variability over such orderings among patients which is more realistic, particularly for highly detailed disease progression models. We describe efficient learning algorithms for ALPACA and discuss promising experimental results on a real cohort of Alzheimer's patients from the  Alzheimer's Disease Neuroimaging Initiative.
Efficient and direct estimation of a neural subunit model for sensory coding
Authors: Brett Vintch, Andrew Zaharia, J Movshon, Eero P. Simoncelli
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Many visual and auditory neurons have response properties that are well explained by pooling the rectified responses of a set of self-similar linear filters. These filters cannot be found using spike-triggered averaging (STA), which estimates only a single filter. Other methods, like spike-triggered covariance (STC), define a multi-dimensional response subspace, but require substantial amounts of data and do not produce unique estimates of the linear filters. Rather, they provide a linear basis for the subspace in which the filters reside. Here, we define a 'subunit' model as an LN-LN cascade, in which the first linear stage is restricted to a set of shifted ("convolutional") copies of a common filter, and the first nonlinear stage consists of rectifying nonlinearities that are identical for all filter outputs; we refer to these initial LN elements as the 'subunits' of the receptive field. The second linear stage then computes a weighted sum of the responses of the rectified subunits. We present a method for directly fitting this model to spike data. The method performs well for both simulated and real data (from primate V1), and the resulting model outperforms STA and STC in terms of both cross-validated accuracy and efficiency.
One Permutation Hashing
Authors: Ping Li, Art Owen, Cun-Hui Zhang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

While minwise hashing is promising for large-scale learning in massive binary data, the preprocessing cost is prohibitive as it requires applying (e.g.,) $k=500$ permutations on the data. The testing time is also  expensive if a new data point (e.g., a new document or a new image) has not been processed.  In this paper, we develop a simple \textbf{one permutation hashing} scheme to address this important issue. While it is true that the preprocessing step can be parallelized, it comes at the cost of additional hardware and implementation. Also, reducing $k$ permutations to just one  would be much more \textbf{energy-efficient}, which might be an important perspective as minwise hashing is commonly deployed in the search industry. While the theoretical probability analysis is  interesting, our experiments on similarity estimation and   SVM \& logistic regression also confirm the theoretical results.
Unsupervised Template Learning for Fine-Grained Object Recognition
Authors: Shulin Yang, Liefeng Bo, Jue Wang, Linda G. Shapiro
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Object, Object Recognition

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.
Fast Bayesian Inference for Non-Conjugate Gaussian Process Regression
Authors: Emtiyaz Khan, Shakir Mohamed, Kevin P. Murphy
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Bayesian Inference, Gaussian Processes, General Classification, Multi-class Classification, regression, Variational Inference

We present a new variational inference algorithm for Gaussian processes with non-conjugate likelihood functions. This includes binary and multi-class classification, as well as ordinal regression. Our method constructs a convex lower bound, which can be optimized by using an efficient fixed point update method. We then show empirically that our new approach is much faster than existing methods without any degradation in performance.
Imitation Learning by Coaching
Authors: He He, Jason Eisner, Hal Daume
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: feature selection, Imitation Learning

Imitation Learning has been shown to be successful in solving many challenging real-world problems. Some recent approaches give strong performance guarantees by training the policy iteratively. However, it is important to note that these guarantees depend on   how well the policy we found can imitate the oracle on the training data.  When there is a substantial difference between the oracle's ability  and the learner's policy space, we may fail to find a policy that has low error on the training set. In such cases, we propose to use a coach that demonstrates easy-to-learn actions for the learner  and gradually approaches the oracle. By a reduction of learning by demonstration to online learning,  we prove that coaching can yield a lower regret bound than using the oracle. We apply our algorithm to a novel cost-sensitive dynamic feature selection problem, a hard decision problem that considers a user-specified accuracy-cost trade-off.  Experimental results on UCI datasets show that our method outperforms state-of-the-art imitation learning methods in dynamic features selection and two static feature selection methods.
Small-Variance Asymptotics for Exponential Family Dirichlet Process Mixture Models
Authors: Ke Jiang, Brian Kulis, Michael. I. Jordan
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering

Links between probabilistic and non-probabilistic learning algorithms can arise by performing small-variance asymptotics, i.e., letting the variance of particular distributions in a graphical model go to zero. For instance, in the context of clustering, such an approach yields precise connections between the k-means and EM algorithms.  In this paper, we explore small-variance asymptotics for exponential family Dirichlet process (DP) and hierarchical Dirichlet process (HDP) mixture models.  Utilizing connections between exponential family distributions and Bregman divergences, we derive novel clustering algorithms from the asymptotic limit of the DP and HDP mixtures that feature the scalability of existing hard clustering methods as well as the flexibility of Bayesian nonparametric models.  We focus on special cases of our analysis for discrete-data problems, including topic modeling, and we demonstrate the utility of our results by applying variants of our algorithms to problems arising in vision and document analysis.
A latent factor model for highly multi-relational data
Authors: Rodolphe Jenatton, Nicolas L. Roux, Antoine Bordes, Guillaume R. Obozinski
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Many data such as social networks, movie preferences or knowledge bases are multi-relational, in that they describe multiple relationships between entities. While there is a large body of work focused on modeling these data, few considered modeling these multiple types of relationships jointly. Further, existing approaches tend to breakdown when the number of these types grows. In this paper, we propose a method for modeling large multi-relational datasets, with possibly thousands of relations. Our model is based on a bilinear structure, which captures the various orders of interaction of the data, but also shares sparse latent factors across different relations. We illustrate the performance of our approach on standard tensor-factorization datasets where we attain, or outperform, state-of-the-art results. Finally, a NLP application demonstrates our scalability and the ability of our model to learn efficient, and semantically meaningful verb representations.
Entropy Estimations Using Correlated Symmetric Stable Random Projections
Authors: Ping Li, Cun-Hui Zhang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Methods for efficiently estimating the Shannon entropy of data streams have important applications in learning, data mining, and network anomaly detections (e.g., the DDoS attacks). For nonnegative data streams, the method of Compressed Counting (CC) based on maximally-skewed stable random projections can provide accurate estimates of the Shannon entropy using small storage. However, CC is no longer applicable when entries of data streams can be below zero, which is a common scenario when comparing two streams. In this paper, we propose an algorithm for entropy estimation in general data streams which allow negative entries. In our method, the Shannon entropy is approximated by the finite difference of two correlated frequency moments estimated from correlated samples of symmetric stable random variables. Our experiments confirm that this method is able to substantially better approximate the Shannon entropy compared to the prior state-of-the-art.
Simultaneously Leveraging Output and Task Structures for Multiple-Output Regression
Authors: Piyush Rai, Abhishek Kumar, Hal Daume
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: parameter estimation, regression

Multiple-output regression models require estimating multiple functions, one for each output. To improve parameter estimation in such models, methods based on structural regularization of the model parameters are usually needed. In this paper, we present a multiple-output regression model that leverages the covariance structure of the functions (i.e., how the multiple functions are related with each other) as well as the conditional covariance structure of the outputs. This is in contrast with existing methods that usually take into account only one of these structures. More importantly, unlike most of the other existing methods, none of these structures need be known a priori in our model, and are learned from the data. Several previously proposed structural regularization based  multiple-output regression models turn out to be special cases of our model. Moreover, in addition to being a rich model for multiple-output regression, our model can also be used in estimating the graphical model structure of a set of variables (multivariate outputs) conditioned on another set of variables (inputs). Experimental results on both synthetic and real datasets demonstrate the effectiveness of our method.
Continuous Relaxations for Discrete Hamiltonian Monte Carlo
Authors: Yichuan Zhang, Zoubin Ghahramani, Amos J. Storkey, Charles A. Sutton
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Continuous relaxations play an important role in discrete optimization, but have not seen much use in approximate probabilistic inference. Here we show that a general form of the Gaussian Integral Trick makes it possible to transform a wide class of discrete variable undirected models into fully continuous systems. The continuous representation allows the use of gradient-based Hamiltonian Monte Carlo for inference,  results in new ways of estimating normalization constants (partition functions), and in general opens up a number of new avenues for inference in difficult discrete systems. We demonstrate some of these continuous relaxation inference algorithms on a number of illustrative problems.
Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence
Authors: Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We study the problem of identifying the best arm(s) in the stochastic multi-armed bandit setting. This problem has been studied in the literature from two different perspectives: fixed budget and fixed confidence. We propose a unifying approach that leads to a meta-algorithm called unified gap-based exploration (UGapE), with a common structure and similar theoretical analysis for these two settings. We prove a performance bound for the two versions of the algorithm showing that the two problems are characterized by the same notion of complexity. We also show how the UGapE algorithm as well as its theoretical analysis can be extended to take into account the variance of the arms and to multiple bandits. Finally, we evaluate the performance of UGapE and compare it with a number of existing fixed budget and fixed confidence algorithms.