pwc-archive/papers-with-abstracts huggingface dataset:
Optimal Scoring for Unsupervised Learning
Authors: Zhihua Zhang, Guang Dai
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering, General Classification, regression

We are often interested in casting classification and clustering problems in a regression framework, because it is feasible to achieve some statistical properties in this framework by imposing some penalty criteria. In this paper we illustrate optimal scoring, which was originally proposed for performing Fisher linear discriminant analysis by regression, in the application of unsupervised learning. In particular, we devise a novel clustering algorithm that we call optimal discriminant clustering (ODC). We associate our algorithm with the existing unsupervised learning algorithms such as spectral clustering, discriminative clustering and sparse principal component analysis. Thus, our work shows that optimal scoring  provides a new approach to the implementation of  unsupervised learning. This approach facilitates the development of new unsupervised learning algorithms.
Anomaly Detection with Score functions based on Nearest Neighbor Graphs
Authors: Manqi Zhao, Venkatesh Saligrama
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Anomaly Detection

We propose a novel non-parametric adaptive anomaly detection algorithm for high dimensional data based on score functions derived from nearest neighbor graphs on n-point nominal data. Anomalies are declared whenever the score of a test sample falls below q, which is supposed to be the desired false alarm level. The resulting anomaly detector is shown to be asymptotically optimal in that it is uniformly most powerful for the specified false alarm level, q, for the case when the anomaly density is a mixture of the nominal and a known density. Our algorithm is computationally efficient, being linear in dimension and quadratic in data size. It does not require choosing complicated tuning parameters or function approximation classes and it can adapt to local structure such as local change in dimensionality. We demonstrate the algorithm on both artificial and real data sets in high dimensional feature spaces.
DUOL: A Double Updating Approach for Online Learning
Authors: Peilin Zhao, Steven C. Hoi, Rong Jin
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

In most online learning algorithms, the weights assigned to the misclassified examples (or support vectors) remain unchanged during the entire learning process. This is clearly insufficient since when a new misclassified example is added to the pool of support vectors, we generally expect it to affect the weights for the existing support vectors. In this paper, we propose a new online learning method, termed Double Updating Online Learning", or "DUOL" for short. Instead of only assigning a fixed weight to the misclassified example received in current trial, the proposed online learning algorithm also tries to update the weight for one of the existing support vectors. We show that the mistake bound can be significantly improved by the proposed online learning method. Encouraging experimental results show that the proposed technique is in general considerably more effective than the state-of-the-art online learning algorithms."
Optimizing Multi-Class Spatio-Spectral Filters via Bayes Error Estimation for EEG Classification
Authors: Wenming Zheng, Zhouchen Lin
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Classification, EEG, Electroencephalogram (EEG), General Classification

The method of common spatio-spectral patterns (CSSPs) is an extension of common spatial patterns (CSPs) by utilizing the technique of delay embedding to alleviate the adverse effects of noises and artifacts on the electroencephalogram (EEG) classification. Although the CSSPs method has shown to be more powerful than the CSPs method in the EEG classification, this method is only suitable for two-class EEG classification problems. In this paper, we generalize the two-class CSSPs method to multi-class cases. To this end, we first develop a novel theory of multi-class Bayes error estimation and then present the multi-class CSSPs (MCSSPs) method based on this Bayes error theoretical framework. By minimizing the estimated closed-form Bayes error, we obtain the optimal spatio-spectral filters of MCSSPs. To demonstrate the effectiveness of the proposed method, we conduct extensive experiments on the data set of BCI competition 2005. The experimental results show that our method significantly outperforms the previous multi-class CSPs (MCSPs) methods in the EEG classification.
Efficient Moments-based Permutation Tests
Authors: Chunxiao Zhou, Huixia J. Wang, Yongmei M. Wang
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

In this paper, we develop an efficient moments-based permutation test approach to improve the system’s efficiency by approximating the permutation distribution of the test statistic with Pearson distribution series. This approach involves the calculation of the first four moments of the permutation distribution. We propose a novel recursive method to derive these moments theoretically and analytically without any permutation.  Experimental results using different test statistics are demonstrated using simulated data and real data. The proposed strategy takes advantage of nonparametric permutation tests and parametric Pearson distribution approximation to achieve both accuracy and efficiency.
Canonical Time Warping for Alignment of Human Behavior
Authors: Feng Zhou, Fernando Torre
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Dynamic Time Warping, Time Series, Time Series Analysis

