pwc-archive/papers-with-abstracts huggingface dataset:
Searching for objects driven by context
Authors: Bogdan Alexe, Nicolas Heess, Yee W. Teh, Vittorio Ferrari
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The dominant visual search paradigm for object class detection is sliding windows. Although simple and effective, it is also wasteful, unnatural and rigidly hardwired. We propose strategies to search for objects which intelligently explore the space of windows by making sequential observations at locations decided based on previous observations. Our strategies adapt to the class being searched and to the content of a particular test image. Their driving force is exploiting context as the statistical relation between the appearance of a window and its location relative to the object, as observed in the training set. In addition to being more elegant than sliding windows, we demonstrate experimentally on the PASCAL VOC 2010 dataset that our strategies evaluate two orders of magnitude fewer windows while at the same time achieving higher detection accuracy.
Timely Object Recognition
Authors: Sergey Karayev, Tobias Baumgartner, Mario Fritz, Trevor Darrell
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Object, object-detection, Object Detection, Object Recognition, Reinforcement Learning

In a large visual multi-class detection framework, the timeliness of results can be crucial. Our method for timely multi-class detection aims to give the best possible performance at any single point after a start time; it is terminated at a deadline time. Toward this goal, we formulate a dynamic, closed-loop policy that infers the contents of the image in order to decide which detector to deploy next. In contrast to previous work, our method significantly diverges from the predominant greedy strategies, and is able to learn to take actions with deferred values. We evaluate our method with a novel timeliness measure, computed as the area under an Average Precision vs. Time curve. Experiments are conducted on the eminent PASCAL VOC object detection dataset. If execution is stopped when only half the detectors have been run, our method obtains $66\%$ better AP than a random ordering, and $14\%$ better performance than an intelligent baseline. On the timeliness measure, our method obtains at least $11\%$ better performance. Our code, to be made available upon publication, is easily extensible as it treats detectors and classifiers as black boxes and learns from execution traces using reinforcement learning.
Nonparanormal Belief Propagation (NPNBP)
Authors: Gal Elidan, Cobi Cario
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The empirical success of the belief propagation approximate inference algorithm has inspired numerous theoretical and algorithmic advances. Yet, for continuous non-Gaussian domains performing belief propagation remains a challenging task: recent innovations such as nonparametric or kernel belief propagation, while useful, come with a substantial computational cost and offer little theoretical guarantees, even for tree structured models.  In this work we present Nonparanormal BP  for performing efficient inference on distributions parameterized by  a Gaussian copulas network and any univariate marginals. For  tree structured networks, our approach is guaranteed to be exact for  this powerful class of non-Gaussian models. Importantly, the method  is as efficient as standard Gaussian BP, and its convergence properties do not depend on the complexity of the univariate marginals, even when a nonparametric representation is used.
Deep Representations and Codes for Image Auto-Annotation
Authors: Ryan Kiros, Csaba Szepesvári
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: feature selection, TAG

The task of assigning a set of relevant tags to an image is challenging due to the size and variability of tag vocabularies. Consequently, most existing algorithms focus on tag assignment and fix an often large number of hand-crafted features to describe image characteristics. In this paper we introduce a hierarchical model for learning representations of full sized color images from the pixel level, removing the need for engineered feature representations and subsequent feature selection. We benchmark our model on the STL-10 recognition dataset, achieving state-of-the-art performance. When our features are combined with TagProp (Guillaumin et al.), we outperform or compete with existing annotation approaches that use over a dozen distinct image descriptors. Furthermore, using 256-bit codes and Hamming distance for training TagProp, we exchange only a small reduction in performance for efficient storage and fast comparisons. In our experiments, using deeper architectures always outperform shallow ones.
A Spectral Algorithm for Latent Dirichlet Allocation
Authors: Anima Anandkumar, Dean P. Foster, Daniel J. Hsu, Sham M. Kakade, Yi-Kai Liu
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, Topic Models

Topic modeling is a generalization of clustering that posits that observations (words in a document) are generated by \emph{multiple} latent factors (topics), as opposed to just one. This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic-word distributions when only words are observed, and the topics are hidden.  This work provides a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of topic models, including Latent Dirichlet Allocation (LDA). For LDA, the procedure correctly recovers both the topic-word distributions and the parameters of the Dirichlet prior over the topic mixtures, using only trigram statistics (\emph{i.e.}, third order moments, which may be estimated with documents containing just three words). The method, called Excess Correlation Analysis, is based on a spectral decomposition of low-order moments via two singular value decompositions (SVDs). Moreover, the algorithm is scalable, since the SVDs are carried out only on $k \times k$ matrices, where $k$ is the number of latent factors (topics) and is typically much smaller than the dimension of the observation (word) space.
Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs
Authors: Aharon Birnbaum, Shai S. Shwartz
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: PAC learning

