pwc-archive/papers-with-abstracts huggingface dataset:
A Reduction from Apprenticeship Learning to Classification
Authors: Umar Syed, Robert E. Schapire
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Classification, General Classification, Reinforcement Learning

We provide new theoretical results for apprenticeship learning, a variant of reinforcement learning in which the true reward function is unknown, and the goal is to perform well relative to an observed expert. We study a common approach to learning from expert demonstrations: using a classification algorithm to learn to imitate the expert's behavior. Although this straightforward learning strategy is widely-used in practice, it has been subject to very little formal analysis. We prove that, if the learned classifier has error rate $\eps$, the difference between the value of the apprentice's policy and the expert's policy is $O(\sqrt{\eps})$. Further, we prove that this difference is only $O(\eps)$ when the expert's policy is close to optimal. This latter result has an important practical consequence: Not only does imitating a near-optimal expert result in a better policy, but far fewer demonstrations are required to successfully imitate such an expert. This suggests an opportunity for substantial savings whenever the expert is known to be good, but demonstrations are expensive or difficult to obtain.
Identifying Patients at Risk of Major Adverse Cardiovascular Events Using Symbolic Mismatch
Authors: Zeeshan Syed, John V. Guttag
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Clustering, Decision Making, Time Series Analysis

Cardiovascular disease is the leading cause of death globally, resulting in 17 million deaths each year. Despite the availability of various treatment options, existing techniques based upon conventional medical knowledge often fail to identify patients who might have benefited from more aggressive therapy. In this paper, we describe and evaluate a novel unsupervised machine learning approach for cardiac risk stratification. The key idea of our approach is to avoid specialized medical knowledge, and assess patient risk using symbolic mismatch, a new metric to assess similarity in long-term time-series activity. We hypothesize that high risk patients can be identified using symbolic mismatch, as individuals in a population with unusual long-term physiological activity. We describe related approaches that build on these ideas to provide improved medical decision making for patients who have recently suffered coronary attacks. We first describe how to compute the symbolic mismatch between pairs of long term electrocardiographic (ECG) signals. This algorithm maps the original signals into a symbolic domain, and provides a quantitative assessment of the difference between these symbolic representations of the original signals. We then show how this measure can be used with each of a one-class SVM, a nearest neighbor classifier, and hierarchical clustering to improve risk stratification. We evaluated our methods on a population of 686 cardiac patients with available long-term electrocardiographic data. In a univariate analysis, all of the methods provided a statistically significant association with the occurrence of a major adverse cardiac event in the next 90 days. In a multivariate analysis that incorporated the most widely used clinical risk variables, the nearest neighbor and hierarchical clustering approaches were able to statistically significantly distinguish patients with a roughly two-fold risk of suffering a major adverse cardiac event in the next 90 days.
Switching state space model for simultaneously estimating state transitions and nonstationary firing rates
Authors: Ken Takiyama, Masato Okada
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We propose an algorithm for simultaneously estimating state transitions among neural states, the number of neural states, and nonstationary firing rates using a switching state space model (SSSM).  This model enables us to detect state transitions based not only on the discontinuous changes of mean firing rates but also on discontinuous changes in temporal profiles of firing rates, e.g., temporal correlation.  We derive a variational Bayes algorithm for a non-Gaussian SSSM whose non-Gaussian property is caused by binary spike events.  Synthetic data analysis reveals the high performance of our algorithm in estimating state transitions, the number of neural states, and nonstationary firing rates compared to previous methods.  We also analyze neural data recorded from the medial temporal area.  The statistically detected neural states probably coincide with transient and sustained states, which have been detected heuristically. Estimated parameters suggest that our algorithm detects the state transition based on discontinuous change in the temporal correlation of firing rates, which transitions previous methods cannot detect.  This result suggests the advantage of our algorithm in real-data analysis.
Pose-Sensitive Embedding by Nonlinear NCA Regression
Authors: Graham W. Taylor, Rob Fergus, George Williams, Ian Spiro, Christoph Bregler
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: regression

