pwc-archive/papers-with-abstracts huggingface dataset:
Automatic Feature Induction for Stagewise Collaborative Filtering
Authors: Joonseok Lee, Mingxuan Sun, Seungyeon Kim, Guy Lebanon
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Collaborative Filtering

Recent approaches to collaborative filtering have concentrated on estimating an algebraic or statistical model, and using the model for predicting missing ratings. In this paper we observe that different models have relative advantages in different regions of the input space. This motivates our approach of using stagewise linear combinations of collaborative filtering algorithms, with non-constant combination coefficients based on kernel smoothing. The resulting stagewise model is computationally scalable and outperforms a wide selection of state-of-the-art collaborative filtering algorithms.
Selective Labeling via Error Bound Minimization
Authors: Quanquan Gu, Tong Zhang, Jiawei Han, Chris H. Ding
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

In many practical machine learning problems, the acquisition of labeled data is often expensive and/or time consuming. This motivates us to study a problem as follows: given a label budget, how to select data points to label such that the learning performance is optimized. We propose a selective labeling method by analyzing the generalization error of Laplacian regularized Least Squares (LapRLS). In particular, we derive a deterministic generalization error bound for LapRLS trained on subsampled data, and propose to select a subset of data points to label by minimizing this upper bound. Since the minimization is a combinational problem, we relax it into continuous domain and solve it by projected gradient descent. Experiments on benchmark datasets show that the proposed method outperforms the state-of-the-art methods.
Volume Regularization for Binary Classification
Authors: Koby Crammer, Tal Wagner
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Binary Classification, Classification, General Classification, Optical Character Recognition, Optical Character Recognition (OCR)

We introduce a large-volume box classification for binary   prediction, which maintains a subset of weight vectors, and   specifically axis-aligned boxes. Our learning algorithm seeks for a   box of large volume that contains ``simple'' weight vectors which   most of are accurate on the training set. Two versions of the   learning process are cast as convex optimization problems, and it   is shown how to solve them efficiently.  The formulation yields a   natural PAC-Bayesian performance bound and it is shown to minimize a   quantity directly aligned with it. The algorithm outperforms SVM and   the recently proposed AROW algorithm on a majority of $30$ NLP   datasets and binarized USPS optical character recognition datasets.
Image Denoising and Inpainting with Deep Neural Networks
Authors: Junyuan Xie, Linli Xu, Enhong Chen
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Denoising, Image Denoising, Image Inpainting

We present a novel approach to low-level vision problems that combines sparse coding and deep networks pre-trained with denoising auto-encoder (DA). We propose an alternative training scheme that successfully adapts DA, originally designed for unsupervised feature learning, to the tasks of image denoising and blind inpainting. Our method achieves state-of-the-art performance in the image denoising task. More importantly, in blind image inpainting task, the proposed method provides solutions to some complex problems that have not been tackled before. Specifically, we can automatically remove complex patterns like superimposed text from an image, rather than simple patterns like pixels missing at random. Moreover, the proposed method does not need the information regarding the region that requires inpainting to be given a priori. Experimental results demonstrate the effectiveness of the proposed method in the tasks of image denoising and blind inpainting. We also show that our new training scheme for DA is more effective and can improve the performance of unsupervised feature learning.
Max-Margin Structured Output Regression for Spatio-Temporal Action Localization
Authors: Du Tran, Junsong Yuan
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Action Localization, Object Localization, regression, Spatio-Temporal Action Localization, Temporal Action Localization

Structured output learning has been successfully applied to object localization, where the mapping between an image and an object bounding box can be well captured. Its extension to action localization in videos, however, is much more challenging, because one needs to predict the locations of the action patterns both spatially and temporally, i.e., identifying a sequence of bounding boxes that track the action in video. The problem becomes intractable due to the exponentially large size of the structured video space where actions could occur. We propose a novel structured learning approach for spatio-temporal action localization. The mapping between a video and a spatio-temporal action trajectory is learned. The intractable inference and learning problems are addressed by leveraging an efficient Max-Path search method, thus makes it feasible to optimize the model over the whole structured space. Experiments on two challenging benchmark datasets show that our proposed method outperforms the state-of-the-art methods.
Action-Model Based Multi-agent Plan Recognition
Authors: Hankz H. Zhuo, Qiang Yang, Subbarao Kambhampati
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: model

