pwc-archive/papers-with-abstracts huggingface dataset:
Streaming Pointwise Mutual Information
Authors: Benjamin V. Durme, Ashwin Lall
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Articles

Recent work has led to the ability to perform space efﬁcient, approximate counting  over large vocabularies in a streaming context. Motivated by the existence of data  structures of this type, we explore the computation of associativity scores, other-  wise known as pointwise mutual information (PMI), in a streaming context. We  give theoretical bounds showing the impracticality of perfect online PMI compu-  tation, and detail an algorithm with high expected accuracy. Experiments on news  articles show our approach gives high accuracy on real world data.
Bayesian Source Localization with the Multivariate Laplace Prior
Authors: Marcel V. Gerven, Botond Cseke, Robert Oostenveld, Tom Heskes
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We introduce a novel multivariate Laplace (MVL) distribution as a sparsity promoting prior for Bayesian source localization that allows the specification of constraints between and within sources. We represent the MVL distribution as a scale mixture that induces a coupling between source variances instead of their means. Approximation of the posterior marginals using expectation propagation is shown to be very efficient due to properties of the scale mixture representation. The computational bottleneck amounts to computing the diagonal elements of a sparse matrix inverse. Our approach is illustrated using a mismatch negativity paradigm for which MEG data and a structural MRI have been acquired. We show that spatial coupling leads to sources which are active over larger cortical areas as compared with an uncoupled prior.
Gaussian process regression with Student-t likelihood
Authors: Jarno Vanhatalo, Pasi Jylänki, Aki Vehtari
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

In the Gaussian process regression the observation model is commonly assumed to be Gaussian, which is convenient in computational perspective. However, the drawback is that the predictive accuracy of the model can be significantly compromised if the observations are contaminated by outliers. A robust observation model, such as the Student-t distribution, reduces the influence of outlying observations and improves the predictions. The problem, however, is the analytically intractable inference. In this work, we discuss the properties of a Gaussian process regression model with the Student-t likelihood and utilize the Laplace approximation for approximate inference. We compare our approach to a variational approximation and a Markov chain Monte Carlo scheme, which utilize the commonly used scale mixture representation of the Student-t distribution.
Measuring model complexity with the prior predictive
Authors: Wolf Vanpaemel
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Descriptive, model

In the last few decades, model complexity has received a lot of press. While many methods have been proposed that jointly measure a model’s descriptive adequacy and its complexity, few measures exist that measure complexity in itself. Moreover, existing measures ignore the parameter prior, which is an inherent part of the model and affects the complexity. This paper presents a stand alone measure for model complexity, that takes the number of parameters, the functional form, the range of the parameters and the parameter prior into account. This Prior Predictive Complexity (PPC) is an intuitive and easy to compute measure. It starts from the observation that model complexity is the property of the model that enables it to fit a wide range of outcomes. The PPC then measures how wide this range exactly is.
Structured output regression for detection with partial truncation
Authors: Andrea Vedaldi, Andrew Zisserman
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

We develop a structured output model for object category detection that explicitly accounts for alignment, multiple aspects and partial truncation in both training and inference. The model is formulated as large margin learning with latent variables and slack rescaling, and both training and inference are computationally efficient. We make the following contributions: (i) we note that extending the Structured Output Regression formulation of Blaschko and Lampert (ECCV 2008) to include a bias term significantly improves performance; (ii) that alignment (to account for small rotations and anisotropic scalings) can be included as a latent variable and efficiently determined and implemented; (iii) that the latent variable extends to multiple aspects (e.g. left facing, right facing, front) with the same formulation; and (iv), most significantly for performance, that truncated and truncated instances can be included in both training and inference with an explicit truncation mask. We demonstrate the method by training and testing on the PASCAL VOC 2007 data set -- training includes the truncated examples, and in testing object instances are detected at multiple scales, alignments, and with significant truncations.
Bootstrapping from Game Tree Search
Authors: Joel Veness, David Silver, Alan Blair, William Uther
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

