pwc-archive/papers-with-abstracts huggingface dataset:
Random Projections for k-means Clustering
Authors: Christos Boutsidis, Anastasios Zouzias, Petros Drineas
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Clustering, Dimensionality Reduction

This paper discusses the topic of dimensionality reduction for $k$-means clustering. We prove that any set of $n$ points in $d$ dimensions (rows in a matrix $A \in \RR^{n \times d}$) can be projected into $t = \Omega(k / \eps^2)$ dimensions, for any $\eps \in (0,1/3)$, in $O(n d \lceil \eps^{-2} k/ \log(d) \rceil )$ time, such that with  constant probability the optimal $k$-partition of the point set is preserved within a factor of $2+\eps$. The projection is done by post-multiplying $A$ with a $d \times t$ random matrix $R$ having entries $+1/\sqrt{t}$ or $-1/\sqrt{t}$ with equal probability. A numerical implementation of our technique and experiments on a large face images dataset verify the speed and the accuracy of our theoretical results.
Segmentation as Maximum-Weight Independent Set
Authors: William Brendel, Sinisa Todorovic
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Segmentation

Given an ensemble of distinct, low-level segmentations of an image, our goal is to identify visually meaningful" segments in the ensemble. Knowledge about any specific objects and surfaces present in the image is not available. The selection of image regions occupied by objects is formalized as the maximum-weight independent set (MWIS) problem. MWIS is the heaviest subset of mutually non-adjacent nodes of an attributed graph. We construct such a graph from all segments in the ensemble. Then, MWIS selects maximally distinctive segments that together partition the image. A new MWIS algorithm is presented. The algorithm seeks a solution directly in the discrete domain, instead of relaxing MWIS to a continuous problem, as common in previous work. It iteratively finds a candidate discrete solution of the Taylor series expansion of the original MWIS objective function around the previous solution. The algorithm is shown to converge to a maximum. Our empirical evaluation on the benchmark Berkeley segmentation dataset shows that the new algorithm eliminates the need for hand-picking optimal input parameters of the state-of-the-art segmenters, and outperforms their best, manually optimized results."
Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning
Authors: Matthias Broecheler, Lise Getoor
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: General Classification, Relational Reasoning

Continuous Markov random fields are a general formalism to model joint probability distributions over events with continuous outcomes. We prove that marginal computation for constrained continuous MRFs is #P-hard in general and present a polynomial-time approximation scheme under mild assumptions on the structure of the random field. Moreover, we introduce a sampling algorithm to compute marginal distributions and develop novel techniques to increase its efficiency. Continuous MRFs are a general purpose probabilistic modeling tool and we demonstrate how they can be applied to statistical relational learning. On the problem of collective classification, we evaluate our algorithm and show that the standard deviation of marginals serves as a useful measure of confidence.
Multi-label Multiple Kernel Learning by Stochastic Approximation: Application to Visual Object Recognition
Authors: Serhat Bucak, Rong Jin, Anil K. Jain
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Object, Object Recognition

Recent studies have shown that multiple kernel learning is very effective for object recognition, leading to the popularity  of kernel learning in computer vision problems. In this work, we develop an efficient algorithm for multi-label multiple kernel learning (ML-MKL). We assume that all the classes under  consideration  share the same combination of kernel functions, and the objective is to find the optimal kernel combination that benefits all the classes. Although several algorithms have been developed for ML-MKL, their computational cost is linear in the number of classes, making them unscalable when the number of classes is large, a challenge  frequently  encountered in visual object recognition. We address this computational challenge by developing a framework for ML-MKL that combines the worst-case analysis with stochastic approximation. Our analysis shows that the complexity of our algorithm is $O(m^{1/3}\sqrt{ln m})$, where $m$ is the number of classes. Empirical studies with object recognition show that while achieving similar classification accuracy, the proposed method is significantly more efficient than the state-of-the-art algorithms for ML-MKL.
Learning concept graphs from text with stick-breaking priors
Authors: America Chambers, Padhraic Smyth, Mark Steyvers
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Topic Models

We present a generative probabilistic model for learning general graph structures, which we term concept graphs, from text. Concept graphs provide a visual summary of the thematic content of a collection of documents-a task that is difficult to accomplish using only keyword search. The proposed model can learn different types of concept graph structures and is capable of utilizing partial prior knowledge about graph structure as well as labeled documents. We describe a generative model that is based on a stick-breaking process for graphs, and a Markov Chain Monte Carlo inference procedure. Experiments on simulated data show that the model can recover known graph structure when learning in both unsupervised and semi-supervised modes. We also show that the proposed model is competitive in terms of empirical log likelihood with existing structure-based topic models (such as hPAM and hLDA) on real-world text data sets. Finally, we illustrate the application of the model to the problem of updating Wikipedia category graphs.
Rates of convergence for the cluster tree
Authors: Kamalika Chaudhuri, Sanjoy Dasgupta
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