Given $\alpha,\epsilon$, we study the time complexity   required to improperly learn a halfspace with misclassification   error rate of at most $(1+\alpha)\,L^*_\gamma + \epsilon$, where   $L^*_\gamma$ is the optimal $\gamma$-margin error rate. For $\alpha   = 1/\gamma$, polynomial time and sample complexity is achievable   using the hinge-loss. For $\alpha = 0$, \cite{ShalevShSr11} showed   that $\poly(1/\gamma)$ time is impossible, while learning is   possible in time $\exp(\tilde{O}(1/\gamma))$.  An immediate   question, which this paper tackles, is what is achievable if $\alpha   \in (0,1/\gamma)$.  We derive positive results interpolating between   the polynomial time for $\alpha = 1/\gamma$ and the exponential   time for $\alpha=0$. In particular, we show that there are cases in   which $\alpha = o(1/\gamma)$ but the problem is still solvable in   polynomial time. Our results naturally extend to the adversarial   online learning model and to the PAC learning with malicious noise   model.
Matrix reconstruction with the local max norm
Authors: Rina Foygel, Nathan Srebro, Ruslan R. Salakhutdinov
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We introduce a new family of matrix norms, the ''local max'' norms, generalizing existing methods such as the max norm, the trace norm (nuclear norm), and the weighted or smoothed weighted trace norms, which have been extensively used in the literature as regularizers for matrix reconstruction problems. We show that this new family can be used to interpolate between the (weighted or unweighted) trace norm and the more conservative max norm. We test this interpolation on simulated data and on the large-scale Netflix and MovieLens ratings data, and find improved accuracy relative to the existing matrix norms. We also provide theoretical results showing learning guarantees for some of the new norms.
Analog readout for optical reservoir computers
Authors: Anteo Smerieri, François Duport, Yvon Paquot, Benjamin Schrauwen, Marc Haelterman, Serge Massar
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Reservoir computing is a new, powerful and flexible machine learning technique that is easily implemented in hardware. Recently, by using a time-multiplexed architecture, hardware reservoir computers have reached performance comparable to digital implementations. Operating speeds allowing for real time information operation have been reached using optoelectronic systems. At present the main performance bottleneck is the readout layer which uses slow, digital postprocessing. We have designed an analog readout suitable for time-multiplexed optoelectronic reservoir computers, capable of working in real time. The readout has been built and tested experimentally on a standard benchmark task. Its performance is better than non-reservoir methods, with ample room for further improvement. The present work thereby overcomes one of the major limitations for the future development of hardware reservoir computers.
Accuracy at the Top
Authors: Stephen Boyd, Corinna Cortes, Mehryar Mohri, Ana Radovanovic
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification

We introduce a new notion of classification accuracy based on the top $\tau$-quantile values of a scoring function, a relevant criterion in a number of problems arising for search engines. We define an algorithm optimizing a convex surrogate of the corresponding loss, and show how its solution can be obtained by solving several convex optimization problems. We also present margin-based guarantees for this algorithm based on the $\tau$-quantile of the functions in the hypothesis set. Finally, we report the results of several experiments evaluating the performance of our algorithm. In a comparison in a bipartite setting with several algorithms seeking high precision at the top, our algorithm achieves a better performance in precision at the top.
Minimizing Sparse High-Order Energies by Submodular Vertex-Cover
Authors: Andrew Delong, Olga Veksler, Anton Osokin, Yuri Boykov
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, Vocal Bursts Intensity Prediction

