mtybilly/Instruct2DS huggingface dataset:
Non-conjugate Variational Message Passing for Multinomial and Binary Regression
Authors: David A. Knowles, Tom Minka
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Variational Message Passing (VMP) is an algorithmic implementation of the Variational Bayes (VB) method which applies only in the special case of conjugate exponential family models. We propose an extension to VMP, which we refer to as Non-conjugate Variational Message Passing (NCVMP) which aims to alleviate this restriction while maintaining modularity, allowing choice in how expectations are calculated, and integrating into an existing message-passing framework: Infer.NET. We demonstrate NCVMP on logistic binary and multinomial regression. In the multinomial case we introduce a novel variational bound for the softmax factor which is tighter than other commonly used bounds whilst maintaining computational tractability.
Im2Text: Describing Images Using 1 Million Captioned Photographs
Authors: Vicente Ordonez, Girish Kulkarni, Tamara L. Berg
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We develop and demonstrate automatic image description methods using a large captioned photo collection.  One contribution is our technique for the automatic collection of this new dataset -- performing a huge number of Flickr queries and then filtering the noisy results down to 1 million images with associated visually relevant captions.  Such a collection allows us to approach the extremely challenging problem of description generation using relatively simple non-parametric methods and produces surprisingly effective results. We also develop methods incorporating many state of the art, but fairly noisy, estimates of image content to produce even more pleasing results. Finally we introduce a new objective performance measure for image captioning.
Modelling Genetic Variations using Fragmentation-Coagulation Processes
Authors: Yee W. Teh, Charles Blundell, Lloyd Elliott
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose a novel class of Bayesian nonparametric models for sequential data called fragmentation-coagulation processes (FCPs).  FCPs model a set of sequences using  a partition-valued Markov process which evolves by splitting and merging clusters.  An FCP is exchangeable, projective, stationary and reversible, and its equilibrium distributions are given by the Chinese restaurant process.  As opposed to hidden Markov models, FCPs allow for flexible modelling of the number of clusters, and they avoid label switching non-identifiability problems. We develop an efficient Gibbs sampler for FCPs which uses uniformization and the forward-backward algorithm.  Our development of FCPs is motivated by applications in population genetics, and we demonstrate the utility of FCPs on problems of genotype imputation with phased and unphased SNP data.
Improving Topic Coherence with Regularized Topic Models
Authors: David Newman, Edwin V. Bonilla, Wray Buntine
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Topic models have the potential to improve search and browsing by extracting useful semantic themes from web pages and other text documents. When learned topics are coherent and interpretable, they can be valuable for faceted browsing, results set diversity analysis, and document retrieval. However, when dealing with small collections or noisy text (e.g. web search result snippets or blog posts), learned topics can be less coherent, less interpretable, and less useful. To overcome this, we propose two methods to regularize the learning of topic models. Our regularizers work by creating a structured prior over words that reflect broad patterns in the external data. Using thirteen datasets we show that both regularizers improve topic coherence and interpretability while learning a faithful representation of the collection of interest. Overall, this work makes topic models more useful across a broader range of text data.
Beating SGD: Learning SVMs in Sublinear Time
Authors: Elad Hazan, Tomer Koren, Nati Srebro
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present an optimization approach for linear SVMs based on a stochastic primal-dual approach, where the primal step is akin to an importance-weighted SGD, and the dual step is a stochastic update on the importance weights.  This yields an optimization method with a sublinear dependence on the training set size, and the first method for learning linear SVMs with runtime less then the size of the training set required for learning!
Inferring spike-timing-dependent plasticity from spike train data
Authors: Ian Stevenson, Konrad Koerding
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Synaptic plasticity underlies learning and is thus central for development, memory, and recovery from injury. However, it is often difficult to detect changes in synaptic strength in vivo, since intracellular recordings are experimentally challenging. Here we present two methods aimed at inferring changes in the coupling between pairs of neurons from extracellularly recorded spike trains. First, using a generalized bilinear model with Poisson output we estimate time-varying coupling assuming that all changes are spike-timing-dependent. This approach allows model-based estimation of STDP modification functions from pairs of spike trains. Then, using recursive point-process adaptive filtering methods we estimate more general variation in coupling strength over time. Using simulations of neurons undergoing spike-timing dependent modification, we show that the true modification function can be recovered. Using multi-electrode data from motor cortex we then illustrate the use of this technique on in vivo data.
Bayesian Spike-Triggered Covariance Analysis
Authors: Ill Memming Park, Jonathan W. Pillow
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Neurons typically respond to a restricted number of stimulus features within the high-dimensional space of natural stimuli. Here we describe an explicit model-based interpretation of traditional estimators for a neuron's multi-dimensional feature space, which allows for several important generalizations and extensions. First, we show that traditional estimators based on the spike-triggered average (STA) and spike-triggered covariance (STC) can be formalized in terms of the "expected log-likelihood" of a Linear-Nonlinear-Poisson (LNP) model with Gaussian stimuli. This model-based formulation allows us to define maximum-likelihood and Bayesian estimators that are statistically consistent and efficient in a wider variety of settings, such as with naturalistic (non-Gaussian) stimuli. It also allows us to employ Bayesian methods for regularization, smoothing, sparsification, and model comparison, and provides Bayesian confidence intervals on model parameters. We describe an empirical Bayes method for selecting the number of features, and extend the model to accommodate an arbitrary elliptical nonlinear response function, which results in a more powerful and more flexible model for feature space inference. We validate these methods using neural data recorded extracellularly from macaque primary visual cortex.
Adaptive Hedge
Authors: Tim V. Erven, Wouter M. Koolen, Steven D. Rooij, Peter Grünwald
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Most methods for decision-theoretic online learning are based on the Hedge algorithm, which takes a parameter called the learning rate. In most previous analyses the learning rate was carefully tuned to obtain optimal worst-case performance, leading to suboptimal performance on easy instances, for example when there exists an action that is significantly better than all others. We propose a new way of setting the learning rate, which adapts to the difficulty of the learning problem: in the worst case our procedure still guarantees optimal performance, but on easy instances it achieves much smaller regret. In particular, our adaptive method achieves constant regret in a probabilistic setting, when there exists an action that on average obtains strictly smaller loss than all other actions. We also provide a simulation study comparing our approach to existing methods.
Matrix Completion for Multi-label Image Classification
Authors: Ricardo S. Cabral, Fernando Torre, Joao P. Costeira, Alexandre Bernardino
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Recently, image categorization has been an active research topic due to the urgent need to retrieve and browse digital images via semantic keywords. This paper formulates image categorization as a multi-label classification problem using recent advances in matrix completion. Under this setting, classification of testing data is posed as a problem of completing unknown label entries on a data matrix that concatenates training and testing features with training labels. We propose two convex algorithms for matrix completion based on a Rank Minimization criterion specifically tailored to visual data, and prove its convergence properties. A major advantage of our approach w.r.t. standard discriminative classification methods for image categorization is its robustness to outliers, background noise and partial occlusions both in the feature and label space. Experimental validation on several datasets shows how our method outperforms state-of-the-art algorithms, while effectively capturing semantic concepts of classes.
Continuous-Time Regression Models for Longitudinal Networks
Authors: Duy Q. Vu, David Hunter, Padhraic Smyth, Arthur U. Asuncion
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The development of statistical models for continuous-time longitudinal network data is of increasing interest in machine learning and social science. Leveraging ideas from survival and event history analysis, we introduce a continuous-time regression modeling framework for network event data that can incorporate both time-dependent network statistics and time-varying regression coefficients. We also develop an efficient inference scheme that allows our approach to scale to large networks. On synthetic and real-world data, empirical results demonstrate that the proposed inference approach can accurately estimate the coefficients of the regression model, which is useful for interpreting the evolution of the network; furthermore, the learned model has systematically better predictive performance compared to standard baseline methods.
Stochastic convex optimization with bandit feedback
Authors: Alekh Agarwal, Dean P. Foster, Daniel J. Hsu, Sham M. Kakade, Alexander Rakhlin
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper addresses the problem of minimizing a convex, Lipschitz  function $f$ over a convex, compact set $X$ under a stochastic bandit feedback model. In this model, the algorithm is allowed to  observe noisy realizations of the function value $f(x)$ at any query  point $x \in X$. We demonstrate a generalization of the  ellipsoid algorithm that incurs $O(\poly(d)\sqrt{T})$ regret. Since any algorithm has regret at least $\Omega(\sqrt{T})$  on this problem, our algorithm is optimal in terms of the scaling  with $T$.
Online Learning: Stochastic, Constrained, and Smoothed Adversaries
Authors: Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Learning theory has largely focused on two main learning scenarios: the classical statistical setting where instances are drawn i.i.d. from a fixed distribution, and the adversarial scenario whereby at every time step the worst instance is revealed to the player. It can be argued that in the real world neither of these assumptions is reasonable. We define the minimax value of a game where the adversary is restricted in his moves, capturing stochastic and non-stochastic assumptions on data. Building on the sequential symmetrization approach, we define a notion of distribution-dependent Rademacher complexity for the spectrum of problems ranging from i.i.d. to worst-case. The bounds let us immediately deduce variation-type bounds. We study a smoothed online learning scenario and show that exponentially small amount of noise can make function classes with infinite Littlestone dimension learnable.
Similarity-based Learning via Data Driven Embeddings
Authors: Purushottam Kar, Prateek Jain
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of classification using similarity/distance functions over data. Specifically, we propose a framework for defining the goodness of a (dis)similarity function with respect to a given learning task and propose algorithms that have guaranteed generalization properties when working with such good functions. Our framework unifies and generalizes the frameworks proposed by (Balcan-Blum 2006) and (Wang et al 2007). An attractive feature of our framework is its adaptability to data - we do not promote a fixed notion of goodness but rather let data dictate it. We show, by giving theoretical guarantees that the goodness criterion best suited to a problem can itself be learned which makes our approach applicable to a variety of domains and problems. We propose a landmarking-based approach to obtaining a classifier from such learned goodness criteria. We then provide a novel diversity based heuristic to perform task-driven selection of landmark points instead of random selection. We demonstrate the effectiveness of our goodness criteria learning method as well as the landmark selection heuristic on a variety of similarity-based learning datasets and benchmark UCI datasets on which our method consistently outperforms existing approaches by a significant margin.
Active Ranking using Pairwise Comparisons
Authors: Kevin G. Jamieson, Robert Nowak
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects).  In general, the ranking of $n$ objects can be identified by standard sorting methods using $n\log_2 n$ pairwise comparisons. We are interested in natural situations in which relationships among the objects may allow for ranking using far fewer pairwise comparisons. {Specifically, we assume that the objects can be embedded into a $d$-dimensional Euclidean space and that the rankings reflect their relative distances from a common reference point in $\R^d$. We show that under this assumption the number of possible rankings grows like $n^{2d}$ and demonstrate an algorithm that can identify a randomly selected ranking using just slightly more than $d\log n$ adaptively selected pairwise comparisons, on average.}  If instead the comparisons are chosen at random, then almost all pairwise comparisons must be made in order to identify any ranking. In addition, we propose a robust, error-tolerant algorithm that only requires that the pairwise comparisons are probably correct. Experimental studies with synthetic and real datasets support the conclusions of our theoretical analysis.
Selecting Receptive Fields in Deep Networks
Authors: Adam Coates, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Recent deep learning and unsupervised feature learning systems that learn from unlabeled data have achieved high performance in benchmarks by using extremely large architectures with many features (hidden units) at each layer.  Unfortunately, for such large architectures the number of parameters usually grows quadratically in the width of the network, thus necessitating hand-coded "local receptive fields" that limit the number of connections from lower level features to higher ones (e.g., based on spatial locality).  In this paper we propose a fast method to choose these connections that may be incorporated into a wide variety of unsupervised training methods.  Specifically, we choose local receptive fields that group together those low-level features that are most similar to each other according to a pairwise similarity metric.  This approach  allows us to harness the advantages of local receptive fields (such  as improved scalability, and reduced data requirements) when we do  not know how to specify such receptive fields by hand or where our  unsupervised training algorithm has no obvious generalization to a  topographic setting.  We produce results showing how this method allows us to use even simple unsupervised training algorithms to train successful multi-layered etworks that achieve state-of-the-art results on CIFAR and STL datasets: 82.0% and 60.1% accuracy, respectively.
Learning Auto-regressive Models from Sequence and Non-sequence Data
Authors: Tzu-kuo Huang, Jeff G. Schneider
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Vector Auto-regressive models (VAR) are useful tools for analyzing time series  data. In quite a few modern time series modelling tasks, the collection of reliable  time series turns out to be a major challenge, either due to the slow progression of  the dynamic process of interest, or inaccessibility of repetitive measurements of  the same dynamic process over time. In those situations, however, we observe that  it is often easier to collect a large amount of non-sequence samples, or snapshots  of the dynamic process of interest. In this work, we assume a small amount of time  series data are available, and propose methods to incorporate non-sequence data  into penalized least-square estimation of VAR models. We consider non-sequence  data as samples drawn from the stationary distribution of the underlying VAR  model, and devise a novel penalization scheme based on the discrete-time Lyapunov  equation concerning the covariance of the stationary distribution. Experiments  on synthetic and video data demonstrate the effectiveness of the proposed  methods.
Multi-View Learning of Word Embeddings via CCA
Authors: Paramveer Dhillon, Dean P. Foster, Lyle H. Ungar
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Recently, there has been substantial interest in using large amounts of unlabeled data to learn word representations which can then be used as features in supervised classifiers for NLP tasks. However, most current approaches are slow to train, do not model context of the word, and lack theoretical grounding. In this paper, we present a new learning method, Low Rank Multi-View Learning (LR-MVL) which uses a fast spectral method to estimate  low dimensional context-specific word representations from unlabeled data. These representation features can then be used with any supervised learner. LR-MVL is extremely fast, gives guaranteed convergence to a global optimum, is theoretically elegant, and achieves state-of-the-art performance on named entity recognition (NER) and chunking problems.
Projection onto A Nonnegative Max-Heap
Authors: Jun Liu, Liang Sun, Jieping Ye
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of computing the Euclidean projection of a vector of length $p$ onto a non-negative max-heap---an ordered tree where the values of the nodes are all nonnegative and the value of any parent node is no less than the value(s) of its child node(s). This Euclidean projection plays a building block role in the optimization problem with a non-negative max-heap constraint. Such a constraint is desirable when the features follow an ordered tree structure, that is, a given feature is selected for the given regression/classification task only if its parent node is selected. In this paper, we show that such Euclidean projection problem admits an analytical solution and we develop a top-down algorithm where the key operation is to find the so-called \emph{maximal root-tree} of the subtree rooted at each node. A naive approach for finding the maximal root-tree is to enumerate all the possible root-trees, which, however, does not scale well. We reveal several important properties of the maximal root-tree, based on which we design a bottom-up algorithm with merge for efficiently finding the maximal root-tree. The proposed algorithm has a (worst-case) linear time complexity for a sequential list, and $O(p^2)$ for a general tree. We report simulation results showing the effectiveness of the max-heap for regression with an ordered tree structure. Empirical results show that the proposed algorithm has an expected linear time complexity for many special cases including a sequential list, a full binary tree, and a tree with depth 1.
Learning to Learn with Compound HD Models
Authors: Antonio Torralba, Joshua B. Tenenbaum, Ruslan Salakhutdinov
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce HD (or ``Hierarchical-Deep'') models, a new compositional learning architecture that integrates deep learning models with structured hierarchical Bayesian models. Specifically we show how we can learn a hierarchical Dirichlet process (HDP) prior over the activities of the top-level features in a Deep Boltzmann Machine (DBM).  This compound HDP-DBM model learns to learn novel concepts from very few training examples, by learning low-level generic features, high-level features that capture correlations among low-level features, and a category hierarchy for sharing priors over the high-level features that are typical of different kinds of concepts.  We present efficient learning and inference algorithms for the HDP-DBM model and show that it is able to learn new concepts from very few examples on CIFAR-100 object recognition, handwritten character recognition, and human motion capture datasets.
Object Detection with Grammar Models
Authors: Ross B. Girshick, Pedro F. Felzenszwalb, David A. McAllester
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Compositional models provide an elegant formalism for representing the  visual appearance of highly variable objects.  While such models are  appealing from a theoretical point of view, it has been difficult to  demonstrate that they lead to performance advantages on challenging  datasets.  Here we develop a grammar model for person detection  and show that it outperforms previous high-performance systems on the  PASCAL benchmark.  Our model represents people using a hierarchy of  deformable parts, variable structure and an explicit model of  occlusion for partially visible objects.  To train the model, we  introduce a new discriminative framework for learning structured  prediction models from weakly-labeled data.
Empirical models of spiking in neural populations
Authors: Jakob H. Macke, Lars Buesing, John P. Cunningham, Byron M. Yu, Krishna V. Shenoy, Maneesh Sahani
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Neurons in the neocortex code and compute as part of a locally interconnected population. Large-scale multi-electrode recording makes it possible to access these population processes empirically by fitting statistical models to unaveraged data. What statistical structure best describes the concurrent spiking of cells within  a local network? We argue that in the cortex, where firing exhibits extensive correlations in both time and space and where a typical sample of neurons still reflects only a very small fraction of the local population, the most appropriate model captures shared variability by a low-dimensional latent process evolving with smooth dynamics, rather than by putative direct coupling. We test this claim by comparing  a latent dynamical model with realistic spiking observations to coupled generalised  linear spike-response models (GLMs) using cortical recordings. We find that the latent dynamical approach outperforms the GLM in terms of goodness-of-fit, and reproduces the temporal correlations in the data more accurately. We also compare models whose observations models are either derived from a Gaussian or point-process models, finding that the non-Gaussian model provides slightly  better goodness-of-fit and more realistic population spike counts.
An Exact Algorithm for F-Measure Maximization
Authors: Krzysztof J. Dembczynski, Willem Waegeman, Weiwei Cheng, Eyke Hüllermeier
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The F-measure, originally introduced in information retrieval, is nowadays routinely used as a performance metric for problems such as binary classification, multi-label classification, and structured output prediction. Optimizing this measure remains a statistically and computationally challenging problem, since no closed-form maximizer exists. Current algorithms are approximate and typically rely on additional assumptions regarding the statistical distribution of the binary response variables. In this paper, we present an algorithm which is not only computationally efficient but also exact, regardless of the underlying distribution. The algorithm requires only a quadratic number of parameters of the joint distribution  (with respect to the number of binary responses). We illustrate its practical performance by means of experimental results for multi-label classification.
Exploiting spatial overlap to efficiently compute appearance distances between image windows
Authors: Bogdan Alexe, Viviana Petrescu, Vittorio Ferrari
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a computationally efficient technique to compute the distance of high-dimensional appearance descriptor vectors between image windows.  The method exploits the relation between appearance distance and spatial overlap.  We derive an upper bound on appearance distance given the spatial overlap of two windows in an image,  and use it to bound the distances of many pairs between two images.  We propose algorithms that build on these basic operations to efficiently solve tasks relevant to many computer vision applications, such as finding all pairs of windows between two images with distance smaller than a threshold,  or finding the single pair with the smallest distance. In experiments on the PASCAL VOC 07 dataset, our algorithms accurately solve these problems while greatly reducing the number of appearance distances computed, and achieve larger speedups than approximate nearest neighbour algorithms based on trees [18]and on hashing [21].    For example, our algorithm finds the most similar pair of windows between two images while computing only 1% of all distances on average.
Signal Estimation Under Random Time-Warpings and Nonlinear Signal Alignment
Authors: Sebastian A. Kurtek, Anuj Srivastava, Wei Wu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: While signal estimation under random amplitudes, phase shifts, and additive noise is studied frequently, the problem of estimating a deterministic signal under random time-warpings has been relatively unexplored. We present a novel framework for estimating the unknown signal that utilizes the action of the warping group to form an equivalence relation between signals. First, we derive an estimator for the equivalence class of the unknown signal using the notion of Karcher mean on the quotient space of equivalence classes. This step requires the use of Fisher-Rao Riemannian metric  and a square-root representation of signals to enable computations of distances and means under this metric. Then, we define a notion of the center of a class and show that the center of the estimated class is a consistent estimator of the underlying unknown signal. This estimation algorithm has many applications: (1)registration/alignment of functional data, (2) separation of phase/amplitude components of functional data, (3) joint demodulation and carrier estimation, and (4) sparse modeling of functional data. Here we demonstrate only (1) and (2):  Given signals are temporally aligned using nonlinear warpings and, thus, separated into their phase and amplitude components. The proposed method for signal alignment is shown to have state of the art performance using Berkeley growth, handwritten signatures, and neuroscience spike train data.
Predicting response time and error rates in visual search
Authors: Bo Chen, Vidhya Navalpakkam, Pietro Perona
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: A model of human visual search is proposed. It predicts both response time (RT) and error rates (RT) as a function of image parameters such as target contrast and clutter. The model is an ideal observer, in that it optimizes the Bayes ratio of tar- get present vs target absent. The ratio is computed on the firing pattern of V1/V2 neurons, modeled by Poisson distributions. The optimal mechanism for integrat- ing information over time is shown to be a ‘soft max’ of diffusions, computed over the visual field by ‘hypercolumns’ of neurons that share the same receptive field and have different response properties to image features. An approximation of the optimal Bayesian observer, based on integrating local decisions, rather than diffusions, is also derived; it is shown experimentally to produce very similar pre- dictions. A psychophyisics experiment is proposed that may discriminate between which mechanism is used in the human brain.
Sequence learning with hidden units in spiking neural networks
Authors: Johanni Brea, Walter Senn, Jean-pascal Pfister
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider a statistical framework in which recurrent networks of spiking neurons learn to generate spatio-temporal spike patterns. Given biologically realistic stochastic neuronal dynamics we derive a tractable learning rule for the synaptic weights towards hidden and visible neurons that leads to optimal recall of the training sequences. We show that learning synaptic weights towards hidden neurons significantly improves the storing capacity of the network. Furthermore, we derive an approximate online learning rule and show that our learning rule is consistent with Spike-Timing Dependent Plasticity in that if a presynaptic spike shortly precedes a postynaptic spike, potentiation is induced and otherwise depression is elicited.
Learning in Hilbert vs. Banach Spaces: A Measure Embedding Viewpoint
Authors: Kenji Fukumizu, Gert R. Lanckriet, Bharath K. Sriperumbudur
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The goal of this paper is to investigate the advantages and disadvantages of learning in Banach spaces over Hilbert spaces. While many works have been carried out in generalizing Hilbert methods to Banach spaces, in this paper, we consider the simple problem of learning a Parzen window classifier in a reproducing kernel Banach space (RKBS)---which is closely related to the notion of embedding probability measures into an RKBS---in order to carefully understand its pros and cons over the Hilbert space classifier. We show that while this generalization yields richer distance measures on probabilities compared to its Hilbert space counterpart, it however suffers from serious computational drawback limiting its practical applicability, which therefore demonstrates the need for developing efficient learning algorithms in Banach spaces.
Predicting Dynamic Difficulty
Authors: Olana Missura, Thomas Gärtner
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Motivated by applications in electronic games as well as teaching systems, we investigate the problem of dynamic difficulty adjustment. The task here is to repeatedly find a game difficulty setting that is neither `too easy' and bores the player, nor `too difficult' and overburdens the player.  The contributions of this paper are ($i$) formulation of difficulty adjustment as an online learning problem on partially ordered sets, ($ii$) an exponential update algorithm for dynamic difficulty adjustment, ($iii$) a bound on the number of wrong difficulty settings relative to the best static setting chosen in hindsight, and ($iv$) an empirical investigation of the algorithm when playing against adversaries.
Robust Multi-Class Gaussian Process Classification
Authors: Daniel Hernández-lobato, Jose M. Hernández-lobato, Pierre Dupont
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Multi-class Gaussian Process Classifiers (MGPCs) are often affected by over-fitting problems when labeling errors occur far from the decision boundaries. To prevent this, we investigate a robust MGPC (RMGPC) which considers labeling errors independently of their distance to the decision boundaries. Expectation propagation is used for approximate inference. Experiments with several datasets in which noise is injected in the class labels illustrate the benefits of RMGPC. This method performs better than other Gaussian process alternatives based on considering latent Gaussian noise or heavy-tailed processes. When no noise is injected in the labels, RMGPC still performs equal or better than the other methods. Finally, we show how RMGPC can be used for successfully identifying data instances which are difficult to classify accurately in practice.
Penalty Decomposition Methods for Rank Minimization
Authors: Yong Zhang, Zhaosong Lu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper we consider general rank minimization problems with rank appearing in either objective function or constraint. We first show that a class of matrix optimization problems can be solved as lower dimensional vector optimization problems. As a consequence, we establish that a class of rank minimization problems have closed form solutions. Using this result, we then propose penalty decomposition methods for general rank minimization problems. The convergence results of the PD methods have been shown in the longer version of the paper. Finally, we test the performance of our methods by applying them to matrix completion and nearest low-rank correlation matrix problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed.
Accelerated Adaptive Markov Chain for Partition Function Computation
Authors: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose a novel Adaptive Markov Chain Monte Carlo algorithm to  compute the partition function. In particular, we show how to  accelerate a flat histogram sampling technique by significantly  reducing the number of ``null moves'' in the chain, while maintaining  asymptotic convergence properties. Our experiments show that our  method converges quickly to highly accurate solutions on a range of  benchmark instances, outperforming other state-of-the-art methods such  as IJGP, TRW, and Gibbs sampling both in run-time and accuracy. We  also show how obtaining a so-called density of states distribution  allows for efficient weight learning in Markov Logic theories.
On Strategy Stitching in Large Extensive Form Multiplayer Games
Authors: Richard G. Gibson, Duane Szafron
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Computing a good strategy in a large extensive form game often demands an extraordinary amount of computer memory, necessitating the use of abstraction to reduce the game size.  Typically, strategies from abstract games perform better in the real game as the granularity of abstraction is increased.  This paper investigates two techniques for stitching a base strategy in a coarse abstraction of the full game tree, to expert strategies in fine abstractions of smaller subtrees.  We provide a general framework for creating static experts, an approach that generalizes some previous strategy stitching efforts.  In addition, we show that static experts can create strong agents for both 2-player and 3-player Leduc and Limit Texas Hold'em poker, and that a specific class of static experts can be preferred among a number of alternatives.  Furthermore, we describe a poker agent that used static experts and won the 3-player events of the 2010 Annual Computer Poker Competition.
Nonnegative dictionary learning in the exponential noise model for adaptive music signal representation
Authors: Onur Dikmen, Cédric Févotte
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper we describe a maximum likelihood likelihood approach for dictionary learning in the multiplicative exponential noise model. This model is prevalent in audio signal processing where it underlies a generative composite model of the power spectrogram. Maximum joint likelihood estimation of the dictionary and expansion coefficients leads to a nonnegative matrix factorization problem where the Itakura-Saito divergence is used. The optimality of this approach is in question because the number of parameters (which include the expansion coefficients) grows with the number of observations. In this paper we describe a variational procedure for optimization of the marginal likelihood, i.e., the likelihood of the dictionary where the activation coefficients have been integrated out (given a specific prior). We compare the output of both maximum joint likelihood estimation (i.e., standard Itakura-Saito NMF) and maximum marginal likelihood estimation (MMLE) on real and synthetical datasets. The MMLE approach is shown to embed automatic model order selection, akin to automatic relevance determination.
From Stochastic Nonlinear Integrate-and-Fire to Generalized Linear Models
Authors: Skander Mensi, Richard Naud, Wulfram Gerstner
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Variability in single neuron models is typically implemented either by a stochastic Leaky-Integrate-and-Fire model or by a model of the Generalized Linear Model (GLM) family. We use analytical and numerical methods to relate state-of-the-art models from both schools of thought. First we find the analytical expressions relating the subthreshold voltage from the Adaptive Exponential Integrate-and-Fire model (AdEx) to the Spike-Response Model with escape noise (SRM as an example of a GLM). Then we calculate numerically the link-function that provides the firing probability given a deterministic membrane potential. We find a mathematical expression for this link-function and test the ability of the GLM to predict the firing probability of a neuron receiving complex stimulation. Comparing the prediction performance of various link-functions, we find that a GLM with an exponential link-function provides an excellent approximation to the Adaptive Exponential Integrate-and-Fire with colored-noise input. These results help to understand the relationship between the different approaches to stochastic neuron models.
Generalised Coupled Tensor Factorisation
Authors: Kenan Y. Yılmaz, Ali T. Cemgil, Umut Simsekli
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We derive algorithms for generalised tensor factorisation (GTF) by building upon the well-established theory of Generalised Linear Models. Our algorithms are general in the sense that we can compute arbitrary factorisations in a message passing framework, derived for a broad class of exponential family distributions including special cases such as Tweedie's distributions corresponding to $\beta$-divergences. By bounding the step size of the Fisher Scoring iteration of the GLM, we obtain general updates for real data and multiplicative updates for non-negative data. The GTF framework is, then extended easily to address the problems when multiple observed tensors are factorised simultaneously. We illustrate our coupled factorisation approach on synthetic data as well as on a musical audio restoration problem.
Prismatic Algorithm for Discrete D.C. Programming Problem
Authors: Yoshinobu Kawahara, Takashi Washio
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), i.e., the discrete version of the D.C. programming problem. The developed algorithm is a branch-and-bound-based algorithm which responds to the structure of this problem through the relationship between submodularity and convexity. The D.S. programming problem covers a broad range of applications in machine learning because this generalizes the optimization of a wide class of set functions. We empirically investigate the performance of our algorithm, and illustrate the difference between exact and approximate solutions respectively obtained by the proposed and existing algorithms in feature selection and discriminative structure learning.
Analysis and Improvement of Policy Gradient Estimation
Authors: Tingting Zhao, Hirotaka Hachiya, Gang Niu, Masashi Sugiyama
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Policy gradient is a useful model-free reinforcement learning approach,  but it tends to suffer from instability of gradient estimates.  In this paper, we analyze and improve the stability of policy gradient methods. We first prove that the variance of gradient estimates in the PGPE(policy gradients with parameter-based exploration) method is smaller than that of the classical REINFORCE method under a mild assumption.  We then derive the optimal baseline for PGPE, which contributes to further reducing the variance.  We also theoretically show that PGPE with the optimal baseline is more preferable than REINFORCE with the optimal baseline in terms of the variance of gradient estimates.  Finally, we demonstrate the usefulness of the improved PGPE method through experiments.
On Tracking The Partition Function
Authors: Guillaume Desjardins, Yoshua Bengio, Aaron C. Courville
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Markov Random Fields (MRFs) have proven very powerful both as density estimators and feature extractors for classification. However, their use is often limited by an inability to estimate the partition function $Z$. In this paper, we exploit the gradient descent training procedure of restricted Boltzmann machines (a type of MRF) to {\bf track} the log partition function during learning. Our method relies on two distinct sources of information: (1) estimating the change $\Delta Z$ incurred by each gradient update, (2) estimating the difference in $Z$ over a small set of tempered distributions using bridge sampling. The two sources of information are then combined using an inference procedure similar to Kalman filtering.  Learning MRFs through Tempered Stochastic Maximum Likelihood, we can estimate $Z$ using no more temperatures than are required for learning. Comparing to both exact values and estimates using annealed importance sampling (AIS), we show on several datasets that our method is able to accurately track the log partition function. In contrast to AIS, our method provides this estimate at each time-step, at a computational cost similar to that required for training alone.
Portmanteau Vocabularies for Multi-Cue Image Representation
Authors: Fahad S. Khan, Joost Weijer, Andrew D. Bagdanov, Maria Vanrell
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We describe a novel technique for feature combination in the bag-of-words model of image classification. Our approach builds discriminative compound words from primitive cues learned independently from training images. Our main observation is that modeling joint-cue distributions independently is more statistically robust for typical classification problems than attempting to empirically estimate the dependent, joint-cue distribution directly. We use Information theoretic vocabulary compression to find discriminative combinations of cues and the resulting vocabulary of portmanteau words is compact, has the cue binding property, and supports individual weighting of cues in the final image representation. State-of-the-art results on both the Oxford Flower-102 and Caltech-UCSD Bird-200 datasets demonstrate the effectiveness of our technique compared to other, significantly more complex approaches to multi-cue image representation
Algorithms for Hyper-Parameter Optimization
Authors: James S. Bergstra, Rémi Bardenet, Yoshua Bengio, Balázs Kégl
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Several recent advances to the state of the art in image classification benchmarks have come from better configurations of existing techniques rather than novel approaches to feature learning. Traditionally, hyper-parameter optimization has been the job of humans because they can be very efficient in regimes where only a few trials are possible. Presently, computer clusters and GPU processors make it possible to run more trials and we show that algorithmic approaches can find better results. We present hyper-parameter optimization results on tasks of training neural networks and deep belief networks (DBNs). We optimize hyper-parameters using random search and two new greedy sequential methods based on the expected improvement criterion. Random search has been shown to be sufficiently efficient for learning neural networks for several datasets, but we show it is unreliable for training DBNs. The sequential algorithms are applied to the most difficult DBN learning problems from [Larochelle et al., 2007] and find significantly better results than the best previously reported. This work contributes novel techniques for making response surface models P (y|x) in which many elements of hyper-parameter assignment (x) are known to be irrelevant given particular values of other elements.
Finite Time Analysis of Stratified Sampling for Monte Carlo
Authors: Alexandra Carpentier, Rémi Munos
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of stratified sampling for Monte-Carlo integration. We model this problem in a multi-armed bandit setting, where the arms represent the strata, and the goal is to estimate a weighted average of the mean values of the arms. We propose a strategy that samples the arms according to an upper bound on their standard deviations and compare its estimation quality to an ideal allocation that would know the standard deviations of the arms. We provide two regret analyses: a distribution-dependent bound O(n^{-3/2}) that depends on a measure of the disparity of the arms, and a distribution-free bound O(n^{-4/3}) that does not. To the best of our knowledge, such a finite-time analysis is new for this problem.