pwc-archive/papers-with-abstracts huggingface dataset:
Interval Estimation for Reinforcement-Learning Algorithms in Continuous-State Domains
Authors: Martha White, Adam White
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Decision Making, parameter estimation, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

The reinforcement learning community has explored many approaches to obtain- ing value estimates and models to guide decision making; these approaches, how- ever, do not usually provide a measure of confidence in the estimate. Accurate estimates of an agent’s confidence are useful for many applications, such as bi- asing exploration and automatically adjusting parameters to reduce dependence on parameter-tuning. Computing confidence intervals on reinforcement learning value estimates, however, is challenging because data generated by the agent- environment interaction rarely satisfies traditional assumptions. Samples of value- estimates are dependent, likely non-normally distributed and often limited, partic- ularly in early learning when confidence estimates are pivotal. In this work, we investigate how to compute robust confidences for value estimates in continuous Markov decision processes. We illustrate how to use bootstrapping to compute confidence intervals online under a changing policy (previously not possible) and prove validity under a few reasonable assumptions. We demonstrate the applica- bility of our confidence estimation algorithms with experiments on exploration, parameter estimation and tracking.
Active Learning Applied to Patient-Adaptive Heartbeat Classification
Authors: Jenna Wiens, John V. Guttag
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Active Learning, Classification, General Classification, Heartbeat Classification

While clinicians can accurately identify different types of heartbeats in electrocardiograms (ECGs) from different patients, researchers have had limited success in applying supervised machine learning to the same task. The problem is made challenging by the variety of tasks, inter- and intra-patient differences, an often severe class imbalance, and the high cost of getting cardiologists to label data for individual patients. We address these difficulties using active learning to perform patient-adaptive and task-adaptive heartbeat classification. When tested on a benchmark database of cardiologist annotated ECG recordings, our method had considerably better performance than other recently proposed methods on the two primary classification tasks recommended by the Association for the Advancement of Medical Instrumentation. Additionally, our method required over 90% less patient-specific training data than the methods to which we compared it.
Probabilistic Inference and Differential Privacy
Authors: Oliver Williams, Frank McSherry
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We identify and investigate a strong connection between probabilistic inference and differential privacy, the latter being a recent privacy definition that permits only indirect observation of data through noisy measurement. Previous research on differential privacy has focused on designing measurement processes whose output is likely to be useful on its own. We consider the potential of applying probabilistic inference to the measurements and measurement process to derive posterior distributions over the data sets and model parameters thereof. We find that probabilistic inference can improve accuracy, integrate multiple observations, measure uncertainty, and even provide posterior distributions over quantities that were not directly measured.
Copula Processes
Authors: Andrew G. Wilson, Zoubin Ghahramani
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Bayesian Inference

We define a copula process which describes the dependencies between arbitrarily many random variables independently of their marginal distributions. As an example, we develop a stochastic volatility model, Gaussian Copula Process Volatility (GCPV), to predict the latent standard deviations of a sequence of random variables. To make predictions we use Bayesian inference, with the Laplace approximation, and with Markov chain Monte Carlo as an alternative. We find our model can outperform GARCH on simulated and financial data. And unlike GARCH, GCPV can easily handle missing data, incorporate covariates other than time, and model a rich class of covariance structures.
Linear readout from a neural population with partial correlation data
Authors: Adrien Wohrer, Ranulfo Romo, Christian K. Machens
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

How much information does a neural population convey about a stimulus? Answers to this question are known to strongly depend on the correlation of response variability in neural populations. These noise correlations, however, are essentially immeasurable as the number of parameters in a noise correlation matrix grows quadratically with population size. Here, we suggest to bypass this problem by imposing a parametric model on a noise correlation matrix. Our basic assumption is that noise correlations arise due to common inputs between neurons. On average, noise correlations will therefore reflect signal correlations, which can be measured in neural populations. We suggest an explicit parametric dependency between signal and noise correlations. We show how this dependency can be used to fill the gaps" in noise correlations matrices using an iterative application of the Wishart distribution over positive definitive matrices. We apply our method to data from the primary somatosensory cortex of monkeys performing a two-alternative-forced choice task. We compare the discrimination thresholds read out from the population of recorded neurons with the discrimination threshold of the monkey and show that our method predicts different results than simpler, average schemes of noise correlations."
A unified model of short-range and long-range motion perception
Authors: Shuang Wu, Xuming He, Hongjing Lu, Alan L. Yuille
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