In this paper we introduce a new algorithm for updating the parameters of a heuristic evaluation function, by updating the heuristic towards the values computed by an alpha-beta search. Our algorithm differs from previous approaches to learning from search, such as Samuels checkers player and the TD-Leaf algorithm, in two key ways. First, we update all nodes in the search tree, rather than a single node. Second, we use the outcome of a deep search, instead of the outcome of a subsequent search, as the training signal for the evaluation function. We implemented our algorithm in a chess program Meep, using a linear heuristic function. After initialising its weight vector to small random values, Meep was able to learn high quality weights from self-play alone. When tested online against human opponents, Meep played at a master level, the best performance of any chess program with a heuristic learned entirely from self-play.
Tracking Dynamic Sources of Malicious Activity at Internet Scale
Authors: Shobha Venkataraman, Avrim Blum, Dawn Song, Subhabrata Sen, Oliver Spatscheck
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We formulate and address the problem of discovering dynamic malicious regions on the Internet. We model this problem as one of adaptively pruning a known decision tree, but with additional challenges: (1) severe space requirements, since the underlying decision tree has over 4 billion leaves, and (2) a changing target function, since malicious activity on the Internet is dynamic. We present a novel algorithm that addresses this problem, by putting together a number of different ``experts algorithms and online paging algorithms. We prove guarantees on our algorithms performance as a function of the best possible pruning of a similar size, and our experiments show that our algorithm achieves high accuracy on large real-world data sets, with significant improvements over existing approaches.
Explaining human multiple object tracking as resource-constrained approximate inference in a dynamic probabilistic model
Authors: Ed Vul, George Alvarez, Joshua B. Tenenbaum, Michael J. Black
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Multiple Object Tracking, Object, Object Tracking

Multiple object tracking is a task commonly used to investigate the architecture of human visual attention. Human participants show a distinctive pattern of successes and failures in tracking experiments that is often attributed to limits on an object system, a tracking module, or other specialized cognitive structures. Here we use a computational analysis of the task of object tracking to ask which human failures arise from cognitive limitations and which are consequences of inevitable perceptual uncertainty in the tracking task. We find that many human performance phenomena, measured through novel behavioral experiments, are naturally produced by the operation of our ideal observer model (a Rao-Blackwelized particle filter). The tradeoff between the speed and number of objects being tracked, however, can only arise from the allocation of a flexible cognitive resource, which can be formalized as either memory or attention.
Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming
Authors: Xiao-Ming Wu, Anthony M. So, Zhenguo Li, Shuo-Yen R. Li
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering, Computational Efficiency, Constrained Clustering, Dimensionality Reduction

Kernel learning is a powerful framework for nonlinear data modeling. Using the kernel trick, a number of problems have been formulated as semidefinite programs (SDPs). These include Maximum Variance Unfolding (MVU) (Weinberger et al., 2004) in nonlinear dimensionality reduction, and Pairwise Constraint Propagation (PCP) (Li et al., 2008) in constrained clustering. Although in theory SDPs can be efficiently solved, the high computational complexity incurred in numerically processing the huge linear matrix inequality constraints has rendered the SDP approach unscalable. In this paper, we show that a large class of kernel learning problems can be reformulated as semidefinite-quadratic-linear programs (SQLPs), which only contain a simple positive semidefinite constraint, a second-order cone constraint and a number of linear constraints. These constraints are much easier to process numerically, and the gain in speedup over previous approaches is at least of the order $m^{2.5}$, where m is the matrix dimension. Experimental results are also presented to show the superb computational efficiency of our approach.
Rethinking LDA: Why Priors Matter
Authors: Hanna M. Wallach, David M. Mimno, Andrew McCallum
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Hyperparameter Optimization, Topic Models

Implementations of topic models typically use symmetric Dirichlet priors with fixed concentration parameters, with the implicit assumption that such smoothing parameters" have little practical effect. In this paper, we explore several classes of structured priors for topic models. We find that an asymmetric Dirichlet prior over the document-topic distributions has substantial advantages over a symmetric prior, while an asymmetric prior over the topic-word distributions provides no real benefit. Approximation of this prior structure through simple, efficient hyperparameter optimization steps is sufficient to achieve these performance gains. The prior structure we advocate substantially increases the robustness of topic models to variations in the number of topics and to the highly skewed word frequency distributions common in natural language. Since this prior structure can be implemented using efficient algorithms that add negligible cost beyond standard inference techniques, we recommend it as a new standard for topic modeling."
Decoupling Sparsity and Smoothness in the Discrete Hierarchical Dirichlet Process
Authors: Chong Wang, David M. Blei
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We present a nonparametric hierarchical Bayesian model of document collections that decouples sparsity and smoothness in the component distributions (i.e., the ``topics). In the sparse topic model (STM), each topic is represented by a bank of selector variables that determine which terms appear in the topic. Thus each topic is associated with a subset of the vocabulary, and topic smoothness is modeled on this subset. We develop an efficient Gibbs sampler for the STM that includes a general-purpose method for sampling from a Dirichlet mixture with a combinatorial number of components. We demonstrate the STM on four real-world datasets. Compared to traditional approaches, the empirical results show that STMs give better predictive performance with simpler inferred models.
Variational Inference for the Nested Chinese Restaurant Process
Authors: Chong Wang, David M. Blei
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Variational Inference

