pwc-archive/papers-with-abstracts huggingface dataset:
Structured sparse coding via lateral inhibition
Authors: Arthur D. Szlam, Karol Gregor, Yann L. Cun
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

This work describes a conceptually simple method for structured sparse coding and dictionary design. Supposing a dictionary with K atoms, we introduce a structure as a set of penalties or interactions between every pair of atoms. We describe modifications of standard sparse coding algorithms for inference in this setting, and describe experiments showing that these algorithms are efficient. We show that interesting dictionaries can be learned for interactions that encode tree structures or locally connected structures. Finally, we show that our framework allows us to learn the values of the interactions from the data, rather than having them pre-specified.
Sparse Filtering
Authors: Jiquan Ngiam, Zhenghao Chen, Sonia A. Bhaskar, Pang W. Koh, Andrew Y. Ng
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Audio Classification, Classification, General Classification

Unsupervised feature learning has been shown to be effective at learning representations that perform well on image, video and audio classification. However, many existing feature learning algorithms are hard to use and require extensive hyperparameter tuning. In this work, we present sparse filtering, a simple new algorithm which is efficient and only has one hyperparameter, the number of features to learn.  In contrast to most other feature learning methods, sparse filtering does not explicitly attempt to construct a model of the data distribution. Instead, it optimizes a simple cost function -- the sparsity of L2-normalized features -- which can easily be implemented in a few lines of MATLAB code. Sparse filtering scales gracefully to handle high-dimensional inputs, and can also be used to learn meaningful features in additional layers with greedy layer-wise stacking. We evaluate sparse filtering on natural images, object classification (STL-10), and phone classification (TIMIT), and show that our method works well on a range of different modalities.
Divide-and-Conquer Matrix Factorization
Authors: Lester W. Mackey, Michael. I. Jordan, Ameet Talwalkar
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Collaborative Filtering

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.
Im2Text: Describing Images Using 1 Million Captioned Photographs
Authors: Vicente Ordonez, Girish Kulkarni, Tamara L. Berg
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Image Captioning, Image Description

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.
Nonstandard Interpretations of Probabilistic Programs for Efficient Inference
Authors: David Wingate, Noah Goodman, Andreas Stuhlmueller, Jeffrey M. Siskind
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Probabilistic Programming

Probabilistic programming languages allow modelers to specify a stochastic    process using syntax that resembles modern programming languages.  Because    the program is in machine-readable format, a variety of techniques from    compiler design and program analysis can be used to examine the structure of    the distribution represented by the probabilistic program.  We show how    nonstandard interpretations of probabilistic programs can be used to    craft efficient inference algorithms: information about the structure of a    distribution (such as gradients or dependencies) is generated as a monad-like side    computation while executing the program.  These interpretations can be easily    coded using special-purpose objects and operator overloading.  We implement    two examples of nonstandard interpretations in two different languages, and    use them as building blocks to construct inference algorithms: automatic    differentiation, which enables gradient based methods, and provenance    tracking, which enables efficient construction of global proposals.
Collective Graphical Models
Authors: Daniel R. Sheldon, Thomas G. Dietterich
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

There are many settings in which we wish to fit a model of the behavior of individuals but where our data consist only of aggregate information (counts or low-dimensional contingency tables).  This paper introduces Collective Graphical Models---a framework for modeling and probabilistic inference that operates directly on the sufficient statistics of the individual model.  We derive a highly-efficient Gibbs sampling algorithm for sampling from the posterior distribution of the sufficient statistics conditioned on noisy aggregate observations, prove its correctness, and demonstrate its effectiveness experimentally.
Metric Learning with Multiple Kernels
Authors: Jun Wang, Huyen T. Do, Adam Woznica, Alexandros Kalousis
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Metric Learning

