Simple PageRank Algorithm Description

This blog post will give a simple explanation of the original PageRank algorithm  This is the algorithm that differentiated Google from the web search incumbents in the late 1990's (e.g. Yahoo!, Altavista, etc.) and helped to make it what it is today.  I will be using material I learned in ChengXiang Zhai's "Text Retrieval and Search Engines" Coursera course, as well as the original technical paper on PageRank by Sergei Brin and Larry Page entitled "The PageRank Citation Ranking: Bringing Order to the Web", 1998.

For this blog post I'm going to use a VERY simplified example of the web so that we can work through it and understand what is happening.  The example below has only 6 web pages, but has the complexity we need for our discussion.

We'll consider each of the items in the network (e.g. A, B, C) to be webpages.  PageRank can actually be used for other things like social networks, etc., but we'll stick with the web page version for this post.  Each black arrow represents a link from where the arrow starts to where the arrow ends.  For example, webpage B has a link to webpage A, and that's it.  Webpage A has links to webpage B, and D.  These links, and the somewhat hidden information that they contain, are the most important part of the PageRank algorithm.

Before PageRank, there were actually lots of people that tried to use the information from these links to help with search.  These mostly focused on the count of how many links a webpage had pointing to it.  If we use this type of thinking page A seems to be the most important with 4 links to it, C and D come in 2nd place with 2, B comes in 3rd with 1 and E and F come in dead last with 0.  This may seem to make sense, but there is something interesting that this method misses.  Since page A has so many links, it's pretty obvious it is important, but since it's important, the links that page A has to other pages are more important that other links in the network.  PageRank takes this into account.

Imagine you are web-surfing in the diagram above.  Say you pick a web page at random and then read it, find a link on that webpage and click it, read that webpage, find a link on that webpage and click it...lather, rinse, repeat...until you get bored, or stuck.  At this point you decide to not follow a link from the page you're on, but to just pick a webpage at random from the web.  Once you're on this new random webpage you start reading and clicking on links all over again.  If you did all of this, this is essentially what the PageRank algorithm does.  It follows this type of random web-surfing and then calculates the probability of arriving at all of the pages in the web.

Now that I've explained that process conceptually, lets get into the math that matches this type of random web-surfer behaviour.  If we start by creating a grid/table where we put a 1 for links from one webpage to another, we'd get something like this

This is helpful because now we can do some analysis on this table, but it's not really what we need.  If you're at a webpage, we want to be able to determine how likely you are to pick one of the links on the webpage.  If there is only one link on the webpage, this is easy; 100%.  If there are 2 or more, the PageRank algorithm just divides this probability up evenly.  If there are 2 links, each link has a 1 out of 2 chance of getting clicked (as a side note, in my opinion it would be more interesting if these probabilities were altered based on where the links were on the screen, or some other characteristic like font size/color).  If we slightly alter our table above to give these probabilities, instead of just the links, it will look like this

