pwc-archive/papers-with-abstracts huggingface dataset:
Learning to Search Efficiently in High Dimensions
Authors: Zhen Li, Huazhong Ning, Liangliang Cao, Tong Zhang, Yihong Gong, Thomas S. Huang
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Computational Efficiency, Vocal Bursts Intensity Prediction

High dimensional similarity search in large scale databases becomes an important challenge due to the advent of Internet. For such applications, specialized data structures are required to achieve computational efficiency. Traditional approaches relied on algorithmic constructions that are often data independent (such as Locality Sensitive Hashing) or weakly dependent (such as kd-trees, k-means trees). While supervised learning algorithms have been applied to related problems, those proposed in the literature mainly focused on learning hash codes optimized for compact embedding of the data rather than search efficiency. Consequently such an embedding has to be used with linear scan or another search algorithm. Hence learning to hash does not directly address the search efficiency issue. This paper considers a new framework that applies supervised learning to directly optimize a data structure that supports efficient large scale search. Our approach takes both search quality and computational cost into consideration. Specifically, we learn a boosted search forest that is optimized using pair-wise similarity labeled examples. The output of this search forest can be efficiently converted into an inverted indexing data structure, which can leverage modern text search infrastructure to achieve both scalability and efficiency. Experimental results show that our approach significantly outperforms the start-of-the-art learning to hash methods (such as spectral hashing), as well as state-of-the-art high dimensional search algorithms (such as LSH and k-means trees).
A Non-Parametric Approach to Dynamic Programming
Authors: Oliver B. Kroemer, Jan R. Peters
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Density Estimation

In this paper, we consider the problem of policy evaluation for continuous-state systems. We present a non-parametric approach to policy evaluation, which uses kernel density estimation to represent the system. The true form of the value function for this model can be determined, and can be computed using Galerkin's method. Furthermore, we also present a unified view of several well-known policy evaluation methods. In particular, we show that the same Galerkin method can be used to derive Least-Squares Temporal Difference learning, Kernelized Temporal Difference learning, and a discrete-state Dynamic Programming solution, as well as our proposed method. In a numerical evaluation of these algorithms, the proposed approach performed better than the other methods.
Advice Refinement in Knowledge-Based SVMs
Authors: Gautam Kunapuli, Richard Maclin, Jude W. Shavlik
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Knowledge-based support vector machines (KBSVMs) incorporate advice from domain experts, which can improve generalization significantly. A major limitation that has not been fully addressed occurs when the expert advice is imperfect, which can lead to poorer models. We propose a model that extends KBSVMs and is able to not only learn from data and advice, but also simultaneously improve the advice. The proposed approach is particularly effective for knowledge discovery in domains with few labeled examples. The proposed model contains bilinear constraints, and is solved using two iterative approaches: successive linear programming and a constrained concave-convex approach. Experimental results demonstrate that these algorithms yield useful refinements to expert advice, as well as improve the performance of the learning algorithm overall.
Kernel Bayes' Rule
Authors: Kenji Fukumizu, Le Song, Arthur Gretton
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Bayesian Inference

A nonparametric kernel-based method for realizing Bayes' rule is proposed, based on kernel representations of probabilities in reproducing kernel Hilbert spaces. The prior and conditional probabilities are expressed as empirical kernel mean and covariance operators, respectively, and the kernel mean of the posterior distribution is computed in the form of a weighted sample.  The kernel Bayes' rule can be applied to a wide variety of Bayesian inference problems: we demonstrate Bayesian computation without likelihood, and filtering with a nonparametric state-space model. A consistency rate for the posterior estimate is established.
Transfer from Multiple MDPs
Authors: Alessandro Lazaric, Marcello Restelli
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Transfer Reinforcement Learning

Transfer reinforcement learning (RL) methods leverage on the experience collected on a set of source tasks to speed-up RL algorithms. A simple and effective approach is to transfer samples from source tasks and include them in the training set used to solve a target task. In this paper, we investigate the theoretical properties of this transfer method and we introduce novel algorithms adapting the transfer process on the basis of the similarity between source and target tasks. Finally, we report illustrative experimental results in a continuous chain problem.
Sparse Bayesian Multi-Task Learning
Authors: Shengbo Guo, Onno Zoeter, Cédric Archambeau
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Classification, General Classification, Multi-Task Learning, regression

