pwc-archive/papers-with-abstracts huggingface dataset:
Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models
Authors: Jing Gao, Feng Liang, Wei Fan, Yizhou Sun, Jiawei Han
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering, General Classification

Little work has been done to directly combine the outputs of multiple supervised and unsupervised models. However, it can increase the accuracy and applicability of ensemble methods. First, we can boost the diversity of classification ensemble by incorporating multiple clustering outputs, each of which provides grouping constraints for the joint label predictions of a set of related objects. Secondly, ensemble of supervised models is limited in applications which have no access to raw data but to the meta-level model outputs. In this paper, we aim at calculating a consolidated classification solution for a set of objects by maximizing the consensus among both supervised predictions and unsupervised grouping constraints. We seek a global optimal label assignment for the target objects, which is different from the result of traditional majority voting and model combination approaches. We cast the problem into an optimization problem on a bipartite graph, where the objective function favors smoothness in the conditional probability estimates over the graph, as well as penalizes deviation from initial labeling of supervised models. We solve the problem through iterative propagation of conditional probability estimates among neighboring nodes, and interpret the method as conducting a constrained embedding in a transformed space, as well as a ranking on the graph. Experimental results on three real applications demonstrate the benefits of the proposed method over existing alternatives.
Lattice Regression
Authors: Eric Garcia, Maya Gupta
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Management, regression

We present a new empirical risk minimization framework for approximating functions from training samples for low-dimensional regression applications where a lattice (look-up table) is stored and interpolated at run-time for an efficient hardware implementation. Rather than evaluating a fitted function at the lattice nodes without regard to the fact that samples will be interpolated, the proposed lattice regression approach estimates the lattice to minimize the interpolation error on the given training samples. Experiments show that lattice regression can reduce mean test error  compared to Gaussian process regression for digital color management of printers, an application for which linearly interpolating a look-up table (LUT) is standard. Simulations confirm that lattice regression performs consistently better than the naive approach to learning the lattice, particularly when the density of training samples is low.
From PAC-Bayes Bounds to KL Regularization
Authors: Pascal Germain, Alexandre Lacasse, Mario Marchand, Sara Shanian, François Laviolette
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

We show that convex KL-regularized objective functions are obtained from a PAC-Bayes risk bound when using convex loss functions for the stochastic Gibbs classifier that upper-bound the standard zero-one loss used for the weighted majority vote. By restricting ourselves to a class of posteriors, that we call quasi uniform, we propose a simple coordinate descent learning algorithm to minimize the proposed KL-regularized cost function. We show that standard ell_p-regularized objective functions currently used, such as ridge regression and ell_p-regularized boosting, are obtained from a relaxation of the KL divergence between the quasi uniform posterior and the uniform prior. We present numerical experiments where the proposed learning algorithm generally outperforms ridge regression and AdaBoost.
Perceptual Multistability as Markov Chain Monte Carlo Inference
Authors: Samuel Gershman, Ed Vul, Joshua B. Tenenbaum
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Bayesian Inference

While many perceptual and cognitive phenomena are well described in terms of Bayesian inference, the necessary computations are intractable at the scale of real-world tasks, and it remains unclear how the human mind approximates Bayesian inference algorithmically. We explore the proposal that for some tasks, humans use a form of Markov Chain Monte Carlo to approximate the posterior distribution over hidden variables.  As a case study, we show how several phenomena of perceptual multistability can be explained as MCMC inference in simple graphical models for low-level vision.
A joint maximum-entropy model for binary neural population patterns and continuous signals
Authors: Sebastian Gerwinn, Philipp Berens, Matthias Bethge
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Second-order maximum-entropy models have recently gained much interest for describing the statistics of binary spike trains. Here, we extend this approach to take continuous stimuli into account as well. By constraining  the joint second-order statistics, we obtain a joint Gaussian-Boltzmann distribution of continuous stimuli and binary neural firing patterns, for which we also compute marginal and conditional distributions. This model has the same computational complexity as pure binary models and fitting it to data is a convex problem. We show that the model can be seen as an extension to the classical spike-triggered average/covariance analysis and can be used as a non-linear method for extracting features which a neural population is sensitive to. Further, by calculating the posterior distribution of stimuli given an observed neural response, the model can be used to decode stimuli and yields a natural spike-train metric. Therefore, extending the framework of maximum-entropy models to continuous variables allows us to gain novel insights into the relationship between the firing patterns of neural ensembles and the stimuli they are processing.
A Biologically Plausible Model for Rapid Natural Scene Identification
Authors: Sennay Ghebreab, Steven Scholte, Victor Lamme, Arnold Smeulders
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: EEG, Electroencephalogram (EEG)

