Nonparametric Belief Propagation with Fast Methods. Alexander Ihler
Nonparametric Belief Propagation (NBP) provides a Monte Carlo
(sample-based) approximation to Belief Propagation (BP) for continuous,
non-Gaussian distributions defined on arbitrary graphical models. NBP
approximates each BP message using a kernel density estimate, specifically
a Gaussian mixture distribution (and is thus similar to regularized
particle filtering on Markov Chains). We have applied NBP successfully in
several problems, including distributed inference in sensor networks and
video tracking of articulated models.
Because NBP makes heavy use of kernel density estimates, fast methods and
approximations play a key role in its practical use. In particular,
drawing samples from the product of d Gaussian mixtures is an extremely
costly procedure (naively O(N^d)). Using multipole-like methods one may
reduce this cost to (asymptotically) O(N). Fast density approximation
techniques may also be applied to render the algorithm more
Distance Transforms of Sampled Functions. Daniel Huttenlocher
A distance transform of a binary image specifies for each 0-valued pixel the
distance to the nearest 1-valued pixel (or vice versa). This tutorial will
describe a generalization of distance transforms to arbitrary sampled
functions rather than binary functions and will then provide simple,
efficient algorithms for computing them. These algorithms are applicable to
computing classical distance transforms of binary images as well as to
solving a broad class of minimization problems involving a cost function with
both local and spatial terms. Alternatively the techniques can be viewed in
terms of the minimum convolution of two functions, which is an important
operation in grayscale morphology. The methods are also applicable to Viterbi
decoding, belief propagation and optimal control.
Fast High-Dimensional Feature Indexing for Object Recognition. David Lowe (UBC)
The best current methods for object recognition extract many
high-dimensional local features from each image and then compare each
feature against a large database of features from many training images.
This talk will discuss practical methods for solving this
high-dimensional indexing problem. The most successful methods found
so far have been those using approximate variants of k-d tree lookup.
These can find almost all useful matches while providing at least 4
orders of magnitude efficiency improvement over the best known methods
for exact matching. One reason for the success is that matches are
useful only when they are significantly closer than would be predicted
by the local density of non-matching neighbors. The result is that
the high-dimensional feature indexing problem can be solved in
practice even for real-time systems and for very large databases.
Tutorial on Statistical N-Body Problems and Proximity Data Structures.
Alex Gray (CMU)
First I will give an overview of adaptive tree data structures which can
be used to make statistical computations go fast. I will describe the
results of a recently-completed thorough experimental comparison
of the best-known data structures for nearest-neighbor search,
comparing over 30 different methods.
I'll survey some important generalized N-body problems which arise in
statistical learning, including kernel density estimation,
all-nearest-neighbors, Gaussian process regression, local polynomial
regression, n-point correlations, nonparametric Bayes classification,
and several others.
Then I will describe the dual-tree (or multi-tree) framework for
developing fast linear-time algorithms for statistical N-body
problems, including how it generalizes and extends work in
computational geometry, spatial databases, and computational
physics. I'll also explain why this new approach is more appropriate
suited to statistical problems than the classical approaches used for
N-body problems in physics. I'll then give several examples of how to
use the framework to create fast methods for the various problems above
requiring different twists, highlighting the new idea needed for each. These
examples will also illustrate several exciting open questions which I
will pose for the workshop.
Fast High-dimensional Function Integration, without Markov Chains.
Alex Gray (CMU)
I will present a new method for integration of high-dimensional
functions, which is not based on Markov chain theory. Instead, I
develop from 'first principles' (of Monte Carlo theory), a new
framework in which the integration problem is cast explicitly as a
problem of statistical estimation, or 'reconstruction' of the function
from samples. The method uses a nonparametric regression estimator
which directly minimizes integration error, rather than some loss
function which is disconnected from the goal, as have been proposed by
some. The main computational sub-problem is approached using
custom-designed N-body algorithms based on a recently-developed
generalized framework for such problems. The resulting method
addresses the two main issues of the Metropolis-Hastings method: Its
parameter selection is automatic and optimal, and it produces iid
samples, making it easier to understand its behavior. It is also more
general - for example it can directly integrate the normalizing
constant arising in Bayesian inference and statistical mechanics. A
head-to-head experimental comparison with MCMC on canonical challenge
functions will illustrate the new method's practical viability. More
largely, characterizing integration as statistical learning opens the
door to a host of powerful mathematical and computational tools beyond
those of Markov chain theory.
Tutorial on Fast Multipole Methods and the FGT. Ramani Duraiswami (University of Maryland)
The fast multipole method has been called one of the ten most significant
numerical algorithms discovered in the 20th century, and won its inventors,
Vladimir Rokhlin and Leslie Greengard, the Steele prize. The algorithm
allows the product of particular dense matrices with a vector to be
evaluated in O(N logN) operations, when direct multiplication requires
O(N2) operations. Coupled with advances in iterative methods for solution
of linear systems, they allow O(N logN) time complexity and O(N) memory
complexity solution of problems that hitherto required O(N3) time
complexity and O(N2) memory complexity. I will discuss the general ideas of
the method, and provide some specific examples of its application.
One particular application, and that which is important to density
estimation techniques, is the fast Gauss transform. Unfortunately, the cost
of a direct extension of the FGT to higher-dimensional problems grows
exponentially with dimension (the curse of dimensionality). We introduce an
improved version of the fast Gauss transform to efficiently estimate sums of
Gaussians in higher dimensions. Our proposed algorithm incorporates three
innovations that dramatically improve the performance: a multivariate Taylor
expansion scheme, a pyramid-like data structure to store and manipulate the
expansions, and an adaptive space subdivision technique based on the
k-center algorithm. These innovations result in an algorithm that is much
faster and has been demonstrated in dimensions up to ten.
The fast Gauss transform has been applied to the kernel density estimation
(KDE), to the mean shift algorithm for clustering, where it improves the
quadratic complexity of each iteration, and to kernel machines. We present
results from these applications.