This paper tackles the complex problem of visually matching people in similar pose but with different clothes, background, and other appearance changes. We achieve this with a novel method for learning a nonlinear embedding based on several extensions to the Neighborhood Component Analysis (NCA) framework. Our method is convolutional, enabling it to scale to realistically-sized images. By cheaply labeling the head and hands in large video databases through Amazon Mechanical Turk (a crowd-sourcing service), we can use the task of localizing the head and hands as a proxy for determining body pose. We apply our method to challenging real-world data and show that it can generalize beyond hand localization to infer a more general notion of body pose. We evaluate our method quantitatively against other embedding methods. We also demonstrate that real-world performance can be improved through the use of synthetic data.
Fast Large-scale Mixture Modeling with Component-specific Data Partitions
Authors: Bo Thiesson, Chong Wang
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Remarkably easy implementation and guaranteed convergence has made the EM algorithm one of the most used algorithms for mixture modeling. On the downside, the E-step is linear in both the sample size and the number of mixture components, making it impractical for large-scale data. Based on the variational EM framework, we propose a fast alternative that uses component-specific data partitions to obtain a sub-linear E-step in sample size, while the algorithm still maintains provable convergence. Our approach builds on previous work, but is significantly faster and scales much better in the number of mixture components. We demonstrate this speedup by experiments on large-scale synthetic and real data.
Policy gradients in linearly-solvable MDPs
Authors: Emanuel Todorov
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We present policy gradient results within the framework of linearly-solvable MDPs. For the first time, compatible function approximators and natural policy gradients are obtained by estimating the cost-to-go function, rather than the (much larger) state-action advantage function as is necessary in traditional MDPs. We also develop the first compatible function approximators and natural policy gradients for continuous-time stochastic systems.
Phoneme Recognition with Large Hierarchical Reservoirs
Authors: Fabian Triefenbach, Azarakhsh Jalalvand, Benjamin Schrauwen, Jean-Pierre Martens
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Automatic Speech Recognition, Automatic Speech Recognition (ASR), Phoneme Recognition, speech-recognition, Speech Recognition

Automatic speech recognition has gradually improved over the years, but the reliable recognition of unconstrained speech is still not within reach. In order to achieve a breakthrough, many research groups are now investigating new methodologies that have potential to outperform the Hidden Markov Model technology that is at the core of all present commercial systems. In this paper, it is shown that the recently introduced concept of Reservoir Computing might form the basis of such a methodology. In a limited amount of time, a reservoir system that can recognize the elementary sounds of continuous speech has been built. The system already achieves a state-of-the-art performance, and there is evidence that the margin for further improvements is still significant.
Exact learning curves for Gaussian process regression on large random graphs
Authors: Matthew Urry, Peter Sollich
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: regression

We study learning curves for Gaussian process regression which characterise performance in terms of the Bayes error averaged over datasets of a given size. Whilst learning curves are in general very difficult to calculate we show that for discrete input domains, where similarity between input points is characterised in terms of a graph, accurate predictions can be obtained. These should in fact become exact for large graphs drawn from a broad range of random graph ensembles with arbitrary degree distributions where each input (node) is connected only to a finite number of others. The method is based on translating the appropriate belief propagation equations to the graph ensemble. We demonstrate the accuracy of the predictions for Poisson (Erdos-Renyi) and regular random graphs, and discuss when and why previous approximations to the learning curve fail.
Worst-case bounds on the quality of max-product fixed-points
Authors: Meritxell Vinyals, Jes\'Us Cerquides, Alessandro Farinelli, Juan A. Rodríguez-Aguilar
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We study worst-case bounds on the quality of any fixed point assignment of the max-product algorithm for Markov Random Fields (MRF). We start proving a bound   independent of the MRF structure and parameters. Afterwards, we show how this bound can be improved for MRFs with particular structures such as bipartite graphs or grids.  Our results provide interesting insight into the behavior of max-product. For example, we prove that max-product provides very good results (at least 90% of the optimal) on MRFs  with large variable-disjoint cycles (MRFs in which all cycles are variable-disjoint, namely that they do not share any edge and in which each cycle contains at least 20 variables).
Brain covariance selection: better individual functional connectivity models using population prior
Authors: Gael Varoquaux, Alexandre Gramfort, Jean-Baptiste Poline, Bertrand Thirion
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Functional Connectivity