Metric learning has become a very active research field. The most popular representative--Mahalanobis metric learning--can be seen as learning a linear transformation and then computing the Euclidean metric in the transformed space. Since a linear transformation might not always be appropriate for a given learning problem, kernelized versions of various metric learning algorithms exist. However, the problem then becomes finding the appropriate kernel function. Multiple kernel learning addresses this limitation by learning a linear combination of a number of predefined kernels; this approach can be also readily used in the context of multiple-source learning to fuse different data sources. Surprisingly, and despite the extensive work on multiple kernel learning for SVMs, there has been no work in   the area of metric learning with multiple kernel learning. In this paper we fill this gap and present a general approach for metric learning with multiple kernel learning. Our approach can be instantiated with different metric learning algorithms provided that they satisfy some constraints. Experimental evidence suggests that our approach outperforms metric learning with an unweighted kernel combination and metric learning with cross-validation based kernel selection.
ShareBoost: Efficient multiclass learning with feature sharing
Authors: Shai Shalev-Shwartz, Yonatan Wexler, Amnon Shashua
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

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.
Active dendrites: adaptation to spike-based communication
Authors: Balazs B. Ujfalussy, Máté Lengyel
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Computational analyses of dendritic computations often assume stationary inputs to neurons, ignoring the pulsatile nature of spike-based communication between neurons and the moment-to-moment fluctuations caused by such spiking inputs. Conversely, circuit computations with spiking neurons are usually formalized without regard to the rich nonlinear nature of dendritic processing. Here we address the computational challenge faced by neurons that compute and represent analogue quantities but communicate with digital spikes, and show that reliable computation of even purely linear functions of inputs can require the interplay of strongly nonlinear subunits within the postsynaptic dendritic tree. Our theory predicts a matching of dendritic nonlinearities and synaptic weight distributions to the joint statistics of presynaptic inputs. This approach suggests normative roles for some puzzling forms of nonlinear dendritic dynamics and plasticity.
Message-Passing for Approximate MAP Inference with Latent Variables
Authors: Jiarong Jiang, Piyush Rai, Hal Daume
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We consider a general inference setting for discrete probabilistic graphical models where we seek maximum a posteriori (MAP) estimates for a subset of the random variables (max nodes), marginalizing over the rest (sum nodes). We present a hybrid message-passing algorithm to accomplish this.  The hybrid algorithm passes a mix of sum and max messages depending on the type of source node (sum or max). We derive our algorithm by showing that it falls out as the solution of a particular relaxation of a variational framework.  We further show that the Expectation Maximization algorithm can be seen as an approximation to our algorithm. Experimental results on synthetic and real-world datasets, against several baselines, demonstrate the efficacy of our proposed algorithm.
Orthogonal Matching Pursuit with Replacement
Authors: Prateek Jain, Ambuj Tewari, Inderjit S. Dhillon
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: compressed sensing

In this paper, we consider the problem of compressed sensing where the goal is to recover almost all the sparse vectors using a small number of fixed linear measurements. For this problem, we propose a novel partial hard-thresholding operator leading to a general family of iterative algorithms. While one extreme of the family yields well known hard thresholding algorithms like ITI and HTP, the other end of the spectrum leads to a novel algorithm that we call  Orthogonal Matching Pursuit with Replacement (OMPR). OMPR, like the classic greedy algorithm OMP, adds exactly one coordinate to the support at each iteration, based on the correlation with the current residual. However, unlike OMP, OMPR also removes one coordinate from the support. This simple change allows us to prove the best known guarantees for OMPR in terms of the Restricted Isometry Property (a condition on the measurement matrix). In contrast, OMP is known to have very weak performance guarantees under RIP.  We also extend OMPR using locality sensitive hashing to get OMPR-Hash, the first provably sub-linear (in dimensionality) algorithm for sparse recovery. Our  proof techniques are novel and flexible enough to also permit the tightest known analysis of popular iterative algorithms such as CoSaMP and Subspace Pursuit.  We provide experimental results on large problems providing  recovery for vectors of size up to million dimensions.  We demonstrate that for large-scale problems our proposed methods are more robust and faster than the existing  methods.
Composite Multiclass Losses
Authors: Elodie Vernet, Mark D. Reid, Robert C. Williamson
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: General Classification, Sensitivity

We consider loss functions for multiclass prediction problems. We   show when a  multiclass loss can be expressed as a ``proper   composite loss'', which is the composition of a proper loss and a link   function. We extend existing results for binary losses to   multiclass losses.  We determine the stationarity condition,   Bregman representation, order-sensitivity, existence and uniqueness   of the composite representation for multiclass losses.  We also   show that the integral representation  for binary proper losses can   not be extended to  multiclass losses. We subsume existing results   on ``classification calibration'' by relating it to properness.  We   draw conclusions concerning the design of multiclass losses.
Beating SGD: Learning SVMs in Sublinear Time
Authors: Elad Hazan, Tomer Koren, Nati Srebro
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

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!
Greedy Model Averaging
Authors: Dong Dai, Tong Zhang
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: model, Model Selection

This paper considers the problem of combining multiple models to achieve a prediction accuracy not much worse than that of the best single model for least squares regression.  It is known that if the models are mis-specified, model averaging is superior to model selection.  Specifically, let $n$ be the sample size, then the worst case regret of the former decays at the rate of $O(1/n)$   while the worst case regret of the latter decays at the rate of $O(1/\sqrt{n})$.  In the literature, the most important and widely studied model averaging method that achieves the optimal $O(1/n)$ average regret   is the exponential weighted model averaging (EWMA) algorithm. However this method suffers from several limitations.   The purpose of this paper is to present a new greedy model averaging procedure that improves EWMA.  We prove strong theoretical guarantees for the new procedure and illustrate our theoretical results with empirical examples.
Large-Scale Category Structure Aware Image Categorization
Authors: Bin Zhao, Fei Li, Eric P. Xing
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Image Categorization