The human vision system is able to effortlessly perceive both short-range and long-range motion patterns in complex dynamic scenes. Previous work has assumed that two different mechanisms are involved in processing these two types of motion. In this paper, we propose a hierarchical model as a unified framework for modeling both short-range and long-range motion perception. Our model consists of two key components: a data likelihood that proposes multiple motion hypotheses using nonlinear matching, and a hierarchical prior that imposes slowness and spatial smoothness constraints on the motion field at multiple scales. We tested our model on two types of stimuli, random dot kinematograms and multiple-aperture stimuli, both commonly used in human vision research. We demonstrate that the hierarchical model adequately accounts for human performance in psychophysical experiments.
A Log-Domain Implementation of the Diffusion Network in Very Large Scale Integration
Authors: Yi-Da Wu, Shi-Jie Lin, Hsin Chen
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

The Diffusion Network(DN) is a stochastic recurrent network which has been shown capable of modeling the distributions of continuous-valued, continuous-time paths. However, the dynamics of the DN are governed by stochastic differential equations, making the DN unfavourable for simulation in a digital computer. This paper presents the implementation of the DN in analogue Very Large Scale Integration, enabling the DN to be simulated in real time. Moreover, the log-domain representation is applied to the DN, allowing the supply voltage and thus the power consumption to be reduced without limiting the dynamic ranges for diffusion processes. A VLSI chip containing a DN with two stochastic units has been designed and fabricated. The design of component circuits will be described, so will the simulation of the full system be presented. The simulation results demonstrate that the DN in VLSI is able to regenerate various types of continuous paths in real-time.
Distributionally Robust Markov Decision Processes
Authors: Huan Xu, Shie Mannor
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We consider Markov decision processes where the values of the parameters are uncertain. This uncertainty is described by a sequence of nested sets (that is, each set contains the previous one), each of which corresponds to a probabilistic guarantee for a different confidence level so that a set of admissible probability distributions of the unknown parameters is specified. This formulation models the case where the decision maker is aware of and wants to exploit some (yet imprecise) a-priori information of the distribution of parameters, and arises naturally in practice where methods to estimate the confidence region of parameters abound. We propose a decision criterion based on *distributional robustness*: the optimal policy maximizes the expected total reward under the most adversarial probability distribution over realizations of the uncertain parameters that is admissible (i.e., it agrees with the a-priori information). We show that finding the optimal distributionally robust policy can be reduced to a standard robust MDP where the parameters belong to a single uncertainty set, hence it can be computed in polynomial time under mild technical conditions.
Inference and communication in the game of Password
Authors: Yang Xu, Charles Kemp
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Communication between a speaker and hearer will be most efficient when both parties make accurate inferences about the other. We study inference and communication in a television game called Password, where speakers must convey secret words to hearers by providing one-word clues. Our working hypothesis is that human communication is relatively efficient, and we use game show data to examine three predictions. First, we predict that speakers and hearers are both considerate, and that both take the other’s perspective into account. Second, we predict that speakers and hearers are calibrated, and that both make accurate assumptions about the strategy used by the other. Finally, we predict that speakers and hearers are collaborative, and that they tend to share the cognitive burden of communication equally. We find evidence in support of all three predictions, and demonstrate in addition that efficient communication tends to break down when speakers and hearers are placed under time pressure.
Feature Transitions with Saccadic Search: Size, Color, and Orientation Are Not Alike
Authors: Stella X. Yu
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Attribute

Size, color, and orientation have long been considered elementary features whose attributes are extracted in parallel and available to guide the deployment of attention. If each is processed in the same fashion with simply a different set of local detectors, one would expect similar search behaviours on localizing an equivalent flickering change among identically laid out disks. We analyze feature transitions associated with saccadic search and find out that size, color, and orientation are not alike in dynamic attribute processing over time. The Markovian feature transition is attractive for size, repulsive for color, and largely reversible for orientation.
Relaxed Clipping: A Global Training Method for Robust Regression and Classification
Authors: Min Yang, Linli Xu, Martha White, Dale Schuurmans, Yao-Liang Yu
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Classification, General Classification, regression

Robust regression and classification are often thought to require non-convex loss functions that prevent scalable, global training. However, such a view neglects the possibility of reformulated training methods that can yield practically solvable alternatives. A natural way to make a loss function more robust to outliers is to truncate loss values that exceed a maximum threshold. We demonstrate that a relaxation of this form of ``loss clipping'' can be made globally solvable and applicable to any standard loss while guaranteeing robustness against outliers. We present a generic procedure that can be applied to standard loss functions and demonstrate improved robustness in regression and classification problems.
Lower Bounds on Rate of Convergence of Cutting Plane Methods
Authors: Xinhua Zhang, Ankan Saha, S. V. N. Vishwanathan
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

