Open Collections

Exorcising N2 stigmata in Sequential Monte Carlo

University of British Columbia

Sequential Monte Carlo (SMC) has, since being "rediscovered" in the early 1990's, become one of the most important inference techniques in machine learning. It enjoys a prominent place in statistics, robotics, quantum physics, as well as control and other industrial applications. SMC methods represent probability densities as a dicrete set of N Dirac masses called particles. This non-parametric representation provably converges to the true distribution of interest and is effective in high dimensional applications. Many sophisticated SMC algorithms require 0(N2) computation, which is viewed as impractically-expensive by researchers in the field. Hence, N2 SMC algorithms possess what we call "N2 stigmata"—they are simply "too slow." This thesis aims to exorcise these stigmata. We present a survey of areas where these algorithms occur and show that in every case their expense results from having to compute a sum-kernel or max-kernel operation. Both are of a class of operations called iV-body problems which occur in physics, statistics, and machine learning. We show how the techniques developed in this field can be used to accelerate sum- and max-kernel (and consequently the SMC algorithms), reducing the cost to 0(Nlog N)—in some cases O(N). Using these methods, iV2 Monte Carlo algorithms should be applicable in a much wider range of settings. Along the way, we introduce new SMC algorithms for marginal filtering and a novel algorithm for drastically accelerating max-kernel.

Text

2009-12-11

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/16586

Computer Science

University of British Columbia

UBCV

DSpace