Fast Methods in Machine Learning

By Mike Klaas

I'm sure many of you have heard Nando talking about "fast methods" in machine learning. I will be giving an overview of what fast methods are, where they can be applied, and briefly describe the my work in this area.
The abstract from the NIPS workshop Nando organized should provide a slightly more detailed idea of what I'll be talking about:

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.

Back to the LCI Forum page