pwc-archive/papers-with-abstracts huggingface dataset:
Clustering by Nonnegative Matrix Factorization Using Graph Random Walk
Authors: Zhirong Yang, Tele Hao, Onur Dikmen, Xi Chen, Erkki Oja
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering

Nonnegative Matrix Factorization (NMF) is a promising relaxation technique for clustering analysis.  However, conventional NMF methods that directly approximate the pairwise similarities using the least square error often yield mediocre performance for data in curved manifolds because they can capture only the immediate similarities between data samples.  Here we propose a new NMF clustering method which replaces the approximated matrix with its smoothed version using random walk.  Our method can thus accommodate farther relationships between data samples.  Furthermore, we introduce a novel regularization in the proposed objective function in order to improve over spectral clustering.  The new learning objective is optimized by a multiplicative Majorization-Minimization algorithm with a scalable implementation for learning the factorizing matrix.  Extensive experimental results on real-world datasets show that our method has strong performance in terms of cluster purity.
Delay Compensation with Dynamical Synapses
Authors: Chi Fung, K. Wong, Si Wu
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Time delay is pervasive in neural information processing. To achieve real-time tracking, it is critical to compensate the transmission and processing delays in a neural system. In the present study we show that dynamical synapses with short-term depression can enhance the mobility of a continuous attractor network to the extent that the system tracks time-varying stimuli in a timely manner. The state of the network can either track the instantaneous position of a moving stimulus perfectly (with zero-lag) or lead it with an effectively constant time, in agreement with experiments on the head-direction systems in rodents. The parameter regions for delayed, perfect and anticipative tracking correspond to network states that are static, ready-to-move and spontaneously moving, respectively, demonstrating the strong correlation between tracking performance and the intrinsic dynamics of the network. We also find that when the speed of the stimulus coincides with the natural speed of the network state, the delay becomes effectively independent of the stimulus amplitude.
ImageNet Classification with Deep Convolutional Neural Networks
Authors: Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification, GPU, Graph Classification, Image Classification, Object Recognition

We trained a large, deep convolutional neural network to classify the 1.3 million high-resolution images in the LSVRC-2010 ImageNet training set into the 1000 different classes. On the test data, we achieved top-1 and top-5 error rates of 39.7\% and 18.9\% which is considerably better than the previous state-of-the-art results. The neural network, which has 60 million parameters and 500,000 neurons, consists of five convolutional layers, some of which are followed by max-pooling layers, and two globally connected layers with a final 1000-way softmax. To make training faster, we used non-saturating neurons and a very efficient GPU implementation of convolutional nets. To reduce overfitting in the globally connected layers we employed a new regularization method that proved to be very effective.
Recognizing Activities by Attribute Dynamics
Authors: Weixin Li, Nuno Vasconcelos
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Action Recognition, Attribute, Temporal Action Localization

In this work, we consider the problem of modeling the dynamic structure of human activities in  the attributes space. A video sequence is first represented in a semantic feature space, where each feature encodes the probability of  occurrence of an activity attribute at a given time. A generative model,  denoted the binary dynamic system (BDS), is proposed to learn both the distribution and dynamics of different activities in this  space. The BDS is a non-linear dynamic system, which extends both the binary  principal component analysis (PCA) and classical linear dynamic systems (LDS), by combining binary observation variables with a hidden Gauss-Markov state  process. In this way, it integrates the representation power of semantic  modeling with the ability of dynamic systems to capture the temporal structure of time-varying processes. An algorithm for learning BDS  parameters, inspired by a popular LDS  learning method from dynamic textures, is proposed. A similarity measure between BDSs, which generalizes  the Binet-Cauchy kernel for LDS, is then introduced and used to design  activity classifiers. The proposed method is shown to outperform similar classifiers  derived from the kernel dynamic system (KDS) and state-of-the-art approaches for  dynamics-based or attribute-based action recognition.
Compressive Sensing MRI with Wavelet Tree Sparsity
Authors: Chen Chen, Junzhou Huang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Compressive Sensing

