pwc-archive/papers-with-abstracts huggingface dataset:
Modelling Reciprocating Relationships with Hawkes Processes
Authors: Charles Blundell, Jeff Beck, Katherine A. Heller
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Time Series, Time Series Analysis

We present a Bayesian nonparametric model that discovers implicit social structure from interaction time-series data. Social groups are often formed implicitly, through actions among members of groups. Yet many models of social networks use explicitly declared relationships to infer social structure. We consider a particular class of Hawkes processes, a doubly stochastic point process, that is able to model reciprocity between groups of individuals. We then extend the Infinite Relational Model by using these reciprocating Hawkes processes to parameterise its edges, making events associated with edges co-dependent through time. Our model outperforms general, unstructured Hawkes processes as well as structured Poisson process-based models at predicting verbal and email turn-taking, and military conflicts among nations.
Expectation Propagation in Gaussian Process Dynamical Systems
Authors: Marc Deisenroth, Shakir Mohamed
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Time Series, Time Series Analysis

Rich and complex time-series data, such as those generated from engineering sys- tems, financial markets, videos or neural recordings are now a common feature of modern data analysis. Explaining the phenomena underlying these diverse data sets requires flexible and accurate models. In this paper, we promote Gaussian process dynamical systems as a rich model class appropriate for such analysis. In particular, we present a message passing algorithm for approximate inference in GPDSs based on expectation propagation. By phrasing inference as a general mes- sage passing problem, we iterate forward-backward smoothing. We obtain more accurate posterior distributions over latent structures, resulting in improved pre- dictive performance compared to state-of-the-art GPDS smoothers, which are spe- cial cases of our general iterative message passing algorithm. Hence, we provide a unifying approach within which to contextualize message passing in GPDSs.
Exact and Stable Recovery of Sequences of Signals with Sparse Increments via Differential _1-Minimization
Authors: Demba Ba, Behtash Babadi, Patrick Purdon, Emery Brown
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Compressive Sensing

We consider the problem of recovering a sequence of vectors, $(x_k)_{k=0}^K$, for which the increments $x_k-x_{k-1}$ are $S_k$-sparse (with $S_k$ typically smaller than $S_1$), based on linear measurements $(y_k = A_k x_k + e_k)_{k=1}^K$, where $A_k$ and $e_k$ denote the measurement matrix and noise, respectively. Assuming each $A_k$ obeys the restricted isometry property (RIP) of a certain order---depending only on $S_k$---we show that in the absence of noise a convex program, which minimizes the weighted sum of the $\ell_1$-norm of successive differences subject to the linear measurement constraints, recovers the sequence $(x_k)_{k=1}^K$ \emph{exactly}. This is an interesting result because this convex program is equivalent to a standard compressive sensing problem with a highly-structured aggregate measurement matrix which does not satisfy the RIP requirements in the standard sense, and yet we can achieve exact recovery. In the presence of bounded noise, we propose a quadratically-constrained convex program for recovery and derive bounds on the reconstruction error of the sequence. We supplement our theoretical analysis with simulations and an application to real video data. These further support the validity of the proposed approach for acquisition and recovery of signals with time-varying sparsity.
Multilabel Classification using Bayesian Compressed Sensing
Authors: Ashish Kapoor, Raajay Viswanathan, Prateek Jain
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Active Learning, Classification, compressed sensing, General Classification, Missing Labels, Prediction, Variational Inference