Contrast statistics of the majority of natural images conform to a Weibull distribution. This property of natural images may facilitate efficient and very rapid extraction of a scenes visual gist. Here we investigate whether a neural response model based on the Weibull contrast distribution captures visual information that humans use to rapidly identify natural scenes. In a learning phase, we measure EEG activity  of 32 subjects viewing brief flashes of 800 natural scenes. From these neural measurements and the contrast statistics of the natural image stimuli,  we  derive an across subject  Weibull response model. We use this model to predict the responses to a large set of new scenes and estimate which scene the subject viewed by finding the best match between the model predictions and the observed EEG responses. In almost 90 percent of the cases our model accurately predicts the observed scene. Moreover, in most failed cases, the scene mistaken for the observed scene is visually similar to the observed scene itself. These results suggest that Weibull contrast statistics of natural images contain a considerable amount of scene gist information to warrant rapid identification of natural images.
A Gaussian Tree Approximation for Integer Least-Squares
Authors: Jacob Goldberger, Amir Leshem
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

This paper proposes a new algorithm for the linear least squares problem where the unknown variables are constrained to be in a finite set.  The factor graph that corresponds to this problem is very loopy; in fact, it is a complete graph. Hence, applying the Belief Propagation (BP) algorithm yields very poor results. The algorithm described here is based on  an optimal  tree approximation of the Gaussian density of the unconstrained linear system. It is shown that even though the approximation is not directly applied to the exact discrete distribution, applying the BP algorithm to the modified factor graph outperforms current methods in terms of both performance and complexity. The improved performance of the proposed algorithm is demonstrated  on the problem of MIMO detection.
Measuring Invariances in Deep Networks
Authors: Ian Goodfellow, Honglak Lee, Quoc V. Le, Andrew Saxe, Andrew Y. Ng
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

For many computer vision applications, the ideal image feature would be invariant to multiple confounding image properties, such as illumination and viewing angle. Recently, deep architectures trained in an unsupervised manner have been proposed as an automatic method for extracting useful features. However, outside of using these learning algorithms in a classiﬁer, they can be sometimes difﬁcult to evaluate. In this paper, we propose a number of empirical tests that directly measure the degree to which these learned features are invariant to different image transforms. We ﬁnd that deep autoencoders become invariant to increasingly complex image transformations with depth. This further justiﬁes the use of “deep” vs. “shallower” representations. Our performance metrics agree with existing measures of invariance. Our evaluation metrics can also be used to evaluate future work in unsupervised deep learning, and thus help the development of future algorithms.
Region-based Segmentation and Object Detection
Authors: Stephen Gould, Tianshi Gao, Daphne Koller
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification, Image Segmentation, Object, object-detection, Object Detection, Segmentation, Semantic Segmentation

Object detection and multi-class image segmentation are two closely related tasks that can be greatly improved when solved jointly by feeding information from one task to the other. However, current state-of-the-art models use a separate representation for each task making joint inference clumsy and leaving classification of many parts of the scene ambiguous. In this work, we propose a hierarchical region-based approach to joint object detection and image segmentation. Our approach reasons about pixels, regions and objects in a coherent probabilistic model. Importantly, our model gives a single unified description of the scene. We explain every pixel in the image and enforce global consistency between all variables in our model. We run experiments on challenging vision datasets and show significant improvement over state-of-the-art object detection accuracy.
Posterior vs Parameter Sparsity in Latent Variable Models
Authors: Kuzman Ganchev, Ben Taskar, Fernando Pereira, João Gama
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Part-Of-Speech Tagging, POS, POS Tagging

In this paper we explore the problem of biasing unsupervised models to favor sparsity. We extend the posterior regularization framework [8] to encourage the  model to achieve posterior sparsity on the unlabeled training data. We apply this new method to learn ﬁrst-order HMMs for unsupervised part-of-speech (POS) tagging, and show that HMMs learned this way consistently and signiﬁcantly out-performs both EM-trained HMMs, and HMMs with a sparsity-inducing Dirichlet prior trained by variational EM. We evaluate these HMMs on three languages — English, Bulgarian and Portuguese — under four conditions. We ﬁnd that our  method always improves performance with respect to both baselines, while variational Bayes actually degrades performance in most cases. We increase accuracy with respect to EM by 2.5%-8.7% absolute and we see improvements even in a semisupervised condition where a limited dictionary is provided.
A Fast, Consistent Kernel Two-Sample Test
Authors: Arthur Gretton, Kenji Fukumizu, Zaïd Harchaoui, Bharath K. Sriperumbudur
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Vocal Bursts Valence Prediction