In Compressive Sensing Magnetic Resonance Imaging (CS-MRI), one can reconstruct a MR image with good quality from only a small number of measurements. This can significantly reduce MR scanning time. According to structured sparsity theory, the measurements can be further reduced to $\mathcal{O}(K+\log n)$ for tree-sparse data instead of $\mathcal{O}(K+K\log n)$ for standard $K$-sparse data with length $n$. However, few of existing algorithms has utilized this for CS-MRI, while most of them use Total Variation and wavelet sparse regularization. On the other side, some algorithms have been proposed for tree sparsity regularization, but few of them has validated   the benefit of tree structure in CS-MRI. In this paper, we propose a fast convex optimization algorithm to improve CS-MRI.  Wavelet sparsity, gradient sparsity and tree sparsity are all considered in our model for real MR images. The original complex problem is decomposed to three simpler subproblems then each of the subproblems can be efficiently solved with an iterative scheme. Numerous experiments have been conducted and show that the proposed algorithm outperforms the state-of-the-art CS-MRI algorithms, and gain better reconstructions results on real MR images than general tree based solvers or algorithms.
Training sparse natural image models with a fast Gibbs sampler of an extended state space
Authors: Lucas Theis, Jascha Sohl-Dickstein, Matthias Bethge
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We present a new learning strategy based on an efficient blocked Gibbs sampler for sparse overcomplete linear models. Particular emphasis is placed on statistical image modeling, where overcomplete models have played an important role in discovering sparse representations. Our Gibbs sampler is faster than general purpose sampling schemes while also requiring no tuning as it is free of parameters. Using the Gibbs sampler and a persistent variant of expectation maximization, we are able to extract highly sparse distributions over latent sources from data. When applied to natural images, our algorithm learns source distributions which resemble spike-and-slab distributions. We evaluate the likelihood and quantitatively compare the performance of the overcomplete linear model to its complete counterpart as well as a product of experts model, which represents another overcomplete generalization of the complete linear model. In contrast to previous claims, we find that overcomplete representations lead to significant improvements, but that the overcomplete linear model still underperforms other models.
A Bayesian Approach for Policy Learning from Trajectory Preference Queries
Authors: Aaron Wilson, Alan Fern, Prasad Tadepalli
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We consider the problem of learning control policies via trajectory preference queries to an expert. In particular, the learning agent can present an expert with short runs of a pair of policies originating from the same state and the expert then indicates the preferred trajectory. The agent's goal is to elicit a latent target policy from the expert with as few queries as possible. To tackle this problem we propose a novel Bayesian model of the querying process and introduce two methods that exploit this model to actively select expert queries. Experimental results on four benchmark problems indicate that our model can effectively learn policies from trajectory preference queries and that active query selection can be substantially more efficient than random selection.
GenDeR: A Generic Diversified Ranking Algorithm
Authors: Jingrui He, Hanghang Tong, Qiaozhu Mei, Boleslaw Szymanski
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Information Retrieval, Retrieval

Diversified ranking is a fundamental task in machine learning. It is broadly applicable in many real world problems, e.g., information retrieval, team assembling, product search, etc. In this paper, we consider a generic setting where we aim to diversify the top-k ranking list based on an arbitrary relevance function and an arbitrary similarity function among all the examples. We formulate it as an optimization problem and show that in general it is NP-hard. Then, we show that for a large volume of the parameter space, the proposed objective function enjoys the diminishing returns property, which enables us to design a scalable, greedy algorithm to find the near-optimal solution. Experimental results on real data sets demonstrate the effectiveness of the proposed algorithm.
On Multilabel Classification and Ranking with Partial Feedback
Authors: Claudio Gentile, Francesco Orabona
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, General Classification

We present a novel multilabel/ranking algorithm working in partial information settings. The algorithm is based on 2nd-order descent methods, and relies on upper-confidence bounds to trade-off exploration and exploitation.  We analyze this algorithm in a partial adversarial setting, where covariates can be adversarial, but multilabel probabilities are ruled by (generalized) linear models. We show $O(T^{1/2}\log T)$ regret bounds, which improve in several ways on the existing results. We test the effectiveness of our upper-confidence scheme by contrasting against full-information baselines on real-world multilabel datasets, often obtaining comparable performance.
The Lovász ϑ function, SVMs and finding large dense subgraphs
Authors: Vinay Jethava, Anders Martinsson, Chiranjib Bhattacharyya, Devdatt Dubhashi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Combinatorial Optimization

The Lovasz $\theta$ function of a graph, is a fundamental tool in combinatorial optimization and approximation algorithms.  Computing $\theta$ involves solving a SDP  and is extremely expensive even for moderately sized graphs.  In this paper we establish that the Lovasz $\theta$ function is equivalent to  a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities  bridging graph theoretic algorithms and machine learning.   We show that there exist graphs, which we call $SVM-\theta$ graphs, on which the Lovasz $\theta$ function can be approximated well by a one-class  SVM.    This leads to a novel use of SVM techniques to solve algorithmic problems in large graphs e.g. identifying a planted clique  of size $\Theta({\sqrt{n}})$ in a random graph $G(n,\frac{1}{2})$. A classic approach for this problem involves computing  the $\theta$ function, however it is not scalable due to SDP computation. We show that the random graph with a planted clique is an example of $SVM-\theta$ graph, and as a consequence a SVM based approach  easily identifies the clique in large graphs and is competitive with the  state-of-the-art.    Further, we introduce  the notion of a ''common orthogonal labeling'' which extends the notion  of a ''orthogonal labelling of a single  graph (used in defining the $\theta$ function)  to multiple graphs.  The problem of finding the optimal common orthogonal labelling is cast as a  Multiple Kernel Learning problem and is used to identify a large common dense region in multiple graphs.  The proposed algorithm achieves an order of magnitude scalability compared to the state of the art.
Multi-Task Averaging
Authors: Sergey Feldman, Maya Gupta, Bela Frigyik
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Multi-Task Learning