Most previous research on image categorization has focused on medium-scale data sets, while large-scale image categorization with millions of images from thousands of categories remains a challenge. With the emergence of structured large-scale dataset such as the ImageNet, rich information about the conceptual relationships between images, such as a tree hierarchy among various image categories, become available. As human cognition of complex visual world benefits from underlying semantic relationships between object classes, we believe a machine learning system can and should leverage such information as well for better performance. In this paper, we employ such semantic relatedness among image categories for large-scale image categorization. Specifically, a category hierarchy is utilized to properly define loss function and select common set of features for  related categories. An efficient optimization method based on proximal approximation and accelerated parallel gradient method is introduced. Experimental results on a subset of ImageNet containing 1.2 million images from 1000 categories demonstrate the effectiveness and promise of our proposed approach.
On the accuracy of l1-filtering of signals with block-sparse structure
Authors: Fatma K. Karzan, Arkadi S. Nemirovski, Boris T. Polyak, Anatoli Juditsky
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We discuss new methods for the recovery of signals with block-sparse structure, based on l1-minimization. Our emphasis is on the efficiently computable error bounds for the recovery routines. We optimize these bounds with respect to the method parameters to construct the estimators with improved statistical properties. We justify the proposed approach with an oracle inequality which links the properties of the recovery algorithms and the best estimation performance.
Finite Time Analysis of Stratified Sampling for Monte Carlo
Authors: Alexandra Carpentier, Rémi Munos
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

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.
Monte Carlo Value Iteration with Macro-Actions
Authors: Zhan Lim, Lee Sun, David Hsu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

POMDP planning faces two major computational challenges: large state spaces and long planning horizons. The recently introduced Monte Carlo Value Iteration (MCVI) can tackle POMDPs with very large discrete state spaces or continuous state spaces, but its performance degrades when faced with long planning horizons. This paper presents Macro-MCVI, which extends MCVI by exploiting macro-actions for temporal abstraction. We provide sufficient conditions for Macro-MCVI to inherit the good theoretical properties of MCVI. Macro-MCVI does not require explicit construction of probabilistic models for macro-actions and is thus easy to apply in practice. Experiments show that Macro-MCVI substantially improves the performance of MCVI with suitable macro-actions.
Structured Learning for Cell Tracking
Authors: Xinghua Lou, Fred A. Hamprecht
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Cell Tracking, Cultural Vocal Bursts Intensity Prediction

We study the problem of learning to track a large quantity of homogeneous objects such as cell tracking in cell culture study and developmental biology. Reliable cell tracking in time-lapse microscopic image sequences is important for modern biomedical research. Existing cell tracking methods are usually kept simple and use only a small number of features to allow for manual parameter tweaking or grid search. We propose a structured learning approach that allows to learn optimum parameters automatically from a training set. This allows for the use of a richer set of features which in turn affords improved tracking compared to recently reported methods on two public benchmark sequences.
Two is better than one: distinct roles for familiarity and recollection in retrieving palimpsest memories
Authors: Cristina Savin, Peter Dayan, Máté Lengyel
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Storing a new pattern in a palimpsest memory system comes at the cost of interfering with the memory traces of previously stored items. Knowing the age of a pattern thus becomes critical for recalling it faithfully. This implies that there should be a tight coupling between estimates of age, as a form of familiarity, and the neural dynamics of recollection, something which current theories omit. Using a normative model of autoassociative memory, we show that a dual memory system, consisting of two interacting modules for familiarity and recollection, has best performance for both recollection and recognition. This finding provides a new window onto actively contentious psychological and neural aspects of recognition memory.
Algorithms and hardness results for parallel large margin learning
Authors: Phil Long, Rocco Servedio
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We study the fundamental problem of learning an unknown large-margin halfspace in the context of parallel computation.    Our main positive result is a parallel algorithm for learning a large-margin halfspace that is based on interior point methods from convex optimization and fast parallel algorithms for matrix computations. We show that this algorithm learns an unknown gamma-margin halfspace over n dimensions using poly(n,1/gamma) processors and runs in time ~O(1/gamma) + O(log n). In contrast, naive parallel algorithms that learn a gamma-margin halfspace in time that depends polylogarithmically on n have Omega(1/gamma^2) runtime dependence on gamma.     Our main negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We give an information-theoretic proof that in the original PAC framework, in which a weak learning algorithm is provided as an oracle that is called by the booster, boosting cannot be parallelized: the ability to  call the weak learner multiple times in parallel within a single boosting stage does not reduce the overall number of successive stages of boosting that are required.
Portmanteau Vocabularies for Multi-Cue Image Representation
Authors: Fahad S. Khan, Joost Weijer, Andrew D. Bagdanov, Maria Vanrell
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: General Classification, image-classification, Image Classification

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