pwc-archive/papers-with-abstracts huggingface dataset:
Kernel Embeddings of Latent Tree Graphical Models
Authors: Le Song, Eric P. Xing, Ankur P. Parikh
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Latent tree graphical models are natural tools for expressing long range and hierarchical dependencies among many variables which are common in computer vision, bioinformatics and natural language processing problems. However, existing models are largely restricted to discrete and Gaussian variables due to computational constraints; furthermore, algorithms for estimating the latent tree structure and learning the model parameters are largely restricted to heuristic local search. We present a method based on kernel embeddings of distributions for latent tree graphical models with continuous and non-Gaussian variables. Our method can recover the latent tree structures with provable guarantees and perform local-minimum free parameter learning and efficient inference. Experiments on simulated and real data show the advantage of our proposed approach.
Inference in continuous-time change-point models
Authors: Florian Stimberg, Manfred Opper, Guido Sanguinetti, Andreas Ruttor
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Bayesian Inference, valid

We consider the problem of Bayesian inference for continuous time multi-stable stochastic systems which can change both their diffusion and drift parameters at discrete times. We propose exact inference and sampling methodologies for two specific cases where the discontinuous dynamics is given by a Poisson process and a two-state Markovian switch. We test the methodology on simulated data, and apply it to two real data sets in finance and systems biology. Our experimental results show that the approach leads to valid inferences and non-trivial insights.
High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity
Authors: Po-Ling Loh, Martin J. Wainwright
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Although the standard formulations of prediction problems involve fully-observed and noiseless data drawn in an i.i.d. manner, many  applications involve noisy and/or missing data, possibly involving dependencies. We study these issues in the context of high-dimensional  sparse linear regression, and propose novel estimators for the cases of noisy, missing, and/or dependent data. Many standard approaches to noisy or missing data, such as those using the EM algorithm, lead to optimization problems that are inherently non-convex, and it is difficult to establish theoretical guarantees on practical algorithms. While our approach also involves optimizing non-convex programs, we are able to both analyze the statistical error associated with any global optimum, and prove that a simple projected gradient descent algorithm will converge in polynomial time to a small neighborhood of the set of global minimizers. On the statistical side, we provide non-asymptotic bounds that hold with high probability for the cases of noisy, missing, and/or dependent data. On the computational side, we prove that under the same types of conditions required for statistical consistency, the projected gradient descent algorithm will converge at geometric rates to a near-global minimizer. We illustrate these theoretical predictions with simulations, showing agreement with the predicted scalings.
Exploiting spatial overlap to efficiently compute appearance distances between image windows
Authors: Bogdan Alexe, Viviana Petrescu, Vittorio Ferrari
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We present a computationally efficient technique to compute the distance of high-dimensional appearance descriptor vectors between image windows.  The method exploits the relation between appearance distance and spatial overlap.  We derive an upper bound on appearance distance given the spatial overlap of two windows in an image,  and use it to bound the distances of many pairs between two images.  We propose algorithms that build on these basic operations to efficiently solve tasks relevant to many computer vision applications, such as finding all pairs of windows between two images with distance smaller than a threshold,  or finding the single pair with the smallest distance. In experiments on the PASCAL VOC 07 dataset, our algorithms accurately solve these problems while greatly reducing the number of appearance distances computed, and achieve larger speedups than approximate nearest neighbour algorithms based on trees [18]and on hashing [21].    For example, our algorithm finds the most similar pair of windows between two images while computing only 1% of all distances on average.
Accelerated Adaptive Markov Chain for Partition Function Computation
Authors: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We propose a novel Adaptive Markov Chain Monte Carlo algorithm to  compute the partition function. In particular, we show how to  accelerate a flat histogram sampling technique by significantly  reducing the number of ``null moves'' in the chain, while maintaining  asymptotic convergence properties. Our experiments show that our  method converges quickly to highly accurate solutions on a range of  benchmark instances, outperforming other state-of-the-art methods such  as IJGP, TRW, and Gibbs sampling both in run-time and accuracy. We  also show how obtaining a so-called density of states distribution  allows for efficient weight learning in Markov Logic theories.
Repeated Games against Budgeted Adversaries
Authors: Jacob D. Abernethy, Manfred K. Warmuth
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We study repeated zero-sum games against an adversary on a budget. Given that an adversary has some constraint on the sequence of actions that he plays, we consider what ought to be the player's best mixed strategy with knowledge of this budget. We show that, for a general class of normal-form games, the minimax strategy is indeed efficiently computable and relies on a random playout" technique. We give three diverse applications of this algorithmic template: a cost-sensitive "Hedge" setting, a particular problem in Metrical Task Systems, and the design of combinatorial prediction markets."
Towards Property-Based Classification of Clustering Paradigms
Authors: Margareta Ackerman, Shai Ben-David, David Loker
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Classification, Clustering, General Classification