For a density f on R^d, a high-density cluster is any connected component of {x: f(x) >= c}, for some c > 0. The set of all high-density clusters form a hierarchy called the cluster tree of f. We present a procedure for estimating the cluster tree given samples from f. We give finite-sample convergence rates for our algorithm, as well as lower bounds on the sample complexity of this estimation problem.
Evidence-Specific Structures for Rich Tractable CRFs
Authors: Anton Chechetka, Carlos Guestrin
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We present a simple and effective approach to learning tractable conditional random fields with structure that depends on the evidence. Our approach retains the advantages of tractable discriminative models, namely efficient exact inference and exact parameter learning. At the same time, our algorithm does not suffer a large expressive power penalty inherent to fixed tractable structures. On real-life relational datasets, our approach matches or exceeds state of the art accuracy of the dense models, and at the same time provides an order of magnitude speedup
Predictive Subspace Learning for Multi-view Data: a Large Margin Approach
Authors: Ning Chen, Jun Zhu, Eric P. Xing
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: General Classification, image-classification, Image Classification, parameter estimation, Retrieval

Learning from multi-view data is important in many applications, such as image classification and annotation. In this paper, we present a large-margin learning framework to discover a predictive latent subspace representation shared by multiple views. Our approach is based on an undirected latent space Markov network that fulfills a weak conditional independence assumption that multi-view observations and response variables are independent given a set of latent variables. We provide efficient inference and parameter estimation methods for the latent subspace model. Finally, we demonstrate the advantages of large-margin learning on real video and web image data for discovering predictive latent representations and improving the performance on image classification, annotation and retrieval.
Two-Layer Generalization Analysis for Ranking Using Rademacher Average
Authors: Wei Chen, Tie-Yan Liu, Zhi-Ming Ma
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Generalization Bounds, Information Retrieval, Learning-To-Rank, Retrieval, Vocal Bursts Valence Prediction