The nested Chinese restaurant process (nCRP) is a powerful nonparametric Bayesian model for learning tree-based hierarchies from data. Since its posterior distribution is intractable, current inference methods have all relied on MCMC sampling. In this paper, we develop an alternative inference technique based on variational methods. To employ variational methods, we derive a tree-based stick-breaking construction of the nCRP mixture model, and a novel variational algorithm that efficiently explores a posterior over a large set of combinatorial structures. We demonstrate the use of this approach for text and hand written digits modeling, where we show we can adapt the nCRP to continuous data as well.
Sufficient Conditions for Agnostic Active Learnable
Authors: Liwei Wang
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Active Learning, General Classification

We study pool-based active learning in the presence of noise, i.e. the agnostic setting. Previous works have shown that the effectiveness of agnostic active learning depends on the learning problem and the hypothesis space. Although there are many cases on which active learning is very useful, it is also easy to construct examples that no active learning algorithm can have advantage. In this paper, we propose intuitively reasonable sufficient conditions under which agnostic active learning algorithm is strictly superior to passive supervised learning. We show that under some noise condition, if the classification boundary and the underlying distribution are smooth to a finite order, active learning achieves polynomial improvement in the label complexity; if the boundary and the distribution are infinitely smooth, the improvement is exponential.
A Rate Distortion Approach for Semi-Supervised Conditional Random Fields
Authors: Yang Wang, Gholamreza Haffari, Shaojun Wang, Greg Mori
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification, Multi-class Classification, Structured Prediction

We propose a novel information theoretic approach for semi-supervised learning of conditional random fields. Our approach defines a training objective that combines the conditional likelihood on labeled data and the mutual information on unlabeled data. Different from previous minimum conditional entropy semi-supervised discriminative learning methods, our approach can be naturally cast into the rate distortion theory framework in information theory. We analyze the tractability of the framework for structured prediction and present a convergent variational training algorithm to defy the combinatorial explosion of terms in the sum over label configurations. Our experimental results show that the rate distortion approach outperforms standard $l_2$ regularization and minimum conditional entropy regularization on both multi-class classification and sequence labeling problems.
Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation
Authors: Yusuke Watanabe, Kenji Fukumizu
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We propose a new approach to the analysis of Loopy Belief Propagation (LBP) by establishing a formula that connects the Hessian of the Bethe free energy with the edge zeta function. The formula has a number of theoretical implications on LBP. It is applied to give a sufficient condition that the Hessian of the Bethe free energy is positive definite, which shows non-convexity for graphs with multiple cycles. The formula clarifies the relation between the local stability of a fixed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP fixed point, and show various conditions of uniqueness.
Strategy Grafting in Extensive Games
Authors: Kevin Waugh, Nolan Bard, Michael Bowling
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Extensive games are often used to model the interactions of multiple agents within an environment.  Much recent work has focused on increasing the size of an extensive game that can be feasibly solved.  Despite these improvements, many interesting games are still too large for such techniques.  A common approach for computing strategies in these large games is to first employ an abstraction technique to reduce the original game to an abstract game that is of a manageable size.  This abstract game is then solved and the resulting strategy is used in the original game.  Most top programs in recent AAAI Computer Poker Competitions use this approach.  The trend in this competition has been that strategies found in larger abstract games tend to beat strategies found in smaller abstract games.  These larger abstract games have more expressive strategy spaces and therefore contain better strategies.  In this paper we present a new method for computing strategies in large games.  This method allows us to compute more expressive strategies without increasing the size of abstract games that we are required to solve.  We demonstrate the power of the approach experimentally in both small and large games, while also providing a theoretical justification for the resulting improvement.
Whose Vote Should Count More: Optimal Integration of Labels from Labelers of Unknown Expertise
Authors: Jacob Whitehill, Ting-Fan Wu, Jacob Bergsma, Javier R. Movellan, Paul L. Ruvolo
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Modern machine learning-based approaches to computer vision require very large databases of labeled images. Some contemporary vision systems already require on the order of millions of images for training (e.g., Omron face detector). While the collection of these large databases is becoming a bottleneck, new Internet-based services that allow labelers from around the world to be easily hired and managed provide a promising solution.  However, using these services to label large databases brings with it new theoretical and practical challenges: (1) The labelers may have wide ranging levels of expertise which are unknown a priori, and in some cases may be adversarial; (2) images may vary in their level of difficulty; and (3) multiple labels for the same image must be combined to provide an estimate of the actual label of the image. Probabilistic approaches provide a principled way to approach these problems. In this paper we present a probabilistic model and use it to simultaneously infer the label of each image, the expertise of each labeler, and the difficulty of each image. On both simulated and real data, we demonstrate that the model outperforms the commonly used ``Majority Vote heuristic for inferring image labels, and is robust to both adversarial and noisy labelers.
Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference
Authors: Khashayar Rohanimanesh, Sameer Singh, Andrew McCallum, Michael J. Black
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Rolling Shutter Correction

