Timezone: »

 
Poster
Spectral Hashing
Yair Weiss · Antonio Torralba · Rob Fergus

Mon Dec 08 08:45 PM -- 12:00 AM (PST) @
in Posters »

Semantic hashing seeks compact binary codes of datapoints so that the Hamming distance between codewords correlates with semantic similarity. Hinton et al. used a clever implementation of autoencoders to find such codes. In this paper, we show that the problem of finding a best code for a given dataset is closely related to the problem of graph partitioning and can be shown to be NP hard. By relaxing the original problem, we obtain a spectral method whose solutions are simply a subset of thresh- olded eigenvectors of the graph Laplacian. By utilizing recent results on convergence of graph Laplacian eigenvectors to the Laplace-Beltrami eigen- functions of manifolds, we show how to efficiently calculate the code of a novel datapoint. Taken together, both learning the code and applying it to a novel point are extremely simple. Our experiments show that our codes significantly outperform the state-of-the art.

[ PDF] 

Author Information

Yair Weiss (Hebrew University)

Yair Weiss is an Associate Professor at the Hebrew University School of Computer Science and Engineering. He received his Ph.D. from MIT working with Ted Adelson on motion analysis and did postdoctoral work at UC Berkeley. Since 2005 he has been a fellow of the Canadian Institute for Advanced Research. With his students and colleagues he has co-authored award winning papers in NIPS (2002),ECCV (2006), UAI (2008) and CVPR (2009).

Antonio Torralba (Massachusetts Institute of Technology)
Rob Fergus (DeepMind / NYU)

Rob Fergus is an Associate Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University. He received a Masters in Electrical Engineering with Prof. Pietro Perona at Caltech, before completing a PhD with Prof. Andrew Zisserman at the University of Oxford in 2005. Before coming to NYU, he spent two years as a post-doc in the Computer Science and Artificial Intelligence Lab (CSAIL) at MIT, working with Prof. William Freeman. He has received several awards including a CVPR best paper prize, a Sloan Fellowship & NSF Career award and the IEEE Longuet-Higgins prize.

More from the Same Authors