This paper is concerned with the generalization analysis on learning to rank for information retrieval (IR). In IR, data are hierarchically organized, i.e., consisting of queries and documents per query. Previous generalization analysis for ranking, however, has not fully considered this structure, and cannot explain how the simultaneous change of query number and document number in the training data will affect the performance of algorithms. In this paper, we propose performing generalization analysis under the assumption of two-layer sampling, i.e., the i.i.d. sampling of queries and the conditional i.i.d sampling of documents per query. Such a sampling can better describe the generation mechanism of real data, and the corresponding generalization analysis can better explain the real behaviors of learning to rank algorithms. However, it is challenging to perform such analysis, because the documents associated with different queries are not identically distributed, and the documents associated with the same query become no longer independent if represented by features extracted from the matching between document and query. To tackle the challenge, we decompose the generalization error according to the two layers, and make use of the new concept of two-layer Rademacher average. The generalization bounds we obtained are quite intuitive and are in accordance with previous empirical studies on the performance of ranking algorithms.
SpikeAnts, a spiking neuron network modelling the emergence of organization in a complex system
Authors: Sylvain Chevallier, Hél\`Ene Paugam-Moisy, Michele Sebag
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Many complex systems, ranging from neural cell assemblies to insect societies, involve and rely on some division of labor. How to enforce such a division in a decentralized and distributed way, is tackled in this paper, using a spiking neuron network architecture. Specifically, a spatio-temporal model called SpikeAnts is shown to enforce the emergence of synchronized activities in an ant colony. Each ant is modelled from two spiking neurons; the ant colony is a sparsely connected spiking neuron network. Each ant makes its decision (among foraging, sleeping and self-grooming) from the competition between its two neurons, after the signals received from its neighbor ants. Interestingly, three types of temporal patterns emerge in the ant colony: asynchronous, synchronous, and synchronous periodic foraging activities - similar to the actual behavior of some living ant colonies. A phase diagram of the emergent activity patterns with respect to two control parameters, respectively accounting for ant sociability and receptivity, is presented and discussed.
Movement extraction by detecting dynamics switches and repetitions
Authors: Silvia Chiappa, Jan R. Peters
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Time Series, Time Series Analysis

Many time-series such as human movement data consist of a sequence of basic actions, e.g., forehands and backhands in tennis. Automatically extracting and characterizing such actions is an important problem for a variety of different applications. In this paper, we present a probabilistic segmentation approach in which an observed time-series is modeled as a concatenation of segments corresponding to different basic actions. Each segment is generated through a noisy transformation of one of a few hidden trajectories representing different types of movement, with possible time re-scaling. We analyze three different approximation methods for dealing with model intractability, and demonstrate how the proposed approach can successfully segment table tennis movements recorded using a robot arm as haptic input device.
Learning sparse dynamic linear systems using stable spline kernels and exponential hyperpriors
Authors: Alessandro Chiuso, Gianluigi Pillonetto
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Gaussian Processes

We introduce a new Bayesian nonparametric approach to identification of sparse dynamic linear systems. The impulse responses are modeled as Gaussian processes whose autocovariances encode the BIBO stability constraint, as defined by the recently introduced “Stable Spline kernel”. Sparse solutions are obtained by placing exponential hyperpriors on the scale factors of such kernels. Numerical experiments regarding estimation of ARMAX models show that this technique provides a definite advantage over a group LAR algorithm and state-of-the-art parametric identification techniques based on prediction error minimization.
Universal Kernels on Non-Standard Input Spaces
Authors: Andreas Christmann, Ingo Steinwart
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: text-classification, Text Classification

During the last years support vector machines (SVMs) have been successfully applied even in situations where the input space $X$ is not necessarily a subset of $R^d$. Examples include SVMs using probability measures to analyse e.g. histograms or coloured images, SVMs for text classification and web mining, and SVMs for applications from computational biology using, e.g., kernels for trees and graphs. Moreover, SVMs are known to be consistent to the Bayes risk, if either the input space is a complete separable metric space and the reproducing kernel Hilbert space (RKHS) $H\subset L_p(P_X)$ is dense, or if the SVM is based on a universal kernel $k$.  So far, however, there are no RKHSs of practical interest known that satisfy these assumptions on $\cH$ or $k$ if $X \not\subset R^d$.  We close this gap by providing a general technique based on Taylor-type kernels to explicitly construct universal kernels on compact metric spaces which are not subset of $R^d$. We apply this technique for the following special cases: universal kernels on the set of probability measures, universal kernels based on Fourier transforms, and universal kernels for signal processing.
Causal discovery in multiple models from different experiments
Authors: Tom Claassen, Tom Heskes
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Causal Discovery, valid

A long-standing open research problem is how to use information from different experiments, including background knowledge, to infer causal relations. Recent developments have shown ways to use multiple data sets, provided they originate from identical experiments. We present the MCI-algorithm as the first method that can infer provably valid causal relations in the large sample limit from different experiments. It is fast, reliable and produces very clear and easily interpretable output. It is based on a result that shows that constraint-based causal discovery is decomposable into a candidate pair identification and subsequent elimination step that can be applied separately from different models. We test the algorithm on a variety of synthetic input model sets to assess its behavior and the quality of the output. The method shows promising signs that it can be adapted to suit causal discovery in real-world application areas as well, including large databases.
Empirical Risk Minimization with Approximations of Probabilistic Grammars
Authors: Noah A. Smith, Shay B. Cohen
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Probabilistic grammars are generative statistical models that are  useful for compositional and sequential structures. We present a framework, reminiscent of structural risk minimization, for empirical risk minimization of the parameters of a fixed probabilistic grammar using the log-loss. We derive sample complexity bounds in this framework that apply both to the supervised setting and the unsupervised setting.
Mixture of time-warped trajectory models for movement decoding
Authors: Elaine Corbett, Eric Perreault, Konrad Koerding
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Applications of Brain-Machine-Interfaces typically estimate user intent based on biological signals that are under voluntary control. For example, we might want to estimate how a patient with a paralyzed arm wants to move based on residual muscle activity. To solve such problems it is necessary to integrate obtained information over time. To do so, state of the art approaches typically use a probabilistic model of how the state, e.g. position and velocity of the arm, evolves over time – a so-called trajectory model. We wanted to further develop this approach using two intuitive insights: (1) At any given point of time there may be a small set of likely movement targets, potentially identified by the location of objects in the workspace or by gaze information from the user. (2) The user may want to produce movements at varying speeds. We thus use a generative model with a trajectory model incorporating these insights. Approximate inference on that generative model is implemented using a mixture of extended Kalman filters. We find that the resulting algorithm allows us to decode arm movements dramatically better than when we use a trajectory model with linear dynamics.
Learning Bounds for Importance Weighting
Authors: Corinna Cortes, Yishay Mansour, Mehryar Mohri
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

This paper presents an analysis of importance weighting for learning from finite samples and gives a series of theoretical and algorithmic results. We point out simple cases where importance weighting can fail, which suggests the need for an analysis of the properties of this technique. We then give both upper and lower bounds for generalization with bounded importance weights and, more significantly, give learning guarantees for the more common case of unbounded importance weights under the weak assumption that the second moment is bounded, a condition related to the Renyi divergence of the training and test distributions. These results are based on a series of novel and general bounds we derive for unbounded loss functions, which are of independent interest. We use these bounds to guide the definition of an alternative reweighting algorithm and report the results of experiments demonstrating its benefits. Finally, we analyze the properties of normalized importance weights which are also commonly used.
Learning via Gaussian Herding
Authors: Koby Crammer, Daniel D. Lee
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We introduce a new family of online learning algorithms based upon   constraining the velocity flow over a distribution of weight   vectors.  In particular, we show how to effectively  herd a   Gaussian weight vector distribution by trading off velocity   constraints with a loss function.  By uniformly bounding this loss   function, we demonstrate how to solve the resulting optimization   analytically.  We compare the resulting algorithms on a variety of    real world datasets, and demonstrate how these algorithms achieve   state-of-the-art robust performance, especially with high label   noise in the training data.
Spatial and anatomical regularization of SVM for brain image analysis
Authors: Remi Cuingnet, Marie Chupin, Habib Benali, Olivier Colliot
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Support vector machines (SVM) are increasingly used in brain image analyses since they allow capturing complex multivariate relationships in the data. Moreover, when the kernel is linear, SVMs can be used to localize spatial patterns of discrimination between two groups of subjects. However, the features' spatial distribution is not taken into account. As a consequence, the optimal margin hyperplane is often scattered and lacks spatial coherence, making its anatomical interpretation difficult. This paper introduces a framework to spatially regularize SVM for brain image analysis. We show that Laplacian regularization provides a flexible framework to integrate various types of constraints and can be applied to both cortical surfaces and 3D brain images. The proposed framework is applied to the classification of MR images based on gray matter concentration maps and cortical thickness measures from 30 patients with Alzheimer's disease and 30 elderly controls. The results demonstrate that the proposed method enables natural spatial and anatomical regularization of the classifier.
Phone Recognition with the Mean-Covariance Restricted Boltzmann Machine
Authors: George Dahl, Marc'Aurelio Ranzato, Abdel-rahman Mohamed, Geoffrey E. Hinton
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Straightforward application of Deep Belief Nets (DBNs) to acoustic modeling produces a rich distributed representation of speech data that is useful for recognition and yields impressive results on the speaker-independent TIMIT phone recognition task. However, the first-layer Gaussian-Bernoulli Restricted Boltzmann Machine (GRBM) has an important limitation, shared with mixtures of diagonal-covariance Gaussians: GRBMs treat different components of the acoustic input vector as conditionally independent given the hidden state. The mean-covariance restricted Boltzmann machine (mcRBM), first introduced for modeling natural images, is a much more representationally efficient and powerful way of modeling the covariance structure of speech data. Every configuration of the precision units of the mcRBM specifies a different precision matrix for the conditional distribution over the acoustic space. In this work, we use the mcRBM to learn features of speech data that serve as input into a standard DBN. The mcRBM features combined with DBNs allow us to achieve a phone error rate of 20.5\%, which is superior to all published results on speaker-independent TIMIT to date.
Co-regularization Based Semi-supervised Domain Adaptation
Authors: Abhishek Kumar, Avishek Saha, Hal Daume
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Domain Adaptation, Generalization Bounds, Semi-supervised Domain Adaptation, Sentiment Analysis

This paper presents a co-regularization based approach to semi-supervised domain adaptation. Our proposed approach (EA++) builds on the notion of augmented space (introduced in EASYADAPT (EA) [1]) and harnesses unlabeled data in target domain to further enable the transfer of information from source to target. This semi-supervised approach to domain adaptation is extremely simple to implement and can be applied as a pre-processing step to any supervised learner. Our theoretical analysis (in terms of Rademacher complexity) of EA and EA++ show that the hypothesis class of EA++ has lower complexity (compared to EA) and hence results in tighter generalization bounds. Experimental results on sentiment analysis tasks reinforce our theoretical findings and demonstrate the efficacy of the proposed method when compared to EA as well as a few other baseline approaches.
Spectral Regularization for Support Estimation
Authors: Ernesto D. Vito, Lorenzo Rosasco, Alessandro Toigo
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

In this paper we consider the problem of learning from data  the  support of a probability distribution when  the distribution {\em does not} have a density (with respect to some reference measure). We  propose a  new class of regularized spectral estimators based on a new notion of reproducing kernel Hilbert space,  which we call {\em   ``completely regular''}. Completely regular kernels   allow to capture the relevant  geometric and topological properties  of an arbitrary probability space.  In particular, they are the key ingredient to prove the  universal consistency  of the spectral  estimators and in this respect they are the analogue of  universal kernels for supervised problems. Numerical  experiments show that spectral estimators compare favorably to state of the art machine learning algorithms for  density support  estimation.