Spectral Hashing
neural information processing systemsPublished 8 December 2008
Yair Weiss, Antonio Torralba, Rob Fergus
Citations2,083
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper shows 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 and obtains a spectral method whose solutions are simply a subset of thresholded eigenvectors of the graph Laplacian.
Abstract
Semantic hashing[1] seeks compact binary codes of data-points so that the Hamming distance between codewords correlates with semantic similarity. 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 thresholded eigenvectors of the graph Laplacian. By utilizing recent results on convergence of graph Laplacian eigenvectors to the Laplace-Beltrami eigenfunctions of manifolds, we show how to efficiently calculate the code of a novel data-point. Taken together, both learning the code and applying it to a novel point are extremely simple. Our experiments show that our codes outperform the state-of-the art.
Keywords
Computer Science
On Spectral Clustering: Analysis and an algorithm
7,751 Citations2001Andrew Y. Ng, Michael I. Jordan +1 more
A simple spectral clustering algorithm that can be implemented using a few lines of Matlab is presented, and tools from matrix perturbation theory are used to analyze the algorithm, and give conditions under which it can be expected to do well.
The MIT Press eBooksLaplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
4,535 Citations2002Mikhail Belkin, Partha Niyogi
The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality preserving properties and a natural connection to clustering.
Proceedings of the National Academy of SciencesGeometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps
1,764 Citations2005Ronald R. Coifman, Stéphane Lafon +5 more
The process of iterating or diffusing the Markov matrix is seen as a generalization of some aspects of the Newtonian paradigm, in which local infinitesimal transitions of a system lead to global macroscopic descriptions by integration.
Stochastic Neighbor Embedding
1,461 Citations2002Geoffrey E. Hinton, Sam T. Roweis
This probabilistic framework makes it easy to represent each object by a mixture of widely separated low-dimensional images, which allows ambiguous objects, like the document count vector for the word "bank", to have versions close to the images of both "river" and "finance" without forcing the image of outdoor concepts to be located close to those of corporate concepts.
IEEE Transactions on Pattern Analysis and Machine IntelligenceSpectral grouping using the nystrom method
1,326 Citations2004Charless C. Fowlkes, Serge Belongie +2 more
The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning making it feasible to apply them to very large grouping problems.
International Journal of Approximate ReasoningSemantic hashing
1,272 Citations2008Ruslan Salakhutdinov, Geoffrey E. Hinton
A deep graphical model of the word-count vectors obtained from a large set of documents is shown, which achieves higher accuracy than applying TF-IDF to the entire document set.
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
1,099 Citations2006Alexandr Andoni, Piotr Indyk
Applied and Computational Harmonic AnalysisDiffusion maps, spectral clustering and reaction coordinates of dynamical systems
1,016 Citations2006Boaz Nadler, Stéphane Lafon +2 more
A unifying view of a family of diffusion maps, defined as the embedding of complex data onto a low dimensional Euclidean space, via the eigenvectors of suitably defined random walks defined on the given datasets, is provided.
Normalized cuts and image segmentation
863 Citations2002Jianbo Shi, Jitendra Malik
This work treats image segmentation as a graph partitioning problem and proposes a novel global criterion, the normalized cut, for segmenting the graph, which measures both the total dissimilarity between the different groups as well as the total similarity within the groups.
Fast pose estimation with parameter-sensitive hashing
764 Citations2003Shakhnarovich, Viola +1 more
A new algorithm is introduced that learns a set of hashing functions that efficiently index examples relevant to a particular estimation task, and can rapidly and accurately estimate the articulated pose of human figures from a large database of example images.
Small codes and large image databases for recognition
739 Citations2008Antonio Torralba, Rob Fergus +1 more
The goal is to develop efficient image search and scene matching techniques that are not only fast, but also require very little memory, enabling their use on standard hardware or even on handheld devices.
Scene completion using millions of photographs
731 Citations2007James Hays, Alexei A. Efros
Journal of Computer and System SciencesTowards a theoretical foundation for Laplacian-based manifold methods
477 Citations2007Mikhail Belkin, Partha Niyogi
It is shown that under certain conditions the graph Laplacian of a point cloud converges to the Laplace-Beltrami operator on the underlying manifold.
Learning a Nonlinear Embedding by Preserving Class Neighbourhood Structure
438 Citations2007Ruslan Salakhutdinov, Geoffrey E. Hinton
Neural ComputationLearning Eigenfunctions Links Spectral Embedding and Kernel PCA
345 Citations2004Yoshua Bengio, Olivier Delalleau +4 more
A direct relation is shown between spectral embedding methods and kernel principal components analysis and how both are special cases of a more general learning problem: learning the principal eigenfunctions of an operator defined from a kernel and the unknown data-generating density.
Limits of Spectral Clustering
97 Citations2004Ulrike von Luxburg, Olivier Bousquet +1 more
This paper investigates whether the partitions constructed on finite samples converge to a useful clustering of the whole data space as the sample size increases and concludes that while in the normalized case, spectral clustering usually converges to a nice partition of the data space, in the unnormalized case the same only holds under strong additional assumptions which are not always satisfied.