pwc-archive/papers-with-abstracts huggingface dataset:
Testing a Bayesian Measure of Representativeness Using a Large Image Database
Authors: Joshua T. Abbott, Katherine A. Heller, Zoubin Ghahramani, Thomas L. Griffiths
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: BIG-bench Machine Learning

How do people determine which elements of a set are most representative of that set? We extend an existing Bayesian measure of representativeness, which indicates the representativeness of a sample from a distribution, to define a measure of the representativeness of an item to a set. We show that this measure is formally related to a machine learning method known as Bayesian Sets. Building on this connection, we derive an analytic expression for the representativeness of objects described by a sparse vector of binary features. We then apply this measure to a large database of images, using it to determine which images are the most representative members of different sets. Comparing the resulting predictions to human judgments of representativeness provides a test of this measure with naturalistic stimuli, and illustrates how databases that are more commonly used in computer vision and machine learning can be used to evaluate psychological theories.
Spike and Slab Variational Inference for Multi-Task and Multiple Kernel Learning
Authors: Michalis K. Titsias, Miguel Lázaro-Gredilla
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Bayesian Inference, Collaborative Filtering, General Classification, Missing Values, Multi-class Classification, Variational Inference

We introduce a variational Bayesian inference algorithm which can be widely applied to sparse linear models. The algorithm is based on the spike and slab prior which, from a Bayesian perspective, is the golden standard for sparse inference. We apply the method to a general multi-task and multiple kernel learning model in which a common set of Gaussian process functions is linearly combined with task-specific sparse weights, thus inducing relation between tasks. This model unifies several sparse linear models, such as generalized linear models, sparse factor analysis and matrix factorization with missing values, so that the variational algorithm can be applied to all these cases. We demonstrate our approach in multi-output Gaussian process regression, multi-class classification, image processing applications and collaborative filtering.
Practical Variational Inference for Neural Networks
Authors: Alex Graves
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Bayesian Inference, Variational Inference

Variational methods have been previously explored as a tractable approximation to Bayesian inference for neural networks. However the approaches proposed so far have only been applicable to a few simple network architectures. This paper introduces an easy-to-implement stochastic variational method (or equivalently, minimum description length loss function) that can be applied to most neural networks. Along the way it revisits several common regularisers from a variational perspective. It also provides a simple pruning heuristic that can both drastically reduce the number of network weights and lead to improved generalisation. Experimental results are provided for a hierarchical multidimensional recurrent neural network applied to the TIMIT speech corpus.
Neuronal Adaptation for Sampling-Based Probabilistic Inference in Perceptual Bistability
Authors: David P. Reichert, Peggy Series, Amos J. Storkey
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

It has been argued that perceptual multistability reflects probabilistic inference performed by the brain when sensory input is ambiguous. Alternatively, more traditional explanations of multistability refer to low-level mechanisms such as neuronal adaptation. We employ a Deep Boltzmann Machine (DBM) model of cortical processing to demonstrate that these two different approaches can be combined in the same framework. Based on recent developments in machine learning, we show how neuronal adaptation can be understood as a mechanism that improves probabilistic, sampling-based inference. Using the ambiguous Necker cube image, we analyze the perceptual switching exhibited by the model. We also examine the influence of spatial attention, and explore how binocular rivalry can be modeled with the same approach. Our work joins earlier studies in demonstrating how the principles underlying DBMs relate to cortical processing, and offers novel perspectives on the neural implementation of approximate probabilistic inference in the brain.
Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts
Authors: Matthias Hein, Simon Setzer
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering

Spectral clustering is based on the spectral relaxation of the normalized/ratio graph cut criterion. While the  spectral relaxation is known to be loose, it has been shown recently that a non-linear  eigenproblem yields a tight relaxation of the Cheeger cut.   In this paper, we extend this result considerably by providing a   characterization of all balanced graph cuts which allow for a tight relaxation. Although the resulting optimization problems are non-convex and non-smooth, we provide   an efficient first-order scheme which scales to large graphs. Moreover, our approach  comes with the quality guarantee that given any partition as initialization the   algorithm either outputs a better partition or it stops immediately.
A rational model of causal inference with continuous causes
Authors: Thomas L. Griffiths, Michael James
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Causal Inference

Rational models of causal induction have been successful in accounting for people's judgments about the existence of causal relationships. However, these models have focused on explaining inferences from discrete data of the kind that can be summarized in a 2 ✕ 2 contingency table. This severely limits the scope of these models, since the world often provides non-binary data. We develop a new rational model of causal induction using continuous dimensions, which aims to diminish the gap between empirical and theoretical approaches and real-world causal induction. This model successfully predicts human judgments from previous studies better than models of discrete causal inference, and outperforms several other plausible models of causal induction with continuous causes in accounting for people's inferences in a new experiment.
Quasi-Newton Methods for Markov Chain Monte Carlo
Authors: Yichuan Zhang, Charles A. Sutton
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: valid