Clustering is a basic data mining task with a wide variety of applications. Not surprisingly, there exist many clustering algorithms. However, clustering is an ill defined problem - given a data set, it is not clear what a “correct” clustering for that set is. Indeed, different algorithms may yield dramatically different outputs for the same input sets. Faced with a concrete clustering task, a user needs to choose an appropriate clustering algorithm. Currently, such decisions are often made in a very ad hoc, if not completely random, manner. Given the crucial effect of the choice of a clustering algorithm on the resulting clustering, this state of affairs is truly regrettable. In this paper we address the major research challenge of developing tools for helping users make more informed decisions when they come to pick a clustering tool for their data. This is, of course, a very ambitious endeavor, and in this paper, we make some first steps towards this goal. We propose to address this problem by distilling abstract properties of the input-output behavior of different clustering paradigms.  In this paper, we demonstrate how abstract, intuitive properties of clustering functions can be used to taxonomize a set of popular clustering algorithmic paradigms. On top of addressing deterministic clustering algorithms, we also propose similar properties for randomized algorithms and use them to highlight functional differences between different common implementations of k-means clustering. We also study relationships between the properties, independent of any particular algorithm. In particular, we strengthen Kleinbergs famous impossibility result, while providing a simpler proof.
Tree-Structured Stick Breaking for Hierarchical Data
Authors: Zoubin Ghahramani, Michael. I. Jordan, Ryan P. Adams
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Bayesian Inference, Clustering

Many data are naturally modeled by an unobserved hierarchical structure. In this paper we propose a flexible nonparametric prior over unknown data hierarchies. The approach uses nested stick-breaking processes to allow for trees of unbounded width and depth, where data can live at any node and are infinitely exchangeable. One can view our model as providing infinite mixtures where the components have a dependency structure corresponding to an evolutionary diffusion down a tree. By using a stick-breaking approach, we can apply Markov chain Monte Carlo methods based on slice sampling to perform Bayesian inference and simulate from the posterior distribution on trees. We apply our method to hierarchical clustering of images and topic modeling of text data.
Sparse Instrumental Variables (SPIV) for Genome-Wide Studies
Authors: Paul Mckeigue, Jon Krohn, Amos J. Storkey, Felix V. Agakov
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

This paper describes a probabilistic framework for studying associations between multiple genotypes, biomarkers, and phenotypic traits in the presence of noise and unobserved confounders for large genetic studies. The framework builds on sparse linear methods developed for regression and modified here for inferring causal structures of richer networks with latent variables. The method is motivated by the use of genotypes as ``instruments'' to infer causal associations between phenotypic biomarkers and outcomes, without making the common restrictive assumptions of instrumental variable methods. The method may be used for an effective screening of potentially interesting genotype phenotype and biomarker-phenotype associations in genome-wide studies, which may have important implications for validating biomarkers as possible proxy endpoints for early stage clinical trials. Where the biomarkers are gene transcripts, the method can be used for fine mapping of quantitative trait loci (QTLs) detected in genetic linkage studies. The method is applied for examining effects of gene transcript levels in the liver on plasma HDL cholesterol levels for a sample of sequenced mice from a heterogeneous stock, with $\sim 10^5$ genetic instruments and $\sim 47 \times 10^3$ gene transcripts.
Fast global convergence rates of gradient methods for high-dimensional statistical recovery
Authors: Alekh Agarwal, Sahand Negahban, Martin J. Wainwright
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Computational Efficiency, regression

