We present Local Naive Bayes Nearest Neighbor, an improvement to the NBNN
image classification algorithm that increases classification accuracy and
improves its ability to scale to large numbers of object classes. The key
observation is that only the classes represented in the local neighborhood of a
descriptor contribute significantly and reliably to their posterior probability
estimates. Instead of maintaining a separate search structure for each class,
we merge all of the reference data together into one search structure, allowing
quick identification of a descriptor's local neighborhood. We show an increase
in classification accuracy when we ignore adjustments to the more distant
classes and show that the run time grows with the log of the number of classes
rather than linearly in the number of classes as did the original. This gives a
100 times speed-up over the original method on the Caltech 256 dataset. We also
provide the first head-to-head comparison of NBNN against spatial pyramid
methods using a common set of input features. We show that local NBNN
outperforms all previous NBNN based methods and the original spatial pyramid
model. However, we find that local NBNN, while competitive with, does not beat
state-of-the-art spatial pyramid methods that use local soft assignment and
max-pooling.

本文提出了 Local Naive Bayes Nearest Neighbor 方法，以提高图像分类算法的准确性和拓展性，该方法将所有参考数据合并成一个搜索结构进行快速搜索，并证明此方法可在 Caltech 256 数据集上带来 100 倍的速度提升。同时，也将 NBNN 与空间金字塔方法进行了头对头比较。本文发现，Local NBNN 方法表现优于以往的 NBNN 方法和原始空间金字塔模型，但仍不及使用本地软分配和 max-pooling 的最先进空间金字塔方法。