The performance of Markov chain Monte Carlo methods is often sensitive to the scaling and correlations between the random variables of interest. An important source of information about the local correlation and scale is given by the Hessian matrix of the target distribution, but this is often either computationally expensive or infeasible. In this paper we propose MCMC samplers that make use of quasi-Newton approximations from the optimization literature, that approximate the Hessian of the target distribution from previous samples and gradients generated by the sampler. A key issue is that MCMC samplers that depend on the history of previous states are in general not valid. We address this problem by using limited memory quasi-Newton methods, which depend only on a fixed window of previous samples. On several real world datasets, we show that the quasi-Newton sampler is a more effective sampler than standard Hamiltonian Monte Carlo at a fraction of the cost of MCMC methods that require higher-order derivatives.
TD_gamma: Re-evaluating Complex Backups in Temporal Difference Learning
Authors: George Konidaris, Scott Niekum, Philip S. Thomas
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We show that the lambda-return target used in the TD(lambda) family of algorithms is the maximum likelihood estimator for a specific model of how the variance of an n-step return estimate increases with n. We introduce the gamma-return estimator, an alternative target based on a more accurate model of variance, which defines the TD_gamma family of complex-backup temporal difference learning algorithms. We derive TD_gamma, the gamma-return equivalent of the original TD(lambda) algorithm, which eliminates the lambda parameter but can only perform updates at the end of an episode and requires time and space proportional to the episode length. We then derive a second algorithm, TD_gamma(C), with a capacity parameter C. TD_gamma(C) requires C times more time and memory than TD(lambda) and is incremental and online. We show that TD_gamma outperforms TD(lambda) for any setting of lambda on 4 out of 5 benchmark domains, and that TD_gamma(C) performs as well as or better than TD_gamma for intermediate settings of C.
Speedy Q-Learning
Authors: Mohammad Ghavamzadeh, Hilbert J. Kappen, Mohammad G. Azar, Rémi Munos
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Q-Learning

We introduce a new convergent variant of Q-learning, called speedy Q-learning, to address the problem of slow convergence in the standard form of the Q-learning algorithm. We prove a PAC bound on the performance of SQL, which shows that for an MDP with n state-action pairs  and the discount factor \gamma only T=O\big(\log(n)/(\epsilon^{2}(1-\gamma)^{4})\big) steps are required for the SQL algorithm to converge to an \epsilon-optimal action-value function with high probability. This bound has a better dependency on 1/\epsilon and 1/(1-\gamma), and thus, is tighter than the best available result for Q-learning. Our bound is also superior to the existing results for both model-free and model-based instances of batch Q-value iteration that are considered to be more efficient than the incremental methods like Q-learning.
Regularized Laplacian Estimation and Fast Eigenvector Approximation
Authors: Patrick O. Perry, Michael W. Mahoney
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Recently, Mahoney and Orecchia demonstrated that popular diffusion-based procedures to compute a quick approximation to the first nontrivial eigenvector of a data graph Laplacian exactly solve certain regularized Semi-Definite Programs (SDPs). In this paper, we extend that result by providing a statistical interpretation of their approximation procedure. Our interpretation will be analogous to the manner in which l2-regularized or l1-regularized l2 regression (often called Ridge regression and Lasso regression, respectively) can be interpreted in terms of a Gaussian prior or a Laplace prior, respectively, on the coefficient vector of the regression problem. Our framework will imply that the solutions to the Mahoney-Orecchia regularized SDP can be interpreted as regularized estimates of the pseudoinverse of the graph Laplacian. Conversely, it will imply that the solution to this regularized estimation problem can be computed very quickly by running, e.g., the fast diffusion-based PageRank procedure for computing an approximation to the first nontrivial eigenvector of the graph Laplacian. Empirical results are also provided to illustrate the manner in which approximate eigenvector computation implicitly performs statistical regularization, relative to running the corresponding exact algorithm.
Understanding the Intrinsic Memorability of Images
Authors: Phillip Isola, Devi Parikh, Antonio Torralba, Aude Oliva
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: feature selection

