pwc-archive/papers-with-abstracts huggingface dataset:
Generalized Beta Mixtures of Gaussians
Authors: Artin Armagan, Merlise Clyde, David B. Dunson
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

In recent years, a rich variety of shrinkage priors have been proposed that have great promise in addressing massive regression problems.  In general, these new priors can be expressed as scale mixtures of normals, but have more complex forms and better properties than traditional Cauchy and double exponential priors. We first propose a new class of normal scale mixtures through a novel generalized beta distribution that encompasses many interesting priors as special cases.  This encompassing framework should prove useful in comparing competing priors, considering properties and revealing close connections. We then develop a class of variational Bayes approximations through the new hierarchy presented that will scale more efficiently to the types of truly massive data sets that are now encountered routinely.
Large-Scale Sparse Principal Component Analysis with Application to Text Data
Authors: Youwei Zhang, Laurent E. Ghaoui
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Topic Models

Sparse PCA provides a linear combination of small number of features that maximizes variance across data. Although Sparse PCA has apparent advantages compared to PCA, such as better interpretability, it is generally thought to be computationally much more expensive. In this paper, we demonstrate the surprising fact that sparse PCA can be easier than PCA in practice, and that it can be reliably applied to very large data sets. This comes from a rigorous feature elimination  pre-processing result, coupled with the favorable fact that features in real-life data typically have exponentially decreasing variances, which allows for many features to be eliminated. We introduce a fast block coordinate ascent algorithm with much better computational complexity than the existing first-order ones. We provide  experimental results obtained on text corpora involving millions of documents and hundreds of thousands of features. These results illustrate how Sparse PCA can help organize a large corpus of text data in a user-interpretable way, providing an attractive alternative approach to topic models.
Simultaneous Sampling and Multi-Structure Fitting with Adaptive Reversible Jump MCMC
Authors: Trung T. Pham, Tat-Jun Chin, Jin Yu, David Suter
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Computational Efficiency, Model Selection

Multi-structure model fitting has traditionally taken a two-stage approach: First, sample a (large) number of model hypotheses, then select the subset of hypotheses that optimise a joint fitting and model selection criterion. This disjoint two-stage approach is arguably suboptimal and inefficient - if the random sampling did not retrieve a good set of hypotheses, the optimised outcome will not represent a good fit. To overcome this weakness we propose a new multi-structure fitting approach based on Reversible Jump MCMC. Instrumental in raising the effectiveness of our method is an adaptive hypothesis generator, whose proposal distribution is learned incrementally and online. We prove that this adaptive proposal satisfies the diminishing adaptation property crucial for ensuring ergodicity in MCMC. Our method effectively conducts hypothesis sampling and optimisation simultaneously, and gives superior computational efficiency over other methods.
\theta-MRF: Capturing Spatial and Semantic Structure in the Parameters for Scene Understanding
Authors: Cong-Cong Li, Ashutosh Saxena, Tsuhan Chen
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Depth Estimation, object-detection, Object Detection, Scene Understanding

For most scene understanding tasks (such as object detection or depth estimation), the classifiers need to consider contextual information in addition to the local features. We can capture such contextual information by taking as input the features/attributes from all the regions in the image. However, this contextual dependence also varies with the spatial location of the region of interest, and we therefore need a different set of parameters for each spatial location. This results in a very large number of parameters. In this work, we model the independence properties between the parameters for each location and for each task, by defining a Markov Random Field (MRF) over the parameters. In particular, two sets of parameters are encouraged to have similar values if they are spatially close or semantically close. Our method is, in principle, complementary to other ways of capturing context such as the ones that use a graphical model over the labels instead. In extensive evaluation over two different settings, of multi-class object detection and of multiple scene understanding tasks (scene categorization, depth estimation, geometric labeling), our method beats the state-of-the-art methods in all the four tasks.
Crowdclustering
Authors: Ryan G. Gomes, Peter Welinder, Andreas Krause, Pietro Perona
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering

Is it possible to crowdsource categorization? Amongst the challenges: (a) each annotator has only a partial view of the data, (b) different annotators may have different clustering criteria and may produce different numbers of categories, (c) the underlying category structure may be hierarchical. We propose a Bayesian model of how annotators may approach clustering and show how one may infer clusters/categories, as well as annotator parameters, using this model. Our experiments, carried out on large collections of images, suggest that Bayesian crowdclustering works well and may be superior to single-expert annotations.
Fast and Balanced: Efficient Label Tree Learning for Large Scale Object Recognition
Authors: Jia Deng, Sanjeev Satheesh, Alexander C. Berg, Fei Li
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Classification, General Classification, image-classification, Image Classification, Object Recognition

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.
Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification
Authors: Ichiro Takeuchi, Masashi Sugiyama
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Classification, feature selection, General Classification, Metric Learning

We consider feature selection and weighting for nearest neighbor classifiers. A technical challenge in this scenario is how to cope with the discrete update of nearest neighbors when the feature space metric is changed during the learning process. This issue, called the target neighbor change, was not properly addressed in the existing feature weighting and metric learning literature.  In this paper, we propose a novel feature weighting algorithm that can exactly and efficiently keep track of the correct target neighbors via sequential quadratic programming. To the best of our knowledge, this is the first algorithm that guarantees the consistency between target neighbors and the feature space metric. We further show that the proposed algorithm can be naturally combined with regularization path tracking, allowing computationally efficient selection of the regularization parameter. We demonstrate the effectiveness of the proposed algorithm through experiments.
The Impact of Unlabeled Patterns in Rademacher Complexity Theory for Kernel Classifiers
Authors: Luca Oneto, Davide Anguita, Alessandro Ghio, Sandro Ridella
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Generalization Bounds, Model Selection

We derive here new generalization bounds, based on Rademacher Complexity theory, for model selection and error estimation   of linear (kernel) classifiers, which exploit  the availability of unlabeled samples.   In particular, two results are obtained: the first one shows that, using the unlabeled samples, the  confidence term of the conventional bound can be reduced by a factor of three; the second one  shows that the unlabeled samples can be used to obtain much tighter bounds, by building localized versions  of the hypothesis class containing the optimal classifier.
Relative Density-Ratio Estimation for Robust Distribution Comparison
Authors: Makoto Yamada, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, Masashi Sugiyama
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Density Ratio Estimation, Outlier Detection, Transfer Learning

Divergence estimators based on direct approximation of density-ratios without going through separate approximation of numerator and denominator densities have been successfully applied to machine learning tasks that involve distribution comparison such as outlier detection, transfer learning, and two-sample homogeneity test. However, since density-ratio functions often possess high fluctuation, divergence estimation is still a challenging task in practice. In this paper, we propose to use relative divergences for distribution comparison, which involves approximation of relative density-ratios. Since relative density-ratios are always smoother than corresponding ordinary density-ratios, our proposed method is favorable in terms of the non-parametric convergence speed. Furthermore, we show that the proposed divergence estimator has asymptotic variance independent of the model complexity under a parametric setup, implying that the proposed estimator hardly overfits even with complex models. Through experiments, we demonstrate the usefulness of the proposed approach.
Solving Decision Problems with Limited Information
Authors: Denis D. Maua, Cassio Campos
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Decision Making

We present a new algorithm for exactly solving decision-making problems represented as an influence diagram. We do not require the usual assumptions of no forgetting and regularity, which allows us to solve problems with limited information. The algorithm, which implements a sophisticated variable elimination procedure, is empirically shown to outperform a state-of-the-art algorithm in randomly generated problems of up to 150 variables and $10^{64}$ strategies.
Learning a Tree of Metrics with Disjoint Visual Features
Authors: Kristen Grauman, Fei Sha, Sung Ju Hwang
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Attribute, Metric Learning, Semantic Similarity, Semantic Textual Similarity

