pwc-archive/papers-with-abstracts huggingface dataset:
Learning Multiple Tasks using Shared Hypotheses
Authors: Koby Crammer, Yishay Mansour
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Generalization Bounds

In this work we consider a setting where we have a very large number   of related tasks with few examples from each individual task. Rather   than either learning each task individually (and having a large   generalization error) or learning all the tasks together using a   single hypothesis (and suffering a potentially large inherent   error), we consider learning a small pool of {\em shared     hypotheses}. Each task is then mapped to a single hypothesis in   the pool (hard association). We derive VC dimension generalization   bounds for our model, based on the number of tasks, shared   hypothesis and the VC dimension of the hypotheses   class. We conducted experiments with both synthetic problems and   sentiment of reviews, which strongly support our approach.
On-line Reinforcement Learning Using Incremental Kernel-Based Stochastic Factorization
Authors: Doina Precup, Joelle Pineau, Andre S. Barreto
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

The ability to learn a policy for a sequential decision problem with continuous state space using on-line data is a long-standing challenge. This paper presents a new reinforcement-learning algorithm, called iKBSF, which extends the benefits of kernel-based learning to the on-line scenario. As a kernel-based method, the proposed algorithm is stable and has good convergence properties. However, unlike other similar algorithms,iKBSF's space complexity is independent of the number of sample transitions, and as a result it can process an arbitrary amount of data. We present theoretical results showing that iKBSF can approximate (to any level of accuracy) the value function that would be learned by an equivalent batch non-parametric kernel-based reinforcement learning approximator. In order to show the effectiveness of the proposed algorithm in practice, we apply iKBSF to the challenging three-pole balancing task, where the ability to process a large number of transitions is crucial for achieving a high success rate.
Forward-Backward Activation Algorithm for Hierarchical Hidden Markov Models
Authors: Kei Wakabayashi, Takao Miura
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: parameter estimation

Hierarchical Hidden Markov Models (HHMMs) are sophisticated stochastic models that enable us to capture a hierarchical context characterization of sequence data. However, existing HHMM parameter estimation methods require large computations of time complexity O(TN^{2D}) at least for model inference, where D is the depth of the hierarchy, N is the number of states in each level, and T is the sequence length. In this paper, we propose a new inference method of HHMMs for which the time complexity is O(TN^{D+1}). A key idea of our algorithm is application of the forward-backward algorithm to ''state activation probabilities''. The notion of a state activation, which offers a simple formalization of the hierarchical transition behavior of HHMMs, enables us to conduct model inference efficiently. We present some experiments to demonstrate that our proposed method works more efficiently to estimate HHMM parameters than do some existing methods such as the flattening method and Gibbs sampling method.
Communication-Efficient Algorithms for Statistical Optimization
Authors: Yuchen Zhang, Martin J. Wainwright, John C. Duchi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Learning-To-Rank

We study two communication-efficient algorithms for distributed statistical optimization on large-scale data. The first algorithm is an averaging method that distributes the $N$ data samples evenly to $m$ machines, performs separate minimization on each subset, and then averages the estimates.  We provide a sharp analysis of this average mixture algorithm, showing that under a reasonable set of conditions, the combined parameter achieves mean-squared error that decays as $\order(N^{-1}+(N/m)^{-2})$. Whenever $m \le \sqrt{N}$, this guarantee matches the best possible rate achievable by a centralized algorithm having access to all $N$ samples.  The second algorithm is a novel method, based on an appropriate form of the bootstrap.  Requiring only a single round of communication, it has mean-squared error that decays as $\order(N^{-1}+(N/m)^{-3})$, and so is more robust to the amount of parallelization. We complement our theoretical results with experiments on large-scale problems from the Microsoft Learning to Rank dataset.
Identifiability and Unmixing of Latent Parse Trees
Authors: Daniel J. Hsu, Sham M. Kakade, Percy S. Liang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Dependency Parsing