Alignment of time series is an important problem to solve in many scientific disciplines. In particular, temporal alignment of two or more subjects performing similar activities is a challenging problem due to the large temporal scale difference between human actions as well as the inter/intra subject variability. In this paper we present canonical time warping (CTW), an extension of canonical correlation analysis (CCA) for spatio-temporal alignment of the behavior between two subjects. CTW extends previous work on CCA in two ways: (i) it combines CCA with dynamic time warping for temporal alignment; and (ii) it extends CCA to allow local spatial deformations. We show CTWs effectiveness in three experiments: alignment of synthetic data, alignment of motion capture data of two subjects performing similar actions, and alignment of two people with similar facial expressions. Our results demonstrate that CTW provides both visually and qualitatively better alignment than state-of-the-art techniques based on dynamic time warping.
Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations
Authors: Mingyuan Zhou, Haojun Chen, Lu Ren, Guillermo Sapiro, Lawrence Carin, John W. Paisley
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Bayesian Inference, Compressive Sensing, Denoising, Dictionary Learning

Non-parametric Bayesian techniques are considered for learning dictionaries for sparse image representations, with applications in denoising, inpainting and compressive sensing (CS). The beta process is employed as a prior for learning the dictionary, and this non-parametric method naturally infers an appropriate dictionary size. The Dirichlet process and a probit stick-breaking process are also considered to exploit structure within an image. The proposed method can learn a sparse dictionary in situ; training images may be exploited if available, but they are not required. Further, the noise variance need not be known, and can be non-stationary. Another virtue of the proposed method is that sequential inference can be readily employed, thereby allowing scaling to large images. Several example results are presented, using both Gibbs and variational Bayesian inference, with comparisons to other state-of-the-art approaches.
Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation
Authors: Shuheng Zhou
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Model Selection, Variable Selection, Vocal Bursts Intensity Prediction

Given $n$ noisy samples with $p$ dimensions, where $n \ll p$, we show that the multi-stage thresholding procedures can accurately estimate a sparse vector $\beta \in \R^p$ in a linear model, under the restricted eigenvalue conditions (Bickel-Ritov-Tsybakov 09). Thus our conditions for model selection consistency are considerably weaker than what has been achieved in previous works. More importantly, this method allows very significant values of $s$, which is the number of non-zero elements in the true parameter $\beta$. For example, it works for cases where the ordinary Lasso would have failed. Finally, we show that if $X$ obeys a uniform uncertainty principle and if the true parameter is sufficiently sparse, the Gauss-Dantzig selector (Cand\{e}s-Tao 07) achieves the $\ell_2$ loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle which would supply perfect information about which coordinates are non-zero and which are above the noise level, while selecting a sufficiently sparse model.
Nonparametric Bayesian Texture Learning and Synthesis
Authors: Long Zhu, Yuanahao Chen, Bill Freeman, Antonio Torralba
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Image Segmentation, Semantic Segmentation, Texture Synthesis

We present a nonparametric Bayesian method for texture learning and synthesis.  A texture image is represented by a 2D-Hidden Markov Model (2D-HMM) where the hidden states correspond to the cluster labeling of textons and the transition matrix encodes their spatial layout (the compatibility between adjacent textons). 2D-HMM is coupled with the Hierarchical Dirichlet process (HDP) which allows the number of textons and the complexity of transition matrix grow as the input texture becomes irregular. The HDP makes use of Dirichlet process prior which favors regular textures by penalizing the model complexity. This framework (HDP-2D-HMM) learns the texton vocabulary and their spatial layout jointly and automatically.  The HDP-2D-HMM results in a compact  representation of textures which allows fast texture synthesis with comparable rendering quality over the state-of-the-art image-based rendering methods. We also show that HDP-2D-HMM can be applied to perform image segmentation and synthesis.
Human Rademacher Complexity
Authors: Jerry Zhu, Bryan R. Gibson, Timothy T. Rogers
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Generalization Bounds, Learning Theory

We propose to use Rademacher complexity, originally developed in computational learning theory, as a measure of human learning capacity.  Rademacher complexity measures a learners ability to fit random data, and can be used to bound the learners true error based on the observed training sample error.  We first review the definition of Rademacher complexity and its generalization bound.  We then describe a learning the noise" procedure to experimentally measure human Rademacher complexities.  The results from empirical studies showed that: (i) human Rademacher complexity can be successfully measured, (ii) the complexity depends on the domain and training sample size in intuitive ways, (iii) human learning respects the generalization bounds, (iv) the bounds can be useful in predicting the danger of overfitting in human learning.  Finally, we discuss the potential applications of human Rademacher complexity in cognitive science."
Slow Learners are Fast
Authors: Martin Zinkevich, John Langford, Alex J. Smola
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Online learning algorithms have impressive convergence properties   when it comes to risk minimization and convex games on very large   problems. However, they are inherently sequential in their design   which prevents them from taking advantage of modern multi-core   architectures. In this paper we prove that online learning with   delayed updates converges well, thereby facilitating parallel online   learning.
The 'tree-dependent components' of natural scenes are edge filters
Authors: Daniel Zoran, Yair Weiss
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Form

