SVM-KNN: Discriminative Nearest Neighbor Classification for Visual Category Recognition

We consider visual category recognition in the framework of measuring similarities, or equivalently perceptual distances, to prototype examples of categories. This approach is quite flexible, and permits recognition based on color, texture, and particularly shape, in a homogeneous framework. While nearest neighbor classifiers are natural in this setting, they suffer from the problem of high variance (in bias-variance decomposition) in the case of limited sampling. Alternatively, one could use support vector machines but they involve time-consuming optimization and computation of pairwise distances. We propose a hybrid of these two methods which deals naturally with the multiclass setting, has reasonable computational complexity both in training and at run time, and yields excellent results in practice. The basic idea is to find close neighbors to a query sample and train a local support vector machine that preserves the distance function on the collection of neighbors. Our method can be applied to large, multiclass data sets for which it outperforms nearest neighbor and support vector machines, and remains efficient when the problem becomes intractable for support vector machines. A wide variety of distance functions can be used and our experiments show state-of-the-art performance on a number of benchmark data sets for shape and texture classification (MNIST, USPS, CUReT) and object recognition (Caltech- 101). On Caltech-101 we achieved a correct classification rate of 59.05%(±0.56%) at 15 training images per class, and 66.23%(±0.48%) at 30 training images.

1. Introduction

While the field of visual category recognition has seen rapid progress in recent years, much remains to be done to reach human level performance. The best current approaches can deal with 100 or so categories, e.g. the CUReT dataset for materials, and the Caltech-101 dataset for objects; this is still a long way from the the estimate of 30,000 or so categories that humans can distinguish. Another significant feature of human visual recognition is that it can be trained with very few examples, cf. machine learning approaches to digits and faces currently require hundreds if not thousands of examples.