pwc-archive/papers-with-abstracts huggingface dataset:
Learning to Explore and Exploit in POMDPs
Authors: Chenghui Cai, Xuejun Liao, Lawrence Carin
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Active Learning, Reinforcement Learning

A fundamental objective in reinforcement learning is the maintenance of a proper balance between exploration and exploitation. This problem becomes more challenging when the agent can only partially observe the states of its environment. In this paper we propose a dual-policy method for jointly learning the agent behavior and the balance between exploration exploitation, in partially observable environments. The method subsumes traditional exploration, in which the agent takes actions to gather information about the environment, and active learning, in which the agent queries an oracle for optimal actions (with an associated cost for employing the oracle). The form of the employed exploration is dictated by the specific problem. Theoretical guarantees are provided concerning the optimality of the balancing of exploration and exploitation. The effectiveness of the method is demonstrated by experimental results on benchmark problems.
Speaker Comparison with Inner Product Discriminant Functions
Authors: Zahi Karam, Douglas Sturim, William M. Campbell
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering, Speaker Recognition, Speaker Verification

Speaker comparison, the process of finding the speaker similarity between two speech signals, occupies a central role in a variety of applications---speaker verification, clustering, and identification. Speaker comparison can be placed in a geometric framework by casting the problem as a model comparison process.  For a given speech signal, feature vectors are produced and used to adapt a Gaussian mixture model (GMM).  Speaker comparison can then be viewed as the process of compensating and finding metrics on the space of adapted models.  We propose a framework, inner product discriminant functions (IPDFs), which extends many common techniques for speaker comparison: support vector machines, joint factor analysis, and linear scoring.  The framework uses inner products between the parameter vectors of GMM models motivated by several statistical methods.  Compensation of nuisances is performed via linear transforms on GMM parameter vectors.  Using the IPDF framework, we show that many current techniques are simple variations of each other.  We demonstrate, on a 2006 NIST speaker recognition evaluation task, new scoring methods using IPDFs which produce excellent error rates and require significantly less computation than current techniques.
A Stochastic approximation method for inference in probabilistic graphical models
Authors: Peter Carbonetto, Matthew King, Firas Hamze
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Variational Inference

We describe a new algorithmic framework for inference in probabilistic models, and apply it to inference for latent Dirichlet allocation. Our framework adopts the methodology of variational inference, but unlike existing variational methods such as mean field and expectation propagation it is not restricted to tractable classes of approximating distributions. Our approach can also be viewed as a sequential Monte Carlo (SMC) method, but unlike existing SMC methods there is no need to design the artificial sequence of distributions. Notably, our framework offers a principled means to exchange the variance of an importance sampling estimate for the bias incurred through variational approximation. Experiments on a challenging inference problem in population genetics demonstrate improvements in stability and accuracy over existing methods, and at a comparable cost.
Bayesian Nonparametric Models on Decomposable Graphs
Authors: Francois Caron, Arnaud Doucet
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering

Over recent years Dirichlet processes and the associated Chinese restaurant process (CRP) have found many applications in clustering while the Indian buffet process (IBP) is increasingly used to describe latent feature models. In the clustering case, we associate to each data point a latent allocation variable. These latent variables can share the same value and this induces a partition of the data set. The CRP is a prior distribution on such partitions.  In latent feature models, we associate to each data point a potentially infinite number of binary latent variables indicating the possession of some features and the IBP is a prior distribution on the associated infinite binary matrix. These prior distributions are attractive because they ensure exchangeability (over samples). We propose here extensions of these models to decomposable graphs. These models have appealing properties and can be easily learned using Monte Carlo techniques.
Adaptive Design Optimization in Experiments with People
Authors: Daniel Cavagnaro, Jay Myung, Mark A. Pitt
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Model Selection

In cognitive science, empirical data collected from participants are the arbiters in model selection. Model discrimination thus depends on designing maximally informative experiments.  It has been shown that adaptive design optimization (ADO) allows one to discriminate models as efficiently as possible in simulation experiments.  In this paper we use ADO in a series of experiments with people to discriminate the Power, Exponential, and Hyperbolic models of memory retention, which has been a long-standing problem in cognitive science, providing an ideal setting in which to test the application of ADO for addressing questions about human cognition. Using an optimality criterion based on mutual information, ADO is able to find designs that are maximally likely to increase our certainty about the true model upon observation of the experiment outcomes.  Results demonstrate the usefulness of ADO and also reveal some challenges in its implementation.
Efficient Bregman Range Search
Authors: Lawrence Cayton
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Density Estimation, Information Retrieval, Outlier Detection, Retrieval