This paper explores unsupervised learning of parsing models along two directions.  First, which models are identifiable from infinite data?  We use a general technique for numerically checking identifiability based on the rank of a Jacobian matrix, and apply it to several standard constituency and dependency parsing models.  Second, for identifiable models, how do we estimate the parameters efficiently?  EM suffers from local optima, while recent work using spectral methods cannot be directly applied since the topology of the parse tree varies across sentences.  We develop a strategy, unmixing, which deals with this additional complexity for restricted classes of parsing models.
Bayesian nonparametric models for ranked data
Authors: Francois Caron, Yee W. Teh
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We develop a Bayesian nonparametric extension of the popular Plackett-Luce choice model that can handle an infinite number of choice items.   Our framework is based on the theory of random atomic measures, with the prior specified by a gamma process.  We derive a posterior characterization and a simple and effective Gibbs sampler for posterior simulation.  We then develop a time-varying extension of our model, and apply our model to the New York Times lists of weekly bestselling books.
Feature-aware Label Space Dimension Reduction for Multi-label Classification
Authors: Yao-Nan Chen, Hsuan-Tien Lin
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, Compressive Sensing, Dimensionality Reduction, General Classification, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION

Label space dimension reduction (LSDR) is an efficient and effective paradigm for multi-label classification with many classes. Existing approaches to LSDR, such as compressive sensing and principal label space transformation, exploit only the label part of the dataset, but not the feature part. In this paper, we propose a novel approach to LSDR that considers both the label and the feature parts. The approach, called conditional principal label space transformation, is based on minimizing an upper bound of the popular Hamming loss. The minimization step of the approach can be carried out efficiently by a simple use of singular value decomposition. In addition, the approach can be extended to a kernelized version that allows the use of sophisticated feature combinations to assist LSDR. The experimental results verify that the proposed approach is more effective than existing ones to LSDR across many real-world datasets.
Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions
Authors: Alekh Agarwal, Sahand Negahban, Martin J. Wainwright
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Stochastic Optimization, Vocal Bursts Intensity Prediction

We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding a $\order(\pdim/T)$ convergence rate for strongly convex objectives in $\pdim$ dimensions and $\order(\sqrt{\spindex( \log\pdim)/T})$ convergence rate when the optimum is $\spindex$-sparse. Our algorithm is based on successively solving a series of $\ell_1$-regularized optimization problems using Nesterov's dual averaging algorithm. We establish that the error of our solution after $T$ iterations is at most $\order(\spindex(\log\pdim)/T)$, with natural extensions to approximate sparsity. Our results apply to locally Lipschitz losses including the logistic, exponential, hinge and least-squares losses. By recourse to statistical minimax results, we show that our convergence rates are optimal up to constants. The effectiveness of our approach is also confirmed in numerical simulations where we compare to several baselines on a least-squares regression problem.
Graphical Gaussian Vector for Image Categorization
Authors: Tatsuya Harada, Yasuo Kuniyoshi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Image Categorization, Object Recognition

This paper proposes a novel image representation called a Graphical Gaussian Vector, which is a counterpart of the codebook and local feature matching approaches. In our method, we model the distribution of local features as a Gaussian Markov Random Field (GMRF) which can efficiently represent the spatial relationship among local features. We consider the parameter of GMRF as a feature vector of the image. Using concepts of information geometry, proper parameters and a metric from the GMRF can be obtained. Finally we define a new image feature by embedding the metric into the parameters, which can be directly applied to scalable linear classifiers. Our method obtains superior performance over the state-of-the-art methods in the standard object recognition datasets and comparable performance in the scene dataset. As the proposed method simply calculates the local auto-correlations of local features, it is able to achieve both high classification accuracy and high efficiency.
Joint Modeling of a Matrix with Associated Text via Latent Binary Features
Authors: Xianxing Zhang, Lawrence Carin
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

A new methodology is developed for joint analysis of a matrix and accompanying documents, with the documents associated with the matrix rows/columns. The documents are modeled with a focused topic model, inferring latent binary features (topics) for each document. A new matrix decomposition is developed, with latent binary features associated with the rows/columns, and with imposition of a low-rank constraint. The matrix decomposition and topic model are coupled by sharing the latent binary feature vectors associated with each. The model is applied to roll-call data, with the associated documents defined by the legislation. State-of-the-art results are manifested for prediction of votes on a new piece of legislation, based only on the observed text legislation. The coupling of the text and legislation is also demonstrated to yield insight into the properties of the matrix decomposition for roll-call data.
Proper losses for learning from partial labels
Authors: Jesús Cid-Sueiro
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