Many statistical $M$-estimators are based on convex optimization problems formed by the weighted sum of a loss function with a norm-based regularizer.  We analyze the convergence rates of first-order gradient methods for solving such problems within a high-dimensional framework that allows the data dimension $d$ to grow with (and possibly exceed) the sample size $n$.  This high-dimensional structure precludes the usual global assumptions---namely, strong convexity and smoothness conditions---that underlie classical optimization analysis.  We define appropriately restricted versions of these conditions, and show that they are satisfied with high probability for various statistical models.  Under these conditions, our theory guarantees that Nesterov's first-order method~\cite{Nesterov07} has a globally geometric rate of convergence up to the statistical precision of the model, meaning the typical Euclidean distance between the true unknown parameter $\theta^*$ and the optimal solution $\widehat{\theta}$.  This globally linear rate is substantially faster than previous analyses of global convergence for specific methods that yielded only sublinear rates.  Our analysis applies to a wide range of $M$-estimators and statistical models, including sparse linear regression using Lasso ($\ell_1$-regularized regression), group Lasso, block sparsity, and low-rank matrix recovery using nuclear norm regularization.  Overall, this result reveals an interesting connection between statistical precision and computational efficiency in high-dimensional estimation.
Learning Multiple Tasks using Manifold Regularization
Authors: Arvind Agarwal, Samuel Gerber, Hal Daume
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We present a novel method for multitask learning (MTL) based on {\it manifold regularization}: assume that all task parameters lie on a manifold. This is the generalization of a common assumption made in the existing literature: task parameters share a common {\it linear} subspace. One proposed method uses the projection distance from the manifold to regularize the task parameters. The manifold structure and the task parameters are learned using an alternating optimization framework. When the manifold structure is fixed, our method decomposes across tasks which can be learnt independently. An approximation of the manifold regularization scheme is presented that preserves the convexity of the single task learning problem, and makes the proposed MTL framework efficient and easy to implement. We show the efficacy of our method on several datasets.
Switched Latent Force Models for Movement Segmentation
Authors: Mauricio Alvarez, Jan R. Peters, Neil D. Lawrence, Bernhard Schölkopf
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Latent force models encode the interaction between multiple related dynamical systems in the form of a kernel or covariance function. Each variable to be modeled is represented as the output of a differential equation and each differential equation is driven by a weighted sum of latent functions with uncertainty given by a Gaussian process prior. In this paper we consider employing the latent force model framework for the problem of determining robot motor primitives. To deal with discontinuities in the dynamical systems or the latent driving force we introduce an extension of the basic latent force model, that switches between different latent functions and potentially different dynamical systems. This creates a versatile representation for robot movements that can capture discrete changes and non-linearities in the dynamics. We give illustrative examples on both synthetic data and for striking movements recorded using a Barrett WAM robot as haptic input device. Our inspiration is robot motor primitives, but we expect our model to have wide application for dynamical systems including models for human motion capture data and systems biology.
A POMDP Extension with Belief-dependent Rewards
Authors: Mauricio Araya, Olivier Buffet, Vincent Thomas, Françcois Charpillet
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Decision Making, Sequential Decision Making

Partially Observable Markov Decision Processes (POMDPs) model sequential decision-making problems under uncertainty and partial observability. Unfortunately, some problems cannot be modeled with state-dependent reward functions, e.g., problems whose objective explicitly implies reducing the uncertainty on the state. To that end, we introduce rho-POMDPs, an extension of POMDPs where the reward function rho depends on the belief state. We show that, under the common assumption that rho is convex, the value function is also convex, what makes it possible to (1) approximate rho arbitrarily well with a piecewise linear and convex (PWLC) function, and (2) use state-of-the-art exact or approximate solving algorithms with limited changes.
Global seismic monitoring as probabilistic inference
Authors: Nimar Arora, Stuart J. Russell, Paul Kidwell, Erik B. Sudderth
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Bayesian Inference

The International Monitoring System (IMS) is a global network of sensors whose purpose is to identify potential violations of the Comprehensive Nuclear-Test-Ban Treaty (CTBT), primarily through detection and localization of seismic events. We report on the first stage of a project to improve on the current automated software system with a Bayesian inference system that computes the most likely global event history given the record of local sensor data. The new system, VISA (Vertically Integrated Seismological Analysis), is based on empirically calibrated, generative models of event occurrence, signal propagation, and signal detection. VISA exhibits significantly improved precision and recall compared to the current operational system and is able to detect events that are missed even by the human analysts who post-process the IMS output.
Learning invariant features using the Transformed Indian Buffet Process
Authors: Joseph L. Austerweil, Thomas L. Griffiths
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Identifying the features of objects becomes a challenge when those features can change in their appearance. We introduce the Transformed Indian Buffet Process (tIBP), and use it to define a nonparametric Bayesian model that infers features that can transform across instantiations. We show that this model can identify features that are location invariant by modeling a previous experiment on human feature learning. However, allowing features to transform adds new kinds of ambiguity: Are two parts of an object the same feature with different transformations or two unique features? What transformations can features undergo? We present two new experiments in which we explore how people resolve these questions, showing that the tIBP model demonstrates a similar sensitivity to context to that shown by human learners when determining the invariant aspects of features.
Supervised Clustering
Authors: Pranjal Awasthi, Reza B. Zadeh
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Clustering