We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence.  The range search task is to return all points in a potentially large database that are within some specified distance of a query.  It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval.  In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks.  Here we describe the first algorithm for range search for an arbitrary Bregman divergence.   This broad class of dissimilarity measures includes the relative entropy,  Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences.  Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality.  We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences.
Discriminative Network Models of Schizophrenia
Authors: Irina Rish, Benjamin Thyreau, Bertrand Thirion, Marion Plaze, Marie-Laure Paillere-Martinot, Catherine Martelli, Jean-Luc Martinot, Jean-Baptiste Poline, Guillermo A. Cecchi
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Schizophrenia is a complex psychiatric disorder that has eluded a characterization in terms of local abnormalities of brain activity, and is hypothesized to affect the collective, ``emergent working of the brain. We propose a novel data-driven approach to capture emergent features using functional brain networks [Eguiluzet al] extracted from fMRI data, and demonstrate its advantage over traditional region-of-interest (ROI) and local, task-specific linear activation analyzes. Our results suggest that schizophrenia is indeed associated with disruption of global, emergent brain properties related to its functioning as a network, which cannot be explained by alteration of local activation patterns. Moreover, further exploitation of interactions by sparse Markov Random Field classifiers shows clear gain over linear methods, such as Gaussian Naive Bayes and SVM, allowing to reach 86% accuracy (over 50% baseline - random guess), which is quite remarkable given that it is based on a single fMRI experiment using a simple auditory task.
Learning with Compressible Priors
Authors: Volkan Cevher
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Bayesian Inference

We describe probability distributions, dubbed compressible priors, whose independent and identically distributed (iid) realizations result in compressible signals. A signal is compressible when sorted magnitudes of its coefficients exhibit a power-law decay so that the signal can be well-approximated by a sparse signal. Since compressible signals live close to sparse signals, their intrinsic information can be stably embedded via simple non-adaptive linear projections into a much lower dimensional space whose dimension grows logarithmically with the ambient signal dimension. By using order statistics, we show that N-sample iid realizations of generalized Pareto, Student’s t, log-normal, Frechet, and log-logistic distributions are compressible, i.e., they have a constant expected decay rate, which is independent of N. In contrast, we show that generalized Gaussian distribution with shape parameter q is compressible only in restricted cases since the expected decay rate of its N-sample iid realizations decreases with N as 1/[q log(N/q)]. We use compressible priors as a scaffold to build new iterative sparse signal recovery algorithms based on Bayesian inference arguments. We show how tuning of these algorithms explicitly depends on the parameters of the compressible prior of the signal, and how to learn the parameters of the signal’s compressible prior on the fly during recovery.
Exploring Functional Connectivities of the Human Brain using Multivariate Information Analysis
Authors: Barry Chai, Dirk Walther, Diane Beck, Li Fei-Fei
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Functional Connectivity

In this study, we present a method for estimating the mutual information for a localized pattern of fMRI data. We show that taking a multivariate information approach to voxel selection leads to a decoding accuracy that surpasses an univariate inforamtion approach and other standard voxel selection methods. Furthermore,we extend the multivariate mutual information theory to measure the functional connectivity between distributed brain regions. By jointly estimating the information shared by two sets of voxels we can reliably map out the connectivities in the human brain during experiment conditions. We validated our approach on a 6-way scene categorization fMRI experiment. The multivariate information analysis is able to ﬁnd strong information ﬂow between PPA and RSC, which conﬁrms existing neuroscience studies on scenes. Furthermore, by exploring over the whole brain, our method identifies other interesting ROIs that share information with the PPA, RSC scene network,suggesting interesting future work for neuroscientists.
Generalization Errors and Learning Curves for Regression with Multi-task Gaussian Processes
Authors: Kian M. Chai
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Gaussian Processes, regression

