mtybilly/Instruct2DS huggingface dataset:
ShareBoost: Efficient multiclass learning with feature sharing
Authors: Yonatan Wexler, Amnon Shashua Shai Shalev-shwartz
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Multiclass prediction is the problem of classifying an object into a    relevant target class.  We consider the problem of learning a    multiclass predictor that uses only few features, and in particular,    the number of used features should increase sub-linearly with the    number of possible classes. This implies that features should be    shared by several classes. We describe and analyze the ShareBoost    algorithm for learning a multiclass predictor that uses few shared    features. We prove that ShareBoost efficiently finds a predictor    that uses few shared features (if such a predictor exists) and that    it has a small generalization error. We also describe how to use    ShareBoost for learning a non-linear predictor that has a fast    evaluation time. In a series of experiments with natural data sets    we demonstrate the benefits of ShareBoost and evaluate its success    relatively to other state-of-the-art approaches.
Heavy-tailed Distances for Gradient Based Image Descriptors
Authors: Trevor Darrell Yangqing Jia
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many applications in computer vision measure the similarity between images or image patches based on some statistics such as oriented gradients. These are often modeled implicitly or explicitly with a Gaussian noise assumption, leading to the use of the Euclidean distance when comparing image descriptors. In this paper, we show that the statistics of gradient based image descriptors often follow a heavy-tailed distribution, which undermines any principled motivation for the use of Euclidean distances. We advocate for the use of a distance measure based on the likelihood ratio test with appropriate probabilistic models that fit the empirical data distribution. We instantiate this similarity measure with the Gamma-compound-Laplace distribution, and show significant improvement over existing distance measures in the application of SIFT feature matching, at relatively low computational cost.
An Application of Tree-Structured Expectation Propagation for Channel Decoding
Authors: Luis Salamanca, Juan Fuentes, Fernando Pérez-Cruz Pablo M. Olmos
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We show an application of a tree structure for approximate inference in graphical models using the expectation propagation algorithm. These approximations are typically used over graphs with short-range cycles. We demonstrate that these approximations also help in sparse graphs with long-range loops, as the ones used in coding theory to approach channel capacity. For asymptotically large sparse graph, the expectation propagation algorithm together with the tree structure yields a completely disconnected approximation to the graphical model but, for for finite-length practical sparse graphs, the tree structure approximation to the code graph provides accurate estimates for the marginal of each variable.
PAC-Bayesian Analysis of Contextual Bandits
Authors: Peter Auer, John S. Shawe-taylor, Ronald Ortner, François Laviolette Yevgeny Seldin
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We derive an instantaneous (per-round) data-dependent regret bound for stochastic multiarmed bandits with side information (also known as contextual bandits). The scaling of our regret bound with the number of states (contexts) $N$ goes as $\sqrt{N I_{\rho_t}(S;A)}$, where $I_{\rho_t}(S;A)$ is the mutual information between states and actions (the side information) used by the algorithm at round $t$. If the algorithm uses all the side information, the regret bound scales as $\sqrt{N \ln K}$, where $K$ is the number of actions (arms). However, if the side information $I_{\rho_t}(S;A)$ is not fully used, the regret bound is significantly tighter. In the extreme case, when $I_{\rho_t}(S;A) = 0$, the dependence on the number of states reduces from linear to logarithmic. Our analysis allows to provide the algorithm large amount of side information, let the algorithm to decide which side information is relevant for the task, and penalize the algorithm only for the side information that it is using de facto. We also present an algorithm for multiarmed bandits with side information with computational complexity that is a linear in the number of actions.
Fast and Balanced: Efficient Label Tree Learning for Large Scale Object Recognition
Authors: Sanjeev Satheesh, Alexander C. Berg, Fei Li Jia Deng
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a novel approach to efficiently learn a label tree for large scale classification with many classes. The key contribution of the approach is a technique to simultaneously determine the structure of the tree and learn the classifiers for each node in the tree. This approach also allows fine grained control over the efficiency vs accuracy trade-off in designing a label tree, leading to more balanced trees. Experiments are performed on large scale image classification with 10184 classes and 9 million images. We demonstrate significant improvements in test accuracy and efficiency with less training time and more balanced trees compared to the previous state of the art by Bengio et al.
Divide-and-Conquer Matrix Factorization
Authors: Michael I. Jordan, Ameet Talwalkar Lester W. Mackey
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This work introduces Divide-Factor-Combine (DFC), a parallel divide-and-conquer framework for noisy matrix factorization.  DFC divides a large-scale matrix factorization task into smaller subproblems, solves each subproblem in parallel using an arbitrary base matrix factorization algorithm, and combines the subproblem solutions using techniques from randomized matrix approximation.  Our experiments with collaborative filtering, video background modeling, and simulated data demonstrate the near-linear to super-linear speed-ups attainable with this approach.  Moreover, our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm.
Non-conjugate Variational Message Passing for Multinomial and Binary Regression
Authors: Tom Minka David A. Knowles
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: Girish Kulkarni, Tamara L. Berg Vicente Ordonez
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: Charles Blundell, Lloyd Elliott Yee W. Teh
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.
Uniqueness of Belief Propagation on Signed Graphs
Authors: Yusuke Watanabe
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: While loopy Belief Propagation (LBP) has been utilized in a wide variety of applications with empirical success, it comes with few theoretical guarantees. Especially, if the interactions of random variables in a graphical model are strong, the behaviors of the algorithm can be difficult to analyze due to underlying phase transitions. In this paper, we develop a novel approach to the uniqueness problem of the LBP fixed point; our new “necessary and sufficient” condition is stated in terms of graphs and signs, where the sign denotes the types (attractive/repulsive) of the interaction (i.e., compatibility function) on the edge. In all previous works, uniqueness is guaranteed only in the situations where the strength of the interactions are “sufficiently” small in certain senses. In contrast, our condition covers arbitrary strong interactions on the specified class of signed graphs. The result of this paper is based on the recent theoretical advance in the LBP algorithm; the connection with the graph zeta function.
Improving Topic Coherence with Regularized Topic Models
Authors: Edwin V. Bonilla, Wray Buntine David Newman
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: Tomer Koren, Nati Srebro Elad Hazan
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: Konrad Koerding Ian Stevenson
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: Jonathan W. Pillow Ill Memming Park
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: Wouter M. Koolen, Steven D. Rooij, Peter Grünwald Tim V. Erven
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: Fernando Torre, Joao P. Costeira, Alexandre Bernardino Ricardo S. Cabral
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: David Hunter, Padhraic Smyth, Arthur U. Asuncion Duy Q. Vu
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: Dean P. Foster, Daniel J. Hsu, Sham M. Kakade, Alexander Rakhlin Alekh Agarwal
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: Karthik Sridharan, Ambuj Tewari Alexander Rakhlin
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: Prateek Jain Purushottam Kar
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.
Maximum Margin Multi-Label Structured Prediction
Authors: Christoph H. Lampert
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study multi-label prediction for structured output spaces, a problem that occurs, for example, in object detection in images, secondary structure prediction in computational biology, and graph matching with symmetries. Conventional multi-label classification techniques are typically not applicable in this situation, because they require explicit enumeration of the label space, which is infeasible in case of structured outputs. Relying on techniques originally designed for single- label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems.  In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular a formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds.
Active Ranking using Pairwise Comparisons
Authors: Robert Nowak Kevin G. Jamieson
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: Andrew Y. Ng Adam Coates
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: Jeff G. Schneider Tzu-kuo Huang
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: Dean P. Foster, Lyle H. Ungar Paramveer Dhillon
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: Liang Sun, Jieping Ye Jun Liu
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: Joshua B. Tenenbaum, Ruslan Salakhutdinov Antonio Torralba
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: Pedro F. Felzenszwalb, David A. McAllester Ross B. Girshick
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.
Inductive reasoning about chimeric creatures
Authors: Charles Kemp
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Given one feature of a novel animal, humans readily make inferences about other features of the animal. For example, winged creatures often fly, and creatures that eat fish often live in the water. We explore the knowledge that supports these inferences and compare two approaches. The first approach proposes that humans rely on abstract representations of dependency relationships between features, and is formalized here as a graphical model.  The second approach proposes that humans rely on specific knowledge of previously encountered animals, and is formalized here as a family of exemplar models. We evaluate these models using a task where participants reason about chimeras, or animals with pairs of features that have not previously been observed to co-occur. The results support the hypothesis that humans rely on explicit representations of relationships between features.
Empirical models of spiking in neural populations
Authors: Lars Buesing, John P. Cunningham, Byron M. Yu, Krishna V. Shenoy, Maneesh Sahani Jakob H. Macke
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: Willem Waegeman, Weiwei Cheng, Eyke Hüllermeier Krzysztof J. Dembczynski
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: Viviana Petrescu, Vittorio Ferrari Bogdan Alexe
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: Anuj Srivastava, Wei Wu Sebastian A. Kurtek
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.
Multi-armed bandits on implicit metric spaces
Authors: Aleksandrs Slivkins
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The multi-armed bandit (MAB) setting is a useful abstraction of many online learning tasks which focuses on the trade-off between exploration and exploitation. In this setting, an online algorithm has a fixed set of alternatives ("arms"), and in each round it selects one arm and then observes the corresponding reward. While the case of small number of arms is by now well-understood, a lot of recent work has focused on multi-armed bandits with (infinitely) many arms, where one needs to assume extra structure in order to make the problem tractable. In particular, in the Lipschitz MAB problem there is an underlying similarity metric space, known to the algorithm, such that any two arms that are close in this metric space have similar payoffs.  In this paper we consider the more realistic scenario in which the metric space is implicit -- it is defined by the available structure but not revealed to the algorithm directly. Specifically, we assume that an algorithm is given a tree-based classification of arms. For any given problem instance such a classification implicitly defines a similarity metric space, but the numerical similarity information is not available to the algorithm. We provide an algorithm for this setting, whose performance guarantees (almost) match the best known guarantees for the corresponding instance of the Lipschitz MAB problem.
Predicting response time and error rates in visual search
Authors: Vidhya Navalpakkam, Pietro Perona Bo Chen
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: Walter Senn, Jean-pascal Pfister Johanni Brea
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.
Convergent Fitted Value Iteration with Linear Function Approximation
Authors: Daniel J. Lizotte
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Fitted value iteration (FVI) with ordinary least squares regression is known to diverge. We present a new method, "Expansion-Constrained Ordinary Least Squares" (ECOLS), that produces a linear approximation but also guarantees convergence when used with FVI. To ensure convergence, we constrain the least squares regression operator to be a non-expansion in the infinity-norm. We show that the space of function approximators that satisfy this constraint is more rich than the space of "averagers," we prove a minimax property of the ECOLS residual error, and we give an efficient algorithm for computing the coefficients of ECOLS based on constraint generation. We illustrate the algorithmic convergence of FVI with ECOLS in a suite of experiments, and discuss its properties.
Learning in Hilbert vs. Banach Spaces: A Measure Embedding Viewpoint
Authors: Gert R. Lanckriet, Bharath K. Sriperumbudur Kenji Fukumizu
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: Thomas Gärtner Olana Missura
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.
Optimistic Optimization of a Deterministic Function without the Knowledge of its Smoothness
Authors: Rémi Munos
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider a global optimization problem of a deterministic function f in a semimetric space, given a finite budget of n evaluations. The function f is assumed to be locally smooth (around one of its global maxima) with respect to a semi-metric . We describe two algorithms based on optimistic exploration that use a hierarchical partitioning of the space at all scales. A first contribution is an algorithm, DOO, that requires the knowledge of . We report a finite-sample performance bound in terms of a measure of the quantity of near-optimal states. We then define a second algorithm, SOO, which does not require the knowledge of the semimetric  under which f is smooth, and whose performance is almost as good as DOO optimally-fitted.
Robust Multi-Class Gaussian Process Classification
Authors: Jose M. Hernández-lobato, Pierre Dupont Daniel Hernández-lobato
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.