7th November 2006 — Space-partitioning data structures

Ed and Iain will work through some examples of speeding up standard machine learning algorithms through space-partitioning data structures. In particular we’ll discuss speeding up nearest neighbour search, k-means, and the extent to which regression problems can be improved.

Basically we will touch on some of the ideas in this tutorial: Data structures for fast statistics, Alexander Gray and Andrew Moore, School of Computer Science, Carnegie Mellon University, 2004, a tutorial presented at ICML.

An example paper to read is: Efficient locally weighted polynomial regression predictions, Andrew Moore, Jeff Schneider and Kan Deng, Fourteenth International Conference on Machine Learning, D. Fisher (editor), 236–244, 1997.

Also relevant:

…and many others. Note we will not include more recent work using analytic expansions of kernels.