Spontaneous brain activity, as observed in functional neuroimaging, has been shown to display reproducible structure that expresses brain architecture and carries markers of brain pathologies. An important view of modern neuroscience is that such large-scale structure of coherent activity reflects modularity properties of brain connectivity graphs. However, to date, there has been no demonstration that the limited and noisy data available in spontaneous activity observations could be used to learn full-brain probabilistic models that generalize to new data.  Learning such models entails two main challenges:  i) modeling full brain connectivity is a difficult estimation problem that faces the curse of dimensionality and  ii) variability between subjects, coupled with the variability of functional signals between experimental runs, makes the use of multiple datasets challenging.  We describe subject-level brain functional connectivity structure as a multivariate Gaussian process and introduce a new strategy to estimate it from group data, by imposing a common structure on the graphical model in the population. We show that individual models learned from functional Magnetic Resonance Imaging (fMRI) data using this population prior generalize better to unseen data than models based on alternative regularization schemes. To our knowledge, this is the first report of a cross-validated model of spontaneous brain activity. Finally, we use the estimated graphical model to explore the large-scale characteristics of functional architecture and show for the first time that known cognitive networks appear as the integrated communities of functional connectivity graph.
Fast detection of multiple change-points shared by many signals using group LARS
Authors: Jean-Philippe Vert, Kevin Bleakley
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We present a fast algorithm for the detection of multiple change-points when each is frequently shared by members of a set of co-occurring one-dimensional signals. We give conditions on consistency of the method when the number of signals increases, and provide empirical evidence to support the consistency results.
Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets
Authors: Paolo Viappiani, Craig Boutilier
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Bayesian approaches to utility elicitation typically adopt (myopic) expected value of information (EVOI) as a natural criterion for selecting queries.  However, EVOI-optimization is  usually computationally prohibitive.  In this paper, we examine EVOI optimization using \emph{choice queries}, queries in which a user  is ask to select her most preferred product from a set. We show that,  under very general assumptions, the optimal choice query w.r.t.\ EVOI coincides with \emph{optimal recommendation set}, that is, a set maximizing expected utility of the user selection. Since recommendation set optimization is a simpler, submodular problem, this can greatly reduce the complexity of both exact and approximate (greedy) computation of optimal choice queries.  We  also examine the case where user responses to choice queries are error-prone (using both constant and follow mixed multinomial logit  noise models) and provide worst-case guarantees.   Finally we present a local search technique that works well with large outcome spaces.
Multiple Kernel Learning and the SMO Algorithm
Authors: Zhaonan Sun, Nawanol Ampornpunt, Manik Varma, S. V. N. Vishwanathan
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Our objective is to train $p$-norm Multiple Kernel Learning (MKL) and, more generally, linear MKL regularised by the Bregman divergence, using the Sequential Minimal Optimization (SMO) algorithm. The SMO algorithm is simple, easy to implement and adapt, and efficiently scales to large problems. As a result, it has gained widespread acceptance and SVMs are routinely trained using SMO in diverse real world applications. Training using SMO has been a long standing goal in MKL for the very same reasons. Unfortunately, the standard MKL dual is not differentiable, and therefore can not be optimised using SMO style co-ordinate ascent. In this paper, we demonstrate that linear MKL regularised with the $p$-norm squared, or with certain Bregman divergences, can indeed be trained using SMO. The resulting algorithm retains both simplicity and efficiency and is significantly faster than the state-of-the-art specialised $p$-norm MKL solvers. We show that we can train on a hundred thousand kernels in approximately seven minutes and on fifty thousand points in less than half an hour on a single core.
Joint Analysis of Time-Evolving Binary Matrices and Associated Documents
Authors: Eric Wang, Dehong Liu, Jorge Silva, Lawrence Carin, David B. Dunson
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We consider problems for which one has incomplete binary matrices that evolve with time (e.g., the votes of legislators on particular legislation, with each year characterized by a different such matrix). An objective of such analysis is to infer structure and inter-relationships underlying the matrices, here defined by latent features associated with each axis of the matrix. In addition, it is assumed that documents are available for the entities associated with at least one of the matrix axes. By jointly analyzing the matrices and documents, one may be used to inform the other within the analysis, and the model offers the opportunity to predict matrix values (e.g., votes) based only on an associated document (e.g., legislation). The research presented here merges two areas of machine-learning that have previously been investigated separately: incomplete-matrix analysis and topic modeling. The analysis is performed from a Bayesian perspective, with efficient inference constituted via Gibbs sampling. The framework is demonstrated by considering all voting data and available documents (legislation) during the 220-year lifetime of the United States Senate and House of Representatives.
Unsupervised Kernel Dimension Reduction
Authors: Meihong Wang, Fei Sha, Michael. I. Jordan
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Classification, Clustering, Dimensionality Reduction, General Classification