This matrix is called the transition matrix (later we'll refer to this matrix as M).  As mentioned above when describing the random web-surfer, there are 2 parts to this algorithm: clicking links and jumping to pages without links.  The transition matrix is useful for the link clicking part of the calculation.  Let's say that we start at time t=0 by randomly selecting one of the webpages to start from (each page has a 1 out of 6 chance of being the page we start on) and we want to figure out the probability that our next clicked link will take us to webpage A. To do this we would calculate this

For our example this equals 1/2, 50%, or 0.5 (however you want to write it).  The method can be generalized to all of the webpages after we pick a starting webpage.  The generalize version of this equation looks like this

Don't freak out, I'm going to explain what all the symbols mean.  The part of the left of the equal sign is just saying that you're going to be calculating the probability that the next click (t+1) is going to land on page dj.  'j' is a subscript that helps you keep track of what page you're calculating the probability for.  In our transition matrix above, if j=3, then dj = C.  The right side is a summation starting at 1 and going to N, where N is the number of pages in your web (in our case N=6).  Mij is the element from the transition matrix in row i and column j.  pt(di) is the probability at the current time that you have arrived at page di.  Since we're still on our first step (t=0), we set pt(di) equal to 1/6 in our example.  Now we can calculate the probability of being on all of the pages in our web (not just A) at t=1.  The result looks like this

You can see that because there are no webpages that point to pages E and F, we have 0 probability of being on those pages after we've clicked just once.  The PageRank algorithm gets to rankings of all of the pages after many repetitions of what we just did.  I'll walk you through another step (t=1 to t=2) so you get the feel of it.  Let's calculate the probability that we're on page A at t=2.

This is very similar to the step from t=0 to t=1.  The first value in each multiple is from the transition matrix (M) and the 2nd value comes from the probability of being at each page at time t=1.  Once you get the hang of this, it can be repeated quickly and converges to a final answer very quickly.  Here's how our web diagram converges.

When we get to about 21 cycles, we see that nothing is really changing and now we have values that can tell us how important each of the webpages are.  Based on this example, page A is most important, then pages B and D tie for 2nd.  This is not what we got when we just counted how many links each website had.  Page B only has 1 link, but it is linked by page A which is the most important, so that link counts for more.  Remember though, that this isn't the whole page rank algorithm.  We have to add in the random jumping to a different page now.  To do this we have to set a probability that, at any given time, we'll "get bored" and jump to another page.  Let's say that we have a 15%  chance of getting bored on the page we happen to be on. We'll call this value alpha (α=15%)

Here you can see that the first term in the probability is basically the same, but that it get's multiplied by (1-α).  This is because we need to discount this probability by the amount that we get get bored and randomly pick a page.  The 2nd term is adding in the probability of randomly jumping to another page.  The 2nd term could be simpler; it could just be α*(1/N).  It is written the way it is because this equation can be turned into a matrix math problem, which I'll show you later.  For not just go with it.

If we start over at t=0, using this new form of the equation, we can calculate a couple examples and show you how this equation converges as well.  If we want to calculate the probability of being at webpage A at t=1 we would do the following:

You can see that in the first term in the first line, I just used the value we calculated in our prior example without jumping.  I also expanded out the second summation so that it is easier to see.  The next 2 lines substitute the actual values into the equation and simplify to an answer.  If you follow this calculation for the other webpages you get this.

I'll walk you through one more step and then show you the whole table and how it converges to a final answer.  If we want to calculate the probability of being at webpage A at time t=2 we get this

The first thing I want you to notice is that I couldn't just use the value from the old method for the first summation.  This is because the probability of being at webpage A at t=1 has changed.  So, we get to do all of the math this time.  Remember that the M terms here come from the transition matrix.  Because we're calculating the probability of being at webpage A, we take the values from column A of the transition matrix.  The rest is basically the same as the last example.  We can do this for all of the webpages (I did it in Excel for this post) and get the table below

You can see that this table converges where values really aren't changing any more by the time it gets to t=17.  The decision of when to stop iterating is based on a user defined variable.  In the original PageRank white paper, the authors suggest that you loop through 't' until a value, delta (δ) gets smaller than this user defined value epsilon (Ɛ).  To calculate delta you need to know this.

The first line shows how to calculate delta, but if you're anything like me, you may have never been exposed to an "L1 Norm" before.  Each of the R terms inside the double bars is a vector containing the probabilities we've calculated for all of the webpages at the given time.  So R1 = {0.45, 0.095833, 0.2375, 0.1666, 0.025, 0.025} using the clicking and jumping values from our most recent example.  R2 would be {0.389792, 0.21625, 0.117083, 0.226875, 0.025, 0.025}.  To calculate our delta value we first have to subtract each term  in R1 from R2, then we will take the L1 norm of the result.  R2 - R1 = {-0.06021, 0.120417, -0.12042, 0.060208, 0, 0}.  Now we need to calculate the L1.  This is shown in the last equation in the list above.  Basically, you just take the absolute value of every term in the vector (R2-R1) and add them all up.  For our example from t=1 to t=2, we get delta equal to 0.36125.  If I add this delta value to the last column of the convergence table you can see how this value gets smaller as we iterate.

I promised earlier I'd show you how the equations to calculate page rank can be turned into a matrix equation.  If you're familiar with linear algebra, this will be interesting to you.  The other MAJOR advantage of having equations in matrix form is that the processing time in a computer is MUCH faster for matrix math; this is because ridiculously smart people have optimized matrix math routines in most math libraries so that they get the right answers while minimizing processing time.  We want to be able to stand on the shoulders of these giants.  So, here's how the equations can get morphed into matrix equations

If you know how to use matrices in Matlab, a programming language, Excel, etc. This last equation can be used to efficiently calculate each iteration.

Before I end this post, I need to explain one more thing.  If our web diagram happened to look like the diagram below we would have a problem

The only thing that I changed is that the arrow that was going from F to C, is now going from C to F.  The reason why this is a problem is that F isn't pointing to anything.  If we randomly select F as our starting point, how can we click on a link to move forward???  We can't.  A simple way to solve this problem is for there to be an exception in the PageRank algorithm.  If the page has no links to other pages, we don't allow the option to click on a link, we force the algorithm to randomly jump to another page.  In essence, in this special case, we set alpha equal to 1.  This keeps the algorithm from getting hung up in a dead end.

Well, I think that wraps it up.  Let me know if you have any additional questions about PageRank that I can answer for you.  As always, I hope this helps somebody out there!

Probabilistic Retrieval Model: Basics, Query Likelihood and Smoothing

This post discusses a different way (compared to the vector space model) to rank documents when performing text retrieval.  This is called the probabilistic retrieval model.  It bases its formulas off of probability theory instead of the rules of thumb that were created for the vector space model through trial and error.  I'll explain the basics of the probability model, explains some limitations and derive a "smooting" implementation (Jelinek-Mercer), and then give an example of how it all works.

If it has been a while since you've take statistics, or never have, I'm hoping to make this first section easy for you to follow.  When it comes to retrieving the right document during a search we can think of the best documents as the ones that have the highest probability of being relevant to the searcher.  The trick comes when we have to define that probability.  The mathspeak version of this probability definition is written as "p(R=1|d,q)".  Translated in to English that reads "the probability that R=1 (i.e. the document is relevant) given that we have document d and query q".  If we can efficiently calculate this probability, we can rank the documents in our search by their probability of being relevant.

The problem with the probability p(R=1|d,q) is that it is actually very hard, if not impossible, to calculate from the information we have when a user submits a query.  So, the data mining community has developed a substitute probability to calculate that gives us basically the same effect.  What they use is the probability that the query entered by the user was randomly generated from a relevant document.  That probably didn't make sense yet, so let me explain what a unigram is and then give you an example.

When you analyze text, you have to decide how the text will be divided up for analysis.  If the user enters a query for "hard drive"  are you going to treat "hard" and "drive" as 2 separate variables? Or, are you going to treat them as one?  How do you know which one you should use?  For the simplest models we treat each word as a different variable and assume that each word has nothing to do with the other words.  This assumption is called statistical independence.  It basically means that you're assuming that there is no correlation between the words in the query.  This is obviously NOT true, but as it turns out, accepting this assumption actually gives pretty good results anyway so we'll go with it.  So each word in the query gets a fancy name called a unigram (basically means 1 word).  If you bunched words into groups of 2 they would be 2-grams, etc.

Query Likelihood Example
Now it's time for that example I promised.  Suppose you entered the query {hard drive test} and
you're looking at document D4 = {...as part of the factory acceptance, every unit gets a hard drive test...}.  This document contains each of the query words once.  Think of the document D4 as a bag of marbles where each document word (unigram) is a different marble in the bag.

Now randomly take a marble out, what's the probability that marble was one of the query words?  It should be the number of times the word is in the document divided by the number of words in the document.  If D4 is only 20 words long, then the probability of pulling out the word "hard" is 1/20.  The probability of pulling out "drive" and "test" if also 1/20 for each term.  If you're familiar with statistics, this is random sampling WITH replacement (put the marble back in the bag after you pick one), because the probability of pulling out "drive" isn't 1/19 after I've picked my first word.  Now that we understand that we can predict the probability of generating the query with the document we're looking at; it's just the probability of pulling out each word multiplied by each other, or (1/20) x (1/20) x (1/20) = 1/8000.  Using this methodology, you can look at all of the documents in the collection and do the same calculation; the highest ranked document will be the one that spits out the highest probability. If you want the mathspeak version of this probability it looks like this, "p(q|d,R=1)".  This basically assumes that all of the documents are relevant (we know they're not) and gives the probability that they generated your query.

Now that we have that understanding, what happens when a method like the one above runs into a document that doesn't contain one of the query words...think about it...the probability calculated will be 0.  That's because if 1 query word is missing from the document, then one of the terms that get multiplied together will be something like (0/20) which equals 0.  Multiplying anything by 0 gives you 0 so this seems to penalize the document WAY to much.  What if this document had the phrase "hard drive examination" instead of "hard drive test".  Would we really want to rank that document at the very bottom...I think not! There's a way to fix this problem, but I'm going to have to explain some formulas before I do that.

Query Likelihood Formulas
Some words are very rare in documents.  If you happen to be searching for a rare term, then the probability of finding this term will be very small.  This small probability will multiply with other fractions and then it's pretty likely that you'll end up with tiny values for your query probability.  In a computer, when variable values get too close to 0 there is a growing risk that round off error in the computer will start to become significant and distort your results.  To avoid this, the magical properties of the logarithm come to save the day.  If you look at the chart below for the log(x) you will see that as x increases, the log(x) also increases (by the way I assume log base 10 here and through the rest of this post).  It's not a linear increase, but when it comes to ranking things, that's OK.  if X is greater than Y, then log(X) is greater than log(Y).  Also notice that the chart spans values where X is 0 to 1, like probabilities are required to do.

The other thing that is SO cool about the logarithm is that log (A*B) = log(A) + log(B).  If we apply this rule to the probabilities we're adding together then for the example above (1/20) x (1/20) x (1/20) becomes log(1/20) + log(1/20) + log(1/20).  It doesn't look very different here, but this minimizes the round-off problem in a computer.  In mathspeak, if we have a lot of terms that get multiplied together we use a large pi symbol.  The way we calculated the probability of a query being generated from a document above would look like this

f(q,d) is just a ranking function that depends on the query, q, and the document, d.  The fraction to the right is the count of a word (this is a word in the query) in a document divided by the number of words in the document.  This fraction can also be written as p(wi|d), or probability of a word given document, d.  That BIG pi symbol means that you're going to multiply all of fractions to the right together from the first word (i=1) in the query to the last word in the query (there are n words in the query).  If we take the logarithm of this formula, then we get this

Both of these formulas are equivalent, but before your head explodes, calm down and we'll walk through each one slowly.  For both of them, we still have f(q,d) as the ranking function.  We don't have log(f(q,d)) because there's no reason to do this since we have proven that the order is maintained when we take the logarithm.  In the top equation, we have the same fraction on the right, but we take the logarithm of this fraction.  Instead of multiplying all of these fractions from i=1 to n, we add them all up.  That's what the BIG sigma symbol means.  Now the difference between the first line and the 2nd one is the subscript on the sigma symbol and the term c(w,q).  The subscript on the sigma symbol means that we are going to sum over all of the words in the volume (or words in the collection of documents).  The reason we can do this without messing everything up is that we are multiplying each term by c(w,q) which is the count of the word in the query.  So when 'w' in the summation equals "hard" then c(w,q)=1 and in effect we're saying this one counts/matters.  If the 'w' in the summation equals "banana", that's not part of our query, so c(w,q)=0 and we add nothing to our ranking function.  At this point in time, you may be thinking, why would anybody add that complexity to the equation?  We'll see why this makes some of the notation easier to understand in upcoming sections

Language Model Smoothing
If we plot the probability of a word being selected in a document using the query likelihood model on one axis and the word number on a 2nd axis, we might get something that looks like this

As described earlier, if the word doesn't exist in the document, then there is 0 probability that it can be picked.  As described earlier, this is probably not desirable because there might be a document that matches very closely, but does not contain one of the words in the query.  What would be better is if we could adjust the curve to a little to look more like the green line below

Notice that near the end of the curve there are non-zero values for p(w|d).  These non-zero values will help solve the problem of query terms that don't show up in a document.  Since this green curve represents the average probabilities for all the words in the document collection, we wouldn't want to just use this curve for p(w|d).  If we did, all of the documents would have the same score and the calculations would be pointless.  What we really want is a way to kind of take a weighted average between the actual document we're ranking and the whole collection of documents.  You can imagine that if we did this that the bumpy blue curve would become much smoother, thus the name "smoothing" for this approach.  One method of doing this is called the Jelinek-Mercer(JM) model.

To get us to the JM model we've got to go through a derivation first.  I've tried to make this derivation as visual as possible.  If you don't really care about how the equation is derived, you can just skip down a little bit.  But, if you're feeling adventurous, here's what I've come up with to explain it.

The top equation is the one we have already explained.  The next step down splits this equation into 2 parts that represent a weighting for the probability of words found in the document and a weighting for the probability of words found in the rest of the collection.  You'll notice that the probability of words in the document turned into a weird looking Pseen.  I'm going to ask you to just ignore this for now, we'll explain this more later.  On the 3rd line we split the 2nd term on the 2nd line because the sum over all of the terms not found in the document is the same as taking all the words in the collection and subtracting the words found in the document.  On the 4th line we use one of the properties of logarithm to split the alpha term out from the p(w|C) term.  Once we've done all of this we combine and reorganize all the terms in the last line.  The first term in the first line takes advantage of the fact that log(a)-log(b)=log(a/b).  For the 2nd term, since alpha is a constant we can simplify the notation where |q| is the count of words in the query.  The last term on the last line is just added to the end from the 4th line.

Now that we have this equation on the last line above, we can adapt it to the JM method of smoothing.  To do this we need to define this term circled in red

The JM method starts by defining how it wants to perform the weighting between the probabilities from the documents and the collections.  Essentially it is giving a new definition for p(w|d), or the probability of a word given a document.  Here's how this is defined in the JM method

Let's start by saying that lambda(λ) is a user selected variable that ranges between 0 and 1 (it's a different way of defining alpha in earlier equations). The first term is the weighted probability of a word based on data from the document, and the 2nd term is the weighted probability of a word based on the collection of documents.  The 2nd half of the first term where we have that fraction, we're just taking the count of the word in the document, divided by the count of words in the document.  You can see that if we set lambda to a large value close to 1, that we will basically just be taking the probability of a word based on the document collection. With this one definition, we can now derive the rest of the JM ranking function.

If you're one of those people that don't care about derivations (it's OK, I used to be one of them) just look at the last equation line and use it.  If not, here's a quick explanation.  The first equation row just used the definition for Pseen to simplify the fraction a little bit.  Notice that lamda gets substituted for alpha.  Up until now we have been using alpha as our generic term that defines the weighting between the document and collection.  Since the JM method defines this as lambda, we just swap alpha out for lambda.  After obtaining a simplified fraction for that weird Pseen fraction term, we substitute it into the ranking function in the 2nd line.  We also get to completely remove the last 2 terms of this ranking function because they're actually constant.  The last term is a probability of a word in the collection and that will be the same for any document in the collection.  The 2nd to last term is based on the number of words in the query, which is the same for every document we're trying to rank as well.  So, there's no need to calculate these values if we're only interested in ranking documents.  They get the X, and we end up with a simpler equation in the last line.  The sum in this final equation is over all the words in the query and document

Now that we have this equation, let's finally do a simple example with it to show how to use it.  Let's say that we have the same query and documents used in the post about the vector space model:

q = {hard drive test}
D1 = {...it's hard to determine...};  |D1|=365
D2 = {...this hard drive has 100GB of memory...make sure the drive is fully installed...};  |D2|=50
D3 = {...before I bought my new car, I took it out for a test drive...};  |D3|=75
D4 = {...as part of the factory acceptance, every unit gets a hard drive test...};  |D4|=50
D5 = {...that was a hard test...a standardized test is design to be hard for...};  |D5|=230

To do all of the calculations we need to know the probability of finding the query words in the collection of documents.  We take the count of the query words in all the documents and divide them by the total number of words in our collection.  For example, the word "hard" shows up 5 times in our collection of documents, and there are 365+50+75+50+230=770 words in the collection.  So the probability of "hard" in the collection is 5/770 = 0.006494 = p("hard"|collection).  If we do the same for drive and test we get p("drive"|collection) = 0.005195 and p("test"|collection) = 0.005195.

The only thing left before we rank some documents is picking a value for lambda.  Let's just say that we use 0.5 for this example.  For the first document we would get the following.

Notice that I only included 3 terms here because the other terms have values of c(w,q) that are equal to zero.  This is because there are only three query terms.  All of the other words in the collection aren't in the query so their value is zero.  This is actually a big weakness for the JM method.  It doesn't actually solve the problem where there are terms missing from our query.  Instead is smooths out the probability of the terms that are in our query with the probability from the collection.  To solve the problem where we don't include a term in our query, you have to use another method like Dirichlet Prior of BM25.  These are examples of other smoothing methods that the data mining community has created.  If we continue our example using the JM method we get the following ranking values for the documents in our collection:

We can sort these scores from largest to smallest and output the documents to the user.  That's basically how it all works.  I think that wraps it up. If you have any other specific questions about this method, please say so in the comments and I'll see what I can do to augment this explanation to cover it.  As always I hope this helped somebody out there!