mtybilly/Instruct2DS huggingface dataset:
Tight Sample Complexity of Large-Margin Learning
Authors: Nathan Srebro, Naftali Tishby Sivan Sabato
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the gamma-adapted-dimension, which is a simple function of the spectrum of a distribution's covariance matrix, and show distribution-specific upper and lower bounds on the sample complexity, both governed by the gamma-adapted-dimension of the source distribution. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. The bounds hold for a rich family of sub-Gaussian distributions.
Minimum Average Cost Clustering
Authors: Yoshinobu Kawahara, Satoru Iwata Kiyohito Nagano
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: A number of objective functions in clustering problems can be described with submodular functions. In this paper, we introduce the minimum average cost criterion, and show that the theory of intersecting submodular functions can be used for clustering with submodular objective functions. The proposed algorithm does not require the number of clusters in advance, and it will be determined by the property of a given set of data points. The minimum average cost clustering problem is parameterized with a real variable, and surprisingly, we show that all information about optimal clusterings for all parameters can be computed in polynomial time in total. Additionally, we evaluate the performance of the proposed algorithm through computational experiments.
Online Classification with Specificity Constraints
Authors: Shie Mannor, Nahum Shimkin Andrey Bernstein
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider the online binary classification problem, where we are given m classifiers. At each stage, the classifiers map the input to the probability that the input belongs to the positive class. An online classification meta-algorithm is an algorithm that combines the outputs of the classifiers in order to attain a certain goal, without having prior knowledge on the form and statistics of the input, and without prior knowledge on the performance of the given classifiers. In this paper, we use sensitivity and  specificity as the performance metrics of the meta-algorithm. In particular, our goal is to design an algorithm which satisfies the following two properties (asymptotically): (i) its average false positive rate (fp-rate) is under some given threshold, and (ii) its average true positive rate (tp-rate) is not worse than the tp-rate of the best convex combination of the m given classifiers that satisfies fp-rate constraint, in hindsight. We show that this problem is in fact a special case of the regret minimization problem with constraints, and therefore the above goal is not attainable. Hence, we pose a relaxed goal and propose a corresponding practical online learning meta-algorithm that attains it. In the case of two classifiers, we show that this algorithm takes a very simple form. To our best knowledge, this is the first algorithm that addresses the problem of the average tp-rate maximization under average fp-rate constraints in the online setting.
Construction of Dependent Dirichlet Processes based on Poisson Processes
Authors: Eric Grimson, John W. Fisher Dahua Lin
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We present a novel method for constructing dependent Dirichlet processes. The approach exploits the intrinsic relationship between Dirichlet and Poisson pro- cesses in order to create a Markov chain of Dirichlet processes suitable for use as a prior over evolving mixture models. The method allows for the creation, re- moval, and location variation of component models over time while maintaining the property that the random measures are marginally DP distributed. Addition- ally, we derive a Gibbs sampling algorithm for model inference and test it on both synthetic and real data. Empirical results demonstrate that the approach is effec- tive in estimating dynamically varying mixture models.
Practical Large-Scale Optimization for Max-norm Regularization
Authors: Ben Recht, Nathan Srebro, Joel Tropp, Ruslan Salakhutdinov Jason Lee
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The max-norm was proposed as a convex matrix regularizer by Srebro et al (2004) and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro (2003) to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.
Deciphering subsampled data: adaptive compressive sampling as a principle of brain communication
Authors: Christopher Hillar, Fritz Sommer Guy Isely
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: A new algorithm is proposed for a) unsupervised learning of sparse representations from subsampled measurements and b) estimating the parameters required for linearly reconstructing signals from the sparse codes. We verify that the new algorithm performs efficient data compression on par with the recent method of compressive sampling. Further, we demonstrate that the algorithm performs robustly when stacked in several stages or when applied in undercomplete or overcomplete situations. The new algorithm can explain how neural populations in the brain that receive subsampled input through fiber bottlenecks are able to form coherent response properties.
Learning Convolutional Feature Hierarchies for Visual Recognition
Authors: Pierre Sermanet, Y-lan Boureau, Karol Gregor, Michael Mathieu, Yann L. Cun Koray Kavukcuoglu
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose an unsupervised method for learning multi-stage   hierarchies of sparse convolutional features. While sparse coding   has become an increasingly popular method for learning visual   features, it is most often trained at the patch level. Applying the   resulting filters convolutionally results in highly redundant codes   because overlapping patches are encoded in isolation.  By training   convolutionally over large image windows, our method reduces the   redudancy between feature vectors at neighboring locations and   improves the efficiency of the overall representation. In addition   to a linear decoder that reconstructs the image from sparse   features, our method trains an efficient feed-forward encoder that   predicts quasi-sparse features from the input.  While patch-based   training rarely produces anything but oriented edge detectors, we   show that convolutional training produces highly diverse filters,   including center-surround filters, corner detectors, cross   detectors, and oriented grating detectors.  We show that using these   filters in multi-stage convolutional network architecture improves   performance on a number of visual recognition and detection tasks.
Multiple Kernel Learning and the SMO Algorithm
Authors: Nawanol Ampornpunt, Manik Varma, S.v.n. Vishwanathan Zhaonan Sun
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Our objective is to train $p$-norm Multiple Kernel Learning (MKL) and, more generally, linear MKL regularised by the Bregman divergence, using the Sequential Minimal Optimization (SMO) algorithm. The SMO algorithm is simple, easy to implement and adapt, and efficiently scales to large problems. As a result, it has gained widespread acceptance and SVMs are routinely trained using SMO in diverse real world applications. Training using SMO has been a long standing goal in MKL for the very same reasons. Unfortunately, the standard MKL dual is not differentiable, and therefore can not be optimised using SMO style co-ordinate ascent. In this paper, we demonstrate that linear MKL regularised with the $p$-norm squared, or with certain Bregman divergences, can indeed be trained using SMO. The resulting algorithm retains both simplicity and efficiency and is significantly faster than the state-of-the-art specialised $p$-norm MKL solvers. We show that we can train on a hundred thousand kernels in approximately seven minutes and on fifty thousand points in less than half an hour on a single core.
Segmentation as Maximum-Weight Independent Set
Authors: Sinisa Todorovic William Brendel
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: 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."
Static Analysis of Binary Executables Using Structural SVMs
Authors: Nikos Karampatziakis
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We cast the problem of identifying basic blocks of code in a binary executable as learning a mapping from a byte sequence to a segmentation of the sequence. In general, inference in segmentation models, such as semi-CRFs, can be cubic in the length of the sequence. By taking advantage of the structure of our problem, we derive a linear-time inference algorithm which makes our approach practical, given that even small programs are tens or hundreds of thousands bytes long. Furthermore, we introduce two loss functions which are appropriate for our problem and show how to use structural SVMs to optimize the learned mapping for these losses. Finally, we present experimental results that demonstrate the advantages of our method against a strong baseline.
Factorized Latent Spaces with Structured Sparsity
Authors: Mathieu Salzmann, Trevor Darrell Yangqing Jia
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Recent approaches to multi-view learning have shown that factorizing the information into parts that are shared across all views and parts that are private to each view could effectively account for the dependencies and independencies between the different input modalities. Unfortunately, these approaches involve minimizing non-convex objective functions. In this paper, we propose an approach to learning such factorized representations inspired by sparse coding techniques. In particular, we show that structured sparsity allows us to address the multi-view learning problem by alternately solving two convex optimization problems. Furthermore, the resulting factorized latent spaces generalize over existing approaches in that they allow :having latent dimensions shared between any subset of the views instead of between all the views only. We show that our approach outperforms state-of-the-art methods on the task of human pose estimation.
A unified model of short-range and long-range motion perception
Authors: Xuming He, Hongjing Lu, Alan L. Yuille Shuang Wu
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: 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.
Structural epitome: a way to summarize one’s visual experience
Authors: Alessandro Perina, Vittorio Murino Nebojsa Jojic
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: In order to study the properties of total visual input in humans, a single subject wore a camera for two weeks capturing, on average, an image every 20 seconds (www.research.microsoft.com/~jojic/aihs). The resulting new dataset contains a mix of indoor and outdoor scenes as well as numerous foreground objects. Our first analysis goal is to create a visual summary of the subject’s two weeks of life using unsupervised algorithms that would automatically discover recurrent scenes, familiar faces or common actions. Direct application of existing algorithms, such as panoramic stitching (e.g.  Photosynth) or appearance-based clustering models (e.g. the epitome), is impractical due to either the large dataset size or the dramatic variation in the lighting conditions.    As a remedy to these problems, we introduce a novel image representation, the “stel epitome,” and an associated efficient learning algorithm. In our model, each image or image patch is characterized by a hidden mapping T, which, as in previous epitome models, defines a mapping between the image-coordinates and the coordinates in the large all-I-have-seen" epitome matrix. The limited epitome real-estate forces the mappings of different images to overlap, with this overlap indicating image similarity. However, in our model the image similarity does not depend on direct pixel-to-pixel intensity/color/feature comparisons as in previous epitome models, but on spatial configuration of scene or object parts, as the model is based on the palette-invariant stel models. As a result, stel epitomes capture structure that is invariant to non-structural changes, such as illumination, that tend to uniformly affect pixels belonging to a single scene or object part."
Tree-Structured Stick Breaking for Hierarchical Data
Authors: Michael I. Jordan, Ryan P. Adams Zoubin Ghahramani
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Many data are naturally modeled by an unobserved hierarchical structure. In this paper we propose a flexible nonparametric prior over unknown data hierarchies. The approach uses nested stick-breaking processes to allow for trees of unbounded width and depth, where data can live at any node and are infinitely exchangeable. One can view our model as providing infinite mixtures where the components have a dependency structure corresponding to an evolutionary diffusion down a tree. By using a stick-breaking approach, we can apply Markov chain Monte Carlo methods based on slice sampling to perform Bayesian inference and simulate from the posterior distribution on trees. We apply our method to hierarchical clustering of images and topic modeling of text data.
LSTD with Random Projections
Authors: Alessandro Lazaric, Odalric Maillard, Rémi Munos Mohammad Ghavamzadeh
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider the problem of reinforcement learning in high-dimensional spaces when the number of features is bigger than the number of samples. In particular, we study the least-squares temporal difference (LSTD) learning algorithm when a space of low dimension is generated with a random projection from a high-dimensional space. We provide a thorough theoretical analysis of the LSTD with random projections and derive performance bounds for the resulting algorithm. We also show how the error of LSTD with random projections is propagated through the iterations of a policy iteration algorithm and provide a performance bound for the resulting least-squares policy iteration (LSPI) algorithm.
Feature Construction for Inverse Reinforcement Learning
Authors: Zoran Popovic, Vladlen Koltun Sergey Levine
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The goal of inverse reinforcement learning is to find a reward function for a Markov decision process, given example traces from its optimal policy. Current IRL techniques generally rely on user-supplied features that form a concise basis for the reward. We present an algorithm that instead constructs reward features from a large collection of component features, by building logical conjunctions of those component features that are relevant to the example policy. Given example traces, the algorithm returns a reward function as well as the constructed features. The reward function can be used to recover a full, deterministic, stationary policy, and the features can be used to transplant the reward function into any novel environment on which the component features are well defined.
An analysis on negative curvature induced by singularity in multi-layer neural-network learning
Authors: Stuart Dreyfus Eiji Mizutani
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: In the neural-network parameter space,  an attractive field is likely to be induced by singularities. In such a singularity region, first-order gradient learning typically causes a long plateau with very little change  in the objective function value E (hence, a flat region). Therefore, it may be confused with ``attractive'' local minima. Our analysis shows that the Hessian matrix of E tends to be indefinite in the vicinity of (perturbed) singular points, suggesting a promising strategy that exploits negative curvature so as to escape from the singularity plateaus. For numerical evidence, we limit the scope to small examples (some of which are found in journal papers)  that allow us to confirm singularities and the eigenvalues of the Hessian matrix, and for which computation using a descent direction of negative curvature encounters no plateau.  Even for those small problems, no efficient methods have been previously developed that avoided plateaus.
Joint Cascade Optimization Using A Product Of Boosted Classifiers
Authors: Francois Fleuret Leonidas Lefakis
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The standard strategy for efficient object detection consists of building a cascade composed of several binary classifiers. The detection process takes the form of a lazy evaluation of the conjunction of the responses of these classifiers, and concentrates the computation on difficult parts of the image which can not be trivially rejected.  We introduce a novel algorithm to construct jointly the classifiers of such a cascade. We interpret the response of a classifier as a probability of a positive prediction, and the overall response of the cascade as the probability that all the predictions are positive. From this noisy-AND model, we derive a consistent loss and a Boosting procedure to optimize that global probability on the training set.  Such a joint learning allows the individual predictors to focus on a more restricted modeling problem, and improves the performance compared to a standard cascade. We demonstrate the efficiency of this approach on face and pedestrian detection with standard data-sets and comparisons with reference baselines.
Parallelized Stochastic Gradient Descent
Authors: Markus Weimer, Lihong Li, Alex J. Smola Martin Zinkevich
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: 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.
Shadow Dirichlet for Restricted Probability Modeling
Authors: Maya Gupta, Yihua Chen Bela Frigyik
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Although the Dirichlet distribution is widely used, the independence structure of its components limits its accuracy as a model. The proposed shadow Dirichlet distribution manipulates the support in order to model probability mass functions (pmfs) with dependencies or constraints that often arise in real world problems, such as regularized pmfs, monotonic pmfs, and pmfs with bounded variation. We describe some properties of this new class of distributions, provide maximum entropy constructions, give an expectation-maximization method for estimating the mean parameter, and illustrate with real data.
MAP estimation in Binary MRFs via Bipartite Multi-cuts
Authors: Sunita Sarawagi, Sundar Vishwanathan Sashank J. Reddi
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a new LP relaxation for obtaining the MAP assignment of a binary MRF with pairwise potentials. Our relaxation is derived from reducing the MAP assignment problem to an instance of a recently proposed Bipartite Multi-cut problem where the LP relaxation is guaranteed to provide an O(log k) approximation where k is the number of vertices adjacent to non-submodular edges in the MRF. We then propose a combinatorial algorithm to efficiently solve the LP and also provide a lower bound by concurrently solving its dual to within an approximation. The algorithm is up to an order of magnitude faster and provides better MAP scores and bounds than the state of the art message passing algorithm of [1] that tightens the local marginal polytope with third-order marginal constraints.
Approximate Inference by Compilation to Arithmetic Circuits
Authors: Pedro Domingos Daniel Lowd
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Arithmetic circuits (ACs) exploit context-specific independence and determinism to allow exact inference even in networks with high treewidth. In this paper, we introduce the first ever approximate inference methods using ACs, for domains where exact inference remains intractable. We propose and evaluate a variety of techniques based on exact compilation, forward sampling, AC structure learning, Markov network parameter learning, variational inference, and Gibbs sampling. In experiments on eight challenging real-world domains, we find that the methods based on sampling and learning work best: one such method (AC2-F) is faster and usually more accurate than loopy belief propagation, mean field, and Gibbs sampling; another (AC2-G) has a running time similar to Gibbs sampling but is consistently more accurate than all baselines.
Random Walk Approach to Regret Minimization
Authors: Alexander Rakhlin Hariharan Narayanan
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a computationally efficient random walk on a convex body which rapidly mixes to a time-varying Gibbs distribution. In the setting of online convex optimization and repeated games, the algorithm yields low regret and presents a novel efficient method for implementing mixture forecasting strategies.
Unsupervised Kernel Dimension Reduction
Authors: Fei Sha, Michael I. Jordan Meihong Wang
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We apply the framework of kernel dimension reduction, originally designed for supervised problems, to unsupervised dimensionality reduction. In this framework, kernel-based measures of independence are used to derive low-dimensional representations that maximally capture information in covariates in order to predict responses. We extend this idea and develop similarly motivated measures for unsupervised problems where covariates and responses are the same. Our empirical studies show that the resulting compact representation yields meaningful and appealing visualization and clustering of data. Furthermore, when used in conjunction with supervised learners for classification, our methods lead to lower classification errors than state-of-the-art methods, especially when embedding data in spaces of very few dimensions.
Multitask Learning without Label Correspondences
Authors: James Petterson, Tibério S. Caetano, Alex J. Smola, S.v.n. Vishwanathan Novi Quadrianto
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose an algorithm to perform multitask learning where each task has potentially distinct label sets and label correspondences are not readily available. This is in contrast with existing methods which either assume that the label sets shared by different tasks are the same or that there exists a label mapping oracle. Our method directly maximizes the mutual information among the labels, and we show that the resulting objective function can be efficiently optimized using existing algorithms. Our proposed approach has a direct application for data integration with different label spaces for the purpose of classification, such as integrating Yahoo! and DMOZ web directories.
CUR from a Sparse Optimization Viewpoint
Authors: Ya Xu, Michael W. Mahoney Jacob Bien
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The CUR decomposition provides an approximation of a matrix X that has low reconstruction error and that is sparse in the sense that the resulting approximation lies in the span of only a few columns of X. In this regard, it appears to be similar to many sparse PCA methods. However, CUR takes a randomized algorithmic approach whereas most sparse PCA methods are framed as convex optimization problems. In this paper, we try to understand CUR from a sparse optimization viewpoint. In particular, we show that CUR is implicitly optimizing a sparse regression objective and, furthermore, cannot be directly cast as a sparse PCA method. We observe that the sparsity attained by CUR possesses an interesting structure, which leads us to formulate a sparse PCA method that achieves a CUR-like sparsity.
Robust Clustering as Ensembles of Affinity Relations
Authors: Longin J. Latecki, Shuicheng Yan Hairong Liu
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: In this paper, we regard clustering as ensembles of k-ary affinity relations and clusters correspond to subsets of objects with maximal average affinity relations. The average affinity relation of a cluster is relaxed and well approximated by a constrained homogenous function. We present an efficient procedure to solve this optimization problem, and show that the underlying clusters can be robustly revealed by using priors systematically constructed from the data. Our method can automatically select some points to form clusters, leaving other points un-grouped; thus it is inherently robust to large numbers of outliers, which has seriously limited the applicability of classical methods. Our method also provides a unified solution to clustering from k-ary affinity relations with k ≥ 2, that is, it applies to both graph-based and hypergraph-based clustering problems. Both theoretical analysis and experimental results show the superiority of our method over classical solutions to the clustering problem, especially when there exists a large number of outliers.
Optimal learning rates for Kernel Conjugate Gradient regression
Authors: Nicole Krämer Gilles Blanchard
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We prove rates of convergence in the statistical sense for kernel-based least squares regression using a conjugate gradient algorithm, where regularization against overfitting is obtained by early stopping. This method is directly related to Kernel Partial Least Squares, a regression method that combines supervised dimensionality reduction with least squares projection. The rates depend on two key quantities: first, on the regularity of the target regression function and second, on the effective dimensionality of the data mapped into the kernel space. Lower bounds on attainable rates depending on these two quantities were established in earlier literature, and we obtain upper bounds for the considered method that match these lower bounds (up to a log factor) if  the true regression function belongs to the reproducing kernel Hilbert space. If the latter assumption is not fulfilled, we obtain similar convergence rates provided additional unlabeled data are available. The order of the learning rates in these two situations match state-of-the-art results that were recently obtained for the least squares support vector machine and for linear regularization operators.
Rates of convergence for the cluster tree
Authors: Sanjoy Dasgupta Kamalika Chaudhuri
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: 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.
Throttling Poisson Processes
Authors: Peter Haider, Thomas Vanck, Michael Brückner, Tobias Scheffer Uwe Dick
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We study a setting in which Poisson processes generate sequences of decision-making events. The optimization goal is allowed to depend on the rate of decision outcomes; the rate may depend on a potentially long backlog of events and decisions. We model the problem as a Poisson process with a throttling policy that enforces a data-dependent rate limit and reduce the learning problem to a convex optimization problem that can be solved efficiently. This problem setting matches applications in which damage caused by an attacker grows as a function of the rate of unsuppressed hostile events. We report on experiments on abuse detection for an email service.
An Approximate Inference Approach to Temporal Optimization in Optimal Control
Authors: Marc Toussaint, Sethu Vijayakumar Konrad Rawlik
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Algorithms based on iterative local approximations present a practical approach to optimal control in robotic systems. However, they generally require the temporal parameters (for e.g. the movement duration or the time point of reaching an intermediate goal) to be specified \textit{a priori}. Here, we present a methodology that is capable of jointly optimising the temporal parameters in addition to the control command profiles. The presented approach is based on a Bayesian canonical time formulation of the optimal control problem, with the temporal mapping from canonical to real time parametrised by an additional control variable. An approximate EM algorithm is derived that efficiently optimises both the movement duration and control commands offering, for the first time, a practical approach to tackling generic via point problems in a systematic way under the optimal control framework. The proposed approach is evaluated on simulations of a redundant robotic plant.
Phone Recognition with the Mean-Covariance Restricted Boltzmann Machine
Authors: Marc'aurelio Ranzato, Abdel-rahman Mohamed, Geoffrey E. Hinton George Dahl
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: 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.
Sparse Coding for Learning Interpretable Spatio-Temporal Primitives
Authors: Gregory Shakhnarovich, Raquel Urtasun Taehwan Kim
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Sparse coding has recently become a popular approach in computer vision to learn dictionaries of natural images. In this paper we extend sparse coding to learn interpretable spatio-temporal primitives of human motion.  We cast the problem of learning spatio-temporal primitives as a tensor factorization problem  and introduce constraints to learn interpretable primitives. In particular, we use group norms over those tensors, diagonal constraints on the activations as well as smoothness constraints that are inherent to human motion.   We demonstrate the effectiveness of our approach to learn interpretable representations  of human motion from motion capture data, and show that our approach outperforms  recently developed matching pursuit and  sparse coding algorithms.
Block Variable Selection in Multivariate Regression and High-dimensional Causal Inference
Authors: Aurelie C. Lozano Vikas Sindhwani
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider multivariate regression problems involving high-dimensional predictor and response spaces. To efficiently address such problems, we propose a variable selection method, Multivariate Group Orthogonal Matching Pursuit, which extends the standard Orthogonal Matching Pursuit technique to account for arbitrary sparsity patterns induced by domain-specific groupings over both input and output variables, while also taking advantage of the correlation that may exist between the multiple outputs. We illustrate the utility of this framework for inferring causal relationships over a collection of high-dimensional time series variables. When applied to time-evolving social media content, our models yield a new family of causality-based influence measures that may be seen as an alternative to PageRank. Theoretical guarantees, extensive simulations and empirical studies confirm the generality and value of our framework.
Reverse Multi-Label Learning
Authors: Tibério S. Caetano James Petterson
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Multi-label classification is the task of predicting potentially multiple labels for a given instance. This is common in several applications such as image annotation, document classification and gene function prediction. In this paper we present a formulation for this problem based on reverse prediction: we predict sets of instances given the labels. By viewing the problem from this perspective, the most popular quality measures for assessing the performance of multi-label classification admit relaxations that can be efficiently optimised. We optimise these relaxations with standard algorithms and compare our results with several state-of-the-art methods, showing excellent performance.
Efficient Relational Learning with Hidden Variable Detection
Authors: Jun Zhu, Liu Liu, Yandong Liu, William W. Cohen Ni Lao
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Markov networks (MNs) can incorporate arbitrarily complex features in modeling relational data. However, this flexibility comes at a sharp price of training an exponentially complex model. To address this challenge, we propose a novel relational learning approach, which consists of a restricted class of relational MNs (RMNs) called relation tree-based RMN (treeRMN), and an efficient Hidden Variable Detection algorithm called Contrastive Variable Induction (CVI). On one hand, the restricted treeRMN only considers simple (e.g., unary and pairwise) features in relational data and thus achieves computational efficiency; and on the other hand, the CVI algorithm efficiently detects hidden variables which can capture long range dependencies. Therefore, the resultant approach is highly efficient yet does not sacrifice its expressive power. Empirical results on four real datasets show that the proposed relational learning method can achieve similar prediction quality as the state-of-the-art approaches, but is significantly more efficient in training; and the induced hidden variables are semantically meaningful and crucial to improve the training speed and prediction qualities of treeRMNs.
Learning from Logged Implicit Exploration Data
Authors: John Langford, Lihong Li, Sham M. Kakade Alex Strehl
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We provide a sound and consistent foundation for the use of \emph{nonrandom} exploration data in contextual bandit'' orpartially labeled'' settings where only the value of a chosen action is learned.                                                       The primary challenge in a variety of settings is that the exploration policy, in which ``offline'' data is logged, is not explicitly known. Prior solutions here require either control of the actions during the learning process, recorded random exploration, or actions chosen obliviously in a repeated manner.  The techniques reported here lift these restrictions, allowing the learning of a policy for choosing actions given features from historical data where no randomization occurred or was logged.  We empirically verify our solution on two reasonably sized sets of real-world data obtained from an Internet %online advertising company.
Parametric Bandits: The Generalized Linear Case
Authors: Olivier Cappe, Aurélien Garivier, Csaba Szepesvári Sarah Filippi
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider structured multi-armed bandit tasks in which the agent is guided by prior structural knowledge that can be exploited to efficiently select the optimal arm(s) in situations where the number of arms is large, or even infinite. We pro- pose a new optimistic, UCB-like, algorithm for non-linearly parameterized bandit problems using the Generalized Linear Model (GLM) framework. We analyze the regret of the proposed algorithm, termed GLM-UCB, obtaining results similar to those recently proved in the literature for the linear regression case. The analysis also highlights a key difficulty of the non-linear case which is solved in GLM-UCB by focusing on the reward space rather than on the parameter space. Moreover, as the actual efficiency of current parameterized bandit algorithms is often deceiving in practice, we provide an asymptotic argument leading to significantly faster convergence. Simulation studies on real data sets illustrate the performance and the robustness of the proposed GLM-UCB approach.
Basis Construction from Power Series Expansions of Value Functions
Authors: Bo Liu Sridhar Mahadevan
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: This paper explores links between basis construction methods in Markov decision processes and power series expansions of value functions. This perspective provides a useful framework to analyze properties of existing bases, as well as provides insight into constructing more effective bases. Krylov and Bellman error bases are based on the Neumann series expansion. These bases incur very large initial Bellman errors, and can converge rather slowly as the discount factor approaches unity. The Laurent series expansion, which relates discounted and average-reward formulations, provides both an explanation for this slow convergence as well as suggests a way to construct more efficient basis representations. The first two terms in the Laurent series represent the scaled average-reward and the average-adjusted sum of rewards, and subsequent terms expand the discounted value function using powers of a generalized inverse called the Drazin (or group inverse) of a singular matrix derived from the transition matrix. Experiments show that Drazin bases converge considerably more quickly than several other bases, particularly for large values of the discount factor. An incremental variant of Drazin bases called Bellman average-reward bases (BARBs) is described, which provides some of the same benefits at lower computational cost.
A Novel Kernel for Learning a Neuron Model from Spike Train Data
Authors: Arunava Banerjee Nicholas Fisher
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: From a functional viewpoint, a spiking neuron is a device that transforms input spike trains on its various synapses into an output spike train on its axon. We demonstrate in this paper that the function mapping underlying the device can be tractably learned based on input and output spike train data alone. We begin by posing the problem in a classification based framework. We then derive a novel kernel for an SRM0 model that is based on PSP and AHP like functions. With the kernel we demonstrate how the learning problem can be posed as a Quadratic Program. Experimental results demonstrate the strength of our approach.
Nonparametric Bayesian Policy Priors for Reinforcement Learning
Authors: David Wingate, Nicholas Roy, Joshua B. Tenenbaum Finale Doshi-velez
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider reinforcement learning in partially observable domains where the agent can query an expert for demonstrations. Our nonparametric Bayesian approach combines model knowledge, inferred from expert information and independent exploration, with policy knowledge inferred from expert trajectories. We introduce priors that bias the agent towards models with both simple representations and simple policies, resulting in improved policy and model learning.
On the Theory of Learnining with Privileged Information
Authors: Vladimir Vapnik Dmitry Pechyony
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: In Learning Using Privileged Information (LUPI) paradigm, along with the standard training data in the decision space, a teacher supplies a learner with the privileged information in the correcting space. The goal of the learner is to find a classifier with a low generalization error in the decision space. We consider a new version of  empirical risk minimization algorithm, called Privileged ERM, that takes into account the privileged information in order to find a good function in the decision space. We outline the conditions on the correcting space that, if satisfied, allow Privileged ERM to have much faster learning rate in the decision space than the one of the regular empirical risk minimization.
Accounting for network effects in neuronal responses using L1 regularized point process models
Authors: Matthew Smith, Robert Kass, Tai S. Lee Ryan Kelly
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Activity of a neuron, even in the early sensory areas, is not simply a function of its local receptive field or tuning properties, but depends on global context of the stimulus, as well as the neural context. This suggests the activity of the surrounding neurons and global brain states can exert considerable influence on the activity of a neuron. In this paper we implemented an L1 regularized point process model to assess the contribution of multiple factors to the firing rate of many individual units recorded simultaneously from V1 with a 96-electrode Utah" array. We found that the spikes of surrounding neurons indeed provide strong predictions of a neuron's response, in addition to the neuron's receptive field transfer function. We also found that the same spikes could be accounted for with the local field potentials, a surrogate measure of global network states. This work shows that accounting for network fluctuations can improve estimates of single trial firing rate and stimulus-response transfer functions."
Probabilistic latent variable models for distinguishing between cause and effect
Authors: Dominik Janzing, Kun Zhang, Joris M. Mooij, Bernhard Schölkopf Oliver Stegle
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a novel method for inferring whether X causes Y or vice versa from joint observations of X and Y. The basic idea is to model the observed data using probabilistic latent variable models, which incorporate the effects of unobserved noise. To this end, we consider the hypothetical effect variable to be a function of the hypothetical cause variable and an independent noise term (not necessarily additive). An important novel aspect of our work is that we do not restrict the model class, but instead put general non-parametric priors on this function and on the distribution of the cause. The causal direction can then be inferred by using standard Bayesian model selection. We evaluate our approach on synthetic data and real-world data and report encouraging results.