{"id":40,"date":"2012-02-04T10:16:07","date_gmt":"2012-02-04T15:16:07","guid":{"rendered":"https:\/\/michaelnielsen.org\/ddi\/?p=40"},"modified":"2012-02-04T10:16:16","modified_gmt":"2012-02-04T15:16:16","slug":"how-to-combine-multiple-notions-of-relevance-in-search","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/ddi\/how-to-combine-multiple-notions-of-relevance-in-search\/","title":{"rendered":"How to combine multiple notions of relevance in search?"},"content":{"rendered":"

In earlier posts I’ve described two different ways we can assess how relevant a given webpage is to a search query: (1) the cosine similarity<\/a> measure; and (2) the PageRank<\/a>, which is a query-independent measure of the importance of a page. While it’s good that we have multiple insights into what makes a webpage relevant, it also gives rise to a problem: how should we combine these two measures to determine the ranking of a particular webpage for a particular search query?<\/p>\n

In fact, in practice the problem gets much more complex than this, because there are more than two useful notions of search relevance. For instance, we’d surely also wish to incorporate a relevance measure that quantifies how likely or unlikely a given page is to be spam. By doing that we could ensure that pages which are likely to be spam receive a much lower ranking. We might also wish to incorporate a measure which ranks a page based on how close together the words in the search query are on that page. Once you start to think about it, we humans combine a very large number of factors when assessing the usefulness of a webpage. This is reflected in the fact that, according to Google, their search engine combines not just two or three measures of relevance but more than 200 measures<\/a> of relevance. How should we best combine all these multiple measures in order to determine how relevant a page is to a given query?<\/p>\n

You might think that the right approach would be to think hard about the meaning of measures like cosine similarity and PageRank, and then on the basis of that understanding, to figure out optimal ways of combining those measures. This approach is certainly worth pursuing, but it suffers from a problem: it doesn’t scale very well. Even if you come up with a good way of combining cosine similarity and PageRank, how would you combine 200 different measures? It’s not so obvious. And if you decide to trial the addition of a 201st measure of relevance, how exactly should you incorporate it into your algorithm, and how should you check to see whether or not it improves search results?<\/p>\n

In this post, I’ll describe an approach to combining multiple measures of relevance that doesn’t require us to consider the details of the individual measures. Instead, the procedure I describe lets the machine automatically learn<\/em> how to combine different measures. It does this with the help of a set of training data<\/em>, where humans have ranked some set of webpages according to their relevance to some set of training queries. The idea is to figure out the best way of combining the measures of relevance in order to reproduce the results of the training data. Whatever method of combination is found is then applied more broadly, to all queries, and all webpages. The big advantage of this machine learning approach is that it lets us easily combine many different notions of search relevance. But it also has some drawbacks, as we’ll see.<\/p>\n

The post is based principally on Chapter 15 of the book<\/a> about information retrieval by Manning, Raghavan, and Sch\\”utze. The book is also available for free on the web<\/a>.<\/p>\n

Originally, I intended this post to be a mix of theory and working code to illustrate how the theory works in practice. This is the style I’ve used for many earlier posts, and is the style I intend to use whenever possible. However, I ran into a problem when I attempted to do that for the current post. The problem was that if I wanted to construct interesting examples (and ask interesting questions about those examples), I needed to add a lot<\/em> of extra context in order for things to make sense. It would have tripled (or more) the length of an already long post. I ultimately decided the extra overhead wasn’t worth the extra insight. Instead, the post focuses on the theory. However, I have included a few pointers to libraries which make it easy to construct your own working code, if you’re so inclined. At some point I expect I’ll come back to this question, in a context where it makes much more sense to include working code.<\/p>\n

As usual, I’ll finish the introduction with the caveat that I’m not an expert on any of this. I’m learning as I go, and there may be mistakes or misunderstandings in the post. Still, I hope the post is useful. At some point, I’ll stop adding this caveat to my posts, but I’m still a long way from being expert enough to do that! Also as per usual, the post will contain some simple exercises<\/em> for the reader, some slightly harder problems<\/em>, and also some problems for the author<\/em>, which are things I’d like to understand better.<\/p>\n

General approach<\/h3>\n

In this section, I’ll work through some simple hypothetical examples, using them to build up a set of heuristics about how to rank webpages. These heuristics will ultimately suggest a complete algorithm for learning how to rank webpages from a set of training data.<\/p>\n

One small point about nomenclature: I’m going to switch from talking about “webpages” (or “pages”), and start referring instead to “documents”. In part this is because the document terminology is more standard. But it’s also because the techniques apply more broadly than the web.<\/p>\n

To keep things simple and concrete in our hypothetical examples, we’ll assume that for any given query and document we have just two different measures of relevance, let’s say the cosine similarity and the PageRank (or some other similar measure, if we’re working with documents not from the web). We’ll call these features<\/em>. And so for any given query and document pair (q,d) we have a feature vector<\/em>:<\/p>\n \\vec \\psi(q,d) = \\left[ \\begin{array}{c} \\mbox{PageRank}(q,d) \\\\ \\mbox{cosine similarity}(q,d) \\end{array} \\right]. \n

Actually, the PageRank of a document doesn’t depend on the query q, but in general we’ll allow the features in the feature vector to depend on the query. Also, in general there will be more than two features, and so the feature vector might have quite a few components. But it turns out that the generalization beyond the two-dimensional case is straightforward, so we’ll stick with two dimensions for now.<\/p>\n

Our broad goal can now be restated in the language of feature vectors. What we want is to find an algorithm which combines the different components of the feature vector \\vec \\psi(q,d) in order to rank the document d for any particular query q. Our task is to find an algorithm which does a pretty good job doing this ranking.<\/p>\n

To get some insight into how we should solve this problem, let’s suppose we have an extremely simple set of training data. We’ll suppose a human operator has ranked three documents d_1, d_2, d_3 for just a single query q. Of course, real training data will need to involve many more documents and queries, but we can learn a lot by starting with this. We have three feature vectors for these three cases, \\vec \\psi(q,d_1), \\vec \\psi(q,d_2), \\vec \\psi(q,d_3). I’ve illustrated these in the following diagram – to avoid clutter, rather than write \\vec \\psi(q,d_j) repeatedly in the diagram, I’ve labelled each vector simply by its document number, d_j, as well as (in parentheses) by its order of relevance as ranked by a human operator:<\/p>\n

<\/p>\n

There are a few reasonable observations: <\/p>\n