This paper discusses the problem of calibrating posterior class probabilities from partially labelled data. Each instance is assumed to be labelled as belonging to one of several candidate categories, at most one of them being true. We generalize the concept of proper loss to this scenario, establish a necessary and sufficient condition for a loss function to be proper, and we show a direct procedure to construct a proper loss for partial labels from a conventional proper loss. The problem can be characterized by the mixing probability matrix relating the true class of the data and the observed labels. An interesting result is that the full knowledge of this matrix is not required, and losses can be constructed that are proper in a subset of the probability simplex.
Selecting Diverse Features via Spectral Regularization
Authors: Abhimanyu Das, Anirban Dasgupta, Ravi Kumar
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Diversity, feature selection, regression

We study the problem of diverse feature selection in linear regression: selecting a small subset of diverse features that can predict a given objective. Diversity is useful for several reasons such as interpretability, robustness to noise, etc.  We propose several spectral regularizers that capture a notion of diversity of features and show that these are all submodular set functions. These regularizers, when added to the objective function for linear regression, result in approximately submodular functions, which can then be maximized approximately by efficient greedy and local search algorithms, with provable guarantees.  We compare our algorithms to traditional greedy and $\ell_1$-regularization schemes and show that we obtain a more diverse set of features that result in the regression problem being stable under perturbations.
Monte Carlo Methods for Maximum Margin Supervised Topic Models
Authors: Qixia Jiang, Jun Zhu, Maosong Sun, Eric P. Xing
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Topic Models

An effective strategy to exploit the supervising side information for discovering predictive topic representations is to impose discriminative constraints induced by such information on the posterior distributions under a topic model. This strategy has been adopted by a number of supervised topic models, such as MedLDA, which employs max-margin posterior constraints. However, unlike the likelihood-based supervised topic models, of which posterior inference can be carried out using the Bayes' rule, the max-margin posterior constraints have made Monte Carlo methods infeasible or at least not directly applicable, thereby limited the choice of inference algorithms to be based on variational approximation with strict mean field assumptions. In this paper, we develop two efficient Monte Carlo methods under much weaker assumptions for max-margin supervised topic models based on an importance sampler and a collapsed Gibbs sampler, respectively, in a convex dual formulation. We report thorough experimental results that compare our approach favorably against existing alternatives in both accuracy and efficiency.
Parametric Local Metric Learning for Nearest Neighbor Classification
Authors: Jun Wang, Alexandros Kalousis, Adam Woznica
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, General Classification, Metric Learning

We study the problem of learning local metrics for nearest neighbor classification. Most previous works on local metric learning learn a number of local unrelated metrics. While this ''independence'' approach delivers an increased flexibility its downside is the considerable risk of overfitting. We present a new parametric local metric learning method in which we learn a smooth metric matrix function over the data manifold. Using an approximation error bound of the metric matrix function we learn local metrics as linear combinations of basis metrics defined on anchor points over different regions of the instance space.  We constrain the metric matrix function by imposing on the linear combinations manifold regularization which makes the learned metric matrix function vary smoothly along the geodesics of the data manifold. Our metric learning method has excellent performance both in terms of predictive power and scalability. We experimented with several large-scale classification problems, tens of thousands of instances, and compared it with several state of the art metric learning methods, both global and local, as well as to SVM with automatic kernel selection, all of which it outperforms in a significant manner.
A Linear Time Active Learning Algorithm for Link Classification
Authors: Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale, Giovanni Zappella
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Active Learning, Classification, Clustering, General Classification

We present very efficient active learning algorithms for link classification in signed networks. Our algorithms are motivated by a stochastic model in which edge labels are obtained through perturbations of a initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to whithin a constant factor) number of mistakes on any graph $G = (V,E)$ such that $|E|$ is at least order of $|V|^{3/2}$ by querying at most order of $|V|^{3/2}$ edge labels. More generally, we show an algorithm that achieves optimality to within a factor of order $k$ by querying at most order of $|V| + (|V|/k)^{3/2}$ edge labels. The running time of this algorithm is at most of order $|E| + |V|\log|V|$.
Bayesian Warped Gaussian Processes
Authors: Miguel Lázaro-Gredilla
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Gaussian Processes, General Classification

Warped Gaussian processes (WGP) [1] model output observations in regression tasks as a parametric nonlinear transformation of a Gaussian process (GP). The use of this nonlinear transformation, which is included as part of the probabilistic model, was shown to enhance performance by providing a better prior model on several data sets. In order to learn its parameters, maximum likelihood was used. In this work we show that it is possible to use a non-parametric nonlinear transformation in WGP and variationally integrate it out. The resulting Bayesian WGP is then able to work in scenarios in which the maximum likelihood WGP failed: Low data regime, data with censored values, classification, etc. We demonstrate the superior performance of Bayesian warped GPs on several real data sets.
Nonparametric Reduced Rank Regression
Authors: Rina Foygel, Michael Horrell, Mathias Drton, John D. Lafferty
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Form, regression