Large, relational factor graphs with structure defined by   first-order logic or other languages give rise to notoriously   difficult inference problems.  Because unrolling the structure   necessary to represent distributions over all hypotheses has   exponential blow-up, solutions are often derived from MCMC. However,   because of limitations in the design and parameterization of the   jump function, these sampling-based methods suffer from local   minima|the system must transition through lower-scoring   configurations before arriving at a better MAP solution. This paper   presents a new method of explicitly selecting fruitful downward   jumps by leveraging reinforcement learning (RL). Rather than setting   parameters to maximize the likelihood of the training data,   parameters of the factor graph are treated as a log-linear function   approximator and learned with temporal difference (TD); MAP   inference is performed by executing the resulting policy on held out   test data. Our method allows efficient gradient updates since only   factors in the neighborhood of variables affected by an action need   to be computed|we bypass the need to compute marginals entirely.   Our method provides dramatic empirical success, producing new   state-of-the-art results on a complex joint model of ontology   alignment, with a 48\% reduction in error over state-of-the-art in   that domain.
Sequential effects reflect parallel learning of multiple environmental regularities
Authors: Matthew Wilder, Matt Jones, Michael C. Mozer
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Across a wide range of cognitive tasks, recent experience inﬂuences behavior. For example, when individuals repeatedly perform a simple two-alternative forced-choice task (2AFC), response latencies vary dramatically based on the immediately preceding trial sequence. These sequential effects have been interpreted as adaptation to the statistical structure of an uncertain, changing environment (e.g. Jones & Sieck, 2003; Mozer, Kinoshita, & Shettel, 2007; Yu & Cohen, 2008). The Dynamic Belief Model (DBM) (Yu & Cohen, 2008) explains sequential effects in 2AFC tasks as a rational consequence of a dynamic internal representation that tracks second-order statistics of the trial sequence (repetition rates) and predicts whether the upcoming trial will be a repetition or an alternation of the previous trial. Experimental results suggest that ﬁrst-order statistics (base rates) also inﬂuence sequential effects. We propose a model that learns both ﬁrst- and second-order sequence properties, each according to the basic principles of the DBM but under a uniﬁed inferential framework. This model, the Dynamic Belief Mixture Model (DBM2), obtains precise, parsimonious ﬁts to data. Furthermore, the model predicts dissociations in behavioral (Maloney, Dal Martello, Sahm, & Spillmann, 2005) and electrophysiological studies (Jentzsch & Sommer, 2002), supporting the psychological and neurobiological reality of its two components.
A Neural Implementation of the Kalman Filter
Authors: Robert Wilson, Leif Finkel
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Bayesian Inference, Time Series, Time Series Analysis

There is a growing body of experimental evidence to suggest that the brain is capable of approximating optimal Bayesian inference in the face of noisy input stimuli.  Despite this progress, the neural underpinnings of this computation are still poorly  understood.  In this paper we focus on the problem of Bayesian filtering of stochastic time series.  In particular we introduce a novel neural network, derived from a line attractor architecture, whose dynamics map directly onto those of the Kalman Filter in the limit where the prediction error is small.  When the prediction error is large we show that the network responds robustly to change-points in a way that is qualitatively compatible with the optimal Bayesian model.  The model suggests ways in which probability distributions are encoded in the brain and makes a number of testable experimental predictions.