Nando de Freitas and
Dan Huttenlocher
Many algorithms for statistical inference have a O(N^2) time dependence on the
size of the state space (N). For example, at the heart of the belief
propagation algorithm is an expensive operation called message passing. The
cost of this operation is O(nN^2), where n is the number of nodes in the
probabilistic graphical model and N is the number of discrete values the node
(random variable) takes. The N^2 component of the cost is particularly large
when we discretize a continuous state space using deterministic or Monte
Carlo grids.
**The N^2 cost arises whenever one computes a kernel density estimate**. In
addition to message passing, many other machine learning algorithms are
subject to this expensive operation. The list includes Gaussian processes, radial
basis networks, SVMs, particle smoothing, population Monte Carlo methods,
multidimensional scaling and kernel methods for dimensionality reduction,
classification, regression and semi-supervised learning. This cost also arises
when one is interested in the max operator (as in max belief propagation) and
nearest neighbour search.
In recent years, researchers in different communities (physics, numerical
computation, machine learning and computer vision) have put forward
algorithms to reduce this cost to O(NlogN) and even O(N) in some
cases. Examples of these techniques include fast multipole methods, the fast
Gauss transform, distance transforms,
kd-trees, ball trees, dual tree recursions and several
other more specialized techniques. The workshop will bring many of these
researchers together.
** The target audience is anyone who would like to see their favourite
machine learning algorithm running in seconds as opposed to hours or days.**