A kernel embedding of probability distributions into reproducing kernel Hilbert spaces (RKHS) has recently been proposed, which  allows the comparison of two probability measures P and Q based on the distance between their respective embeddings: for a sufficiently rich RKHS, this distance is zero if and only if P and Q coincide. In using this distance as a statistic for a  test of whether two samples are from different distributions, a major difficulty arises in computing the significance threshold, since the empirical statistic has as its null distribution (where P=Q)  an infinite weighted sum of $\chi^2$ random variables. The main result of the present work is a  novel, consistent estimate of this null distribution, computed from  the eigenspectrum of the Gram matrix on the aggregate sample from P and Q. This estimate may be computed faster than a previous consistent estimate based on the bootstrap.  Another prior approach was to compute the null distribution based on fitting a parametric family with the low order moments of the test statistic: unlike the present work, this heuristic has no guarantee of being accurate or consistent. We verify the performance of our null distribution estimate on both   an artificial example and on high dimensional multivariate data.
Non-stationary continuous dynamic Bayesian networks
Authors: Marco Grzegorczyk, Dirk Husmeier
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Time Series, Time Series Analysis, valid

Dynamic Bayesian networks have been applied widely to reconstruct the structure of regulatory processes from time series data. The standard approach is based on the assumption of a homogeneous Markov chain, which is not valid in many real-world scenarios. Recent research efforts addressing this shortcoming have considered undirected graphs, directed graphs for discretized data, or over-flexible models that lack any information sharing between time series segments. In the present article, we propose a non-stationary dynamic Bayesian network for continuous data, in which parameters are allowed to vary between segments, and in which a common network structure provides essential information sharing across segments.  Our model is based on a Bayesian change-point process, and we apply a variant of the allocation sampler of Nobile and Fearnside to infer the number and location of the change-points.
Label Selection on Graphs
Authors: Andrew Guillory, Jeff A. Bilmes
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We investigate methods for selecting sets of labeled vertices for use in predicting the labels of vertices on a graph.  We specifically study methods which choose a single batch of labeled vertices (i.e. offline, non sequential methods).  In this setting, we find common graph smoothness assumptions directly motivate simple label selection methods with interesting theoretical guarantees. These methods bound prediction error in terms of the smoothness of the true labels with respect to the graph.  Some of these bounds give new motivations for previously proposed algorithms, and some suggest new algorithms which we evaluate.  We show improved performance over baseline methods on several real world data sets.
Beyond Convexity: Online Submodular Minimization
Authors: Elad Hazan, Satyen Kale
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efficient and are Hannan-consistent in both the full information and bandit settings.
On Stochastic and Worst-case Models for Investing
Authors: Elad Hazan, Satyen Kale
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Management, valid

In practice, most investing is done assuming a probabilistic model of stock price returns known as the Geometric Brownian Motion (GBM). While it is often an acceptable approximation, the GBM model is not always valid empirically. This motivates a worst-case approach to investing, called universal portfolio management, where the objective is to maximize wealth relative to the wealth earned by the best fixed portfolio in hindsight.  In this paper we tie the two approaches, and design an investment strategy which is universal in the worst-case, and yet capable of exploiting the mostly valid GBM model. Our method is based on new and improved regret bounds for online convex optimization with exp-concave loss functions.
Robust Nonparametric Regression with Metric-Space Valued Output
Authors: Matthias Hein
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification, Multi-class Classification, regression