We propose a new model for natural image statistics. Instead of minimizing dependency between components of natural images, we maximize a simple form of dependency in the form of tree-dependency. By learning filters and tree structures which are best suited for natural images we observe that the resulting filters are edge filters, similar to the famous ICA on natural images results. Calculating the likelihood of the model requires estimating the squared output of pairs of filters connected in the tree. We observe that after learning, these pairs of filters are predominantly of similar orientations but different phases, so their joint energy resembles models of complex cells.
Structure Learning in Human Sequential Decision-Making
Authors: Daniel Acuna, Paul R. Schrater
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Decision Making, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Sequential Decision Making

We use graphical models and structure learning to explore how people learn policies in sequential decision making tasks. Studies of sequential decision-making in humans frequently find suboptimal performance relative to an ideal actor that knows the graph model that generates reward in the environment. We argue that the learning problem humans face also involves learning the graph structure for reward generation in the environment. We formulate the structure learning problem using mixtures of reward models, and solve the optimal action selection problem using Bayesian Reinforcement Learning. We show that structure learning in one and two armed bandit problems produces many of the qualitative behaviors deemed suboptimal in previous studies. Our argument is supported by the results of experiments that demonstrate humans rapidly learn and exploit new reward structure.
The Gaussian Process Density Sampler
Authors: Iain Murray, David Mackay, Ryan P. Adams
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Density Estimation

We present the Gaussian Process Density Sampler (GPDS), an exchangeable generative model for use in nonparametric Bayesian density estimation. Samples drawn from the GPDS are consistent with exact, independent samples from a fixed density function that is a transformation of a function drawn from a Gaussian process prior. Our formulation allows us to infer an unknown density from data using Markov chain Monte Carlo, which gives samples from the posterior distribution over density functions and from the predictive distribution on data space. We can also infer the hyperparameters of the Gaussian process. We compare this density modeling technique to several existing techniques on a toy problem and a skull-reconstruction task.
Online Models for Content Optimization
Authors: Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, Nitin Motgi, Seung-Taek Park, Raghu Ramakrishnan, Scott Roy, Joe Zachariah
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Articles

We describe a new content publishing system that selects articles to serve to a user, choosing from an editorially programmed pool that is frequently refreshed. It is now deployed on a major Internet portal, and selects articles to serve to hundreds of millions of user visits per day, significantly increasing the number of user clicks over the original manual approach, in which editors periodically selected articles to display. Some of the challenges we face include a dynamic content pool, short article lifetimes, non-stationary click-through rates, and extremely high traffic volumes. The fundamental problem we must solve is to quickly identify which items are popular(perhaps within different user segments), and to exploit them while they remain current. We must also explore the underlying pool constantly to identify promising alternatives, quickly discarding poor performers. Our approach is based on tracking per article performance in near real time through online models. We describe the characteristics and constraints of our application setting, discuss our design choices, and show the importance and effectiveness of coupling online models with a simple randomization procedure. We discuss the challenges encountered in a production online content-publishing environment and highlight issues that deserve careful attention. Our analysis of this application also suggests a number of future research avenues.
Mixed Membership Stochastic Blockmodels
Authors: Edo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Variational Inference

Observations consisting of measurements on relationships for pairs of objects arise in many settings, such as protein interaction and gene regulatory networks, collections of author-recipient email, and social networks. Analyzing such data with probabilisic models can be delicate because the simple exchangeability assumptions underlying many boilerplate models no longer hold. In this paper, we describe a class of latent variable models of such data called Mixed Membership Stochastic Blockmodels. This model extends blockmodels for relational data to ones which capture mixed membership latent relational structure, thus providing an object-specific low-dimensional representation. We develop a general variational inference algorithm for fast approximate posterior inference. We explore applications to social networks and protein interaction networks.
Nonrigid Structure from Motion in Trajectory Space
Authors: Ijaz Akhter, Yaser Sheikh, Sohaib Khan, Takeo Kanade
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12

