{"id":12,"date":"2011-07-07T15:11:43","date_gmt":"2011-07-07T19:11:43","guid":{"rendered":"https:\/\/michaelnielsen.org\/ddi\/?p=12"},"modified":"2011-07-07T16:13:29","modified_gmt":"2011-07-07T20:13:29","slug":"documents-as-geometric-objects-how-to-rank-documents-for-full-text-search","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/ddi\/documents-as-geometric-objects-how-to-rank-documents-for-full-text-search\/","title":{"rendered":"Documents as geometric objects: how to rank documents for full-text search"},"content":{"rendered":"

When we type a query into a search engine – say “Einstein on relativity” – how does the search engine decide which documents to return? When the document is on the web, part of the answer to that question is provided by the PageRank algorithm<\/a>, which analyses the link structure of the web to determine the importance of different webpages. But what should we do when the documents aren’t on the web, and there is no link structure? How should we determine which documents most closely match the intent of the query?<\/p>\n

In this post I explain the basic ideas of how to rank different documents according to their relevance. The ideas used are very beautiful. They are based on the fearsome-sounding vector space model<\/a> for documents. Although it sounds fearsome, the vector space model is actually very simple. The key idea is to transform search from a linguistic problem into a geometric problem<\/em>. Instead of thinking of documents and queries as strings of letters, we adopt a point of view in which both documents and queries are represented as vectors in a vector space. In this point of view, the problem of determining how relevant a document is to a query is just a question of determining how parallel<\/em> the query vector and the document vector are. The more parallel the vectors, the more relevant the document is.<\/p>\n

This geometric way of treating documents turns out to be very powerful. It’s used by most modern web search engines, including (most likely) web search engines such as Google and Bing, as well as search libraries such as Lucene<\/a>. The ideas can also be used well beyond search, for problems such as document classification, and for finding clusters of related documents. What makes this approach powerful is that it enables us to bring the tools of geometry to bear on the superficially very non-geometric problem of understanding text.<\/p>\n

I’ve based my treatment on chapters 6 and 7 of a very good book<\/a> about information retrieval, by Manning, Raghavan, and Schuetze. The book is also available for free on the web here<\/a>.<\/p>\n

It’s worth mentioning that although this post is a mixture of mathematics and algorithms, search is not a purely mathematical or algorithmic problem. That is, search is not like solving a quadratic equation or sorting a list: there is no right answer, no well-defined notion of what it means to “solve” the search problem. To put it another way, as pointed out by Peter Norvig in an interview in Peter Seibel’s book Coders at Work<\/a>, it makes no sense to think about “proving” that Google is correct, as one might perhaps do for a sorting algorithm. And yet we would no doubt all agree that some search algorithms are better, and others are worse.<\/p>\n

The vector space model explained<\/h3>\n

Suppose d is a document in the corpus of documents we’d like to search. As a trivial example of a corpus, later in this post I’ll use a corpus containing just four documents, which I’ve chosen to be product descriptions for the books Lord of the Rings<\/em>, The Hobbit<\/em>, The Silmarillion<\/em> and Rainbows End<\/em> (all taken from Amazon). A real corpus would be much larger. In any case, what we’re going to do is to associate with d a document vector<\/em>, for which we’ll use the notation \\vec d. You can think of the document vector \\vec d as a geometric way of representing the document d.<\/p>\n

To explain how \\vec d is defined, we need first to define the vector space \\vec d lives in. To do that we need to go through a few preparatory steps. Starting from our corpus, we’ll extract all the words in that corpus, and we’ll call them the terms<\/em> that make up the corpus dictionary<\/em>. To each term t in the dictionary we will associate a different unit vector \\vec e_t in the vector space. So, for instance, if the word “Einstein” appears in the corpus, then there is a unit vector \\vec e_{\\rm Einstein}. We’ll further stiuplate that the unit vectors for different terms are orthogonal to one another. And so the vector space we’re working in – our geometric arena – is, by definition, the vector space spanned by all the unit vectors \\vec e_t corresponding to the different terms in the dictionary.<\/p>\n

Somewhat oddly, so far as I know this vector space doesn’t have a name. I think it should: it is, after all, the geometric arena in which the vector space model for documents works. I will call it document space<\/em>.<\/p>\n

With all the above in mind, we can now define the document vector:<\/p>\n\\vec d \\equiv \\sum_{t} \\mbox{imp}(t,d) \\vec e_t.\n

Here, \\mbox{imp}(t,d) is some function that measures the importance of term t in document d (more on this function below). The key point to take away for now is that the document vector \\vec d is just the vector whose component in the direction \\vec e_t of term t is a measure of the importance of term t in the document d. That’s a pretty simple and natural geometric notion. It means that if some term is very important in a document, say “Einstein”, then \\vec d will have a large component in the \\vec e_{\\rm Einstein} direction. But if some term isn’t very important – say “turnips” – then the component in the \\vec e_{\\rm turnips} direction will be small.<\/p>\n

How should we define the importance function \\mbox{imp}(t,d)? There is, of course, no unique way of defining such a function, and below we’ll discuss several different concrete approaches to defining \\mbox{imp}(t,d). But as a simple example, one way you could define importance is to set \\mbox{imp}(t,d) equal to the frequency of the term t in the document d. Later we’ll come up with an even better measure, but this illustrates the flavour of how \\mbox{imp}(t,d) is defined.<\/p>\n

A caveat about the document vector \\vec d is that typically doesn’t preserve all the information about the document. For instance, if we use frequency as a measure of importance, then the document vector for the document “She sells sea shells by the sea shore” will be the same as the document vector for the document “Sea shells by the sea shore she sells”, because the term frequencies are the same in both documents. So the document vector is only an imperfect representation of the original document. Still, provided you choose a reasonable function for importance, the document vector preserves quite a lot of information about the original document.<\/p>\n

Finding documents relevant to a query<\/h3>\n

Having defined document vectors, we can now say how to find the document most relevant to a given search query, q. We do it by defining a query vector<\/em>, \\vec q, exactly as we defined the document vector. That is, we regard the query text q as a document, and construct the corresponding vector in document space:<\/p>\n\\vec q \\equiv \\sum_{t} \\mbox{imp}(t,q) \\vec e_t\n

Now, how should me measure how relevant a document d is to a particular query q? One way is to simply consider the angle \\theta between the query vector \\vec q and the document vector \\vec d, as defined by the equation:<\/p>\n\\cos \\theta = \\frac{\\vec q \\cdot \\vec d}{\\| \\vec q \\| \\| \\vec d \\|}.\n

This is called the cosine similarity<\/em> between the document and the query. Our notion of relevance, then, is that the smaller the angle \\theta is, the more relevant the document d is to the query q.<\/p>\n

What makes the cosine similarity so beautiful is that it lets us use our geometric intuition to think about the problem of ranking documents. Want the top K ranked documents for the query? Just compute the angle \\theta for every document in the corpus, and return the K documents whose angles are smallest. Want to find documents that are similar to a document d (“find documents like this one”)? Just look for the other documents whose document vectors have the smallest angle to \\vec d.<\/p>\n

Of course, using the angle is a very ad hoc<\/em> choice. The justification is not theoretical, it is empirical: search engines which use cosine similarity on the whole leave their users pretty satisfied. If you can find another measure which leaves users more satisfied, then by all means, feel free to use that measure instead.<\/p>\n

Problems<\/h3>\n