We apply the framework of kernel dimension reduction, originally designed for supervised problems, to unsupervised dimensionality reduction. In this framework, kernel-based measures of independence are used to derive low-dimensional representations that maximally capture information in covariates in order to predict responses. We extend this idea and develop similarly motivated measures for unsupervised problems where covariates and responses are the same. Our empirical studies show that the resulting compact representation yields meaningful and appealing visualization and clustering of data. Furthermore, when used in conjunction with supervised learners for classification, our methods lead to lower classification errors than state-of-the-art methods, especially when embedding data in spaces of very few dimensions.
Multi-View Active Learning in the Non-Realizable Case
Authors: Wei Wang, Zhi-Hua Zhou
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Active Learning

The sample complexity of active learning under the realizability assumption has been well-studied. The realizability assumption, however, rarely holds in practice. In this paper, we theoretically characterize the sample complexity of active learning in the non-realizable case under multi-view setting. We prove that, with unbounded Tsybakov noise, the sample complexity of multi-view active learning can be $\widetilde{O}(\log \frac{1}{\epsilon})$, contrasting to single-view setting where the polynomial improvement is the best possible achievement. We also prove that in general multi-view setting the sample complexity of active learning with unbounded Tsybakov noise is $\widetilde{O}(\frac{1}{\epsilon})$, where the order of $1/\epsilon$ is independent of the parameter in Tsybakov noise, contrasting to previous polynomial bounds where the order of $1/\epsilon$ is related to the parameter in Tsybakov noise.
A Discriminative Latent Model of Image Region and Object Tag Correspondence
Authors: Yang Wang, Greg Mori
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: TAG

We propose a discriminative latent model for annotating images with unaligned object-level textual annotations. Instead of using the bag-of-words image representation currently popular in the computer vision community, our model explicitly captures more intricate relationships underlying visual and textual information. In particular, we model the mapping that translates image regions to annotations. This mapping allows us to relate image regions to their corresponding annotation terms. We also model the overall scene label as latent information. This allows us to cluster test images. Our training data consist of images and their associated annotations. But we do not have access to the ground-truth region-to-annotation mapping or the overall scene label. We develop a novel variant of the latent SVM framework to model them as latent variables. Our experimental results demonstrate the effectiveness of the proposed model compared with other baseline methods.
Heavy-Tailed Process Priors for Selective Shrinkage
Authors: Fabian L. Wauthier, Michael. I. Jordan
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Gaussian Processes, General Classification, regression

Heavy-tailed distributions are often used to enhance the robustness of regression and classification methods to outliers in output space.  Often, however, we are confronted with ``outliers'' in input space, which are isolated observations in sparsely populated regions. We show that heavy-tailed process priors (which we construct from Gaussian processes via a copula), can be used to improve robustness of regression and classification estimators to such outliers by selectively shrinking them more strongly in sparse regions than in dense regions. We carry out a theoretical analysis to show that selective shrinkage occurs provided the marginals of the heavy-tailed process have sufficiently heavy tails. The analysis is complemented by experiments on biological data which indicate significant improvements of estimates in sparse regions while producing competitive results in dense regions.
Sidestepping Intractable Inference with Structured Ensemble Cascades
Authors: David Weiss, Benjamin Sapp, Ben Taskar
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Pose Estimation, Structured Prediction

For many structured prediction problems, complex models often require adopting approximate inference techniques such as variational methods or sampling, which generally provide no satisfactory accuracy guarantees. In this work, we propose sidestepping intractable inference altogether by learning ensembles of tractable sub-models as part of a structured prediction cascade. We focus in particular on problems with high-treewidth and large state-spaces, which occur in many computer vision tasks. Unlike other variational methods, our ensembles do not enforce agreement between sub-models, but filter the space of possible outputs by simply adding and thresholding the max-marginals of each constituent model. Our framework jointly estimates parameters for all models in the ensemble for each level of the cascade by minimizing a novel, convex loss function, yet requires only a linear increase in computation over learning or inference in a single tractable sub-model. We provide a generalization bound on the filtering loss of the ensemble as a theoretical justification of our approach, and we evaluate our method on both synthetic data and the task of estimating articulated human pose from challenging videos. We find that our approach significantly outperforms loopy belief propagation on the synthetic data and a state-of-the-art model on the pose estimation/tracking problem.