Existing approaches to nonrigid structure from motion assume that the instantaneous 3D shape of a deforming object is a linear combination of basis shapes, which have to be estimated anew for each video sequence. In contrast, we propose that the evolving 3D structure be described by a linear combination of basis trajectories. The principal advantage of this lateral approach is that we do not need to estimate any basis vectors during computation. Instead, we show that generic bases over trajectories, such as the Discrete Cosine Transform (DCT) bases, can be used to effectively describe most real motions. This results in a significant reduction in unknowns, and corresponding stability, in estimation. We report empirical performance, quantitatively using motion capture data and qualitatively on several video sequences exhibiting nonrigid motions including piece-wise rigid motion, articulated motion, partially nonrigid motion (such as a facial expression), and highly nonrigid motion (such as a person dancing).
Probabilistic detection of short events, with application to critical care monitoring
Authors: Norm Aleks, Stuart J. Russell, Michael G. Madden, Diane Morabito, Kristan Staudenmayer, Mitchell Cohen, Geoffrey T. Manley
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Decision Making

We describe an application of probabilistic modeling and inference technology to the problem of analyzing sensor data in the setting of an intensive care unit (ICU). In particular, we consider the arterial-line blood pressure sensor, which is subject to frequent data artifacts that cause false alarms in the ICU and make the raw data almost useless for automated decision making. The problem is complicated by the fact that the sensor data are acquired at fixed intervals whereas the events causing data artifacts may occur at any time and have durations that may be significantly shorter than the data collection interval. We show that careful modeling of the sensor, combined with a general technique for detecting sub-interval events and estimating their duration, enables effective detection of artifacts and accurate estimation of the underlying blood pressure values.
Sparse Convolved Gaussian Processes for Multi-output Regression
Authors: Mauricio Alvarez, Neil D. Lawrence
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Gaussian Processes, regression

We present a sparse approximation approach for dependent output Gaussian processes (GP). Employing a latent function framework, we apply the convolution process formalism to establish dependencies between output variables, where each latent function is represented as a GP. Based on these latent functions, we establish an approximation scheme using a conditional independence assumption between the output processes, leading to an approximation of the full covariance which is determined by the locations at which the latent functions are evaluated. We show results of the proposed methodology for synthetic data and real world applications on pollution prediction and a sensor network.
A Transductive Bound for the Voted Classifier with an Application to Semi-supervised Learning
Authors: Massih Amini, Nicolas Usunier, François Laviolette
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Self-Learning

In this paper we present two transductive bounds on the risk of the majority vote estimated over partially labeled training sets. Our first bound is tight when the additional unlabeled training data are used in the cases where the voted classifier makes its errors on low margin observations and where the errors of the associated Gibbs classifier can accurately be estimated. In semi-supervised learning, considering the margin as an indicator of confidence constitutes the working hypothesis of algorithms which search the decision boundary on low density regions. In this case, we propose a second bound on the joint probability that the voted classifier makes an error over an example having its margin over a fixed threshold. As an application we are interested on self-learning algorithms which assign iteratively pseudo-labels to unlabeled training examples having margin above a threshold obtained from this bound. Empirical results on different datasets show the effectiveness of our approach compared to the same algorithm and the TSVM in which the threshold is fixed manually.
Sparse probabilistic projections
Authors: Cédric Archambeau, Francis R. Bach
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12

We present a generative model for performing sparse probabilistic projections, which includes sparse principal component analysis and sparse canonical correlation analysis as special cases. Sparsity is enforced by means of automatic relevance determination or by imposing appropriate prior distributions, such as generalised hyperbolic distributions. We derive a variational Expectation-Maximisation algorithm for the estimation of the hyperparameters and show that our novel probabilistic approach compares favourably to existing techniques. We illustrate how the proposed method can be applied in the context of cryptoanalysis as a pre-processing tool for the construction of template attacks.
Asynchronous Distributed Learning of Topic Models
Authors: Padhraic Smyth, Max Welling, Arthur U. Asuncion
Date: 2008-12-01 00:00:00
Proceeding: NeurIPS 2008 12
Tasks: Topic Models

Distributed learning is a problem of fundamental interest in machine learning and cognitive science. In this paper, we present asynchronous distributed learning algorithms for two well-known unsupervised learning frameworks: Latent Dirichlet Allocation (LDA) and Hierarchical Dirichlet Processes (HDP). In the proposed approach, the data are distributed across P processors, and processors independently perform Gibbs sampling on their local data and communicate their information in a local asynchronous manner with other processors. We demonstrate that our asynchronous algorithms are able to learn global topic models that are statistically as accurate as those learned by the standard LDA and HDP samplers, but with significant improvements in computation time and memory. We show speedup results on a 730-million-word text corpus using 32 processors, and we provide perplexity results for up to 1500 virtual processors. As a stepping stone in the development of asynchronous HDP, a parallel HDP sampler is also introduced.