Project Progress Summary

Matthew Gray

April 30, 1998

I’m going to be looking at the gesture classification problem. Looking at the data, it appears to be a good candidate for clustering, as the classes are reasonably well seperated. Further, I wanted to try implementing an algorithm described in a paper I read.^{1} The paper uses a kernel approach to create a large feature space for principal component analysis, in a way similar to what is used in nonlinear Support Vector Machines. This algorithm is implemented for the paper. Also in the paper, it suggests this approach might be successful with clustering algorithms as well. Essentially the “trick” involves reformulating clustering (initially I will do non-linear k-means, and time permitting, nonlinear GMMs) in terms of the dot product of observations transformed into a high-dimensional feature space. Normally using such a high-dimensional feature space would be prohibitively expensive computationally. These dot products of features can be replaced with a kernel function, greatly reducing the computational complexity. As a preliminary exercise, I implemented straightforward linear k-means clustering as a guage of what kind of minimum performance could be expected. With 40 means, and without composing the observations into any sort of lag space, k-means gives 13% error on out-of-sample data, after assigning each cluster the class of its dominant population from the training set.

1“Nonlinear Component Analysis as a Kernel Eigenvalue Problem”, Bernhard Schölkopf, Alexander Smola, Klaus-Robert Müller, December 1996