mtybilly/Instruct2DS huggingface dataset:
Multi-Step Dyna Planning for Policy Evaluation and Control
Authors: Hengshuai Yao, Shalabh Bhatnagar, Dongcui Diao, Richard S. Sutton, Csaba Szepesvári
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: Chong Wang, David M. Blei
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: Sennay Ghebreab, Steven Scholte, Victor Lamme, Arnold Smeulders
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: Tom Ouyang, Randall Davis
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: Arthur Choi, Adnan Darwiche
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: Mingyuan Zhou, Haojun Chen, Lu Ren, Guillermo Sapiro, Lawrence Carin, John W. Paisley
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.
Efficient and Accurate Lp-Norm Multiple Kernel Learning
Authors: Marius Kloft, Ulf Brefeld, Pavel Laskov, Klaus-Robert Müller, Alexander Zien, Sören Sonnenburg
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: Jörg Lücke, Richard Turner, Maneesh Sahani, Marc Henniges
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.
A Smoothed Approximate Linear Program
Authors: Vijay Desai, Vivek Farias, Ciamac C. Moallemi
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: Ed Vul, George Alvarez, Joshua B. Tenenbaum, Michael J. Black
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: Jing Gao, Feng Liang, Wei Fan, Yizhou Sun, Jiawei Han
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: Ryan Mcdonald, Mehryar Mohri, Nathan Silberman, Dan Walker, Gideon S. Mann
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: Saketha N. Jagarlapudi, Dinesh G, Raman S, Chiranjib Bhattacharyya, Aharon Ben-tal, Ramakrishnan K.r.
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: Yusuke Fujiwara, Yoichi Miyawaki, Yukiyasu Kamitani
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: Sahand Negahban, Bin Yu, Martin J. Wainwright, Pradeep K. Ravikumar
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: Grzegorz Swirszcz, Naoki Abe, Aurelie C. Lozano
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: Parikshit Ram, Dongryeol Lee, Hua Ouyang, Alexander G. Gray
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: Matthew Streeter, Daniel Golovin, Andreas Krause
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: George Konidaris, Andrew G. Barto
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: Kevin Waugh, Nolan Bard, Michael Bowling
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: Khashayar Rohanimanesh, Sameer Singh, Andrew McCallum, Michael J. Black
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: M. P. Kumar, Daphne Koller
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: Mario Fritz, Gary Bradski, Sergey Karayev, Trevor Darrell, Michael J. Black
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: Jean-pascal Pfister, Peter Dayan, Máté Lengyel
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: Alexandre Bouchard-côté, Slav Petrov, Dan Klein
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: Yang Wang, Gholamreza Haffari, Shaojun Wang, Greg Mori
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: Chenghui Cai, Xuejun Liao, Lawrence Carin
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: Masayuki Karasuyama, Ichiro Takeuchi
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: Marcel V. Gerven, Botond Cseke, Robert Oostenveld, Tom Heskes
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: Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh
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: Jian Peng, Liefeng Bo, Jinbo Xu
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.
An Online Algorithm for Large Scale Image Similarity Learning
Authors: Gal Chechik, Uri Shalit, Varun Sharma, Samy Bengio
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Learning a measure of similarity between pairs of objects is a fundamental problem in machine learning. It stands in the core of classification methods like kernel machines, and is particularly useful for applications like searching for images that are similar to a given image or finding videos that are relevant to a given video. In these tasks, users look for objects that are not only visually similar but also semantically related to a given object. Unfortunately, current approaches for learning similarity may not scale to large datasets with high dimensionality, especially when imposing metric constraints on the learned similarity. We describe OASIS, a method for learning pairwise similarity that is fast and scales linearly with the number of objects and the number of non-zero features. Scalability is achieved through online learning of a bilinear model over sparse representations using a large margin criterion and an efficient hinge loss cost. OASIS is accurate at a wide range of scales: on a standard benchmark with thousands of images, it is more precise than state-of-the-art methods, and faster by orders of magnitude. On 2 million images collected from the web, OASIS can be trained within 3 days on a single CPU. The non-metric similarities learned by OASIS can be transformed into metric similarities, achieving higher precisions than similarities that are learned as metrics in the first place. This suggests an approach for learning a metric from data that is larger by an order of magnitude than was handled before.
Functional network reorganization in motor cortex can be explained by reward-modulated Hebbian learning
Authors: Steven Chase, Andrew Schwartz, Wolfgang Maass, Robert A. Legenstein
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The control of neuroprosthetic devices from the activity of motor cortex neurons benefits from learning effects where the function of these neurons is adapted to the control task. It was recently shown that tuning properties of neurons in monkey motor cortex are adapted selectively in order to compensate for an erroneous interpretation of their activity. In particular, it was shown that the tuning curves of those neurons whose preferred directions had been misinterpreted changed more than those of other neurons. In this article, we show that the experimentally observed self-tuning properties of the system can be explained on the basis of a simple learning rule. This learning rule utilizes neuronal noise for exploration and performs Hebbian weight updates that are modulated by a global reward signal. In contrast to most previously proposed reward-modulated Hebbian learning rules, this rule does not require extraneous knowledge about what is noise and what is signal. The learning rule is able to optimize the performance of the model system within biologically realistic periods of time and under high noise levels. When the neuronal noise is fitted to experimental data, the model produces learning effects similar to those found in monkey experiments.
Accelerated Gradient Methods for Stochastic Optimization and Online Learning
Authors: Chonghai Hu, Weike Pan, James T. Kwok
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Regularized risk minimization often involves non-smooth optimization, either because of the loss function (e.g., hinge loss) or the regularizer (e.g., $\ell_1$-regularizer). Gradient descent methods, though highly scalable and easy to implement, are known to converge slowly on these problems. In this paper, we develop novel accelerated gradient methods for stochastic optimization while still preserving their computational simplicity and scalability. The proposed algorithm, called SAGE (Stochastic Accelerated GradiEnt), exhibits fast convergence rates on stochastic optimization with both convex and strongly convex objectives. Experimental results show that SAGE is faster than recent (sub)gradient methods including FOLOS, SMIDAS and SCD. Moreover, SAGE can also be extended for online learning, resulting in a simple but powerful algorithm.
Robust Value Function Approximation Using Bilinear Programming
Authors: Marek Petrik, Shlomo Zilberstein
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose approximate bilinear programming, a new formulation of value function approximation that provides strong a priori guarantees. In particular, it provably finds an approximate value function that minimizes the Bellman residual. Solving a bilinear program optimally is NP hard, but this is unavoidable because the Bellman-residual minimization itself is NP hard. We, therefore, employ and analyze a common approximate algorithm for bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on a simple benchmark problem.
Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units
Authors: Feng Yan, Ningyi Xu, Yuan Qi
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The recent emergence of Graphics Processing Units (GPUs) as general-purpose parallel computing devices provides us with new opportunities to develop scalable learning methods for massive data. In this work, we consider the problem of parallelizing two inference methods on GPUs for latent Dirichlet Allocation (LDA) models, collapsed Gibbs sampling (CGS) and collapsed variational Bayesian (CVB). To address limited memory constraints on GPUs, we propose a novel data partitioning scheme that effectively reduces the memory cost. Furthermore, the partitioning scheme balances the computational cost on each multiprocessor and enables us to easily avoid memory access conflicts. We also use data streaming to handle extremely large datasets. Extensive experiments showed that our parallel inference methods consistently produced LDA models with the same predictive power as sequential training methods did but with 26x speedup for CGS and 196x speedup for CVB on a GPU with 30 multiprocessors; actually the speedup is almost linearly scalable with the number of multiprocessors available. The proposed partitioning scheme and data streaming can be easily ported to many other models in machine learning.
Local Rules for Global MAP: When Do They Work ?
Authors: Kyomin Jung, Pushmeet Kohli, Devavrat Shah
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within $2n\ln n$ iterations on average and with high probability for {\em any} $n$ node pair-wise MRF with {\em geometry} (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood -- this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.
Bayesian estimation of orientation preference maps
Authors: Sebastian Gerwinn, Leonard White, Matthias Kaschube, Matthias Bethge, Jakob H. Macke
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Imaging techniques such as optical imaging of intrinsic signals, 2-photon calcium imaging and voltage sensitive dye imaging can be used to measure the functional organization of visual cortex across different spatial scales. Here, we present Bayesian methods based on Gaussian processes for extracting topographic maps from functional imaging data.  In particular, we focus on the estimation of orientation preference maps (OPMs) from intrinsic signal imaging data.  We model the underlying map as a bivariate Gaussian process, with a prior covariance function that reflects known properties of OPMs, and a noise covariance adjusted to the data.  The posterior mean can be interpreted as an optimally smoothed estimate of the map, and can be used for model based interpolations of the map from sparse measurements.  By sampling from the posterior distribution, we can get error bars on statistical properties such as preferred orientations,  pinwheel locations or -counts.  Finally, the use of an explicit probabilistic model facilitates interpretation of parameters and provides the basis for decoding studies.  We demonstrate our model both on simulated data and on intrinsic signaling data from ferret visual cortex.