We propose a new sparse Bayesian model for multi-task regression and classification. The model is able to capture correlations between tasks, or more specifically a low-rank approximation of the covariance matrix, while being sparse in the features. We introduce a general family of group sparsity inducing priors based on matrix-variate Gaussian scale mixtures. We show the amount of sparsity can be learnt from the data by combining an approximate inference approach with type II maximum likelihood estimation of the hyperparameters. Empirical evaluations on data sets from biology and vision demonstrate the applicability of the model, where on both regression and classification tasks it achieves competitive predictive performance compared to previously proposed methods.
Online Learning: Stochastic, Constrained, and Smoothed Adversaries
Authors: Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Learning Theory

Learning theory has largely focused on two main learning scenarios: the classical statistical setting where instances are drawn i.i.d. from a fixed distribution, and the adversarial scenario whereby at every time step the worst instance is revealed to the player. It can be argued that in the real world neither of these assumptions is reasonable. We define the minimax value of a game where the adversary is restricted in his moves, capturing stochastic and non-stochastic assumptions on data. Building on the sequential symmetrization approach, we define a notion of distribution-dependent Rademacher complexity for the spectrum of problems ranging from i.i.d. to worst-case. The bounds let us immediately deduce variation-type bounds. We study a smoothed online learning scenario and show that exponentially small amount of noise can make function classes with infinite Littlestone dimension learnable.
Learning in Hilbert vs. Banach Spaces: A Measure Embedding Viewpoint
Authors: Kenji Fukumizu, Gert R. Lanckriet, Bharath K. Sriperumbudur
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

The goal of this paper is to investigate the advantages and disadvantages of learning in Banach spaces over Hilbert spaces. While many works have been carried out in generalizing Hilbert methods to Banach spaces, in this paper, we consider the simple problem of learning a Parzen window classifier in a reproducing kernel Banach space (RKBS)---which is closely related to the notion of embedding probability measures into an RKBS---in order to carefully understand its pros and cons over the Hilbert space classifier. We show that while this generalization yields richer distance measures on probabilities compared to its Hilbert space counterpart, it however suffers from serious computational drawback limiting its practical applicability, which therefore demonstrates the need for developing efficient learning algorithms in Banach spaces.
Sparse Recovery with Brownian Sensing
Authors: Alexandra Carpentier, Odalric-Ambrym Maillard, Rémi Munos
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We consider the problem of recovering the parameter alpha in R^K of a sparse function f, i.e. the number of non-zero entries of alpha is small compared to the number K of features, given noisy evaluations of f at a set of well-chosen sampling points. We introduce an additional randomisation process, called Brownian sensing, based on the computation of stochastic integrals, which produces a Gaussian sensing matrix, for which good recovery properties are proven independently on the number of sampling points N, even when the features are arbitrarily non-orthogonal. Under the assumption that f is Hölder continuous with exponent at least 1/2, we provide an estimate a of the parameter such that ||\alpha - a||_2 = O(||eta||_2\sqrt{N}), where eta is the observation noise. The method uses a set of sampling points uniformly distributed along a one-dimensional curve selected according to the features. We report numerical experiments illustrating our method.
An Unsupervised Decontamination Procedure For Improving The Reliability Of Human Judgments
Authors: Michael C. Mozer, Benjamin Link, Harold Pashler
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Informativeness

Psychologists have long been struck by individuals' limitations in expressing their internal sensations, impressions, and evaluations via rating scales.  Instead of using an absolute scale, individuals rely on reference points from recent experience.  This _relativity of judgment_ limits  the informativeness of responses on surveys, questionnaires, and evaluation forms. Fortunately, the cognitive processes that map stimuli to responses are not simply noisy, but rather are influenced by recent experience in a lawful manner.  We explore techniques to remove sequential dependencies, and thereby  _decontaminate_ a series of ratings to obtain more meaningful human  judgments.  In our formulation, the problem is to infer latent (subjective) impressions from a sequence of stimulus labels (e.g., movie names) and responses.  We describe an unsupervised approach that simultaneously recovers  the impressions and parameters of a contamination model that predicts how  recent judgments affect the current response.  We test our _iterated  impression inference_, or I^3, algorithm in three domains:  rating the gap between dots, the desirability of a movie based on an advertisement, and the morality of an action. We demonstrate significant objective improvements  in the quality of the recovered impressions.
Bayesian Bias Mitigation for Crowdsourcing
Authors: Fabian L. Wauthier, Michael. I. Jordan
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Active Learning