We introduce an approach to learn discriminative visual representations while exploiting external semantic knowledge about object category relationships.  Given a hierarchical taxonomy that captures semantic similarity between the objects, we learn a corresponding tree of metrics (ToM).  In this tree, we have one metric for each non-leaf node of the object hierarchy, and each metric is responsible for discriminating among its immediate subcategory children.  Specifically, a Mahalanobis metric learned for a given node must satisfy the appropriate (dis)similarity constraints generated only among its subtree members' training instances.  To further exploit the semantics, we introduce a novel regularizer coupling the metrics that prefers a sparse disjoint set of features to be selected for each metric relative to its ancestor supercategory nodes' metrics.  Intuitively, this reflects that visual cues most useful to distinguish the generic classes (e.g., feline vs. canine) should be different than those cues most useful to distinguish their component fine-grained classes (e.g., Persian cat vs. Siamese cat).  We validate our approach with multiple image datasets using the WordNet taxonomy, show its advantages over alternative metric learning approaches, and analyze the meaning of attribute features selected by our algorithm.
On Causal Discovery with Cyclic Additive Noise Models
Authors: Joris M. Mooij, Dominik Janzing, Tom Heskes, Bernhard Schölkopf
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Causal Discovery, regression

We study a particular class of cyclic causal models, where each variable is a (possibly nonlinear) function of its parents and additive noise. We prove that the causal graph of such models is generically identifiable in the bivariate, Gaussian-noise case. We also propose a method to learn such models from observational data. In the acyclic case, the method reduces to ordinary regression, but in the more challenging cyclic case, an additional term arises in the loss function, which makes it a special case of nonlinear independent component analysis. We illustrate the proposed method on synthetic data.
Learning to Agglomerate Superpixel Hierarchies
Authors: Viren Jain, Srinivas C. Turaga, K Briggman, Moritz N. Helmstaedter, Winfried Denk, H. S. Seung
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Boundary Detection, Clustering, Reinforcement Learning, Superpixels

An agglomerative clustering algorithm merges the most similar pair of clusters at every iteration. The function that evaluates similarity is traditionally hand- designed, but there has been recent interest in supervised or semisupervised settings in which ground-truth clustered data is available for training. Here we show how to train a similarity function by regarding it as the action-value function of a reinforcement learning problem. We apply this general method to segment images by clustering superpixels, an application that we call Learning to Agglomerate Superpixel Hierarchies (LASH). When applied to a challenging dataset of brain images from serial electron microscopy, LASH dramatically improved segmentation accuracy when clustering supervoxels generated by state of the boundary detection algorithms. The naive strategy of directly training only supervoxel similarities and applying single linkage clustering produced less improvement.
A Convergence Analysis of Log-Linear Training
Authors: Simon Wiesler, Hermann Ney
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Handwriting Recognition

Log-linear models are widely used probability models for statistical pattern recognition. Typically, log-linear models are trained according to a convex criterion. In recent years, the interest in log-linear models has greatly increased. The optimization of log-linear model parameters is costly and therefore an important topic, in particular for large-scale applications. Different optimization algorithms have been evaluated empirically in many papers. In this work, we analyze the optimization problem analytically and show that the training of log-linear models can be highly ill-conditioned. We verify our findings on two handwriting tasks. By making use of our convergence analysis, we obtain good results on a large-scale continuous handwriting recognition task with a simple and generic approach.
Shallow vs. Deep Sum-Product Networks
Authors: Olivier Delalleau, Yoshua Bengio
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We investigate the representational power of sum-product networks  (computation networks analogous to neural networks,  but whose individual units compute either products  or weighted sums), through a theoretical analysis that compares  deep (multiple hidden layers) vs. shallow (one hidden layer) architectures.  We prove there exist families of functions that can be represented  much more efficiently with a deep network than with a shallow one, i.e.  with substantially fewer hidden units.  Such results were not available until now, and  contribute to motivate recent research involving learning of deep  sum-product networks, and more generally motivate research in Deep  Learning.
Signal Estimation Under Random Time-Warpings and Nonlinear Signal Alignment
Authors: Sebastian A. Kurtek, Anuj Srivastava, Wei Wu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

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.
From Bandits to Experts: On the Value of Side-Observations
Authors: Shie Mannor, Ohad Shamir
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Multi-Armed Bandits

