2007--Semantic hashing.pdf

International Journal of Approximate Reasoning 50 (2009) 969–978Contents lists available at ScienceDirect International Journal of Approximate Reasoning journal homepage: www.elsevier .com/locate / i jarSemantic hashing Ruslan Salakhutdinov *, Geoffrey Hinton Department of Computer Science, University of Toronto, 6 King’s College Road, Toronto, Ontario, Canada M5S 3G4a r t i c l e i n f o Article history: Received 11 January 2008 Received in revised form 15 November 2008 Accepted 19 November 2008 Available online 10 December 2008 Keywords: Information retrieval Graphical models Unsupervised learning0888-613X/$ - see front matter  2008 Elsevier Inc doi:10.1016/j.ijar.2008.11.006 * Corresponding author. E-mail addresses: rsalakhu@ (R. Saa b s t r a c t We show how to learn a deep graphical model of the word-count vectors obtained from a large set of documents. The values of the latent variables in the deepest layer are easy to infer and give a much better representation of each document than Latent Semantic Anal- ysis. When the deepest layer is forced to use a small number of binary variables (e.g. 32), the graphical model performs ‘‘semantic hashing”: Documents are mapped to memory addresses in such a way that semantically similar documents are located at nearby addresses. Documents similar to a query document can then be found by simply accessing all the addresses that differ by only a few bits from the address of the query document. This way of extending the efficiency of hash-coding to approximate matching is much faster than locality sensitive hashing, which is the fastest current method. By using semantic hashing to filter the documents given to TF-IDF, we achieve higher accuracy than applying TF-IDF to the entire document set.  2008 Elsevier Inc. All rights reserved.1. Introduction One of the most popular and widely-used algorithms for retrieving documents that are similar to a query document is TF- IDF [19,18] which measures the similarity between documents