We provide some insights into how task correlations in multi-task Gaussian process (GP) regression affect the generalization error and the learning curve.  We analyze the asymmetric two-task case, where a secondary task is to help the learning of a primary task. Within this setting, we give bounds on the generalization error and the learning curve of the primary task. Our approach admits intuitive understandings of the multi-task GP by relating it to single-task GPs. For the case of one-dimensional input-space under optimal sampling with data only for the secondary task, the limitations of multi-task GP can be quantified explicitly.
A Parameter-free Hedging Algorithm
Authors: Kamalika Chaudhuri, Yoav Freund, Daniel J. Hsu
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We study the problem of decision-theoretic online learning (DTOL). Motivated by practical applications, we focus on DTOL when the number of actions is very large. Previous algorithms for learning in this framework have a tunable learning rate parameter, and a major barrier to using online-learning in practical applications is that it is not understood how to set this parameter optimally, particularly when the number of actions is large. In this paper, we offer a clean solution by proposing a novel and completely parameter-free algorithm for DTOL.   In addition, we introduce a new notion of regret, which is more natural for applications with a large number of actions. We show that our algorithm achieves good performance with respect to this new notion of regret; in addition, it also achieves performance close to that of the best bounds achieved by previous algorithms with optimally-tuned parameters, according to previous notions of regret.
An Online Algorithm for Large Scale Image Similarity Learning
Authors: Gal Chechik, Uri Shalit, Varun Sharma, Samy Bengio
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: CPU

Learning a measure of similarity between pairs of objects is a fundamental problem in machine learning. It stands in the core of classification methods like kernel machines, and is particularly useful for applications like searching for images that are similar to a given image or finding videos that are relevant to a given video. In these tasks, users look for objects that are not only visually similar but also semantically related to a given object. Unfortunately, current approaches for learning similarity may not scale to large datasets with high dimensionality, especially when imposing metric constraints on the learned similarity. We describe OASIS, a method for learning pairwise similarity that is fast and scales linearly with the number of objects and the number of non-zero features. Scalability is achieved through online learning of a bilinear model over sparse representations using a large margin criterion and an efficient hinge loss cost. OASIS is accurate at a wide range of scales: on a standard benchmark with thousands of images, it is more precise than state-of-the-art methods, and faster by orders of magnitude. On 2 million images collected from the web, OASIS can be trained within 3 days on a single CPU. The non-metric similarities learned by OASIS can be transformed into metric similarities, achieving higher precisions than similarities that are learned as metrics in the first place. This suggests an approach for learning a metric from data that is larger by an order of magnitude than was handled before.
Ranking Measures and Loss Functions in Learning to Rank
Authors: Wei Chen, Tie-Yan Liu, Yanyan Lan, Zhi-Ming Ma, Hang Li
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification, Learning-To-Rank

Learning to rank has become an important research topic in machine learning. While most learning-to-rank methods learn the ranking function by minimizing the loss functions, it is the ranking measures (such as NDCG and MAP) that are used to evaluate the performance of the learned ranking function. In this work, we reveal the relationship between ranking measures and loss functions in learning-to-rank methods, such as Ranking SVM, RankBoost, RankNet, and ListMLE. We show that these loss functions are upper bounds of the measure-based ranking errors. As a result, the minimization of these loss functions will lead to the maximization of the ranking measures. The key to obtaining this result is to model ranking as a sequence of classification tasks, and define a so-called essential loss as the weighted sum of the classification errors of individual tasks in the sequence. We have proved that the essential loss is both an upper bound of the measure-based ranking errors, and a lower bound of the loss functions in the aforementioned methods. Our proof technique also suggests a way to modify existing loss functions to make them tighter bounds of the measure-based ranking errors. Experimental results on benchmark datasets show that the modifications can lead to better ranking performance, demonstrating the correctness of our analysis.
Factor Modeling for Advertisement Targeting
Authors: Ye Chen, Michael Kapralov, John Canny, Dmitry Y. Pavlov
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We adapt a probabilistic latent variable model, namely GaP (Gamma-Poisson), to ad targeting in the contexts of sponsored search (SS) and behaviorally targeted (BT) display advertising. We also approach the important problem of ad positional bias by formulating a one-latent-dimension GaP factorization. Learning from click-through data is intrinsically large scale, even more so for ads. We scale up the algorithm to terabytes of real-world SS and BT data that contains hundreds of millions of users and hundreds of thousands of features, by leveraging the scalability characteristics of the algorithm and the inherent structure of the problem including data sparsity and locality. Specifically, we demonstrate two somewhat orthogonal philosophies of scaling algorithms to large-scale problems, through the SS and BT implementations, respectively. Finally, we report the experimental results using Yahoos vast datasets, and show that our approach substantially outperform the state-of-the-art methods in prediction accuracy. For BT in particular, the ROC area achieved by GaP is exceeding 0.95, while one prior approach using Poisson regression yielded 0.83. For computational performance, we compare a single-node sparse implementation with a parallel implementation using Hadoop MapReduce, the results are counterintuitive yet quite interesting. We therefore provide insights into the underlying principles of large-scale learning.
The Ordered Residual Kernel for Robust Motion Subspace Clustering
Authors: Tat-Jun Chin, Hanzi Wang, David Suter
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering, Computational Efficiency, Motion Segmentation, Segmentation