In a recent paper Joachims (2006) presented SVM-Perf, a cutting plane method (CPM) for training linear Support Vector Machines (SVMs) which converges to an $\epsilon$ accurate solution in $O(1/\epsilon^{2})$ iterations. By tightening the analysis, Teo et al. (2010) showed that $O(1/\epsilon)$ iterations suffice. Given the impressive convergence speed of CPM on a number of practical problems, it was conjectured that these rates could be further improved. In this paper we disprove this conjecture. We present counter examples which are not only applicable for training linear SVMs with hinge loss, but also hold for support vector methods which optimize a \emph{multivariate} performance score. However, surprisingly, these problems are not inherently hard. By exploiting the structure of the objective function we can devise an algorithm that converges in $O(1/\sqrt{\epsilon})$ iterations.
Learning Multiple Tasks with a Sparse Matrix-Normal Penalty
Authors: Yi Zhang, Jeff G. Schneider
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

In this paper, we propose a matrix-variate normal penalty with sparse inverse covariances to couple multiple tasks. Learning multiple (parametric) models can be viewed as estimating a matrix of parameters, where rows and columns of the matrix correspond to tasks and features, respectively. Following the matrix-variate normal density, we design a penalty that decomposes the full covariance of matrix elements into the Kronecker product of row covariance and column covariance, which characterizes both task relatedness and feature representation. Several recently proposed methods are variants of the special cases of this formulation. To address the overfitting issue and select meaningful task and feature structures, we include sparse covariance selection into our matrix-normal regularization via L-1 penalties on task and feature inverse covariances. We empirically study the proposed method and compare with related models in two real-world problems: detecting landmines in multiple fields and recognizing faces between different subjects. Experimental results show that the proposed framework provides an effective and flexible way to model various different structures of multiple tasks.
Probabilistic Multi-Task Feature Selection
Authors: Yu Zhang, Dit-yan Yeung, Qian Xu
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Cancer Classification, compressed sensing, feature selection, Multi-Task Learning

Recently, some variants of the $l_1$ norm, particularly matrix norms such as the $l_{1,2}$ and $l_{1,\infty}$ norms, have been widely used in multi-task learning, compressed sensing and other related areas to enforce sparsity via joint regularization. In this paper, we unify the $l_{1,2}$ and $l_{1,\infty}$ norms by considering a family of $l_{1,q}$ norms for $1 < q\le\infty$ and study the problem of determining the most appropriate sparsity enforcing norm to use in the context of multi-task feature selection. Using the generalized normal distribution, we provide a probabilistic interpretation of the general multi-task feature selection problem using the $l_{1,q}$ norm. Based on this probabilistic interpretation, we develop a probabilistic model using the noninformative Jeffreys prior. We also extend the model to learn and exploit more general types of pairwise relationships between tasks. For both versions of the model, we devise expectation-maximization~(EM) algorithms to learn all model parameters, including $q$, automatically. Experiments have been conducted on two cancer classification applications using microarray gene expression data.
Worst-Case Linear Discriminant Analysis
Authors: Yu Zhang, Dit-yan Yeung
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Dimensionality Reduction, Metric Learning

Dimensionality reduction is often needed in many applications due to the high dimensionality of the data involved. In this paper, we first analyze the scatter measures used in the conventional linear discriminant analysis~(LDA) model and note that the formulation is based on the average-case view. Based on this analysis, we then propose a new dimensionality reduction method called worst-case linear discriminant analysis~(WLDA) by defining new between-class and within-class scatter measures. This new model adopts the worst-case view which arguably is more suitable for applications such as classification. When the number of training data points or the number of features is not very large, we relax the optimization problem involved and formulate it as a metric learning problem. Otherwise, we take a greedy approach by finding one direction of the transformation at a time. Moreover, we also analyze a special case of WLDA to show its relationship with conventional LDA. Experiments conducted on several benchmark datasets demonstrate the effectiveness of WLDA when compared with some related dimensionality reduction methods.
Sufficient Conditions for Generating Group Level Sparsity in a Robust Minimax Framework
Authors: Hongbo Zhou, Qiang Cheng
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Generalization Bounds