Multi-Agent Plan Recognition (MAPR) aims to recognize dynamic team structures and team behaviors from the observed team traces (activity sequences) of a set of intelligent agents. Previous MAPR approaches required a library of team activity sequences (team plans) be given as input. However, collecting a library of team plans to ensure adequate coverage is often difficult and costly. In this paper, we relax this constraint, so that team plans are not required to be provided beforehand. We assume instead that a set of action models are available. Such models are often already created to describe domain physics; i.e., the  preconditions and effects of effects actions. We propose a novel approach for recognizing multi-agent team plans based on such action models rather than libraries of team plans. We encode the resulting MAPR problem as a \emph{satisfiability problem} and solve the problem using a state-of-the-art weighted MAX-SAT solver. Our approach also allows for incompleteness in the observed plan traces. Our empirical studies demonstrate that our algorithm is both effective and efficient in comparison to state-of-the-art MAPR methods based on plan libraries.
Visual Recognition using Embedded Feature Selection for Curvature Self-Similarity
Authors: Angela Eigenstetter, Bjorn Ommer
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: feature selection, Object, object-detection, Object Detection

Category-level object detection has a crucial need for informative object representations. This demand has led to feature descriptors of ever increasing dimensionality  like co-occurrence statistics and self-similarity. In this paper we propose a new object representation based on curvature self-similarity that goes beyond the currently popular  approximation of objects using straight lines. However, like all descriptors using second order statistics, ours also exhibits a high dimensionality. Although improving discriminability,  the high dimensionality becomes a critical issue due to lack of generalization ability and curse of dimensionality. Given only a limited amount of training data, even sophisticated  learning algorithms such as the popular kernel methods are not able to suppress noisy or superfluous dimensions of such high-dimensional data. Consequently, there is a natural need for  feature selection when using present-day informative features and, particularly, curvature self-similarity. We therefore suggest an embedded feature selection method for SVMs that  reduces complexity and improves generalization capability of object models. By successfully integrating the proposed curvature self-similarity representation together with the embedded  feature selection in a widely used state-of-the-art object detection framework we show the general pertinence of the approach.
Non-parametric Approximate Dynamic Programming via the Kernel Method
Authors: Nikhil Bhat, Vivek Farias, Ciamac C. Moallemi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

This paper presents a novel non-parametric approximate dynamic programming (ADP) algorithm that enjoys graceful, dimension-independent approximation and sample complexity guarantees. In particular, we establish both theoretically and computationally that our proposal can serve as a viable alternative to state-of-the-art parametric ADP algorithms, freeing the designer from carefully specifying an approximation architecture. We accomplish this by developing a kernel-based mathematical program for ADP. Via a computational study on a controlled queueing network, we show that our non-parametric procedure is competitive with parametric ADP approaches.
Optimal Regularized Dual Averaging Methods for Stochastic Optimization
Authors: Xi Chen, Qihang Lin, Javier Pena
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Stochastic Optimization

This paper considers a wide spectrum of regularized stochastic optimization problems where both the loss function and regularizer can be non-smooth.  We develop a novel algorithm based on the regularized dual averaging (RDA) method, that can simultaneously achieve the optimal convergence rates for both convex and strongly convex loss. In particular, for strongly convex loss, it achieves the optimal  rate of $O(\frac{1}{N}+\frac{1}{N^2})$ for $N$  iterations, which improves the best known rate $O(\frac{\log N }{N})$ of previous stochastic dual averaging algorithms. In addition, our method constructs the final solution directly from the proximal mapping instead of averaging of all previous iterates. For widely used sparsity-inducing regularizers (e.g., $\ell_1$-norm), it has the advantage of encouraging sparser solutions. We further develop a multi-stage extension using the proposed algorithm as a subroutine, which achieves the uniformly-optimal rate $O(\frac{1}{N}+\exp\{-N\})$ for strongly convex loss.
The variational hierarchical EM algorithm for clustering hidden Markov models
Authors: Emanuele Coviello, Gert R. Lanckriet, Antoni B. Chan
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, Music Tagging

In this paper, we derive a novel algorithm to cluster  hidden Markov models (HMMs) according to their probability distributions. We propose a variational hierarchical EM algorithm that i) clusters a given collection of HMMs into groups of HMMs that are similar, in terms of the distributions they represent, and ii) characterizes each group by a ``cluster center'', i.e., a novel HMM that is representative for the group. We illustrate the benefits of the proposed algorithm on hierarchical clustering of motion capture sequences as well as on automatic music tagging.
Truncation-free Online Variational Inference for Bayesian Nonparametric Models
Authors: Chong Wang, David M. Blei
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Topic Models, Variational Inference