We propose an approach to multivariate nonparametric regression that generalizes reduced rank regression for linear models.  An additive model is estimated for each dimension of a $q$-dimensional response, with a shared $p$-dimensional predictor variable.  To control the complexity of the model, we employ a functional form of the Ky-Fan or nuclear norm, resulting in a set of function estimates that have low rank.  Backfitting algorithms are derived and justified using a nonparametric form of the nuclear norm subdifferential.  Oracle inequalities on excess risk are derived that exhibit the scaling behavior of the procedure in the high dimensional setting.  The methods are illustrated on gene expression data.
Multiresolution analysis on the symmetric group
Authors: Risi Kondor, Walter Dempsey
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Multi-Object Tracking, Object Tracking

There is no generally accepted way to define wavelets on permutations. We address this issue by introducing the notion of coset based multiresolution analysis (CMRA) on the symmetric group; find the corresponding wavelet functions; and describe a fast wavelet transform of O(n^p) complexity with small p for sparse signals (in contrast to the O(n^q n!) complexity typical of FFTs). We discuss potential applications in ranking, sparse approximation, and multi-object tracking.
Isotropic Hashing
Authors: Weihao Kong, Wu-Jun Li
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Most existing hashing methods adopt some projection functions to project the original data into several dimensions of real values, and then each of these projected dimensions is quantized into one bit (zero or one) by thresholding. Typically, the variances of different projected dimensions are different for existing projection functions such as principal component analysis (PCA). Using the same number of bits for different projected dimensions is unreasonable because larger-variance dimensions will carry more information. Although this viewpoint has been widely accepted by many researchers, it is still not verified by either theory or experiment because no methods have been proposed to find a projection with equal variances for different dimensions. In this paper, we propose a novel method, called isotropic hashing (IsoHash), to learn projection functions which can produce projected dimensions with isotropic variances (equal variances). Experimental results on real data sets show that IsoHash can outperform its counterpart with different variances for different dimensions, which verifies the viewpoint that projections with isotropic variances will be better than those with anisotropic variances.
On Lifting the Gibbs Sampling Algorithm
Authors: Deepak Venugopal, Vibhav Gogate
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Relational Reasoning

Statistical relational learning models combine the power of first-order logic, the de facto tool for handling relational structure, with that of probabilistic graphical models, the de facto tool for handling uncertainty. Lifted probabilistic inference algorithms for them have been the subject of much recent research. The main idea in these algorithms is to improve the speed, accuracy and scalability of existing graphical models' inference algorithms by exploiting symmetry in the first-order representation. In this paper, we consider blocked Gibbs sampling, an advanced variation of the classic Gibbs sampling algorithm and lift it to the first-order level. We propose to achieve this by partitioning the first-order atoms in the relational model into a set of disjoint clusters such that exact lifted inference is polynomial in each cluster given an assignment to all other atoms not in the cluster. We propose an approach for constructing such clusters and determining their complexity and show how it can be used to trade accuracy with computational complexity in a principled manner. Our experimental evaluation shows that lifted Gibbs sampling is superior to the propositional algorithm in terms of accuracy and convergence.
On the connections between saliency and tracking
Authors: Vijay Mahadevan, Nuno Vasconcelos
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Visual Tracking

A model connecting visual tracking and saliency has recently been proposed. This model is based on the saliency hypothesis for tracking which postulates that tracking is achieved by the top-down tuning, based on target features, of discriminant center-surround saliency mechanisms over time. In this work, we identify three main predictions that must hold if the hypothesis were true: 1) tracking reliability should be larger for salient than for non-salient targets, 2) tracking reliability should have a dependence on the defining variables of saliency, namely feature contrast and distractor heterogeneity, and must replicate the dependence of saliency on these variables, and 3) saliency and tracking can be implemented with common low level neural mechanisms. We confirm that the first two predictions hold by reporting results from a set of human behavior studies on the connection between saliency and tracking. We also show that the third prediction holds by constructing a common neurophysiologically plausible architecture that can computationally solve both saliency and tracking. This architecture is fully compliant with the standard physiological models of V1 and MT, and with what is known about attentional control in area LIP, while explaining the results of the human behavior experiments.