Regularization technique has become a principle tool for statistics and machine learning research and practice. However, in most situations, these regularization terms are not well interpreted, especially on how they are related to the loss function and data. In this paper, we propose a robust minimax framework to interpret the relationship between data and regularization terms for a large class of loss functions. We show that various regularization terms are essentially corresponding to different distortions to the original data matrix. This minimax framework includes ridge regression, lasso, elastic net, fused lasso, group lasso, local coordinate coding, multiple kernel learning, etc., as special cases. Within this minimax framework, we further gave mathematically exact definition for a novel representation called sparse grouping representation (SGR), and proved sufficient conditions for generating such group level sparsity. Under these sufficient conditions, a large set of consistent regularization terms can be designed. This SGR is essentially different from group lasso in the way of using class or group information, and it outperforms group lasso when there appears group label noise. We also gave out some generalization bounds in a classification setting.
Large Margin Learning of Upstream Scene Understanding Models
Authors: Jun Zhu, Li-Jia Li, Li Fei-Fei, Eric P. Xing
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: General Classification, Prediction, Scene Classification, Scene Understanding, Topic Models

Upstream supervised topic models have been widely used for complicated scene understanding. However, existing maximum likelihood estimation (MLE) schemes can make the prediction model learning independent of latent topic discovery and result in an imbalanced prediction rule for scene classification. This paper presents a joint max-margin and max-likelihood learning method for upstream scene understanding models, in which latent topic discovery and prediction model estimation are closely coupled and well-balanced. The optimization problem is efficiently solved with a variational EM procedure, which iteratively solves an online loss-augmented SVM. We demonstrate the advantages of the large-margin approach on both an 8-category sports dataset and the 67-class MIT indoor scene dataset for scene categorization.
Parallelized Stochastic Gradient Descent
Authors: Martin Zinkevich, Markus Weimer, Lihong Li, Alex J. Smola
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

With the increase in available data parallel machine learning has   become an increasingly pressing problem. In this paper we present   the first parallel stochastic gradient descent algorithm including a   detailed analysis and experimental evidence. Unlike prior work on   parallel optimization algorithms our   variant comes with parallel acceleration guarantees and it poses no   overly tight latency constraints, which might only be available in   the multicore setting. Our analysis introduces a novel proof   technique --- contractive mappings to quantify the   speed of convergence of parameter distributions to their asymptotic   limits. As a side effect this answers the question of how quickly   stochastic gradient descent algorithms reach the asymptotically   normal regime.
A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups
Authors: Sofia Mosci, Silvia Villa, Alessandro Verri, Lorenzo Rosasco
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Variable Selection

We deal with the problem of variable selection when  variables must be selected group-wise, with possibly overlapping groups defined a priori. In particular we propose a new optimization procedure  for solving the regularized algorithm presented in Jacob et al. 09, where the group lasso  penalty is generalized to overlapping groups of variables. While in Jacob et al. 09 the proposed implementation requires explicit replication of the variables belonging to more than one group, our iterative procedure is based on a combination of proximal methods in the primal space and constrained Newton method in a reduced dual space, corresponding to the active groups.  This procedure provides a scalable alternative with no need for data duplication, and allows to deal with high dimensional problems without pre-processing  to reduce the  dimensionality of the data.  The computational advantages of our scheme with respect to state-of-the-art algorithms  using data duplication are shown empirically with numerical simulations.
Double Q-learning
Authors: Hado V. Hasselt
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In some stochastic environments the well-known reinforcement learning algorithm Q-learning performs very poorly. This poor performance is caused by large overestimations of action values. These overestimations result from a positive bias that is introduced because Q-learning uses the maximum action value as an approximation for the maximum expected action value. We introduce an alternative way to approximate the maximum expected value for any set of random variables. The obtained double estimator method is shown to sometimes underestimate rather than overestimate the maximum expected value. We apply the double estimator to Q-learning to construct Double Q-learning, a new off-policy reinforcement learning algorithm. We show the new algorithm converges to the optimal policy and that it performs well in some settings in which Q-learning performs poorly due to its overestimation.
Getting lost in space: Large sample analysis of the resistance distance
Authors: Ulrike V. Luxburg, Agnes Radl, Matthias Hein
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

The commute distance between two vertices in a graph is the expected   time it takes a random walk to travel from the first to the second   vertex and back. We study the behavior of the commute distance as the size of the underlying graph   increases. We prove that the commute distance converges to an   expression that does not take into account the structure of the   graph at all and that is completely meaningless as a distance   function on the graph. Consequently, the use of the raw commute   distance for machine learning purposes is strongly discouraged for   large graphs and in high dimensions. As an alternative we introduce   the amplified commute distance that corrects for   the undesired large sample effects.