mtybilly/Instruct2DS huggingface dataset:
Hierarchical Modeling of Local Image Features through $L_p$-Nested Symmetric Distributions
Authors: Eero P. Simoncelli, Fabian H. Sinz Matthias Bethge
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We introduce a new family of distributions, called $L_p${\em -nested symmetric distributions}, whose densities access the data exclusively through a hierarchical cascade of $L_p$-norms. This class generalizes the family of spherically and $L_p$-spherically symmetric distributions which have recently been successfully used for natural image modeling. Similar to those distributions it allows for a nonlinear mechanism to reduce the dependencies between its variables. With suitable choices of the parameters and norms, this family also includes the Independent Subspace Analysis (ISA) model, which has been proposed as a means of deriving filters that mimic complex cells found in mammalian primary visual cortex. $L_p$-nested distributions are easy to estimate and allow us to explore the variety of models between ISA and the $L_p$-spherically symmetric models. Our main findings are that, without a preprocessing step of contrast gain control, the independent subspaces of ISA are in fact more dependent than the individual filter coefficients within a subspace and, with contrast gain control, where ISA finds more than one subspace, the filter responses were almost independent anyway.
Optimizing Multi-Class Spatio-Spectral Filters via Bayes Error Estimation for EEG Classification
Authors: Zhouchen Lin Wenming Zheng
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The method of common spatio-spectral patterns (CSSPs) is an extension of common spatial patterns (CSPs) by utilizing the technique of delay embedding to alleviate the adverse effects of noises and artifacts on the electroencephalogram (EEG) classification. Although the CSSPs method has shown to be more powerful than the CSPs method in the EEG classification, this method is only suitable for two-class EEG classification problems. In this paper, we generalize the two-class CSSPs method to multi-class cases. To this end, we first develop a novel theory of multi-class Bayes error estimation and then present the multi-class CSSPs (MCSSPs) method based on this Bayes error theoretical framework. By minimizing the estimated closed-form Bayes error, we obtain the optimal spatio-spectral filters of MCSSPs. To demonstrate the effectiveness of the proposed method, we conduct extensive experiments on the data set of BCI competition 2005. The experimental results show that our method significantly outperforms the previous multi-class CSPs (MCSPs) methods in the EEG classification.
Nash Equilibria of Static Prediction Games
Authors: Tobias Scheffer Michael Brückner
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The standard assumption of identically distributed training and test data can be violated when an adversary can exercise some control over the generation of the test data. In a prediction game, a learner produces a predictive model while an adversary may alter the distribution of input data. We study single-shot prediction games in which the cost functions of learner and adversary are not necessarily antagonistic. We identify conditions under which the prediction game has a unique Nash equilibrium, and derive algorithms that will find the equilibrial prediction models. In a case study, we explore properties of Nash-equilibrial prediction models for email spam filtering empirically.
Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization
Authors: Arvind Ganesh, Shankar Rao, Yigang Peng, Yi Ma John Wright
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized “robust principal component analysis” problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the error entries E can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns, by solving a simple convex program. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our analysis is the first proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision.
Unsupervised Feature Selection for the $k$-means Clustering Problem
Authors: Petros Drineas, Michael W. Mahoney Christos Boutsidis
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We present a novel feature selection algorithm for the $k$-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter $\epsilon \in (0,1)$, selects and appropriately rescales in an unsupervised manner $\Theta(k \log(k / \epsilon) / \epsilon^2)$ features from a dataset of arbitrary dimensions. We prove that, if we run any $\gamma$-approximate $k$-means algorithm ($\gamma \geq 1$) on the features selected using our method, we can find a $(1+(1+\epsilon)\gamma)$-approximate partition with high probability.
Multi-Step Dyna Planning for Policy Evaluation and Control
Authors: Shalabh Bhatnagar, Dongcui Diao, Richard S. Sutton, Csaba Szepesvári Hengshuai Yao
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We extend Dyna planning architecture for policy evaluation and control in two significant aspects. First, we introduce a multi-step Dyna planning that projects the simulated state/feature many steps into the future. Our multi-step Dyna is based on a multi-step model, which we call the {\em $\lambda$-model}. The $\lambda$-model interpolates between the one-step model and an infinite-step model, and can be learned efficiently online. Second, we use for Dyna control a dynamic multi-step model that is able to predict the results of a sequence of greedy actions and track the optimal policy in the long run. Experimental results show that Dyna using the multi-step model evaluates a policy faster than using single-step models; Dyna control algorithms using the dynamic tracking model are much faster than model-free algorithms; further, multi-step Dyna control algorithms enable the policy and value function to converge much faster to their optima than single-step Dyna algorithms.
Variational Inference for the Nested Chinese Restaurant Process
Authors: David M. Blei Chong Wang
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The nested Chinese restaurant process (nCRP) is a powerful nonparametric Bayesian model for learning tree-based hierarchies from data. Since its posterior distribution is intractable, current inference methods have all relied on MCMC sampling. In this paper, we develop an alternative inference technique based on variational methods. To employ variational methods, we derive a tree-based stick-breaking construction of the nCRP mixture model, and a novel variational algorithm that efficiently explores a posterior over a large set of combinatorial structures. We demonstrate the use of this approach for text and hand written digits modeling, where we show we can adapt the nCRP to continuous data as well.
A Biologically Plausible Model for Rapid Natural Scene Identification
Authors: Steven Scholte, Victor Lamme, Arnold Smeulders Sennay Ghebreab
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Contrast statistics of the majority of natural images conform to a Weibull distribution. This property of natural images may facilitate efficient and very rapid extraction of a scenes visual gist. Here we investigate whether a neural response model based on the Weibull contrast distribution captures visual information that humans use to rapidly identify natural scenes. In a learning phase, we measure EEG activity  of 32 subjects viewing brief flashes of 800 natural scenes. From these neural measurements and the contrast statistics of the natural image stimuli,  we  derive an across subject  Weibull response model. We use this model to predict the responses to a large set of new scenes and estimate which scene the subject viewed by finding the best match between the model predictions and the observed EEG responses. In almost 90 percent of the cases our model accurately predicts the observed scene. Moreover, in most failed cases, the scene mistaken for the observed scene is visually similar to the observed scene itself. These results suggest that Weibull contrast statistics of natural images contain a considerable amount of scene gist information to warrant rapid identification of natural images.
Learning from Neighboring Strokes: Combining Appearance and Context for Multi-Domain Sketch Recognition
Authors: Randall Davis Tom Ouyang
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We propose a new sketch recognition framework that combines a rich representation of low level visual appearance with a graphical model for capturing high level relationships between symbols. This joint model of appearance and context allows our framework to be less sensitive to noise and drawing variations, improving accuracy and robustness. The result is a recognizer that is better able to handle the wide range of drawing styles found in messy freehand sketches. We evaluate our work on two real-world domains, molecular diagrams and electrical circuit diagrams, and show that our combined approach significantly improves recognition performance.
Approximating MAP by Compensating for Structural Relaxations
Authors: Adnan Darwiche Arthur Choi
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We introduce a new perspective on approximations to the maximum a posteriori (MAP) task in probabilistic graphical models, that is based on simplifying a given instance, and then tightening the approximation.  First, we start with a structural relaxation of the original model.  We then infer from the relaxation its deficiencies, and compensate for them.  This perspective allows us to identify two distinct classes of approximations.  First, we find that max-product belief propagation can be viewed as a way to compensate for a relaxation, based on a particular idealized case for exactness.  We identify a second approach to compensation that is based on a more refined idealized case, resulting in a new approximation with distinct properties.  We go on to propose a new class of algorithms that, starting with a relaxation, iteratively yields tighter approximations.
Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations
Authors: Haojun Chen, Lu Ren, Guillermo Sapiro, Lawrence Carin, John W. Paisley Mingyuan Zhou
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Non-parametric Bayesian techniques are considered for learning dictionaries for sparse image representations, with applications in denoising, inpainting and compressive sensing (CS). The beta process is employed as a prior for learning the dictionary, and this non-parametric method naturally infers an appropriate dictionary size. The Dirichlet process and a probit stick-breaking process are also considered to exploit structure within an image. The proposed method can learn a sparse dictionary in situ; training images may be exploited if available, but they are not required. Further, the noise variance need not be known, and can be non-stationary. Another virtue of the proposed method is that sequential inference can be readily employed, thereby allowing scaling to large images. Several example results are presented, using both Gibbs and variational Bayesian inference, with comparisons to other state-of-the-art approaches.
Discrete MDL Predicts in Total Variation
Authors: Marcus Hutter
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are close to the true distribution in a strong sense. The result is completely general. No independence, ergodicity, stationarity, identifiability, or other assumption on the model class need to be made. More formally, we show that for any countable class of models, the distributions selected by MDL (or MAP) asymptotically predict (merge with) the true measure in the class in total variation distance. Implications for non-i.i.d. domains like time-series forecasting, discriminative learning, and reinforcement learning are discussed.
Efficient and Accurate Lp-Norm Multiple Kernel Learning
Authors: Ulf Brefeld, Pavel Laskov, Klaus-Robert Müller, Alexander Zien, Sören Sonnenburg Marius Kloft
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Learning linear combinations of multiple kernels is an appealing strategy when the right choice of features is unknown. Previous approaches to multiple kernel learning (MKL) promote sparse kernel combinations and hence support interpretability. Unfortunately, L1-norm MKL is hardly observed to outperform trivial baselines in practical applications. To allow for robust kernel mixtures, we generalize MKL to arbitrary Lp-norms. We devise new insights on the connection between  several existing MKL formulations and develop two efficient interleaved optimization strategies for arbitrary p>1. Empirically, we demonstrate that the interleaved optimization strategies are much faster compared to the traditionally used wrapper approaches. Finally, we apply Lp-norm MKL to real-world problems from computational biology, showing that non-sparse MKL achieves accuracies that go beyond the state-of-the-art.
Occlusive Components Analysis
Authors: Richard Turner, Maneesh Sahani, Marc Henniges Jörg Lücke
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We study unsupervised learning in a probabilistic generative model for occlusion. The model uses two types of latent variables: one indicates which objects are present in the image, and the other how they are ordered in depth. This depth order then determines how the positions and appearances of the objects present, specified in the model parameters, combine to form the image. We show that the object parameters can be learnt from an unlabelled set of images in which objects occlude one another. Exact maximum-likelihood learning is intractable. However, we show that tractable approximations to Expectation Maximization (EM) can be found if the training images each contain only a small number of objects on average. In numerical experiments it is shown that these approximations recover the correct set of object parameters. Experiments on a novel version of the bars test using colored bars, and experiments on more realistic data, show that the algorithm performs well in extracting the generating causes. Experiments based on the standard bars benchmark test for object learning show that the algorithm performs well in comparison to other recent component extraction approaches. The model and the learning algorithm thus connect research on occlusion with the research field of multiple-cause component extraction methods.
Distribution-Calibrated Hierarchical Classification
Authors: Ofer Dekel
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: While many advances have already been made on the topic of hierarchical classi-  ﬁcation learning, we take a step back and examine how a hierarchical classiﬁca-  tion problem should be formally deﬁned. We pay particular attention to the fact  that many arbitrary decisions go into the design of the the label taxonomy that  is provided with the training data, and that this taxonomy is often unbalanced.  We correct this problem by using the data distribution to calibrate the hierarchical  classiﬁcation loss function. This distribution-based correction must be done with  care, to avoid introducing unmanagable statstical dependencies into the learning  problem. This leads us off the beaten path of binomial-type estimation and into  the uncharted waters of geometric-type estimation. We present a new calibrated  deﬁnition of statistical risk for hierarchical classiﬁcation, an unbiased geometric  estimator for this risk, and a new algorithmic reduction from hierarchical classiﬁ-  cation to cost-sensitive classiﬁcation.
A Smoothed Approximate Linear Program
Authors: Vivek Farias, Ciamac C. Moallemi Vijay Desai
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We present a novel linear program for the approximation of the dynamic programming cost-to-go function in high-dimensional stochastic control problems. LP approaches to approximate DP naturally restrict attention to approximations that are lower bounds to the optimal cost-to-go function. Our program -- the `smoothed approximate linear program -- relaxes this restriction in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: First, we demonstrate superior bounds on the quality of approximation to the optimal cost-to-go function afforded by our approach. Second, experiments with our approach on a challenging problem (the game of Tetris) show that the approach outperforms the existing LP approach (which has previously been shown to be competitive with several ADP algorithms) by an order of magnitude.
Explaining human multiple object tracking as resource-constrained approximate inference in a dynamic probabilistic model
Authors: George Alvarez, Joshua B. Tenenbaum, Michael J. Black Ed Vul
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Multiple object tracking is a task commonly used to investigate the architecture of human visual attention. Human participants show a distinctive pattern of successes and failures in tracking experiments that is often attributed to limits on an object system, a tracking module, or other specialized cognitive structures. Here we use a computational analysis of the task of object tracking to ask which human failures arise from cognitive limitations and which are consequences of inevitable perceptual uncertainty in the tracking task. We find that many human performance phenomena, measured through novel behavioral experiments, are naturally produced by the operation of our ideal observer model (a Rao-Blackwelized particle filter). The tradeoff between the speed and number of objects being tracked, however, can only arise from the allocation of a flexible cognitive resource, which can be formalized as either memory or attention.
Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models
Authors: Feng Liang, Wei Fan, Yizhou Sun, Jiawei Han Jing Gao
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Little work has been done to directly combine the outputs of multiple supervised and unsupervised models. However, it can increase the accuracy and applicability of ensemble methods. First, we can boost the diversity of classification ensemble by incorporating multiple clustering outputs, each of which provides grouping constraints for the joint label predictions of a set of related objects. Secondly, ensemble of supervised models is limited in applications which have no access to raw data but to the meta-level model outputs. In this paper, we aim at calculating a consolidated classification solution for a set of objects by maximizing the consensus among both supervised predictions and unsupervised grouping constraints. We seek a global optimal label assignment for the target objects, which is different from the result of traditional majority voting and model combination approaches. We cast the problem into an optimization problem on a bipartite graph, where the objective function favors smoothness in the conditional probability estimates over the graph, as well as penalizes deviation from initial labeling of supervised models. We solve the problem through iterative propagation of conditional probability estimates among neighboring nodes, and interpret the method as conducting a constrained embedding in a transformed space, as well as a ranking on the graph. Experimental results on three real applications demonstrate the benefits of the proposed method over existing alternatives.
Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models
Authors: Mehryar Mohri, Nathan Silberman, Dan Walker, Gideon S. Mann Ryan Mcdonald
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Training conditional maximum entropy models on massive data requires significant time and computational resources. In this paper, we investigate three common distributed training strategies: distributed gradient, majority voting ensembles, and parameter mixtures. We analyze the worst-case runtime and resource costs of each and present a theoretical foundation for the convergence of parameters under parameter mixtures, the most efficient strategy. We present large-scale experiments comparing the different strategies and demonstrate that parameter mixtures over independent models use fewer resources and achieve comparable loss as compared to standard approaches.
On the Algorithmics and Applications of a Mixed-norm based Kernel Learning Formulation
Authors: Dinesh G, Raman S, Chiranjib Bhattacharyya, Aharon Ben-tal, Ramakrishnan K.r. Saketha N. Jagarlapudi
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Motivated from real world problems, like object categorization, we study a particular mixed-norm regularization for Multiple Kernel Learning (MKL). It is assumed that the given set of kernels are grouped into distinct components where each component is crucial for the learning task at hand. The formulation hence employs $l_\infty$ regularization for promoting combinations at the component level and $l_1$ regularization for promoting sparsity among kernels in each component. While previous attempts have formulated this as a non-convex problem, the formulation given here is an instance of non-smooth convex optimization problem which admits an efficient Mirror-Descent (MD) based procedure. The MD procedure optimizes over product of simplexes, which is not a well-studied case in literature. Results on real-world datasets show that the new MKL formulation is well-suited for object categorization tasks and that the MD based algorithm outperforms state-of-the-art MKL solvers like \texttt{simpleMKL} in terms of computational effort.
Estimating image bases for visual image reconstruction from human brain activity
Authors: Yoichi Miyawaki, Yukiyasu Kamitani Yusuke Fujiwara
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Image representation based on image bases provides a framework for understanding neural representation of visual perception. A recent fMRI study has shown that arbitrary contrast-defined visual images can be reconstructed from fMRI activity patterns using a combination of multi-scale local image bases. In the reconstruction model, the mapping from an fMRI activity pattern to the contrasts of the image bases was learned from measured fMRI responses to visual images. But the shapes of the images bases were fixed, and thus may not be optimal for reconstruction. Here, we propose a method to build a reconstruction model in which image bases are automatically extracted from the measured data. We constructed a probabilistic model that relates the fMRI activity space to the visual image space via a set of latent variables. The mapping from the latent variables to the visual image space can be regarded as a set of image bases. We found that spatially localized, multi-scale image bases were estimated near the fovea, and that the model using the estimated image bases was able to accurately reconstruct novel visual images. The proposed method provides a means to discover a novel functional mapping between stimuli and brain activity patterns.
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers
Authors: Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar Sahand Negahban
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The estimation of high-dimensional parametric models requires imposing some structure on the models, for instance that they be sparse, or that matrix structured parameters have low rank. A general approach for such structured parametric model estimation is to use regularized M-estimation procedures, which regularize a loss function that measures goodness of fit of the parameters to the data with some regularization function that encourages the assumed structure. In this paper, we aim to provide a unified analysis of such regularized M-estimation procedures. In particular, we report the convergence rates of such estimators in any metric norm. Using just our main theorem, we are able to rederive some of the many existing results, but also obtain a wide range of novel convergence rates results. Our analysis also identifies key properties of loss and regularization functions such as restricted strong convexity, and decomposability, that ensure the corresponding regularized M-estimators have good convergence rates.
Grouped Orthogonal Matching Pursuit for Variable Selection and Prediction
Authors: Naoki Abe, Aurelie C. Lozano Grzegorz Swirszcz
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We consider the problem of variable group selection for least squares regression, namely, that of selecting groups of variables for best regression performance, leveraging and adhering to a natural grouping structure within the explanatory variables. We show that this problem can be efficiently addressed by using a certain greedy style algorithm. More precisely, we propose the Group Orthogonal Matching Pursuit algorithm (Group-OMP), which extends the standard OMP procedure (also referred to as ``forward greedy feature selection algorithm for least squares regression) to perform stage-wise group variable selection. We prove that under certain conditions Group-OMP can identify the correct (groups of) variables. We also provide an upperbound on the $l_\infty$ norm of the difference between the estimated regression coefficients and the true coefficients. Experimental results on simulated and real world datasets indicate that Group-OMP compares favorably to Group Lasso, OMP and Lasso, both in terms of variable selection and prediction accuracy.
Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions
Authors: Dongryeol Lee, Hua Ouyang, Alexander G. Gray Parikshit Ram
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The long-standing problem of efficient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 fingerprinting to bioinformatics to movie recommendations.  As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+eps)-distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the first time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN.  Experiments with high-dimensional datasets show that it often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior.
Online Learning of Assignments
Authors: Daniel Golovin, Andreas Krause Matthew Streeter
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Which ads should we display in sponsored search in order to maximize our revenue?  How should we dynamically rank information sources to maximize value of information?  These applications exhibit strong diminishing returns: Selection of redundant ads and information sources decreases their marginal utility.  We show that these and other problems can be formalized as repeatedly selecting an assignment of items to positions to maximize a sequence of monotone submodular functions that arrive one by one.  We present an efficient algorithm for this general problem and analyze it in the no-regret model.  Our algorithm is equipped with strong theoretical guarantees, with a performance ratio that converges to the optimal constant of 1-1/e.  We empirically evaluate our algorithms on two real-world online optimization problems on the web: ad allocation with submodular utilities, and dynamically ranking blogs to detect information cascades.
Skill Discovery in Continuous Reinforcement Learning Domains using Skill Chaining
Authors: Andrew G. Barto George Konidaris
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We introduce skill chaining, a skill discovery method for reinforcement learning agents in continuous domains, that builds chains of skills leading to an end-of-task reward. We demonstrate experimentally that it creates skills that result in performance benefits in a challenging continuous domain.
Strategy Grafting in Extensive Games
Authors: Nolan Bard, Michael Bowling Kevin Waugh
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Extensive games are often used to model the interactions of multiple agents within an environment.  Much recent work has focused on increasing the size of an extensive game that can be feasibly solved.  Despite these improvements, many interesting games are still too large for such techniques.  A common approach for computing strategies in these large games is to first employ an abstraction technique to reduce the original game to an abstract game that is of a manageable size.  This abstract game is then solved and the resulting strategy is used in the original game.  Most top programs in recent AAAI Computer Poker Competitions use this approach.  The trend in this competition has been that strategies found in larger abstract games tend to beat strategies found in smaller abstract games.  These larger abstract games have more expressive strategy spaces and therefore contain better strategies.  In this paper we present a new method for computing strategies in large games.  This method allows us to compute more expressive strategies without increasing the size of abstract games that we are required to solve.  We demonstrate the power of the approach experimentally in both small and large games, while also providing a theoretical justification for the resulting improvement.
Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference
Authors: Sameer Singh, Andrew McCallum, Michael J. Black Khashayar Rohanimanesh
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Large, relational factor graphs with structure defined by   first-order logic or other languages give rise to notoriously   difficult inference problems.  Because unrolling the structure   necessary to represent distributions over all hypotheses has   exponential blow-up, solutions are often derived from MCMC. However,   because of limitations in the design and parameterization of the   jump function, these sampling-based methods suffer from local   minima|the system must transition through lower-scoring   configurations before arriving at a better MAP solution. This paper   presents a new method of explicitly selecting fruitful downward   jumps by leveraging reinforcement learning (RL). Rather than setting   parameters to maximize the likelihood of the training data,   parameters of the factor graph are treated as a log-linear function   approximator and learned with temporal difference (TD); MAP   inference is performed by executing the resulting policy on held out   test data. Our method allows efficient gradient updates since only   factors in the neighborhood of variables affected by an action need   to be computed|we bypass the need to compute marginals entirely.   Our method provides dramatic empirical success, producing new   state-of-the-art results on a complex joint model of ontology   alignment, with a 48\% reduction in error over state-of-the-art in   that domain.
Learning a Small Mixture of Trees
Authors: Daphne Koller M. P. Kumar
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The problem of approximating a given probability distribution using a simpler distribution plays an important role in several areas of machine learning, e.g. variational inference and classification. Within this context, we consider the task of learning a mixture of tree distributions. Although mixtures of trees can be learned by minimizing the KL-divergence using an EM algorithm, its success depends heavily on the initialization. We propose an efficient strategy for obtaining a good initial set of trees that attempts to cover the entire observed distribution by minimizing the $\alpha$-divergence with $\alpha = \infty$. We formulate the problem using the fractional covering framework and present a convergent sequential algorithm that only relies on solving a convex program at each iteration. Compared to previous methods, our approach results in a significantly smaller mixture of trees that provides similar or better accuracies. We demonstrate the usefulness of our approach by learning pictorial structures for face recognition.
An Additive Latent Feature Model for Transparent Object Recognition
Authors: Gary Bradski, Sergey Karayev, Trevor Darrell, Michael J. Black Mario Fritz
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Existing methods for recognition of object instances and categories based on quantized local features can perform poorly when local features exist on transparent surfaces, such as glass or plastic objects. There are characteristic patterns to the local appearance of transparent objects, but they may not be well captured by distances to individual examples or by a local pattern codebook obtained by vector quantization.  The appearance of a transparent patch is determined in part by the refraction of a background pattern through a transparent medium: the energy from the background usually dominates the patch appearance.  We model transparent local patch appearance using an additive  model of latent factors: background factors due to scene content,  and factors which capture a local edge energy distribution characteristic of the refraction.  We implement our method using a novel LDA-SIFT formulation which performs LDA prior to any vector quantization step; we discover latent topics which are characteristic of particular transparent patches and quantize the SIFT space into transparent visual words according to the latent topic dimensions. No knowledge of the background scene is required at test time; we show examples recognizing transparent glasses in a domestic environment.
Know Thy Neighbour: A Normative Theory of Synaptic Depression
Authors: Peter Dayan, Máté Lengyel Jean-pascal Pfister
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Synapses exhibit an extraordinary degree of short-term malleability, with release probabilities and effective synaptic strengths changing markedly over multiple timescales. From the perspective of a fixed computational operation in a network, this seems like a most unacceptable degree of added noise. We suggest an alternative theory according to which short term synaptic plasticity plays a normatively-justifiable role. This theory starts from the commonplace observation that the spiking of a neuron is an incomplete, digital, report of the analog quantity that contains all the critical information, namely its membrane potential. We suggest that one key task for a synapse is to solve the inverse problem of estimating the pre-synaptic membrane potential from the spikes it receives and prior  expectations, as in a recursive filter. We show that short-term synaptic depression has canonical dynamics which closely resemble those required for optimal estimation, and that it indeed supports high quality estimation. Under this account, the local postsynaptic potential and the level of synaptic resources track the (scaled) mean and variance of the estimated presynaptic membrane potential. We make  experimentally testable predictions for how the statistics of subthreshold membrane potential fluctuations and the form of spiking non-linearity should be related to the properties of short-term plasticity in any particular cell type.
Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs
Authors: Slav Petrov, Dan Klein Alexandre Bouchard-côté
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Pruning can massively accelerate the computation of feature expectations in large models.  However, any single pruning mask will introduce bias.  We present a novel approach which employs a randomized sequence of pruning masks. Formally, we apply auxiliary variable MCMC sampling to generate this sequence of masks, thereby gaining theoretical guarantees about convergence. Because each mask is generally able to skip large portions of an underlying dynamic program, our approach is particularly compelling for high-degree algorithms.  Empirically, we demonstrate our method on bilingual parsing, showing decreasing bias as more masks are incorporated, and outperforming fixed tic-tac-toe pruning.
A Rate Distortion Approach for Semi-Supervised Conditional Random Fields
Authors: Gholamreza Haffari, Shaojun Wang, Greg Mori Yang Wang
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We propose a novel information theoretic approach for semi-supervised learning of conditional random fields. Our approach defines a training objective that combines the conditional likelihood on labeled data and the mutual information on unlabeled data. Different from previous minimum conditional entropy semi-supervised discriminative learning methods, our approach can be naturally cast into the rate distortion theory framework in information theory. We analyze the tractability of the framework for structured prediction and present a convergent variational training algorithm to defy the combinatorial explosion of terms in the sum over label configurations. Our experimental results show that the rate distortion approach outperforms standard $l_2$ regularization and minimum conditional entropy regularization on both multi-class classification and sequence labeling problems.
Learning to Explore and Exploit in POMDPs
Authors: Xuejun Liao, Lawrence Carin Chenghui Cai
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: A fundamental objective in reinforcement learning is the maintenance of a proper balance between exploration and exploitation. This problem becomes more challenging when the agent can only partially observe the states of its environment. In this paper we propose a dual-policy method for jointly learning the agent behavior and the balance between exploration exploitation, in partially observable environments. The method subsumes traditional exploration, in which the agent takes actions to gather information about the environment, and active learning, in which the agent queries an oracle for optimal actions (with an associated cost for employing the oracle). The form of the employed exploration is dictated by the specific problem. Theoretical guarantees are provided concerning the optimality of the balancing of exploration and exploitation. The effectiveness of the method is demonstrated by experimental results on benchmark problems.
Multiple Incremental Decremental Learning of Support Vector Machines
Authors: Ichiro Takeuchi Masayuki Karasuyama
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We propose a multiple incremental decremental algorithm  of Support Vector Machine (SVM). Conventional single  cremental decremental SVM can update the trained model  efficiently when single data point is added to or removed  from the training set. When we add and/or remove multiple  data points, this algorithm is time-consuming because we  need to repeatedly apply it to each data point. The roposed  algorithm is computationally more efficient when multiple  data points are added and/or removed simultaneously. The  single incremental decremental algorithm is built on an  optimization technique called parametric programming.  We extend the idea and introduce multi-parametric  programming for developing the proposed algorithm.  Experimental results on synthetic and real data sets indicate that the proposed algorithm can significantly  reduce the computational cost of multiple incremental  decremental operation. Our approach is especially useful  for online SVM learning in which we need to remove old  data points and add new data points in a short amount of  time.
Bayesian Source Localization with the Multivariate Laplace Prior
Authors: Botond Cseke, Robert Oostenveld, Tom Heskes Marcel V. Gerven
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We introduce a novel multivariate Laplace (MVL) distribution as a sparsity promoting prior for Bayesian source localization that allows the specification of constraints between and within sources. We represent the MVL distribution as a scale mixture that induces a coupling between source variances instead of their means. Approximation of the posterior marginals using expectation propagation is shown to be very efficient due to properties of the scale mixture representation. The computational bottleneck amounts to computing the diagonal elements of a sparse matrix inverse. Our approach is illustrated using a mismatch negativity paradigm for which MEG data and a structural MRI have been acquired. We show that spatial coupling leads to sources which are active over larger cortical areas as compared with an uncoupled prior.
Learning Non-Linear Combinations of Kernels
Authors: Mehryar Mohri, Afshin Rostamizadeh Corinna Cortes
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: This paper studies the general problem of learning kernels based on a polynomial combination of base kernels. It analyzes this problem in the case of regression and the kernel ridge regression algorithm. It examines the corresponding learning kernel optimization problem, shows how that minimax problem can be reduced to a simpler minimization problem, and proves that the global solution of this problem always lies on the boundary. We give a projection-based gradient descent algorithm for solving the optimization problem, shown empirically to converge in few iterations. Finally, we report the results of extensive experiments with this algorithm using several publicly available datasets demonstrating the effectiveness of our technique.
Conditional Neural Fields
Authors: Liefeng Bo, Jinbo Xu Jian Peng
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Conditional random fields (CRF) are quite successful on sequence labeling tasks such as natural language processing and biological sequence analysis. CRF models use linear potential functions to represent the relationship between input features and outputs. However, in many real-world applications such as protein structure prediction and handwriting recognition, the relationship between input features and outputs is highly complex and nonlinear, which cannot be accurately modeled by a linear function. To model the nonlinear relationship between input features and outputs we propose Conditional Neural Fields (CNF), a new conditional probabilistic graphical model for sequence labeling. Our CNF model extends CRF by adding one (or possibly several) middle layer between input features and outputs. The middle layer consists of a number of hidden parameterized gates, each acting as a local neural network node or feature extractor to capture the nonlinear relationship between input features and outputs. Therefore, conceptually this CNF model is much more expressive than the linear CRF model. To better control the complexity of the CNF model, we also present a hyperparameter optimization procedure within the evidence framework. Experiments on two widely-used benchmarks indicate that this CNF model performs significantly better than a number of popular methods. In particular, our CNF model is the best among about ten machine learning methods for protein secondary tructure prediction and also among a few of the best methods for handwriting recognition.