We present a multi-task learning approach to jointly estimate the means of multiple independent data sets. The proposed multi-task averaging (MTA) algorithm results in a convex combination of the single-task averages. We derive the optimal amount of regularization, and show that it can be effectively estimated. Simulations and real data experiments demonstrate that MTA  both maximum likelihood and James-Stein estimators, and that our approach to estimating the amount of regularization rivals cross-validation in performance but is more computationally efficient.
Unsupervised Structure Discovery for Semantic Analysis of Audio
Authors: Sourish Chaudhuri, Bhiksha Raj
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Audio Classification, General Classification, Retrieval

Approaches to audio classification and retrieval tasks largely rely on detection-based discriminative models. We submit that such models make a simplistic assumption in mapping acoustics directly to semantics, whereas the actual process is likely more complex. We present a generative model that maps acoustics in a hierarchical manner to increasingly higher-level semantics. Our model has 2 layers with the first being generic sound units with no clear semantic associations, while the second layer attempts to find patterns over the generic sound units. We evaluate our model on a large-scale retrieval task from TRECVID 2011, and report significant improvements over standard baselines.
A Marginalized Particle Gaussian Process Regression
Authors: Yali Wang, Brahim Chaib-Draa
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Computational Efficiency, regression

We present a novel marginalized particle Gaussian process (MPGP) regression, which provides a fast, accurate online Bayesian filtering framework to model the latent function. Using a state space model established by the data construction procedure, our MPGP recursively filters out the estimation of hidden function values by a Gaussian mixture. Meanwhile, it provides a new online method for training hyperparameters with a number of weighted particles. We demonstrate the estimated performance of our MPGP on both simulated and real large data sets. The results show that our MPGP is a robust estimation algorithm with high computational efficiency, which outperforms other state-of-art sparse GP methods.
Angular Quantization-based Binary Codes for Fast Similarity Search
Authors: Yunchao Gong, Sanjiv Kumar, Vishal Verma, Svetlana Lazebnik
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Quantization, Retrieval, Text Retrieval

This paper focuses on the problem of learning binary embeddings for efficient retrieval of high-dimensional non-negative data. Such data typically arises in a large number of vision and text applications where counts or frequencies are used as features.  Also, cosine distance is commonly used as a measure of dissimilarity between such vectors. In this work, we introduce a novel spherical quantization scheme to generate binary embedding of such data and analyze its properties. The number of quantization landmarks in this scheme grows exponentially with data dimensionality resulting in low-distortion quantization.  We propose a very efficient method for computing the binary embedding using such large number of landmarks. Further, a linear transformation is learned to minimize the quantization error by adapting the method to the input data resulting in improved embedding.  Experiments on image and text retrieval applications show superior performance of the proposed method over other existing state-of-the-art methods.
Optimal kernel choice for large-scale two-sample tests
Authors: Arthur Gretton, Dino Sejdinovic, Heiko Strathmann, Sivaraman Balakrishnan, Massimiliano Pontil, Kenji Fukumizu, Bharath K. Sriperumbudur
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Vocal Bursts Valence Prediction

Abstract Given samples from distributions $p$ and $q$, a two-sample test determines whether to reject the null hypothesis that $p=q$, based on the value of a test statistic measuring the distance between the samples. One choice of test statistic is the maximum mean discrepancy (MMD), which is a distance between embeddings of the probability distributions in a reproducing kernel Hilbert space. The kernel used in obtaining these embeddings is thus critical in ensuring the test has high power, and correctly distinguishes unlike distributions with high probability. A means of parameter selection for the two-sample test based on the MMD is proposed. For a given test level (an upper bound on the probability of making a Type I error), the kernel is chosen so as to maximize the test power, and minimize the probability of making a Type II error. The test statistic, test threshold, and optimization over the kernel parameters are obtained with cost linear in the sample size. These properties make the kernel selection and test procedures suited to data streams, where the observations cannot all be stored in memory. In experiments, the new kernel selection approach yields a more powerful test than earlier kernel selection heuristics.
Large Scale Distributed Deep Networks
Authors: Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc'Aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc V. Le, Andrew Y. Ng
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: CPU, Object Recognition, speech-recognition, Speech Recognition

