EE Seminar: Supervised K-means in Hamming Space
Speaker: Inbal Lavi
M.Sc. student under the supervision of Prof. Shai Avidan and Prof. Yacov Hel Or
Wednesday, April 17th, 2019 at 15:30
Room 011, Kitot Bldg., Faculty of Engineering
Supervised K-means in Hamming Space
Abstract
The k-means approach is a common scheme for unsupervised learning, used for clustering, data representation, compression, and more. K-means in Hamming spaces is an instance of k-means where binary codes are sought for a set of data points in Rd and their k representative centers satisfying some desired properties. These can be used to apply fast approximation of nearest-neighbor search (ANN) or as an alternative to standard k-means when the number of data points is too large.
In this work we propose Supervised K-means in Hamming Space, enabling fast and efficient classification using Nearest Neighbor classification. The main goal of this approach is to provide a set of k binary codes (centers) along with their labels, and a set of hashing functions that will correctly classify new data points using nearest-neighbor search against the k centers. This approach is most important in classification problems applied in embedding spaces, used for tasks such as face recognition, where nearest-neighbor search is repeatedly applied to classify a data point in high-dimensional embedding space. Our algorithm, called Class Preserving Code, allows for accurate nearest neighbor classification on large numbers of classes with a very low storage requirement and extremely fast querying.