In this paper, we present a Bayesian framework for multilabel classification using compressed sensing. The key idea in compressed sensing for multilabel classification is to first project the label vector to a lower dimensional space using a random transformation and then learn regression functions over these projections. Our approach considers both of these components in a single probabilistic model, thereby jointly optimizing over compression as well as learning tasks. We then derive an efficient variational inference scheme that provides joint posterior distribution over all the unobserved labels. The two key benefits of the model are that a) it can naturally handle datasets that have  missing labels and b) it can also measure uncertainty in prediction. The uncertainty estimate provided by the model naturally allows for active learning paradigms where an oracle provides information about labels that promise to be maximally informative for the prediction task. Our experiments show significant boost over prior methods in terms of prediction performance over benchmark datasets, both in the fully labeled and the missing labels case.  Finally, we also highlight various useful active learning scenarios that are enabled by the probabilistic model.
Scaling MPE Inference for Constrained Continuous Markov Random Fields with Consensus Optimization
Authors: Stephen Bach, Matthias Broecheler, Lise Getoor, Dianne O'Leary
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Probabilistic graphical models are powerful tools for analyzing constrained, continuous domains. However, finding most-probable explanations (MPEs) in these models can be computationally expensive. In this paper, we improve the scalability of MPE inference in a class of graphical models with piecewise-linear and piecewise-quadratic dependencies and linear constraints over continuous domains. We derive algorithms based on a consensus-optimization framework and demonstrate their superior performance over state of the art. We show empirically that in a large-scale voter-preference modeling problem our algorithms scale linearly in the number of dependencies and constraints.
A Stochastic Gradient Method with an Exponential Convergence _Rate for Finite Training Sets
Authors: Nicolas L. Roux, Mark Schmidt, Francis R. Bach
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: BIG-bench Machine Learning

We propose a new stochastic gradient method for optimizing the sum of  a finite set of smooth functions, where the sum is strongly convex.  While standard stochastic gradient methods  converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence  rate.  In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard  algorithms, both in terms of optimizing the training error and reducing the test error quickly.
Query Complexity of Derivative-Free Optimization
Authors: Kevin G. Jamieson, Robert Nowak, Ben Recht
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Text-to-Image Generation

Derivative Free Optimization (DFO) is attractive when the objective function's derivatives are not available and evaluations are costly.   Moreover, if the function evaluations are noisy, then approximating gradients by finite differences is difficult.  This paper gives quantitative lower bounds on the performance of DFO with noisy function evaluations, exposing a fundamental and unavoidable gap between optimization performance based on noisy evaluations versus noisy gradients. This challenges the conventional wisdom that the method of finite differences is comparable to a stochastic gradient.  However, there are situations in which DFO is unavoidable, and for such situations we propose a new DFO algorithm that is proved to be near optimal for the class of strongly convex objective functions.  A distinctive feature of the algorithm is that it only uses Boolean-valued function comparisons, rather than evaluations.  This makes the algorithm useful in an even wider range of applications, including optimization based on paired comparisons from human subjects, for example.  Remarkably, we show that regardless of whether DFO is based on noisy function evaluations or Boolean-valued function comparisons, the convergence rate is the same.
Emergence of Object-Selective Features in Unsupervised Feature Learning
Authors: Adam Coates, Andrej Karpathy, Andrew Y. Ng
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering

Recent work in unsupervised feature learning has focused on the goal   of discovering high-level features from unlabeled images.  Much   progress has been made in this direction, but in most cases it is   still standard to use a large amount of labeled data in order to   construct detectors sensitive to object classes or other complex   patterns in the data.  In this paper, we aim to test the hypothesis   that unsupervised feature learning methods, provided with only   unlabeled data, can learn high-level, invariant features that are   sensitive to commonly-occurring objects.  Though a handful of prior   results suggest that this is possible when each object class   accounts for a large fraction of the data (as in many labeled   datasets), it is unclear whether something similar can be   accomplished when dealing with completely unlabeled data.  A major   obstacle to this test, however, is scale: we cannot expect to   succeed with small datasets or with small numbers of learned   features.  Here, we propose a large-scale feature learning system   that enables us to carry out this experiment, learning 150,000   features from tens of millions of unlabeled images.  Based on two   scalable clustering algorithms (K-means and agglomerative   clustering), we find that our simple system can discover features   sensitive to a commonly occurring object class (human faces) and can   also combine these into detectors invariant to significant global   distortions like large translations and scale.
Burn-in, bias, and the rationality of anchoring
Authors: Falk Lieder, Tom Griffiths, Noah Goodman
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Bayesian Inference