We present a truncation-free online variational inference algorithm for Bayesian nonparametric models. Unlike traditional (online) variational inference algorithms that require truncations for the model or the variational distribution, our method adapts model complexity on the fly. Our experiments for Dirichlet process mixture models and hierarchical Dirichlet process topic models on two large-scale data sets show better performance than previous online variational inference algorithms.
Context-Sensitive Decision Forests for Object Detection
Authors: Peter Kontschieder, Samuel R. Bulò, Antonio Criminisi, Pushmeet Kohli, Marcello Pelillo, Horst Bischof
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification, Object, object-detection, Object Detection, Pedestrian Detection, Prediction, regression

In this paper we introduce Context-Sensitive Decision Forests - A new perspective to exploit contextual information in the popular decision forest framework for the object detection problem. They are tree-structured classifiers with the ability to access intermediate prediction (here: classification and regression) information during training and inference time. This intermediate prediction is available to each sample, which allows us to develop context-based decision criteria, used for refining the prediction process. In addition, we introduce a novel split criterion which in combination with a priority based way of constructing the trees, allows more accurate regression mode selection and hence improves the current context information. In our experiments, we demonstrate improved results for the task of pedestrian detection on the challenging TUD data set when compared to state-of-the-art methods.
Learning Invariant Representations of Molecules for Atomization Energy Prediction
Authors: Grégoire Montavon, Katja Hansen, Siamac Fazli, Matthias Rupp, Franziska Biegler, Andreas Ziehe, Alexandre Tkatchenko, Anatole V. Lilienfeld, Klaus-Robert Müller
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: BIG-bench Machine Learning

The accurate prediction of molecular energetics in chemical compound space is a crucial ingredient for rational compound design.  The inherently graph-like, non-vectorial nature of molecular data gives rise to a unique and difficult machine learning problem. In this paper, we adopt a learning-from-scratch approach where quantum-mechanical molecular energies are predicted directly from the raw molecular geometry. The study suggests a benefit from setting flexible priors and enforcing invariance stochastically rather than structurally. Our results improve the state-of-the-art by a factor of almost three, bringing statistical methods one step closer to the holy grail of ''chemical accuracy''.
Bandit Algorithms boost Brain Computer Interfaces for motor-task selection of a brain-controlled button
Authors: Joan Fruitet, Alexandra Carpentier, Maureen Clerc, Rémi Munos
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Brain Computer Interface, General Classification

A brain-computer interface (BCI) allows users to “communicate” with a computer without using their muscles. BCI based on sensori-motor rhythms use imaginary motor tasks, such as moving the right or left hand to send control signals. The performances of a BCI can vary greatly across users but also depend on the tasks used, making the problem of appropriate task selection an important issue. This study presents a new procedure to automatically select as fast as possible a discriminant motor task for a brain-controlled button. We develop for this purpose an adaptive algorithm UCB-classif based on the stochastic bandit theory. This shortens the training stage, thereby allowing the exploration of a greater variety of tasks. By not wasting time on inefficient tasks, and focusing on the most promising ones, this algorithm results in a faster task selection and a more efficient use of the BCI training session. Comparing the proposed method to the standard practice in task selection, for a fixed time budget, UCB-classif leads to an improve classification rate, and for a fix classification rate, to a reduction of the time spent in training by 50%.
Multiplicative Forests for Continuous-Time Processes
Authors: Jeremy Weiss, Sriraam Natarajan, David Page
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: regression

Learning temporal dependencies between variables over continuous time is an important and challenging task. Continuous-time Bayesian networks effectively model such processes but are limited by the number of conditional intensity matrices, which grows exponentially in the number of parents per variable. We develop a partition-based representation using regression trees and forests whose parameter spaces grow linearly in the number of node splits. Using a multiplicative assumption we show how to update the forest likelihood in closed form, producing efficient model updates. Our results show multiplicative forests can be learned from few temporal trajectories with large gains in performance and scalability.
Patient Risk Stratification for Hospital-Associated C. diff as a Time-Series Classification Task
Authors: Jenna Wiens, Eric Horvitz, John V. Guttag
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, Diagnostic, General Classification, Time Series, Time Series Analysis, Time Series Classification