Biased labelers are a systemic problem in crowdsourcing, and a  comprehensive toolbox for handling their responses is still being  developed. A typical crowdsourcing application can be divided into  three steps: data collection, data curation, and learning. At present  these steps are often treated separately. We present Bayesian Bias  Mitigation for Crowdsourcing (BBMC), a Bayesian model to unify all  three. Most data curation methods account for the {\it effects} of  labeler bias by modeling all labels as coming from a single latent  truth. Our model captures the {\it sources} of bias by describing  labelers as influenced by shared random effects. This approach can  account for more complex bias patterns that arise in ambiguous or hard  labeling tasks and allows us to merge data curation and learning into  a single computation. Active learning integrates data collection with  learning, but is commonly considered infeasible with Gibbs sampling  inference. We propose a general approximation strategy for Markov  chains to efficiently quantify the effect of a perturbation on the  stationary distribution and specialize this approach to active  learning. Experiments show BBMC to outperform many common heuristics.
Ranking annotators for crowdsourced labeling tasks
Authors: Vikas C. Raykar, Shipeng Yu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

With the advent of crowdsourcing services it has become quite cheap and reasonably effective to get a dataset labeled by multiple annotators in a short amount of time. Various methods have been proposed to estimate the consensus labels by correcting for the bias of annotators with different kinds of expertise. Often we have low quality annotators or spammers--annotators who assign labels randomly (e.g., without actually looking at the instance). Spammers can make the cost of acquiring labels very expensive and can potentially degrade the quality of the consensus labels. In this paper we formalize the notion of a spammer and define a score which can be used to rank the annotators---with the spammers having a score close to zero and the good annotators having a high score close to one.
Clustering via Dirichlet Process Mixture Models for Portable Skill Discovery
Authors: Scott Niekum, Andrew G. Barto
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering, Reinforcement Learning, Reinforcement Learning (RL)

Skill discovery algorithms in reinforcement learning typically identify single states or regions in state space that correspond to task-specific subgoals.  However, such methods do not directly address the question of how many distinct skills are appropriate for solving the tasks that the agent faces.  This can be highly inefficient when many identified subgoals correspond to the same underlying skill, but are all used individually as skill goals.  Furthermore, skills created in this manner are often only transferable to tasks that share identical state spaces, since corresponding subgoals across tasks are not merged into a single skill goal.  We show that these problems can be overcome by clustering subgoal data defined in an agent-space and using the resulting clusters as templates for skill termination conditions.  Clustering via a Dirichlet process mixture model is used to discover a minimal, sufficient collection of portable skills.
Probabilistic Joint Image Segmentation and Labeling
Authors: Adrian Ion, Joao Carreira, Cristian Sminchisescu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Image Segmentation, Segmentation, Semantic Segmentation

We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories.  The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag, followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning.   We show that the proposed methodology matches the current state of the art in the Stanford dataset, as well as in VOC2010, where 41.7% accuracy on the test set is achieved.
Variance Reduction in Monte-Carlo Tree Search
Authors: Joel Veness, Marc Lanctot, Michael Bowling
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Decision Making

Monte-Carlo Tree Search (MCTS) has proven to be a powerful, generic planning technique for decision-making in single-agent and adversarial environments. The stochastic nature of the Monte-Carlo simulations introduces errors in the value estimates, both in terms of bias and variance. Whilst reducing bias (typically through the addition of domain knowledge) has been studied in the MCTS literature, comparatively little effort has focused on reducing variance. This is somewhat surprising, since variance reduction techniques are a well-studied area in classical statistics. In this paper, we examine the application of some standard techniques for variance reduction in MCTS, including common random numbers, antithetic variates and control variates. We demonstrate how these techniques can be applied to MCTS and explore their efficacy on three different stochastic, single-agent settings: Pig, Can't Stop and Dominion.
Learning Patient-Specific Cancer Survival Distributions as a Sequence of Dependent Regressors
Authors: Chun-Nam Yu, Russell Greiner, Hsiu-Chin Lin, Vickie Baracos
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression, Survival Analysis