Inference on high-order graphical models has become increasingly important in recent years.  We consider energies with simple 'sparse' high-order potentials.  Previous work in this area uses either specialized message-passing  or transforms each high-order potential to the pairwise case. We take a fundamentally different approach, transforming the entire original problem into a comparatively small instance of a submodular vertex-cover problem. These vertex-cover instances can then be attacked by standard pairwise methods, where they run much faster (4--15 times) and are often more effective than on the original problem. We evaluate our approach on synthetic data, and we show that our algorithm can be useful in a fast hierarchical clustering and model estimation framework.
Perfect Dimensionality Recovery by Variational Bayesian PCA
Authors: Shinichi Nakajima, Ryota Tomioka, Masashi Sugiyama, S. D. Babacan
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The variational Bayesian (VB) approach is one of the best tractable approximations to the Bayesian estimation, and it was demonstrated to perform well in many applications. However, its good performance was not fully understood theoretically. For example, VB sometimes produces a sparse solution, which is regarded as a practical advantage of VB, but such sparsity is hardly observed in the rigorous Bayesian estimation. In this paper, we focus on probabilistic PCA and give more theoretical insight into the empirical success of VB. More specifically, for the situation where the noise variance is unknown, we derive a sufficient condition for perfect recovery of the true PCA dimensionality in the large-scale limit when the size of an observed matrix goes to infinity. In our analysis, we obtain bounds for a noise variance estimator and simple closed-form solutions for other parameters, which themselves are actually very useful for better implementation of VB-PCA.
Mirror Descent Meets Fixed Share (and feels no regret)
Authors: Nicolò Cesa-Bianchi, Pierre Gaillard, Gabor Lugosi, Gilles Stoltz
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets. Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters.
Near-optimal Differentially Private Principal Components
Authors: Kamalika Chaudhuri, Anand Sarwate, Kaushik Sinha
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Principal components analysis (PCA) is a standard tool for identifying good low-dimensional approximations to data sets in high dimension.  Many current data sets of interest contain private or sensitive information about individuals.  Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs.  Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs.  In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output.  We demonstrate that on real data, there this a large performance gap between the existing methods and our method.  We show that the sample complexity for the two procedures differs in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling.
Inverse Reinforcement Learning through Structured Classification
Authors: Edouard Klein, Matthieu Geist, Bilal Piot, Olivier Pietquin
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, General Classification, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This paper adresses the inverse reinforcement learning (IRL) problem, that is inferring a reward for which a demonstrated expert behavior is optimal. We introduce a new algorithm, SCIRL, whose principle is to use the so-called feature expectation of the expert as the parameterization of the score function of a multi-class classifier. This approach produces a reward function for which the expert policy is provably near-optimal. Contrary to most of existing IRL algorithms, SCIRL does not require solving the direct RL problem. Moreover, with an appropriate heuristic, it can succeed with only trajectories sampled according to the expert behavior. This is illustrated on a car driving simulator.
Augmented-SVM: Automatic space partitioning for combining multiple non-linear dynamics
Authors: Ashwini Shukla, Aude Billard
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Motion Generation

Non-linear dynamical systems (DS) have been used extensively for building generative models of human behavior. Its applications range from modeling brain dynamics  to encoding motor commands. Many schemes have been proposed for encoding robot motions using dynamical systems with a single attractor placed at a predefined target in state space. Although these enable the robots to react against sudden perturbations without any re-planning, the motions are always directed towards a single target. In this work, we focus on combining several such DS with distinct attractors, resulting in a multi-stable DS. We show its applicability in reach-to-grasp tasks where the attractors represent several grasping points on the target object. While exploiting multiple attractors provides more flexibility in recovering from unseen perturbations, it also increases the complexity of the underlying learning problem. Here we present the Augmented-SVM (A-SVM) model which inherits region partitioning ability of the well known SVM classifier and is augmented with novel constraints derived from the individual DS. The new constraints modify the original SVM dual whose optimal solution then results in a new class of support vectors (SV). These new SV ensure that the resulting multi-stable DS incurs minimum deviation from the original dynamics and is stable at each of the attractors within a finite region of attraction. We show, via implementations on a simulated 10 degrees of freedom mobile robotic platform, that the model is capable of real-time motion generation and is able to adapt on-the-fly to perturbations.
Dimensionality Dependent PAC-Bayes Margin Bound
Authors: Chi Jin, Li-Wei Wang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Model Selection

Margin is one of the most important concepts in machine learning. Previous margin bounds, both for SVM and for boosting, are dimensionality independent. A major advantage of this dimensionality independency is that it can explain the excellent performance of SVM whose feature spaces are often of high or infinite dimension. In this paper we address the problem whether such dimensionality independency is intrinsic for the margin bounds. We prove a dimensionality dependent PAC-Bayes margin bound. The bound is monotone increasing with respect to the dimension when keeping all other factors fixed. We show that our bound is strictly sharper than a previously well-known PAC-Bayes margin bound if the feature space is of finite dimension; and the two bounds tend to be equivalent as the dimension goes to infinity. In addition, we show that the VC bound for linear classifiers can be recovered from our bound under mild conditions. We conduct extensive experiments on benchmark datasets and find that the new bound is useful for model selection and is significantly sharper than the dimensionality independent PAC-Bayes margin bound as well as the VC bound for linear classifiers.
Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs
Authors: Anima Anandkumar, Ragupathyraj Valluvan
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Model Selection