Despite the ubiquity of clustering as a tool in unsupervised learning, there is not yet a consensus on a formal theory, and the vast majority  of work in this direction has focused on unsupervised clustering. We study a recently proposed framework for supervised clustering where there is access to a teacher. We give an improved generic algorithm to cluster any concept class  in that model. Our algorithm is query-efficient in the sense that it involves only a small amount  of interaction with the teacher. We also present and study two natural generalizations of the model.  The model assumes that the teacher response to the algorithm is perfect. We eliminate  this limitation by proposing a noisy model and give an algorithm for  clustering the class of intervals in this noisy model. We also propose a dynamic model where the teacher sees  a random subset of the points. Finally, for datasets  satisfying a spectrum of weak to strong properties, we give query bounds, and show that a class  of clustering functions containing Single-Linkage will find the target clustering under the strongest  property.
Occlusion Detection and Motion Estimation with Convex Optimization
Authors: Alper Ayvaci, Michalis Raptis, Stefano Soatto
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Motion Estimation, Optical Flow Estimation

We tackle the problem of simultaneously detecting occlusions and estimating optical flow. We show that, under standard assumptions of Lambertian reflection and static illumination, the task can be posed as a convex minimization problem. Therefore, the solution, computed using efficient algorithms, is guaranteed to be globally optimal, for any number of independently moving objects, and any number of occlusion layers. We test the proposed algorithm on benchmark datasets, expanded to enable evaluation of occlusion detection performance.
Batch Bayesian Optimization via Simulation Matching
Authors: Javad Azimi, Alan Fern, Xiaoli Z. Fern
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Bayesian Optimization

Bayesian optimization methods are often used to optimize unknown functions that are costly to evaluate. Typically, these methods sequentially select inputs to be evaluated one at a time based on a posterior over the unknown function that is updated after each evaluation. There are a number of effective sequential policies for selecting the individual inputs. In many applications, however, it is desirable to perform multiple evaluations in parallel, which requires selecting batches of multiple inputs to evaluate at once. In this paper, we propose a novel approach to batch Bayesian optimization, providing a policy for selecting batches of inputs with the goal of optimizing the function as efficiently as possible. The key idea is to exploit the availability of high-quality and efficient sequential policies, by using Monte-Carlo simulation to select input batches that closely match their expected behavior. To the best of our knowledge, this is the first batch selection policy for Bayesian optimization. Our experimental results on six benchmarks show that the proposed approach significantly outperforms two baselines and can lead to large advantages over a top sequential approach in terms of performance per unit time.
Structured sparsity-inducing norms through submodular functions
Authors: Francis R. Bach
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Sparse methods for supervised learning aim at finding good linear predictors from as few variables as possible, i.e., with small cardinality of their supports. This combinatorial selection problem is often turned into a convex optimization problem by replacing the cardinality function by its convex envelope (tightest convex lower bound), in this case the L1-norm. In this paper, we investigate more general set-functions than the cardinality, that may incorporate prior knowledge or structural constraints which are common in many applications: namely, we show that for nondecreasing submodular set-functions, the corresponding convex envelope can be obtained from its Lovasz extension, a common tool in submodular analysis. This defines a family of polyhedral norms, for which we provide generic algorithmic tools (subgradients and proximal operators) and theoretical results (conditions for support recovery or high-dimensional inference). By selecting specific submodular functions, we can give a new interpretation to known norms, such as those based on rank-statistics or grouped norms with potentially overlapping groups; we also define new norms, in particular ones that can be used as non-factorial priors for supervised learning.
A Bayesian Approach to Concept Drift
Authors: Stephen Bach, Mark Maloof
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Change Point Detection

To cope with concept drift, we placed a probability distribution over the location of the most-recent drift point. We used Bayesian model comparison to update this distribution from the predictions of models trained on blocks of consecutive observations and pruned potential drift points with low probability. We compare our approach to a non-probabilistic method for drift and a probabilistic method for change-point detection. In our experiments, our approach generally yielded improved accuracy and/or speed over these other methods.