Efficient Multiscale Sampling from Products of Gaussian Mixtures

Published 9 December 2003

Alexander Ihler, Erik B. Sudderth, William T. Freeman, Alan S. Willsky

Citations85

TL;DR

Two multi-scale samplers for sampling from a product of Gaussian mixtures are developed, a multiscale variant of previously proposed Monte Carlo techniques, with comparable theoretical guarantees but improved empirical convergence rates.

Abstract

The problem of approximating the product of several Gaussian mixture distributions arises in a number of contexts, including the nonparametric belief propagation (NBP) inference algorithm and the training of product of experts models. This paper develops two multiscale algorithms for sampling from a product of Gaussian mixtures, and compares their performance to existing methods. The first is a multiscale variant of previously proposed Monte Carlo techniques, with comparable theoretical guarantees but improved empirical convergence rates. The second makes use of approximate kernel density evaluation methods to construct a fast approximate sampler, which is guaranteed to sample points to within a tunable parameter # of their true probability. We compare both multiscale samplers on a set of computational examples motivated by NBP, demonstrating significant improvements over existing methods.

Keywords

Computer ScienceMathematics

IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images

17,980 Citations1984Stuart Geman, Donald Geman

The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.

Density Estimation for Statistics and Data Analysis

15,768 Citations2018B.W. Silverman

Sequential Monte Carlo Methods in Practice

7,410 Citations2001Arnaud Doucet

This book presents the first comprehensive treatment of Monte Carlo techniques, including convergence results and applications to tracking, guidance, automated target recognition, aircraft navigation, robot navigation, econometrics, financial modeling, neural networks, optimal control, optimal filtering, communications, reinforcement learning, signal enhancement, model averaging and selection.

View PDF

Neural ComputationTraining Products of Experts by Minimizing Contrastive Divergence

5,017 Citations2002Geoffrey E. Hinton

A product of experts (PoE) is an interesting candidate for a perceptual system in which rapid inference is vital and generation is unnecessary because it is hard even to approximate the derivatives of the renormalization term in the combination rule.

Nonparametric belief propagation

422 Citations2003Erik B. Sudderth, Alexander Ihler +2 more

PAMPAS: real-valued graphical models for computer vision

191 Citations2003Michael Isard

This paper combines belief propagation with ideas from particle filtering; the resulting algorithm performs inference on graphs containing both cycles and continuous-valued latent variables with general conditional probability distributions, which has wide applicability in the computer vision domain.

BiometrikaGeneralised Gibbs sampler and multigrid Monte Carlo for Bayesian computation

150 Citations2000Jun S. Liu

The generalised Gibbs sampler provides a framework encompassing a class of recently proposed tricks such as parameter expansion and reparameterisation and is applied to Bayesian inference problems for nonlinear state-space models, ordinal data and stochastic differential equations with discrete observations.

International Joint Conference on Artificial IntelligenceMultiresolution instance-based learning

70 Citations1995Kan Deng, Andrew Moore

A new way of structuring a database and a new algorithm for accessing it is presented and evaluated that maintains the advantages ot instance-based learning and permits the same flexibility as a conventional linear search but at greatly reduced computational cost.

SIAM Journal on Scientific and Statistical ComputingThe Fast Gauss Transform with Variable Scales

59 Citations1991John Strain

This algorithm evaluates the sum of N Gaussians at M arbitrarily distributed points in C(N + M) work, where C depends only on the precision required and the essential minimum of the scales.

Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Processes

42 Citations1999Sebastian Thrun, John Langford +1 more

It is proved that under mild assumptions, Monte Carlo Hidden Markov Models converge to a local maximum in likelihood space, just like conventional HMMs.