Relationship between SVMs vs kNN

Suppose you have a training dataset T = {(x_i,y_i) for i = 1...N}, where each x is the multi-dimensional input, and each y is a binary output (+1 or -1).

If you're using Gaussian kernels, then the K-NN classifier is

h(x) = sum( y_i * k(x,x_i) for (x_i,y_i) in N(x)),

where N(x) is the K closest training points to x and k(.,.) is the Gaussian kernel. The predicted output is the sign of h(x).

The SVM classifier is

h(x) = sum( y_i * a_i * k(x,x_i) forall (x_i,y_i) in T),

where the vector of (a_i) variables is the model learned by the SVM training algorithm (also known as the dual variables). The predicted output is again the sign of h(x).

So the two classifiers are structurally similar. The K-NN classifier only looks at the K closest training points to the input point x, and weights them by their kernel similarity to x. The SVM classifier globally weights all the training points using the learned model (a_i), and multiplies that to the kernel similarity of each training point to x.

In other words, if you want to phrase the K-NN classifier in the exact form of the SVM classifier, then the K-NN classifer sets a_i = 1 for every x_i in N(x) and 0 otherwise (this is done uniquely for every input x, whereas the a_i model parameters learned by the SVM are global and fixed after training).

In a vaguely general sense, I can see this being true.

kNN is a clustering algorithm, so you're classifying (or whatever) based on how close something falls to the centroid of a cluster.

SVMs, on the other hand, use 'clusters' that are chosen not by the centroid of a particular region of input space but rather a hyperplane that segregates one region from another.

At the heart of it, though, both systems employ a mechanism whereby you're comparing one sample to another to measure how similar they are to each-other. In kNN it's [usually] some sort of distance metric; one of the simplest examples is the L2 norm, which uses a simple inner product to induce a metric on the vector space of inputs.

SVMs do the same thing, but the inner product used can vary quite a bit. For example, for inputs that have temporal behaviors, you can use a convolution of one sample with another, then square & sum the results. The resulting value is a symmetric semi-definite inner product -- but the same inner product could be used for kNN, if appropriately adapted.

The main difference -- and you'll hopefully forgive my lack of experience with kNN here, I'm sure I'll botch something as I have only studied that algorithm, not implemented it -- between them is the 'kernel trick', and the fact that kNN works off clustering not partitioning regions of input space. However, I seem to recall seeing some clustering techniques that make use of the kernel trick.

-Brian