We present a novel and highly effective approach for multi-body motion segmentation. Drawing inspiration from robust statistical model fitting, we estimate putative subspace hypotheses from the data. However, instead of ranking them we encapsulate the hypotheses in a novel Mercer kernel which elicits the potential of two point trajectories to have emerged from the same subspace. The kernel permits the application of well-established statistical learning methods for effective outlier rejection, automatic recovery of the number of motions and accurate segmentation of the point trajectories. The method operates well under severe outliers arising from spurious trajectories or mistracks. Detailed experiments on a recent benchmark dataset (Hopkins 155) show that our method is superior to other state-of-the-art approaches in terms of recovering the number of motions, segmentation accuracy, robustness against gross outliers and computational efficiency.
Kernel Methods for Deep Learning
Authors: Youngmin Cho, Lawrence K. Saul
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Deep Learning

We introduce a new family of positive-definite kernel functions that mimic the computation in large, multilayer neural nets.  These kernel functions can be used in shallow architectures, such as support vector machines (SVMs), or in deep kernel-based architectures that we call multilayer kernel machines (MKMs).  We evaluate SVMs and MKMs with these kernel functions on problems designed to illustrate the advantages of deep architectures.  On several problems, we obtain better results than previous, leading benchmarks from both SVMs with Gaussian kernels as well as deep belief nets.
Approximating MAP by Compensating for Structural Relaxations
Authors: Arthur Choi, Adnan Darwiche
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We introduce a new perspective on approximations to the maximum a posteriori (MAP) task in probabilistic graphical models, that is based on simplifying a given instance, and then tightening the approximation.  First, we start with a structural relaxation of the original model.  We then infer from the relaxation its deficiencies, and compensate for them.  This perspective allows us to identify two distinct classes of approximations.  First, we find that max-product belief propagation can be viewed as a way to compensate for a relaxation, based on a particular idealized case for exactness.  We identify a second approach to compensation that is based on a more refined idealized case, resulting in a new approximation with distinct properties.  We go on to propose a new class of algorithms that, starting with a relaxation, iteratively yields tighter approximations.
AUC optimization and the two-sample problem
Authors: Nicolas Vayatis, Marine Depecker, Stéphan J. Clémençcon
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Vocal Bursts Valence Prediction

The purpose of the paper is to explore the connection between multivariate homogeneity tests and $\auc$ optimization. The latter problem has recently received much attention in the statistical learning literature. From the elementary observation that, in the two-sample problem setup, the null assumption corresponds to the situation where the area under the optimal ROC curve is equal to 1/2, we propose a two-stage testing method based on data splitting. A nearly optimal scoring function in the AUC sense is first learnt from one of the two half-samples. Data from the remaining half-sample are then projected onto the real line and eventually ranked according to the scoring function computed at the first stage. The last step amounts to performing a standard Mann-Whitney Wilcoxon  test in the one-dimensional framework. We show that the learning step of the procedure does not affect the consistency of the test as well as its properties in terms of power, provided the ranking produced is accurate enough in the AUC sense. The results of a numerical experiment are eventually displayed in order to show the efficiency of the method.
Statistical Models of Linear and Nonlinear Contextual Interactions in Early Visual Processing
Authors: Ruben Coen-Cagli, Peter Dayan, Odelia Schwartz
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

A central hypothesis about early visual processing is that it represents inputs in a coordinate system matched to the statistics of natural scenes. Simple versions of this lead to Gabor-like receptive fields and divisive gain modulation from local surrounds; these have led to influential neural and psychological models of visual processing. However, these accounts are based on an incomplete view of the visual context surrounding each point. Here, we consider an approximate model of linear and non-linear correlations between the responses of spatially distributed Gabor-like receptive fields, which, when trained on an ensemble of natural scenes, unifies a range of spatial context effects. The full model accounts for neural surround data in primary visual cortex (V1), provides a statistical foundation for perceptual phenomena associated with Lis (2002) hypothesis that V1 builds a saliency map, and fits data on the tilt illusion.