Bayesian inference provides a unifying framework for addressing problems in machine learning, artificial intelligence, and robotics, as well as the problems facing the human mind. Unfortunately, exact Bayesian inference is intractable in all but the simplest models. Therefore minds and machines have to approximate Bayesian inference. Approximate inference algorithms can achieve a wide range of time-accuracy tradeoffs, but what is the optimal tradeoff? We investigate time-accuracy tradeoffs using the Metropolis-Hastings algorithm as a metaphor for the mind's inference algorithm(s). We find that reasonably accurate decisions are possible long before the Markov chain has converged to the posterior distribution, i.e. during the period known as burn-in. Therefore the strategy that is optimal subject to the mind's bounded processing speed and opportunity costs may perform so few iterations that the resulting samples are biased towards the initial value. The resulting cognitive process model provides a rational basis for the anchoring-and-adjustment heuristic. The model's quantitative predictions are tested against published data on anchoring in numerical estimation tasks. Our theoretical and empirical results suggest that the anchoring bias is consistent with approximate Bayesian inference.
Truly Nonparametric Online Variational Inference for Hierarchical Dirichlet Processes
Authors: Michael Bryant, Erik B. Sudderth
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Continual Learning, Variational Inference

Variational methods provide a computationally scalable alternative to Monte Carlo methods for large-scale, Bayesian nonparametric learning.  In practice, however, conventional batch and online variational methods quickly become trapped in local optima. In this paper, we consider a nonparametric topic model based on the hierarchical Dirichlet process (HDP), and develop a novel online variational inference algorithm based on split-merge topic updates. We derive a simpler and faster variational approximation of the HDP, and show that by intelligently splitting and merging components of the variational posterior, we can achieve substantially better predictions of test data than conventional online and batch variational algorithms. For streaming analysis of large datasets where batch analysis is infeasible, we show that our split-merge updates better capture the nonparametric properties of the underlying model, allowing continual learning of new topics.
A Neural Autoregressive Topic Model
Authors: Hugo Larochelle, Stanislas Lauly
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: model, Representation Learning

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.
A Unifying Perspective of Parametric Policy Search Methods for Markov Decision Processes
Authors: Thomas Furmston, David Barber
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Parametric policy search algorithms are one of the methods of choice for the optimisation of Markov Decision Processes, with Expectation Maximisation and natural gradient ascent being considered the current state of the art in the field. In this article we provide a unifying perspective of these two algorithms by showing that their step-directions in the parameter space are closely related to the search direction of an approximate Newton method. This analysis leads naturally to the consideration of this approximate Newton method as an alternative gradient-based method for Markov Decision Processes. We are able show that the algorithm has numerous desirable properties, absent in the naive application of Newton's method, that make it a viable alternative to either Expectation Maximisation or natural gradient ascent. Empirical results suggest that the algorithm has excellent convergence and robustness properties, performing strongly in comparison to both Expectation Maximisation and natural gradient ascent.
Entangled Monte Carlo
Authors: Seong-Hwan Jun, Liangliang Wang, Alexandre Bouchard-Côté
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We propose a novel method for scalable parallelization of SMC algorithms, Entangled Monte Carlo simulation (EMC).  EMC avoids the transmission of particles between  nodes, and instead reconstructs them from the particle genealogy. In particular, we show that we can reduce the communication to the particle weights for each machine while efficiently maintaining implicit global coherence of the parallel simulation. We explain methods to efficiently maintain a genealogy of particles from which any particle can be reconstructed. We demonstrate using examples from Bayesian phylogenetic that the computational gain from parallelization using EMC significantly outweighs the cost of particle reconstruction. The timing experiments show that reconstruction of particles is indeed much more efficient as compared to transmission of particles.
Near-Optimal MAP Inference for Determinantal Point Processes
Authors: Jennifer Gillenwater, Alex Kulesza, Ben Taskar
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Document Summarization, Image Retrieval, Point Processes, Pose Estimation

