Object Classification using pyramid match kernel

Question

I have been reading up on the pyramid match kernel as an alternative to using the bag-of-words model for object classification using a SVM. The bag-of-words model provides a model for transforming a set of features to a single feature vector, however im confused as to how the pyramid match kernel can be used for this task, for instant if a SVM has been trained using a pyramid match kernel how do I present a test image represented by a set of feature vectors to the SVM as, as far as I can tell the kernel generates some feature space F(x) but provides no mapping to this space. Could someone please give a brief description of how this works?

Answer 1

The pyramid match kernel does not operate on the sets of feature vectors directly. It operates on multi-level histograms of feature vectors. Let's say you are using the SIFT descriptors, which live in 128-dimensional space. First you divide each dimension into 2 bins, which divides the entire feature space into $2^{128}$ bins. Then you count how many features fall into each bin. This is the first level of your histogram. Then you divide each dimension into 4 bins, and so on. Luckily, this histogram is going to be very sparse, so you only need to allocate the memory for non-zero bins.

You do this for the training images, and the images that you want to classify. Then the pyramid match kernel is simply the intersection of two histograms.