A patient's risk for adverse events is affected by temporal processes including the nature and timing of diagnostic and therapeutic activities, and the overall evolution of the patient's pathophysiology over time. Yet many investigators ignore this temporal aspect when modeling patient risk, considering only the patient's current or aggregate state. We explore representing patient risk as a time series. In doing so, patient risk stratification becomes a time-series classification task. The task differs from most applications of time-series analysis, like speech processing, since the time series itself must first be extracted. Thus, we begin by defining and extracting approximate \textit{risk processes}, the evolving approximate daily risk of a patient. Once obtained, we use these signals to explore different approaches to time-series classification with the goal of identifying high-risk patterns. We apply the classification to the specific task of identifying patients at risk of testing positive for hospital acquired colonization with \textit{Clostridium Difficile}. We achieve an area under the receiver operating characteristic curve of 0.79 on a held-out set of several hundred patients. Our two-stage approach to risk stratification outperforms classifiers that consider only a patient's current state (p$<$0.05).
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison
Authors: Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, Zhi-Hua Zhou
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Both random Fourier features and the Nyström method have been successfully applied to efficient kernel learning. In this work, we investigate the fundamental difference between these two approaches, and how the difference could affect their generalization performances. Unlike approaches based on random Fourier features  where the basis functions (i.e., cosine and sine functions) are sampled from a distribution  {\it independent} from the training data, basis functions used by the Nyström method are randomly sampled from the training examples and are therefore {\it data dependent}. By exploring this difference, we show that when there is a large gap in the eigen-spectrum of the kernel matrix, approaches based the Nyström method can yield  impressively  better generalization error bound than random Fourier features based approach. We empirically verify our theoretical findings on a wide range of large data sets.
Multiclass Learning Approaches: A Theoretical Comparison with Implications
Authors: Amit Daniely, Sivan Sabato, Shai S. Shwartz
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: All, Binary Classification, Classification, General Classification

We theoretically analyze and compare the following five popular multiclass classification methods: One vs. All, All Pairs, Tree-based classifiers, Error Correcting Output Codes (ECOC) with randomly generated code matrices, and Multiclass SVM. In the first four methods, the classification is based on a reduction to binary classification. We consider the case where the binary classifier comes from a class of VC dimension $d$, and in particular from the class of halfspaces over $\reals^d$. We analyze both the estimation error and the approximation error of these methods. Our analysis reveals interesting conclusions of practical relevance, regarding the success of the different approaches under various conditions. Our proof technique employs tools from VC theory to analyze the \emph{approximation error} of hypothesis classes. This is in sharp contrast to most, if not all, previous uses of VC theory, which only deal with estimation error.
Stochastic Gradient Descent with Only One Projection
Authors: Mehrdad Mahdavi, Tianbao Yang, Rong Jin, Shenghuo Zhu, Jin-Feng Yi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Although many variants of stochastic gradient descent have been proposed for large-scale convex optimization, most of them require projecting the solution at {\it each} iteration to ensure that the obtained solution stays within the feasible domain. For complex domains (e.g., positive semidefinite cone), the projection step can be computationally expensive, making stochastic gradient descent unattractive for large-scale optimization problems. We address this limitation by developing a novel stochastic gradient descent algorithm that does not need intermediate projections. Instead, only one projection at the last iteration is needed to obtain a feasible solution in the given domain. Our theoretical analysis shows that with a high probability, the proposed algorithms achieve an $O(1/\sqrt{T})$ convergence rate for general convex optimization, and an $O(\ln T/T)$  rate for  strongly convex optimization under mild conditions about the domain and the objective function.
Neuronal Spike Generation Mechanism as an Oversampling, Noise-shaping A-to-D converter
Authors: Dmitri B. Chklovskii, Daniel Soudry
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We explore the hypothesis that the neuronal spike generation mechanism is an analog-to-digital converter, which rectifies low-pass filtered summed synaptic currents and encodes them into spike trains linearly decodable in post-synaptic neurons. To digitally encode an analog current waveform, the sampling rate of the spike generation mechanism must exceed its Nyquist rate. Such oversampling is consistent with the experimental observation that the precision of the spike-generation mechanism is an order of magnitude greater than the cut-off frequency of dendritic low-pass filtering. To achieve additional reduction in the error of analog-to-digital conversion, electrical engineers rely on noise-shaping. If noise-shaping were used in neurons, it would introduce correlations in spike timing to reduce low-frequency (up to Nyquist) transmission error at the cost of high-frequency one (from Nyquist to sampling rate). Using experimental data from three different classes of neurons, we demonstrate that biological neurons utilize noise-shaping. We also argue that rectification by the spike-generation mechanism may improve energy efficiency and carry out de-noising. Finally, the zoo of ion channels in neurons may be viewed as a set of predictors, various subsets of which are activated depending on the statistics of the input current.