Recent work in unsupervised feature learning and deep learning has shown that  being able to train large models can dramatically improve performance.  In this  paper, we consider the problem of training a deep network with billions of  parameters using tens of thousands of CPU cores.  We have developed a  software framework called DistBelief that can utilize computing clusters  with thousands of machines to train large models.  Within this framework, we  have developed two algorithms for large-scale distributed training: (i) Downpour  SGD, an asynchronous stochastic gradient descent procedure supporting a  large number of model replicas, and (ii) Sandblaster, a framework that supports  for a variety of distributed batch optimization procedures, including a distributed  implementation of L-BFGS.  Downpour SGD and Sandblaster L-BFGS both  increase the scale and speed of deep network training.  We have successfully  used our system to train a deep network 100x larger than previously reported in  the literature, and achieves state-of-the-art performance on ImageNet, a visual  object recognition task with 16 million images and 21k categories.  We show that  these same techniques dramatically accelerate the training of a more modestly  sized deep network for a commercial speech recognition service. Although we  focus on and report performance of these methods as applied to training large  neural networks, the underlying algorithms are applicable to any gradient-based  machine learning algorithm.
Statistical Consistency of Ranking Methods in A Rank-Differentiable Probability Space
Authors: Yanyan Lan, Jiafeng Guo, Xueqi Cheng, Tie-Yan Liu
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

This paper is concerned with the statistical consistency of ranking methods. Recently, it was proven that many commonly used pairwise ranking methods are inconsistent with the weighted pairwise disagreement loss (WPDL), which can be viewed as the true loss of ranking, even in a low-noise setting. This result is interesting but also surprising, given that the pairwise ranking methods have been shown very effective in practice. In this paper, we argue that the aforementioned result might not be conclusive, depending on what kind of assumptions are used. We give a new assumption that the labels of objects to rank lie in a rank-differentiable probability space (RDPS), and prove that the pairwise ranking methods become consistent with WPDL under this assumption. What is especially inspiring is that RDPS is actually not stronger than but similar to the low-noise setting. Our studies provide theoretical justifications of some empirical findings on pairwise ranking methods that are unexplained before, which bridge the gap between theory and applications.
Wavelet based multi-scale shape features on arbitrary surfaces for cortical thickness discrimination
Authors: Won H. Kim, Deepti Pachauri, Charles Hatt, Moo. K. Chung, Sterling Johnson, Vikas Singh
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Two-sample testing

Hypothesis testing on signals deﬁned on surfaces (such as the cortical surface) is a fundamental component of a variety of studies in Neuroscience. The goal here is to identify regions that exhibit changes as a function of the clinical condition under study. As the clinical questions of interest move towards identifying very early signs of diseases, the corresponding statistical differences at the group level invariably become weaker and increasingly hard to identify. Indeed, after a multiple comparisons correction is adopted (to account for correlated statistical tests over all surface points), very few regions may survive. In contrast to hypothesis tests on point-wise measurements, in this paper, we make the case for performing statistical analysis on multi-scale shape descriptors that characterize the local topological context of the signal around each surface vertex. Our descriptors are based on recent results from harmonic analysis, that show how wavelet theory extends to non-Euclidean settings (i.e., irregular weighted graphs). We provide strong evidence that these descriptors successfully pick up group-wise differences, where traditional methods either fail or yield unsatisfactory results. Other than this primary application, we show how the framework allows performing cortical surface smoothing in the native space without mappint to a unit sphere.
A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
Authors: Aaron Defazio, Tibério S. Caetano
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

A key problem in statistics and machine learning is the determination of network structure from data. We consider the case where the structure of the graph to be reconstructed is known to be scale-free. We show that in such cases it is natural to formulate structured sparsity inducing priors using submodular functions, and we use their Lovasz extension to obtain a convex relaxation. For tractable classes such as Gaussian graphical models, this leads to a convex optimization problem that can be efficiently solved. We show that our method results in an improvement in the accuracy of reconstructed networks for synthetic data. We also show how our prior encourages scale-free reconstructions on a bioinfomatics dataset.
Fused sparsity and robust estimation for linear models with unknown variance
Authors: Arnak Dalalyan, Yin Chen
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

In this paper, we develop a novel approach to the problem of learning sparse representations in the context of fused sparsity and unknown noise level. We propose an algorithm, termed Scaled Fused Dantzig Selector (SFDS), that accomplishes the aforementioned learning task by means of a second-order cone program. A special  emphasize is put on the particular instance of fused sparsity corresponding to  the learning in presence of outliers. We establish finite sample risk bounds and  carry out an experimental evaluation on both synthetic and real data.