An accurate model of patient survival time can help in the treatment and care of cancer patients. The common practice of providing survival time estimates based only on population averages for the site and stage of cancer ignores many important individual differences among patients. In this paper, we propose a local regression method for learning patient-specific survival time distribution based on patient attributes such as blood tests and clinical assessments. When tested on a cohort of more than 2000 cancer patients, our method gives survival time predictions that are much more accurate than popular survival analysis models such as the Cox and Aalen regression models. Our results also show that using patient-specific attributes can reduce the prediction error on survival time by as much as 20% when compared to using cancer site and stage only.
An Application of Tree-Structured Expectation Propagation for Channel Decoding
Authors: Pablo M. Olmos, Luis Salamanca, Juan Fuentes, Fernando Pérez-Cruz
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We show an application of a tree structure for approximate inference in graphical models using the expectation propagation algorithm. These approximations are typically used over graphs with short-range cycles. We demonstrate that these approximations also help in sparse graphs with long-range loops, as the ones used in coding theory to approach channel capacity. For asymptotically large sparse graph, the expectation propagation algorithm together with the tree structure yields a completely disconnected approximation to the graphical model but, for for finite-length practical sparse graphs, the tree structure approximation to the code graph provides accurate estimates for the marginal of each variable.
High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions
Authors: Animashree Anandkumar, Vincent Tan, Alan S. Willsky
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Model Selection, Vocal Bursts Intensity Prediction

We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm   for structure estimation based known as  conditional mutual information test. This simple local algorithm    requires only low-order statistics of the data and decides    whether  two nodes   are neighbors in the unknown graph. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent)  when the number of samples scales as n= Omega(J_{min}^{-4} log p), where p is the number of nodes and J_{min} is the minimum edge potential.  We also prove novel non-asymptotic necessary conditions for graphical model selection.
Structural equations and divisive normalization for energy-dependent component analysis
Authors: Jun-Ichiro Hirayama, Aapo Hyvärinen
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Components estimated by independent component analysis and related methods  are typically not independent in real data. A very common form of nonlinear  dependency between the components is correlations in their variances or ener-  gies. Here, we propose a principled probabilistic model to model the energy-  correlations between the latent variables. Our two-stage model includes a linear  mixing of latent signals into the observed ones like in ICA. The main new fea-  ture is a model of the energy-correlations based on the structural equation model  (SEM), in particular, a Linear Non-Gaussian SEM. The SEM is closely related to  divisive normalization which effectively reduces energy correlation. Our new two-  stage model enables estimation of both the linear mixing and the interactions re-  lated to energy-correlations, without resorting to approximations of the likelihood  function or other non-principled approaches. We demonstrate the applicability of  our method with synthetic dataset, natural images and brain signals.
Robust Lasso with missing and grossly corrupted observations
Authors: Nasser M. Nasrabadi, Trac. D. Tran, Nam Nguyen
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

This paper studies the problem of accurately recovering a sparse vector $\beta^{\star}$ from highly corrupted linear measurements $y = X \beta^{\star} + e^{\star} + w$ where $e^{\star}$ is a sparse error vector whose nonzero entries may be unbounded and $w$ is a bounded noise. We propose a so-called extended Lasso optimization which takes into consideration sparse prior information of both $\beta^{\star}$ and $e^{\star}$. Our first result shows that the extended Lasso can faithfully recover both the regression and the corruption vectors. Our analysis is relied on a notion of extended restricted eigenvalue for the design matrix $X$. Our second set of results applies to a general class of Gaussian design matrix $X$ with i.i.d rows $\oper N(0, \Sigma)$, for which we provide a surprising phenomenon: the extended Lasso can recover exact signed supports of both $\beta^{\star}$ and $e^{\star}$ from only $\Omega(k \log p \log n)$ observations, even the fraction of corruption is arbitrarily close to one. Our analysis also shows that this amount of observations required to achieve exact signed support is optimal.
A concave regularization technique for sparse mixture models
Authors: Martin O. Larsson, Johan Ugander
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Latent variable mixture models are a powerful tool for exploring the structure in large datasets. A common challenge for interpreting such models is a desire to impose sparsity, the natural assumption that each data point only contains few latent features. Since mixture distributions are constrained in their L1 norm, typical sparsity techniques based on L1 regularization become toothless, and concave regularization becomes necessary. Unfortunately concave regularization typically results in EM algorithms that must perform problematic non-concave M-step maximizations. In this work, we introduce a technique for circumventing this difficulty, using the so-called Mountain Pass Theorem to provide easily verifiable conditions under which the M-step is well-behaved despite the lacking concavity. We also develop a correspondence between logarithmic regularization and what we term the pseudo-Dirichlet distribution, a generalization of the ordinary Dirichlet distribution well-suited for inducing sparsity. We demonstrate our approach on a text corpus, inferring a sparse topic mixture model for 2,406 weblogs.