Fast Classification with Binary Prototypes
[edit]
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:12551263, 2017.
Abstract
In this work, we propose a new technique for \emphfast knearest neighbor (kNN) classification in which the original database is represented via a small set of learned binary prototypes. The training phase simultaneously learns a hash function which maps the data points to binary codes, and a set of representative binary prototypes. In the prediction phase, we first hash the query into a binary code and then do the kNN classification using the binary prototypes as the database. Our approach speeds up kNN classification in two aspects. First, we compress the database into a smaller set of prototypes such that kNN search only goes through a smaller set rather than the whole dataset. Second, we reduce the original space to a compact binary embedding, where the Hamming distance between two binary codes is very efficient to compute. We propose a formulation to learn the hash function and prototypes such that the classification error is minimized. We also provide a novel theoretical analysis of the proposed technique in terms of Bayes error consistency. Empirically, our method is much faster than the stateoftheart kNN compression methods with comparable accuracy.
Related Material


