Boosting k-NN for large scale image classification

Speaker: Michel Barlaud, professeur émérite, membre senior de l'Institut Universitaire de France at Université de Nice-Sophia Antipolis, Nice, France

Recent works show that large scale image classification problems rule out computationally demanding methods. On such problems, simple approaches like k-NN are affordable contenders, still with room space for statistical improvements. We first present algorithm UNN, showing how to leverage k-NN to yield a formal boosting algorithm. Second, we propose N3, an Adaptive Newton-Raphson scheme to leverage k-NN. We show that it is a boosting algorithm, with several key algorithmic and statistical properties. N3 brings efficient estimators of posteriors at no additional cost. We propose a divide and conquer algorithm in order to cope with the classical curse of dimensionality of NN search. Experiments are provided on the SUN, Caltech and ImageNet databases. They confirm that boosting a subsample — sometimes containing few examples only — is sufficient to reach the convergence regime of N3. Under such conditions, N3 challenges the accuracy of much more computationally demanding contenders.

Published on : Friday 24 October 2014