mtybilly/Instruct2DS huggingface dataset:
Universal low-rank matrix recovery from Pauli measurements
Authors: Yi-kai Liu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd polylog d) Pauli measurements.  This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing:  recovering a sparse vector from a few of its Fourier coefficients.      We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP).  This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error.  A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm.  Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
A Convergence Analysis of Log-Linear Training
Authors: Hermann Ney Simon Wiesler
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Log-linear models are widely used probability models for statistical pattern recognition. Typically, log-linear models are trained according to a convex criterion. In recent years, the interest in log-linear models has greatly increased. The optimization of log-linear model parameters is costly and therefore an important topic, in particular for large-scale applications. Different optimization algorithms have been evaluated empirically in many papers. In this work, we analyze the optimization problem analytically and show that the training of log-linear models can be highly ill-conditioned. We verify our findings on two handwriting tasks. By making use of our convergence analysis, we obtain good results on a large-scale continuous handwriting recognition task with a simple and generic approach.
On the accuracy of l1-filtering of signals with block-sparse structure
Authors: Arkadi S. Nemirovski, Boris T. Polyak, Anatoli Juditsky Fatma K. Karzan
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We discuss new methods for the recovery of signals with block-sparse structure, based on l1-minimization. Our emphasis is on the efficiently computable error bounds for the recovery routines. We optimize these bounds with respect to the method parameters to construct the estimators with improved statistical properties. We justify the proposed approach with an oracle inequality which links the properties of the recovery algorithms and the best estimation performance.
Group Anomaly Detection using Flexible Genre Models
Authors: Barnabás Póczos, Jeff G. Schneider Liang Xiong
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: An important task in exploring and analyzing real-world data sets is to detect unusual and interesting phenomena. In this paper, we study the group anomaly detection problem. Unlike traditional anomaly detection research that focuses on data points, our goal is to discover anomalous aggregated behaviors of groups of points. For this purpose, we propose the Flexible Genre Model (FGM). FGM is designed to characterize data groups at both the point level and the group level so as to detect various types of group anomalies. We evaluate the effectiveness of FGM on both synthetic and real data sets including images and turbulence data, and show that it is superior to existing approaches in detecting group anomalies.
Randomized Algorithms for Comparison-based Search
Authors: Suhas Diggavi, Payam Delgosha, Soheil Mohajer Dominique Tschopp
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper addresses the problem of finding the nearest neighbor (or    one of the $R$-nearest neighbors) of a query object $q$ in a    database of $n$ objects, when we can only use a comparison    oracle. The comparison oracle, given two reference objects and a    query object, returns the reference object most similar to the query    object.  The main problem we study is how to search the database for    the nearest neighbor (NN) of a query, while minimizing the    questions.  The difficulty of this problem depends on properties of    the underlying database. We show the importance of a    characterization: \emph{combinatorial disorder} $D$ which defines    approximate triangle inequalities on ranks. We present a lower bound    of $\Omega(D\log \frac{n}{D}+D^2)$ average number of questions in    the search phase for any randomized algorithm, which demonstrates    the fundamental role of $D$ for worst case behavior. We develop a    randomized scheme for NN retrieval in $O(D^3\log^2 n+ D\log^2 n    \log\log n^{D^3})$ questions.  The learning requires asking $O(n    D^3\log^2 n+ D \log^2 n \log\log n^{D^3})$ questions and    $O(n\log^2n/\log(2D))$ bits to store.
Multiple Instance Learning on Structured Data
Authors: Yan Liu, Luo Si, Jian Zhang, Richard D. Lawrence Dan Zhang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Most existing Multiple-Instance Learning (MIL) algorithms  assume data instances and/or data bags are independently and  identically distributed. But there often exists rich additional  dependency/structure information between instances/bags within many  applications of MIL. Ignoring this structure information limits the  performance of existing MIL algorithms. This paper explores the  research problem as multiple instance learning on structured  data (MILSD) and formulates a novel framework that considers  additional structure information. In particular, an effective and  efficient optimization algorithm has been proposed to solve the  original non-convex optimization problem by using a combination of  Concave-Convex Constraint Programming (CCCP) method and an adapted  Cutting Plane method, which deals with two sets of constraints caused  by learning on  instances within individual bags and learning on  structured data. Our method has the nice convergence property,  with specified precision on each set of constraints. Experimental  results on three different applications, i.e., webpage  classification, market targeting, and protein fold identification,  clearly demonstrate the advantages of the proposed method over  state-of-the-art methods.
Probabilistic Joint Image Segmentation and Labeling
Authors: Joao Carreira, Cristian Sminchisescu Adrian Ion
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories.  The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag, followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning.   We show that the proposed methodology matches the current state of the art in the Stanford dataset, as well as in VOC2010, where 41.7% accuracy on the test set is achieved.
Learning to Search Efficiently in High Dimensions
Authors: Huazhong Ning, Liangliang Cao, Tong Zhang, Yihong Gong, Thomas S. Huang Zhen Li
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: High dimensional similarity search in large scale databases becomes an important challenge due to the advent of Internet. For such applications, specialized data structures are required to achieve computational efficiency. Traditional approaches relied on algorithmic constructions that are often data independent (such as Locality Sensitive Hashing) or weakly dependent (such as kd-trees, k-means trees). While supervised learning algorithms have been applied to related problems, those proposed in the literature mainly focused on learning hash codes optimized for compact embedding of the data rather than search efficiency. Consequently such an embedding has to be used with linear scan or another search algorithm. Hence learning to hash does not directly address the search efficiency issue. This paper considers a new framework that applies supervised learning to directly optimize a data structure that supports efficient large scale search. Our approach takes both search quality and computational cost into consideration. Specifically, we learn a boosted search forest that is optimized using pair-wise similarity labeled examples. The output of this search forest can be efficiently converted into an inverted indexing data structure, which can leverage modern text search infrastructure to achieve both scalability and efficiency. Experimental results show that our approach significantly outperforms the start-of-the-art learning to hash methods (such as spectral hashing), as well as state-of-the-art high dimensional search algorithms (such as LSH and k-means trees).
Learning a Tree of Metrics with Disjoint Visual Features
Authors: Fei Sha, Sung Ju Hwang Kristen Grauman
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce an approach to learn discriminative visual representations while exploiting external semantic knowledge about object category relationships.  Given a hierarchical taxonomy that captures semantic similarity between the objects, we learn a corresponding tree of metrics (ToM).  In this tree, we have one metric for each non-leaf node of the object hierarchy, and each metric is responsible for discriminating among its immediate subcategory children.  Specifically, a Mahalanobis metric learned for a given node must satisfy the appropriate (dis)similarity constraints generated only among its subtree members' training instances.  To further exploit the semantics, we introduce a novel regularizer coupling the metrics that prefers a sparse disjoint set of features to be selected for each metric relative to its ancestor supercategory nodes' metrics.  Intuitively, this reflects that visual cues most useful to distinguish the generic classes (e.g., feline vs. canine) should be different than those cues most useful to distinguish their component fine-grained classes (e.g., Persian cat vs. Siamese cat).  We validate our approach with multiple image datasets using the WordNet taxonomy, show its advantages over alternative metric learning approaches, and analyze the meaning of attribute features selected by our algorithm.
Monte Carlo Value Iteration with Macro-Actions
Authors: Lee Sun, David Hsu Zhan Lim
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: POMDP planning faces two major computational challenges: large state spaces and long planning horizons. The recently introduced Monte Carlo Value Iteration (MCVI) can tackle POMDPs with very large discrete state spaces or continuous state spaces, but its performance degrades when faced with long planning horizons. This paper presents Macro-MCVI, which extends MCVI by exploiting macro-actions for temporal abstraction. We provide sufficient conditions for Macro-MCVI to inherit the good theoretical properties of MCVI. Macro-MCVI does not require explicit construction of probabilistic models for macro-actions and is thus easy to apply in practice. Experiments show that Macro-MCVI substantially improves the performance of MCVI with suitable macro-actions.
Non-parametric Group Orthogonal Matching Pursuit for Sparse Learning with Multiple Kernels
Authors: Aurelie C. Lozano Vikas Sindhwani
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider regularized risk minimization in a large dictionary of Reproducing  kernel Hilbert Spaces (RKHSs) over which the target function has a sparse representation.  This setting, commonly referred to as Sparse Multiple Kernel Learning  (MKL), may be viewed as the non-parametric extension of group sparsity in linear  models. While the two dominant algorithmic strands of sparse learning, namely  convex relaxations using l1 norm (e.g., Lasso) and greedy methods (e.g., OMP),  have both been rigorously extended for group sparsity, the sparse MKL literature  has so farmainly adopted the former withmild empirical success. In this paper, we  close this gap by proposing a Group-OMP based framework for sparse multiple  kernel learning. Unlike l1-MKL, our approach decouples the sparsity regularizer  (via a direct l0 constraint) from the smoothness regularizer (via RKHS norms)  which leads to better empirical performance as well as a simpler optimization  procedure that only requires a black-box single-kernel solver. The algorithmic  development and empirical studies are complemented by theoretical analyses in  terms of Rademacher generalization bounds and sparse recovery conditions analogous  to those for OMP [27] and Group-OMP [16].
Distributed Delayed Stochastic Optimization
Authors: John C. Duchi Alekh Agarwal
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We analyze the convergence of gradient-based optimization algorithms whose updates depend on delayed stochastic gradient information. The  main application of our results is to the development of distributed  minimization algorithms where a master node performs parameter updates while worker nodes compute stochastic gradients based on local information in parallel, which may give rise to delays due to  asynchrony. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible. In  application to distributed optimization, we show $n$-node architectures whose optimization error in stochastic problems---in spite of asynchronous delays---scales asymptotically as $\order(1 / \sqrt{nT})$, which is known to be optimal even in the absence of delays.
An Unsupervised Decontamination Procedure For Improving The Reliability Of Human Judgments
Authors: Benjamin Link, Harold Pashler Michael Mozer
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Psychologists have long been struck by individuals' limitations in expressing their internal sensations, impressions, and evaluations via rating scales.  Instead of using an absolute scale, individuals rely on reference points from recent experience.  This relativity of judgment limits  the informativeness of responses on surveys, questionnaires, and evaluation forms. Fortunately, the cognitive processes that map stimuli to responses are not simply noisy, but rather are influenced by recent experience in a lawful manner.  We explore techniques to remove sequential dependencies, and thereby  decontaminate a series of ratings to obtain more meaningful human  judgments.  In our formulation, the problem is to infer latent (subjective) impressions from a sequence of stimulus labels (e.g., movie names) and responses.  We describe an unsupervised approach that simultaneously recovers  the impressions and parameters of a contamination model that predicts how  recent judgments affect the current response.  We test our iterated  impression inference, or I^3, algorithm in three domains:  rating the gap between dots, the desirability of a movie based on an advertisement, and the morality of an action. We demonstrate significant objective improvements  in the quality of the recovered impressions.
Contextual Gaussian Process Bandit Optimization
Authors: Cheng S. Ong Andreas Krause
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: How should we design experiments to maximize performance of a complex system, taking into account uncontrollable environmental conditions? How should we select relevant documents (ads) to display, given information about the user? These tasks can be formalized as contextual bandit problems, where at each round, we receive context (about the experimental conditions, the query), and have to choose an action (parameters, documents). The key challenge is to trade off exploration by gathering data for estimating the mean payoff function over the context-action space, and to exploit by choosing an action deemed optimal based on the gathered data. We model the payoff function as a sample from a Gaussian process defined over the joint context-action space, and develop CGP-UCB, an intuitive upper-confidence style algorithm. We show that by mixing and matching kernels for contexts and actions, CGP-UCB can handle a variety of practical applications. We further provide generic tools for deriving regret bounds when using such composite kernel functions. Lastly, we evaluate our algorithm on two case studies, in the context of automated vaccine design and sensor management. We show that context-sensitive optimization outperforms no or naive use of context.
Learning with the weighted trace-norm under arbitrary sampling distributions
Authors: Ohad Shamir, Nati Srebro, Ruslan Salakhutdinov Rina Foygel
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We provide rigorous guarantees on learning with the weighted trace-norm under arbitrary sampling distributions.  We show that the standard weighted-trace norm might fail when the sampling distribution is not a product distribution (i.e. when row and column indexes are not selected independently), present a corrected variant for which we establish strong learning guarantees, and demonstrate that it works better in practice.  We provide guarantees when weighting by either the true or empirical sampling distribution, and suggest that even if the true distribution is known (or is uniform), weighting by the empirical distribution may be beneficial.
Demixed Principal Component Analysis
Authors: Ranulfo Romo, Christian K. Machens Wieland Brendel
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In many experiments, the data points collected live in high-dimensional observation spaces, yet can be assigned a set of labels or parameters. In electrophysiological recordings, for instance, the responses of populations of neurons generally depend on mixtures of experimentally controlled parameters. The heterogeneity and diversity of these parameter dependencies can make visualization and interpretation of such data extremely difficult. Standard dimensionality reduction techniques such as principal component analysis (PCA) can provide a succinct and complete description of the data, but the description is constructed independent of the relevant task variables and is often hard to interpret. Here, we start with the assumption that a particularly informative description is one that reveals the dependency of the high-dimensional data on the individual parameters. We show how to modify the loss function of PCA so that the principal components seek to capture both the maximum amount of variance about the data, while also depending on a minimum number of parameters. We call this method demixed principal component analysis (dPCA) as the principal components here segregate the parameter dependencies. We phrase the problem as a probabilistic graphical model, and present a fast Expectation-Maximization (EM) algorithm. We demonstrate the use of this algorithm for electrophysiological data and show that it serves to demix the parameter-dependence of a neural population response.
Reconstructing Patterns of Information Diffusion from Incomplete Observations
Authors: David Liben-nowell, Jon M. Kleinberg Flavio Chierichetti
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Motivated by the spread of on-line information in general and   on-line petitions in particular, recent research has raised the following   combinatorial estimation problem.  There is a tree T that we cannot observe directly (representing  the structure along which the information has spread), and certain  nodes randomly decide to make their copy of the information public.  In the case of a petition, the list of names on each public copy   of the petition also reveals a path leading back to the root of the tree.  What can we conclude about the properties of the tree we observe  from these revealed paths,  and can we use the structure of the observed tree  to estimate the size of the full unobserved tree T?    Here we provide the first algorithm for this size estimation task,  together with provable guarantees on its performance.  We also establish structural properties of the observed tree, providing the  first rigorous explanation for some of the unusual structural  phenomena present in the spread of real chain-letter petitions  on the Internet.
Differentially Private M-Estimators
Authors: Jing Lei
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper studies privacy preserving M-estimators using perturbed histograms. The proposed approach allows the release of a  wide class of M-estimators with both differential privacy and statistical utility without knowing a priori the particular inference procedure. The performance of the proposed method is demonstrated through a careful study of the convergence rates. A practical algorithm is given and applied on a real world data set containing both continuous and categorical  variables.
Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification
Authors: Masashi Sugiyama Ichiro Takeuchi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider feature selection and weighting for nearest neighbor classifiers. A technical challenge in this scenario is how to cope with the discrete update of nearest neighbors when the feature space metric is changed during the learning process. This issue, called the target neighbor change, was not properly addressed in the existing feature weighting and metric learning literature.  In this paper, we propose a novel feature weighting algorithm that can exactly and efficiently keep track of the correct target neighbors via sequential quadratic programming. To the best of our knowledge, this is the first algorithm that guarantees the consistency between target neighbors and the feature space metric. We further show that the proposed algorithm can be naturally combined with regularization path tracking, allowing computationally efficient selection of the regularization parameter. We demonstrate the effectiveness of the proposed algorithm through experiments.
Hierarchical Matching Pursuit for Image Classification: Architecture and Fast Algorithms
Authors: Xiaofeng Ren, Dieter Fox Liefeng Bo
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Extracting good representations from images is essential for many computer vision tasks. In this paper, we propose hierarchical matching pursuit (HMP), which builds a feature hierarchy layer-by-layer using an efficient matching pursuit encoder. It includes three modules: batch (tree) orthogonal matching pursuit, spatial pyramid max pooling, and contrast normalization. We investigate the architecture of HMP, and show that all three components are critical for good performance. To speed up the orthogonal matching pursuit, we propose a batch tree orthogonal matching pursuit that is particularly suitable to encode a large number of observations that share the same large dictionary. HMP is scalable and can efficiently handle full-size images. In addition, HMP enables linear support vector machines (SVM) to match the performance of nonlinear SVM while being scalable to large datasets. We compare HMP with many state-of-the-art algorithms including convolutional deep belief networks, SIFT based single layer sparse coding, and kernel based feature learning. HMP consistently yields superior accuracy on three types of image classification problems: object recognition (Caltech-101), scene recognition (MIT-Scene), and static event recognition (UIUC-Sports).
Solving Decision Problems with Limited Information
Authors: Cassio Campos Denis D. Maua
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a new algorithm for exactly solving decision-making problems represented as an influence diagram. We do not require the usual assumptions of no forgetting and regularity, which allows us to solve problems with limited information. The algorithm, which implements a sophisticated variable elimination procedure, is empirically shown to outperform a state-of-the-art algorithm in randomly generated problems of up to 150 variables and $10^{64}$ strategies.
How Do Humans Teach: On Curriculum Learning and Teaching Dimension
Authors: Bilge Mutlu, Xiaojin Zhu Faisal Khan
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study the empirical strategies that humans follow as they teach a target concept with a simple 1D threshold to a robot.  Previous studies of computational teaching, particularly the teaching dimension model and the curriculum learning principle, offer contradictory predictions on what optimal strategy the teacher should follow in this teaching task. We show through behavioral studies that humans employ three distinct teaching strategies, one of which is consistent with the curriculum learning principle, and propose a novel theoretical framework as a potential explanation for this strategy. This framework, which assumes a teaching goal of minimizing the learner's expected generalization error at each iteration, extends the standard teaching dimension model and offers a theoretical justification for curriculum learning.
A rational model of causal inference with continuous causes
Authors: Michael James Thomas L. Griffiths
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Rational models of causal induction have been successful in accounting for people's judgments about the existence of causal relationships. However, these models have focused on explaining inferences from discrete data of the kind that can be summarized in a 2 ✕ 2 contingency table. This severely limits the scope of these models, since the world often provides non-binary data. We develop a new rational model of causal induction using continuous dimensions, which aims to diminish the gap between empirical and theoretical approaches and real-world causal induction. This model successfully predicts human judgments from previous studies better than models of discrete causal inference, and outperforms several other plausible models of causal induction with continuous causes in accounting for people's inferences in a new experiment.
Identifying Alzheimer's Disease-Related Brain Regions from Multi-Modality Neuroimaging Data using Sparse Composite Linear Discrimination Analysis
Authors: Jing Li, Jieping Ye, Teresa Wu, Kewei Chen, Adam Fleisher, Eric Reiman Shuai Huang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Diagnosis of Alzheimer's disease (AD) at the early stage of the disease development is of great clinical importance. Current clinical assessment that relies primarily on cognitive measures proves low sensitivity and specificity. The fast growing neuroimaging techniques hold great promise. Research so far has focused on single neuroimaging modalities. However, as different modalities provide complementary measures for the same disease pathology, fusion of multi-modality data may increase the statistical power in identification of disease-related brain regions. This is especially true for early AD, at which stage the disease-related regions are most likely to be weak-effect regions that are difficult to be detected from a single modality alone. We propose a sparse composite linear discriminant analysis model (SCLDA) for identification of disease-related brain regions of early AD from multi-modality data. SCLDA uses a novel formulation that decomposes each LDA parameter into a product of a common parameter shared by all the modalities and a parameter specific to each modality, which enables joint analysis of all the modalities and borrowing strength from one another. We prove that this formulation is equivalent to a penalized likelihood with non-convex regularization, which can be solved by the DC ((difference of convex functions) programming. We show that in using the DC programming, the property of the non-convex regularization in terms of preserving weak-effect features can be nicely revealed. We perform extensive simulations to show that SCLDA outperforms existing competing algorithms on feature selection, especially on the ability for identifying weak-effect features. We apply SCLDA to the Magnetic Resonance Imaging (MRI) and Positron Emission Tomography (PET) images of 49 AD patients and 67 normal controls (NC). Our study identifies disease-related brain regions consistent with findings in the AD literature.
Structured sparse coding via lateral inhibition
Authors: Karol Gregor, Yann L. Cun Arthur D. Szlam
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This work describes a conceptually simple method for structured sparse coding and dictionary design. Supposing a dictionary with K atoms, we introduce a structure as a set of penalties or interactions between every pair of atoms. We describe modifications of standard sparse coding algorithms for inference in this setting, and describe experiments showing that these algorithms are efficient. We show that interesting dictionaries can be learned for interactions that encode tree structures or locally connected structures. Finally, we show that our framework allows us to learn the values of the interactions from the data, rather than having them pre-specified.
TD_gamma: Re-evaluating Complex Backups in Temporal Difference Learning
Authors: Scott Niekum, Philip S. Thomas George Konidaris
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We show that the lambda-return target used in the TD(lambda) family of algorithms is the maximum likelihood estimator for a specific model of how the variance of an n-step return estimate increases with n. We introduce the gamma-return estimator, an alternative target based on a more accurate model of variance, which defines the TDgamma family of complex-backup temporal difference learning algorithms. We derive TDgamma, the gamma-return equivalent of the original TD(lambda) algorithm, which eliminates the lambda parameter but can only perform updates at the end of an episode and requires time and space proportional to the episode length. We then derive a second algorithm, TDgamma(C), with a capacity parameter C. TDgamma(C) requires C times more time and memory than TD(lambda) and is incremental and online. We show that TDgamma outperforms TD(lambda) for any setting of lambda on 4 out of 5 benchmark domains, and that TDgamma(C) performs as well as or better than TD_gamma for intermediate settings of C.
Estimating time-varying input signals and ion channel states from a single voltage trace of a neuron
Authors: Yasuhiro Tsubo, Petr Lansky, Shigeru Shinomoto Ryota Kobayashi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: State-of-the-art statistical methods in neuroscience have enabled us to fit mathematical models to experimental data and subsequently to infer the dynamics of hidden parameters underlying the observable phenomena. Here, we develop a Bayesian method for inferring the time-varying mean and variance of the synaptic input, along with the dynamics of each ion channel from a single voltage trace of a neuron. An estimation problem may be formulated on the basis of the state-space model with prior distributions that penalize large fluctuations in these parameters. After optimizing the hyperparameters by maximizing the marginal likelihood, the state-space model provides the time-varying parameters of the input signals and the ion channel states. The proposed method is tested not only on the simulated data from the Hodgkin-Huxley type models but also on experimental data obtained from a cortical slice in vitro.
Joint 3D Estimation of Objects and Scene Layout
Authors: Christian Wojek, Raquel Urtasun Andreas Geiger
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose a novel generative model that is able to reason jointly about the 3D scene layout as well as the 3D location and orientation of objects in the scene. In particular, we infer the scene topology, geometry as well as traffic activities from a short video sequence acquired with a single camera mounted on a moving car. Our generative model takes advantage of dynamic information in the form of vehicle tracklets as well as static information coming from semantic labels and geometry  (i.e., vanishing points). Experiments show that our approach outperforms a discriminative baseline based on multiple kernel learning (MKL) which has access to the same image information. Furthermore, as we reason about objects in 3D, we are able to significantly increase the performance of state-of-the-art object detectors in their ability to estimate  object orientation.
Sparse Manifold Clustering and Embedding
Authors: René Vidal Ehsan Elhamifar
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose an algorithm called Sparse Manifold Clustering and Embedding (SMCE) for simultaneous clustering and dimensionality reduction of data lying in multiple nonlinear manifolds. Similar to most dimensionality reduction methods, SMCE finds a small neighborhood around each data point and connects each point to its neighbors with appropriate weights. The key difference is that SMCE finds both the neighbors and the weights automatically. This is done by solving a sparse optimization problem, which encourages selecting nearby points that lie in the same manifold and approximately span a low-dimensional affine subspace. The optimal solution encodes information that can be used for clustering and dimensionality reduction using spectral clustering and embedding. Moreover, the size of the optimal neighborhood of a data point, which can be different for different points, provides an estimate of the dimension of the manifold to which the point belongs. Experiments demonstrate that our method can effectively handle multiple manifolds that are very close to each other, manifolds with non-uniform sampling and holes, as well as estimate the intrinsic dimensions of the manifolds.
Submodular Multi-Label Learning
Authors: Tibério S. Caetano James Petterson
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper we present an algorithm to learn a multi-label classifier which attempts at directly optimising the F-score. The key novelty of our formulation is that we explicitly allow for assortative (submodular) pairwise label interactions, i.e., we can leverage the co-ocurrence of pairs of labels in order to improve the quality of prediction. Prediction in this model consists of minimising a particular submodular set function, what can be accomplished exactly and efficiently via graph-cuts. Learning however is substantially more involved and requires the solution of an intractable combinatorial optimisation problem. We present an approximate algorithm for this problem and prove that it is sound in the sense that it never predicts incorrect labels. We also present a nontrivial test of a sufficient condition for our algorithm to have found an optimal solution. We present experiments on benchmark multi-label datasets, which attest the value of our proposed technique. We also make available source code that enables the reproduction of our experiments.
Learning Probabilistic Non-Linear Latent Variable Models for Tracking Complex Activities
Authors: Juergen Gall, Luc V. Gool, Raquel Urtasun Angela Yao
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: A common approach for handling the complexity and inherent ambiguities of 3D human pose estimation is to use pose priors learned from  training data. Existing approaches however, are either too simplistic (linear), too complex to learn, or  can only learn latent spaces from "simple data", i.e., single activities such as walking or running. In this paper, we present an efficient stochastic gradient descent algorithm that is able to learn probabilistic non-linear latent  spaces composed of multiple  activities. Furthermore, we derive an incremental algorithm for the online setting which can update the latent space without extensive relearning. We demonstrate the  effectiveness of our approach on the  task of monocular and multi-view tracking and show that our approach  outperforms the state-of-the-art.
Collective Graphical Models
Authors: Thomas G. Dietterich Daniel R. Sheldon
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: There are many settings in which we wish to fit a model of the behavior of individuals but where our data consist only of aggregate information (counts or low-dimensional contingency tables).  This paper introduces Collective Graphical Models---a framework for modeling and probabilistic inference that operates directly on the sufficient statistics of the individual model.  We derive a highly-efficient Gibbs sampling algorithm for sampling from the posterior distribution of the sufficient statistics conditioned on noisy aggregate observations, prove its correctness, and demonstrate its effectiveness experimentally.
Sparse Estimation with Structured Dictionaries
Authors: David P. Wipf
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In the vast majority of recent work on sparse estimation algorithms, performance has been evaluated using ideal or quasi-ideal dictionaries (e.g., random Gaussian or Fourier) characterized by unit $\ell_2$ norm, incoherent columns or features.  But in reality, these types of dictionaries represent only a subset of the dictionaries that are actually used in practice (largely restricted to idealized compressive sensing applications).  In contrast, herein sparse estimation is considered in the context of structured dictionaries possibly exhibiting high coherence between arbitrary groups of columns and/or rows.  Sparse penalized regression models are analyzed with the purpose of finding, to the extent possible, regimes of dictionary invariant performance.  In particular, a Type II Bayesian estimator with a dictionary-dependent sparsity penalty is shown to have a number of desirable invariance properties leading to provable advantages over more conventional penalties such as the $\ell_1$ norm, especially in areas where existing theoretical recovery guarantees no longer hold.  This can translate into improved performance in applications such as model selection with correlated features, source localization, and compressive sensing with constrained measurement directions.
Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction
Authors: Satyen Kale Elad Hazan
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present an efficient algorithm for the problem of online multiclass prediction with bandit feedback in the fully adversarial setting. We measure its regret with respect to the log-loss defined in \cite{AbernethyR09}, which is parameterized by a scalar (\alpha). We prove that the regret of \newtron is (O(\log T)) when (\alpha) is a constant that does not vary with horizon (T), and at most (O(T^{2/3})) if (\alpha) is allowed to increase to infinity with (T). For (\alpha) = (O(\log T)), the regret is bounded by (O(\sqrt{T})), thus solving the open problem of \cite{KST08, AbernethyR09}. Our algorithm is based on a novel application of the online Newton method \cite{HAK07}. We test our algorithm and show it to perform well in experiments, even when (\alpha) is a small constant.
The Fixed Points of Off-Policy TD
Authors: J. Z. Kolter
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Off-policy learning, the ability for an agent to learn about a policy other than the one it is following, is a key element of Reinforcement Learning, and in recent years there has been much work on developing Temporal Different (TD) algorithms that are guaranteed to converge under off-policy sampling.  It has remained an open question, however, whether anything can be said a priori about the quality of the TD solution when off-policy sampling is employed with function approximation.  In general the answer is no: for arbitrary off-policy sampling the error of the TD solution can be unboundedly large, even when the approximator can represent the true value function well.  In this paper we propose a novel approach to address this problem: we show that by considering a certain convex subset of off-policy distributions we can indeed provide guarantees as to the solution quality similar to the on-policy case.  Furthermore, we show that we can efficiently project on to this convex set using only samples generated from the system.  The end result is a novel TD algorithm that has approximation guarantees even in the case of off-policy sampling and which empirically outperforms existing TD methods.
Transfer from Multiple MDPs
Authors: Marcello Restelli Alessandro Lazaric
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Transfer reinforcement learning (RL) methods leverage on the experience collected on a set of source tasks to speed-up RL algorithms. A simple and effective approach is to transfer samples from source tasks and include them in the training set used to solve a target task. In this paper, we investigate the theoretical properties of this transfer method and we introduce novel algorithms adapting the transfer process on the basis of the similarity between source and target tasks. Finally, we report illustrative experimental results in a continuous chain problem.
Pylon Model for Semantic Segmentation
Authors: Andrea Vedaldi, Andrew Zisserman Victor Lempitsky
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Graph cut optimization is one of the standard workhorses of image segmentation since for binary random field representations of the  image, it gives globally optimal results and there are efficient  polynomial time implementations.  Often, the random field is applied  over a flat partitioning of the image into non-intersecting elements,  such as pixels or super-pixels.    In the paper we show that if, instead of a flat partitioning, the image is represented by a hierarchical segmentation tree, then the resulting energy combining unary and boundary terms can still be optimized using graph cut (with all the corresponding benefits of global optimality and efficiency). As a result of such inference, the image gets partitioned into a set of segments that may come from different layers of the tree.    We apply this formulation, which we call the pylon model, to the task of semantic segmentation where the goal is to separate an image into areas belonging to different semantic classes. The experiments highlight the advantage of inference on a segmentation tree (over a flat partitioning) and demonstrate that the optimization in the pylon model is able to flexibly choose the level of segmentation across the image. Overall, the proposed system has superior segmentation accuracy on several datasets (Graz-02, Stanford background) compared to previously suggested approaches.
How biased are maximum entropy models?
Authors: Iain Murray, Peter E. Latham Jakob H. Macke
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Maximum entropy models have become popular statistical models in neuroscience and other areas in biology, and can be useful tools for obtaining estimates of mu- tual information in biological systems. However, maximum entropy models fit to small data sets can be subject to sampling bias; i.e. the true entropy of the data can be severely underestimated. Here we study the sampling properties of estimates of the entropy obtained from maximum entropy models. We show that if the data is generated by a distribution that lies in the model class, the bias is equal to the number of parameters divided by twice the number of observations. However, in practice, the true distribution is usually outside the model class, and we show here that this misspecification can lead to much larger bias. We provide a perturba- tive approximation of the maximally expected bias when the true model is out of model class, and we illustrate our results using numerical simulations of an Ising model; i.e. the second-order maximum entropy distribution on binary data.
Gaussian process modulated renewal processes
Authors: Vinayak Rao Yee W. Teh
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Renewal processes are generalizations of the Poisson process on the real line, whose intervals are drawn i.i.d. from some distribution. Modulated renewal processes allow these distributions to vary with time, allowing the introduction nonstationarity. In this work, we take a nonparametric Bayesian approach, modeling this nonstationarity with a Gaussian process. Our approach is based on the idea of uniformization, allowing us to draw exact samples from an otherwise intractable distribution. We develop a novel and efficient MCMC sampler for posterior inference. In our experiments, we test these on a number of synthetic and real datasets.