Motivated by recent developments in manifold-valued regression we propose a family of nonparametric kernel-smoothing estimators with metric-space valued output including a robust median type estimator and the classical Frechet mean. Depending on the choice of the output space and the chosen metric the estimator reduces to partially well-known procedures for multi-class classification, multivariate regression in Euclidean space, regression with manifold-valued output and even some cases of structured output learning. In this paper we focus on the case of regression with manifold-valued input and output. We show pointwise and Bayes consistency for all estimators in the family for the case of manifold-valued output and illustrate the robustness properties of the estimator with experiments.
Hierarchical Learning of Dimensional Biases in Human Categorization
Authors: Adam Sanborn, Nick Chater, Katherine A. Heller
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Existing models of categorization typically represent to-be-classified items as points in a multidimensional space. While from a mathematical point of view, an infinite number of basis sets can be used to represent points in this space, the choice of basis set is psychologically crucial. People generally choose the same basis dimensions, and have a strong preference to generalize along the axes of these dimensions, but not diagonally". What makes some choices of dimension special? We explore the idea that the dimensions used by people echo the natural variation in the environment. Specifically, we present a rational model that does not assume dimensions, but learns the same type of dimensional generalizations that people display. This bias is shaped by exposing the model to many categories with a structure hypothesized to be like those which children encounter. Our model can be viewed as a type of transformed Dirichlet process mixture model, where it is the learning of the base distribution of the Dirichlet process which allows dimensional generalization.The learning behaviour of our model captures the developmental shift from roughly "isotropic" for children to the axis-aligned generalization that adults show."
Bayesian Sparse Factor Models and DAGs Inference and Comparison
Authors: Ricardo Henao, Ole Winther
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: valid

In this paper we present a novel approach to learn directed acyclic graphs (DAG) and factor models within the same framework while also allowing for model comparison between them. For this purpose, we exploit the connection between factor models and DAGs to propose Bayesian hierarchies based on spike and slab priors to promote sparsity, heavy-tailed priors to ensure identifiability and predictive densities to perform the model comparison. We require identifiability to be able to produce variable orderings leading to valid DAGs and sparsity to learn the structures. The effectiveness of our approach is demonstrated through extensive experiments on artificial and biological data showing that our approach outperform a number of state of the art methods.
Sparse and Locally Constant Gaussian Graphical Models
Authors: Jean Honorio, Dimitris Samaras, Nikos Paragios, Rita Goldstein, Luis E. Ortiz
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Locality information is crucial in datasets where each variable corresponds to a measurement in a manifold (silhouettes, motion trajectories, 2D and 3D images). Although these datasets are typically under-sampled and high-dimensional, they often need to be represented with low-complexity statistical models, which are comprised of only the important probabilistic dependencies in the datasets. Most methods attempt to reduce model complexity by enforcing structure sparseness. However, sparseness cannot describe inherent regularities in the structure. Hence, in this paper we first propose a new class of Gaussian graphical models which, together with sparseness, imposes local constancy through ${\ell}_1$-norm penalization. Second, we propose an efficient algorithm which decomposes the strictly convex maximum likelihood estimation into a sequence of problems with closed form solutions. Through synthetic experiments, we evaluate the closeness of the recovered models to the ground truth. We also test the generalization performance of our method in a wide range of complex real-world datasets and demonstrate that it can capture useful structures such as the rotation and shrinking of a beating heart, motion correlations between body parts during walking and functional interactions of brain regions. Our method outperforms the state-of-the-art structure learning techniques for Gaussian graphical models both for small and large datasets.
Differential Use of Implicit Negative Evidence in Generative and Discriminative Language Learning
Authors: Anne Hsu, Thomas L. Griffiths
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Sentence

A classic debate in cognitive science revolves around understanding how children learn complex linguistic rules, such as those governing  restrictions on verb alternations, without negative  evidence. Traditionally, formal learnability arguments have been used to claim that such learning is impossible without the aid of innate  language-specific knowledge. However, recently, researchers have shown  that statistical models are capable of learning complex rules from only  positive evidence. These two kinds of learnability analyses differ in their assumptions about the role of the distribution from which linguistic  input is generated.  The former analyses assume that learners seek to identify grammatical sentences in a way that is robust to the distribution  from which the sentences are generated, analogous to discriminative  approaches in machine learning. The latter assume that learners are trying  to estimate a generative model, with sentences being sampled from that  model. We show that these two learning approaches differ in their use of implicit negative evidence -- the absence of a sentence -- when learning  verb alternations, and demonstrate that human learners can produce results  consistent with the predictions of both approaches, depending on the  context in which the learning problem is presented.
Periodic Step Size Adaptation for Single Pass On-line Learning
Authors: Chun-Nan Hsu, Yu-Ming Chang, Hanshen Huang, Yuh-Jye Lee
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

It has been established that the second-order stochastic gradient descent (2SGD) method can potentially achieve generalization performance as well as empirical optimum in a single pass (i.e., epoch) through the training examples. However, 2SGD requires computing the inverse of the Hessian matrix of the loss function, which is prohibitively expensive. This paper presents Periodic Step-size Adaptation (PSA), which approximates the Jacobian matrix of the mapping function and explores a linear relation between the Jacobian and Hessian to approximate the Hessian periodically and achieve near-optimal results in experiments on a wide variety of models and tasks.