Artists, advertisers, and photographers are routinely presented with the task of creating an image that a viewer will remember. While it may seem like image memorability is purely subjective, recent work shows that it is not an inexplicable phenomenon: variation in memorability of images is consistent across subjects, suggesting that some images are intrinsically more memorable than others, independent of a subjects' contexts and biases. In this paper, we used the publicly available memorability dataset of Isola et al., and augmented the object and scene annotations with interpretable spatial, content, and aesthetic image properties. We used a feature-selection scheme with desirable explaining-away properties to determine a compact set of attributes that characterizes the memorability of any individual image. We find that images of enclosed spaces containing people with visible faces are memorable, while images of vistas and peaceful scenes are not. Contrary to popular belief, unusual or aesthetically pleasing scenes do not tend to be highly memorable. This work represents one of the first attempts at understanding intrinsic image memorability, and opens a new domain of investigation at the interface between human cognition and computer vision.
The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning
Authors: Marius Kloft, Gilles Blanchard
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We derive an upper bound on the local Rademacher complexity of Lp-norm multiple kernel learning, which yields a tighter excess risk bound than global approaches. Previous local approaches analyzed the case p=1 only while our analysis covers all cases $1\leq p\leq\infty$, assuming the different feature mappings corresponding to the different kernels to be uncorrelated. We also show a lower bound that shows that the bound is tight, and derive consequences regarding excess loss, namely fast convergence rates of the order $O(n^{-\frac{\alpha}{1+\alpha}})$, where $\alpha$ is the minimum eigenvalue decay rate of the individual kernels.
Contextual Gaussian Process Bandit Optimization
Authors: Andreas Krause, Cheng S. Ong
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Management

How should we design experiments to maximize performance of a complex system, taking into account uncontrollable environmental conditions? How should we select relevant documents (ads) to display, given information about the user? These tasks can be formalized as contextual bandit problems, where at each round, we receive context (about the experimental conditions, the query), and have to choose an action (parameters, documents). The key challenge is to trade off exploration by gathering data for estimating the mean payoff function over the context-action space, and to exploit by choosing an action deemed optimal based on the gathered data. We model the payoff function as a sample from a Gaussian process defined over the joint context-action space, and develop CGP-UCB, an intuitive upper-confidence style algorithm. We show that by mixing and matching kernels for contexts and actions, CGP-UCB can handle a variety of practical applications. We further provide generic tools for deriving regret bounds when using such composite kernel functions. Lastly, we evaluate our algorithm on two case studies, in the context of automated vaccine design and sensor management. We show that context-sensitive optimization outperforms no or naive use of context.
Co-Training for Domain Adaptation
Authors: Minmin Chen, Kilian Q. Weinberger, John Blitzer
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Domain Adaptation

Domain adaptation algorithms seek to generalize a model trained in a source domain to a new target domain.  In many  practical cases, the source and target distributions can differ substantially, and in some cases crucial target features may not have support in the source domain.  In this paper we introduce an algorithm that bridges the gap between source and target domains by slowly adding both the target features and instances in which the current  algorithm is the most confident.  Our algorithm is a variant of co-training, and we name it CODA (Co-training for domain adaptation).  Unlike the original co-training work, we do not assume a particular feature split.  Instead, for each iteration of co-training, we add target features and formulate a single optimization problem which simultaneously learns a target predictor, a split of the feature space into views, and a shared subset of source  and target features to include in the predictor.  CODA significantly out-performs the state-of-the-art on the 12-domain benchmark data set of Blitzer et al.. Indeed, over a wide range (65 of 84 comparisons) of target supervision, ranging from no labeled target data to a relatively large number of target labels, CODA achieves the best performance.
Autonomous Learning of Action Models for Planning
Authors: Neville Mehta, Prasad Tadepalli, Alan Fern
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

This paper introduces two new frameworks for learning action models for planning.  In the mistake-bounded planning framework, the learner has access to a planner for the given model representation, a simulator, and a planning problem generator, and aims to learn a model with at most a polynomial number of faulty plans.  In the planned exploration framework, the learner does not have access to a problem generator and must instead design its own problems, plan for them, and converge with at most a polynomial number of planning attempts.  The paper reduces learning in these frameworks to concept learning with one-sided error and provides algorithms for successful learning in both frameworks.  A specific family of hypothesis spaces is shown to be efficiently learnable in both the frameworks.
Gaussian process modulated renewal processes
Authors: Yee W. Teh, Vinayak Rao
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Renewal processes are generalizations of the Poisson process on the real line, whose intervals are drawn i.i.d. from some distribution. Modulated renewal processes allow these distributions to vary with time, allowing the introduction nonstationarity. In this work, we take a nonparametric Bayesian approach, modeling this nonstationarity with a Gaussian process. Our approach is based on the idea of uniformization, allowing us to draw exact samples from an otherwise intractable distribution. We develop a novel and efficient MCMC sampler for posterior inference. In our experiments, we test these on a number of synthetic and real datasets.
Linear Submodular Bandits and their Application to Diversified Retrieval
Authors: Yisong Yue, Carlos Guestrin
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Articles, Information Retrieval, News Recommendation, Retrieval