Graphical model selection refers to the problem of estimating the unknown graph structure given observations at the nodes in the model. We consider a challenging instance of this problem when some of the nodes are latent or hidden.  We  characterize  conditions for tractable graph estimation and develop efficient methods with provable guarantees. We consider the class of Ising models Markov on  locally tree-like graphs, which are in the regime of correlation decay. We  propose an efficient method for graph estimation, and establish its structural consistency when the number of samples $n$ scales as $n = \Omega(\theta_{\min}^{-\delta \eta(\eta+1)-2}\log p)$, where $\theta_{\min}$ is the minimum edge potential, $\delta$ is the depth (i.e., distance from a hidden node to the nearest  observed nodes), and $\eta$ is a parameter which depends on the minimum and maximum node and edge potentials in the Ising model. The proposed method is practical to implement and provides  flexibility to control  the number of latent variables and the cycle lengths in the output graph.  We also present necessary conditions for graph estimation by any method and show that our method nearly matches the lower bound  on sample requirements.
Learning Mixtures of Tree Graphical Models
Authors: Anima Anandkumar, Daniel J. Hsu, Furong Huang, Sham M. Kakade
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We consider  unsupervised estimation of mixtures of discrete graphical models, where the class variable   is hidden and each mixture component  can have a potentially different Markov graph structure and parameters over the observed variables. We propose a novel method for estimating the mixture components with  provable guarantees.   Our output is   a tree-mixture model which serves as a good approximation to the underlying graphical model mixture. The   sample and computational requirements for our method scale as $\poly(p,  r)$,   for an $r$-component mixture of $p$-variate graphical models, for a wide class of models which includes tree mixtures and mixtures over bounded degree graphs.
Hamming Distance Metric Learning
Authors: Mohammad Norouzi, David J. Fleet, Ruslan R. Salakhutdinov
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification, Metric Learning, Retrieval, Semantic Similarity, Semantic Textual Similarity, Triplet

Motivated by large-scale multimedia applications we propose to learn mappings from high-dimensional data to binary codes that preserve semantic similarity. Binary codes are well suited to large-scale applications as they are storage efficient and permit exact sub-linear kNN search. The framework is applicable to broad families of mappings, and uses a flexible form of triplet ranking loss. We overcome discontinuous optimization of the discrete mappings by minimizing a piecewise-smooth upper bound on empirical loss, inspired by latent structural SVMs.  We develop a new loss-augmented inference algorithm that is quadratic in the code length.  We show strong retrieval performance on CIFAR-10 and MNIST, with promising classification results using no more than kNN on the binary codes.
Spiking and saturating dendrites differentially expand single neuron computation capacity
Authors: Romain Cazé, Mark Humphries, Boris S. Gutkin
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The integration of excitatory inputs in dendrites is non-linear: multiple excitatory inputs can produce a local depolarization departing from the arithmetic sum of each input's response taken separately. If this depolarization is bigger than the arithmetic sum, the dendrite is spiking; if the depolarization is smaller, the dendrite is saturating. Decomposing a dendritic tree into independent dendritic spiking units greatly extends its computational capacity, as the neuron then maps onto a two layer neural network, enabling it to compute linearly non-separable Boolean functions (lnBFs). How can these lnBFs be implemented by dendritic architectures in practise? And can saturating dendrites equally expand computational capacity? To adress these questions we use a binary neuron model and Boolean algebra. First, we confirm that spiking dendrites enable a neuron to compute lnBFs using an architecture based on the disjunctive normal form (DNF). Second, we prove that saturating dendrites as well as spiking dendrites also enable a neuron to compute lnBFs using an architecture based on the conjunctive normal form (CNF). Contrary to the DNF-based architecture, a CNF-based architecture leads to a dendritic unit tuning that does not imply the neuron tuning, as has been observed experimentally. Third, we show that one cannot use a DNF-based architecture with saturating dendrites. Consequently, we show that an important family of lnBFs implemented with a CNF-architecture can require an exponential number of saturating dendritic units, whereas the same family implemented with either a DNF-architecture or a CNF-architecture always require a linear number of spiking dendritic unit. This minimization could explain why a neuron spends energetic resources to make its dendrites spike.