We consider an adversarial online learning setting where a decision maker can choose an action in every stage of the game. In addition to observing the reward of the chosen action, the decision maker gets side observations on the reward he would have obtained had he chosen some of the other actions. The observation structure is encoded as a graph, where node i is linked to  node j if sampling i provides information on the reward of j. This setting naturally interpolates between the well-known ``experts'' setting, where the decision maker can view all rewards, and the multi-armed bandits setting, where the decision maker can only view the reward of the chosen action. We develop practical algorithms with provable regret guarantees, which depend on non-trivial graph-theoretic properties of the information feedback structure. We also provide partially-matching lower bounds.
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Authors: Benjamin Recht, Christopher Re, Stephen Wright, Feng Niu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve state-of-the-art performance on a variety of machine  learning tasks.  Several researchers have recently proposed schemes  to parallelize SGD, but all require  performance-destroying memory locking and synchronization. This work aims to show using novel theoretical analysis, algorithms,  and implementation that SGD can be implemented *without any locking*. We present an update scheme called Hogwild which allows processors access to shared memory with the possibility of overwriting each other's work. We show that when the associated optimization problem is sparse, meaning most gradient updates only modify small parts of the decision variable, then Hogwild achieves a nearly optimal rate of convergence.  We demonstrate experimentally that Hogwild outperforms alternative schemes that use locking by an order of magnitude.
Clustered Multi-Task Learning Via Alternating Structure Optimization
Authors: Jiayu Zhou, Jianhui Chen, Jieping Ye
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Multi-Task Learning

Multi-task learning (MTL) learns multiple related tasks simultaneously to improve generalization performance. Alternating structure optimization (ASO) is a popular MTL method that learns a shared low-dimensional predictive structure on hypothesis spaces from multiple related tasks. It has been applied successfully in many real world applications. As an alternative MTL approach, clustered multi-task learning (CMTL) assumes that multiple tasks follow a clustered structure, i.e., tasks are partitioned into a set of groups where tasks in the same group are similar to each other, and that such a clustered structure is unknown a priori. The objectives in ASO and CMTL differ in how multiple tasks are related. Interestingly, we show in this paper the equivalence relationship between ASO and CMTL, providing significant new insights into ASO and CMTL as well as their inherent relationship. The CMTL formulation is non-convex, and we adopt a convex relaxation to the CMTL formulation. We further establish the equivalence relationship between the proposed convex relaxation of CMTL and an existing convex relaxation of ASO, and show that the proposed convex CMTL formulation is significantly more efficient especially for high-dimensional data. In addition, we present three algorithms for solving the convex CMTL formulation. We report experimental results on benchmark datasets to demonstrate the efficiency of the proposed algorithms.
Why The Brain Separates Face Recognition From Object Recognition
Authors: Joel Z. Leibo, Jim Mutch, Tomaso Poggio
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Face Identification, Face Recognition, Object, Object Recognition

Many studies have uncovered evidence that visual cortex contains specialized regions involved in processing faces but not other object classes.  Recent electrophysiology studies of cells in several of these specialized regions revealed that at least some of these regions are organized in a hierarchical manner with viewpoint-specific cells projecting to downstream viewpoint-invariant identity-specific cells (Freiwald and Tsao 2010).  A separate computational line of reasoning leads to the claim that some transformations of visual inputs that preserve viewed object identity are class-specific.  In particular, the 2D images evoked by a face undergoing a 3D rotation are not produced by the same image transformation (2D) that would produce the images evoked by an object of another class undergoing the same 3D rotation.  However, within the class of faces, knowledge of the image transformation evoked by 3D rotation can be reliably transferred from previously viewed faces to help identify a novel face at a new viewpoint.  We show, through computational simulations, that an architecture which applies this method of gaining invariance to class-specific transformations is effective when restricted to faces and fails spectacularly when applied across object classes.  We argue here that in order to accomplish viewpoint-invariant face identification from a single example view, visual cortex must separate the circuitry involved in discounting 3D rotations of faces from the generic circuitry involved in processing other objects.  The resulting model of the ventral stream of visual cortex is consistent with the recent physiology results showing the hierarchical organization of the face processing network.