Determinantal point processes (DPPs) have recently been proposed as   computationally efficient probabilistic models of diverse sets for a   variety of applications, including document summarization, image   search, and pose estimation.  Many DPP inference operations,   including normalization and sampling, are tractable; however,   finding the most likely configuration (MAP), which is often required   in practice for decoding, is NP-hard, so we must resort to   approximate inference.  Because DPP probabilities are   log-submodular, greedy algorithms have been used in the past with   some empirical success; however, these methods only give   approximation guarantees in the special case of DPPs with monotone   kernels.  In this paper we propose a new algorithm for approximating   the MAP problem based on continuous techniques for submodular   function maximization.  Our method involves a novel continuous   relaxation of the log-probability function, which, in contrast to   the multilinear extension used for general submodular functions, can   be evaluated and differentiated exactly and efficiently.  We obtain   a practical algorithm with a 1/4-approximation guarantee for a   general class of non-monotone DPPs.  Our algorithm also extends to   MAP inference under complex polytope constraints, making it possible   to combine DPPs with Markov random fields, weighted matchings, and   other models.  We demonstrate that our approach outperforms greedy   methods on both synthetic and real-world data.
Probabilistic Low-Rank Subspace Clustering
Authors: S. D. Babacan, Shinichi Nakajima, Minh Do
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, Density Estimation, Missing Values

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.
How They Vote: Issue-Adjusted Models of Legislative Behavior
Authors: Sean Gerrish, David M. Blei
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We develop a probabilistic model of legislative data that uses the text of the bills to uncover lawmakers' positions on specific political issues.  Our model can be used to explore how a lawmaker's voting patterns deviate from what is expected and how that deviation depends on what is being voted on. We derive approximate posterior inference algorithms based on variational methods. Across 12 years of legislative data, we demonstrate both improvement in heldout predictive performance and the model's utility in interpreting an inherently multi-dimensional space.
Density Propagation and Improved Bounds on the Partition Function
Authors: Stefano Ermon, Ashish Sabharwal, Bart Selman, Carla P. Gomes
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Tree Decomposition

Given a probabilistic graphical model, its density of states is a function that, for any likelihood value, gives the number of configurations with that probability. We introduce a novel message-passing algorithm called Density Propagation (DP) for estimating this function. We show that DP is exact for tree-structured graphical models and is, in general, a strict generalization of both sum-product and max-product algorithms. Further, we use density of states and tree decomposition to introduce a new family of upper and lower bounds on the partition function. For any tree decompostion, the new upper bound based on finer-grained density of state information is provably at least as tight as previously known bounds based on convexity of the log-partition function, and strictly stronger if a general condition holds. We conclude with empirical evidence of improvement over convex relaxations and mean-field based bounds.
Perceptron Learning of SAT
Authors: Alex Flint, Matthew Blaschko
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Sentence

Boolean satisfiability (SAT) as a canonical NP-complete decision problem is one of the most important problems in computer science.  In practice, real-world SAT sentences are drawn from a distribution that may result in efficient algorithms for their solution. Such SAT instances are likely to have shared characteristics and substructures. This work approaches the exploration of a family of SAT solvers as a learning problem.  In particular, we relate polynomial time solvability of a SAT subset to a notion of margin between sentences mapped by a feature function into a Hilbert space.  Provided this mapping is based on polynomial time computable statistics of a sentence, we show that the existance of a margin between these data points implies the existance of a polynomial time solver for that SAT subset based on the Davis-Putnam-Logemann-Loveland algorithm.  Furthermore, we show that a simple perceptron-style learning rule will find an optimal SAT solver with a bounded number of training updates.  We derive a linear time computable set of features and show analytically that margins exist for important polynomial special cases of SAT.  Empirical results show an order of magnitude improvement over a state-of-the-art SAT solver on a hardware verification task.
Learning Networks of Heterogeneous Influence
Authors: Nan Du, Le Song, Ming Yuan, Alex J. Smola
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Information, disease, and influence diffuse over networks of entities in both natural systems and human society. Analyzing these transmission networks plays an important role in understanding the diffusion processes and predicting events in the future. However, the underlying transmission networks are often hidden and incomplete, and we observe only the time stamps when cascades of events happen. In this paper, we attempt to address the challenging problem of uncovering the hidden network only from the cascades.  The structure discovery problem is complicated by the fact that the influence among different entities in a network are heterogeneous, which can not be described by a simple parametric model. Therefore, we propose a kernel-based method which can capture a diverse range of different types of influence without any prior assumption. In both synthetic and real cascade data, we show that our model can better recover the underlying diffusion network and drastically improve the estimation of the influence functions between networked entities.