Diversified retrieval and online learning are two core research areas in the design of modern information retrieval systems.In this paper, we propose the linear submodular bandits problem, which is an online learning setting for optimizing a general class of feature-rich submodular utility models for diversified retrieval. We present an algorithm, called LSBGREEDY, and prove that it efficiently converges to a near-optimal model. As a case study, we applied our approach to the setting of personalized news recommendation, where the system must recommend small sets of news articles selected from tens of thousands of available articles each day. In a live user study, we found that LSBGREEDY significantly outperforms existing online learning approaches.
Continuous-Time Regression Models for Longitudinal Networks
Authors: Duy Q. Vu, David Hunter, Padhraic Smyth, Arthur U. Asuncion
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

The development of statistical models for continuous-time longitudinal network data is of increasing interest in machine learning and social science. Leveraging ideas from survival and event history analysis, we introduce a continuous-time regression modeling framework for network event data that can incorporate both time-dependent network statistics and time-varying regression coefficients. We also develop an efficient inference scheme that allows our approach to scale to large networks. On synthetic and real-world data, empirical results demonstrate that the proposed inference approach can accurately estimate the coefficients of the regression model, which is useful for interpreting the evolution of the network; furthermore, the learned model has systematically better predictive performance compared to standard baseline methods.
On Tracking The Partition Function
Authors: Guillaume Desjardins, Yoshua Bengio, Aaron C. Courville
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Markov Random Fields (MRFs) have proven very powerful both as density estimators and feature extractors for classification. However, their use is often limited by an inability to estimate the partition function $Z$. In this paper, we exploit the gradient descent training procedure of restricted Boltzmann machines (a type of MRF) to {\bf track} the log partition function during learning. Our method relies on two distinct sources of information: (1) estimating the change $\Delta Z$ incurred by each gradient update, (2) estimating the difference in $Z$ over a small set of tempered distributions using bridge sampling. The two sources of information are then combined using an inference procedure similar to Kalman filtering.  Learning MRFs through Tempered Stochastic Maximum Likelihood, we can estimate $Z$ using no more temperatures than are required for learning. Comparing to both exact values and estimates using annealed importance sampling (AIS), we show on several datasets that our method is able to accurately track the log partition function. In contrast to AIS, our method provides this estimate at each time-step, at a computational cost similar to that required for training alone.
Variational Gaussian Process Dynamical Systems
Authors: Andreas Damianou, Michalis K. Titsias, Neil D. Lawrence
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Dimensionality Reduction, Time Series, Time Series Analysis

High dimensional time series are endemic in applications of machine learning  such as robotics (sensor data), computational biology (gene expression data), vision   (video sequences) and graphics (motion capture data). Practical nonlinear  probabilistic approaches to this data are required. In this paper we introduce  the variational Gaussian process dynamical system. Our work builds on recent  variational approximations for Gaussian process latent variable models to allow  for nonlinear dimensionality reduction simultaneously with learning a dynamical  prior in the latent space. The approach also allows for the appropriate dimensionality   of the latent space to be automatically determined. We demonstrate the  model on a human motion capture data set and a series of high resolution video  sequences.
Non-parametric Group Orthogonal Matching Pursuit for Sparse Learning with Multiple Kernels
Authors: Vikas Sindhwani, Aurelie C. Lozano
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Generalization Bounds, Sparse Learning

We consider regularized risk minimization in a large dictionary of Reproducing  kernel Hilbert Spaces (RKHSs) over which the target function has a sparse representation.  This setting, commonly referred to as Sparse Multiple Kernel Learning  (MKL), may be viewed as the non-parametric extension of group sparsity in linear  models. While the two dominant algorithmic strands of sparse learning, namely  convex relaxations using l1 norm (e.g., Lasso) and greedy methods (e.g., OMP),  have both been rigorously extended for group sparsity, the sparse MKL literature  has so farmainly adopted the former withmild empirical success. In this paper, we  close this gap by proposing a Group-OMP based framework for sparse multiple  kernel learning. Unlike l1-MKL, our approach decouples the sparsity regularizer  (via a direct l0 constraint) from the smoothness regularizer (via RKHS norms)  which leads to better empirical performance as well as a simpler optimization  procedure that only requires a black-box single-kernel solver. The algorithmic  development and empirical studies are complemented by theoretical analyses in  terms of Rademacher generalization bounds and sparse recovery conditions analogous  to those for OMP [27] and Group-OMP [16].