Eigenvectors and PageRank

Eigenvectors are another topic that I used in a math class or two but never really understood what they were for. As I mentioned in my last post Bipartite Graphs and Google Adwords, I like how the professors of the Coursera class Mining Massive Datasets gave great examples of how to apply some academic concepts to real world problems. Their PageRank material is no different as it explains how eigenvectors are used in the algorithm. Here is my summary of the class' link analysis chapter which I'm sure is greatly simplified from what Google really does, but I think it's interesting nonetheless.

Early search engines used an inverted index which I covered in my tf-idf post. That approach is vulnerable to term spam. People would put invisible text on their pages (same color as the background) to trick web crawlers into thinking that the page was about a topic it wasn't. The PageRank algorithm solves that problem by giving more importance to pages that have many in-links, and especially important in-links. Even if someone creates millions of fake pages that link to their real page, it's importance will not be that high because the fake pages will have a low importance as no one is linking to them.

The web can be thought of as a directed graph where web pages are the vertexes and links are the arcs. The basic idea of PageRank is that you simulate web surfers starting at random spots in the web graph and then following random out-links. The most important pages, the pages with the most in-links, will end up with the most surfers.

To implement this simulation, consider a transition matrix M which has n rows and columns where n is the number of pages crawled. M_ij has the value 1/k if page j has k arcs out and one of them is to page i, otherwise it has the value 0. Start with a vector v₀ which has all elements set to 1/n. The first step is to multiply v₀ by M, the second step is to multiple by M², and so on (this is an example of a Markov process which means you can make predictions on its future state based only on the present state and do not need the history).

If the web graph is one strongly connected component and doesn't have any dead ends, then v = Mv is the limiting distribution. The limit would be reached when multiplying the distribution by M another time doesn't change the distribution. Vector v is an eigenvector of M because v = λMv. Vector v is also the principal eigenvector because M is a stochastic matrix and the eigenvalue associated with the principal eigenvector is 1. In practice it takes 50-75 iterations to reach this limit.

M is too big for us to use Gaussian elimination. M is also very sparse, so it makes sense to store only the non-zero elements. An entire column can be represented by the out-degree of a page and the row number of the non-zero elements (since those element's values will be 1 divided by the out-degree). That means we only need to store a little over 4 bytes for each non-zero element. Then we can solve for v using MapReduce and v tells us the "page rank" of each page.

In reality the web is not strongly connected. There are dead ends and there are spider traps, or cycles, in the graph. This problem is solved by the concept of taxation. Each surfer has a small probability of teleporting to a random page instead of following an out-link. There are also other algorithm variations for dealing with link spam. For example, besides page content, you also consider the link text or words near the link, so you are getting other people's take on what the page is about instead of relying solely on the page owner.

UPDATE:

This same idea can be applied to sports ratings where links are replaced by something like goals scored. My Machine Learning for NCAA Basketball Prediction - Performance Edition post has more details and some code.

Resources:
http://infolab.stanford.edu/~ullman/mmds/ch5.pdf

Bipartite Graphs and Google Adwords

Continuing my series of posts relating to the Coursera Mining Massive Datasets class, this post summarizes the chapter on Google AdWords. I liked how the professors showed it to be related to matching in a bipartite graph--something that I learned about in a university graph theory class but without such a practical context as web advertising. I think that too often happens, at least in my experience. I've taken a lot of math classes (and done well in them), but I still don't feel like I had much practice applying what I learned to real-world problems.

To be clear, AdWords is for advertisers and AdSense is for website owners. Google provides an explanation in The difference between AdWords and AdSense. Today I'm focusing on how AdWords works.

The "adwords" model matches web searches with advertisements. Advertisers bid to be shown in response to certain search queries. If a user clicks on one of the ads shown to them then the advertiser will pay. Of course, the most relevant ads are clicked more often than less attractive ads, so the challenge is displaying the ads with the highest bids that are most likely to be clicked, while staying within an advertisers budget. This is a problem that traditional newspapers and magazines don't really have. They can only target specific niches of people (like people who buy Golf Digest), but web advertisers can target individuals (like people searching for a specific brand of golf clubs).

Google knows the click-through rate, or the percentage of the time an ad is clicked when it is displayed. It knows how much of an advertiser's budget has been spent. Google also knows what people have searched for in the past, but it doesn't know for sure what people are going to search for in the future. The "adwords" problem therefore needs a greedy algorithm because all you can do is make the best choice for each search and hope it results in the best overall outcome.

A simplified version of this "adwords" problem can be modeled as maximal matching in bipartite graphs. A matching is a subset of edges where no vertex is an end of two or more edges. A perfect matching contains every vertex and a maximal matching is the largest possible matching for the graph. In this case one side of the graph is search queries, the other side is ads, and the edges are who the ads could be shown to. The maximal matching is the best way to display the ads. The simplifying assumptions are that one ad is shown, all advertisers have the same budget, click-through rates are the same, and bids are either 0 or 1.

The obvious greedy algorithm for matching will consider edges in the order they are given. An edge is part of the matching if neither end is connected to an edge already added to the matching. The competitive ratio is defined as the ratio between the worst online algorithm and the best offline algorithm. The offline solution is the optimal solution because all information about the problem is known in advance. For our bipartite matching solution the ratio is only 0.5, that is it will always find at least half as many matches as what is optimal.

It is possible to do better. The more realistic BALANCE algorithm considers the highest bidder and the highest remaining budget. By doing so it results in a competitive ratio of 0.63 which is the highest possible for an online algorithm.

UPDATE:

Bipartite matching implementations can be found in NetworkX and SciPy.

Resources
http://infolab.stanford.edu/~ullman/mmds/ch8.pdf

Locality Sensitive Hashing

In my previous post on tf-idf, I summarized my notes on how to look for similar documents in the sense that the documents are about the same topic. However, there is a slightly different problem of finding similar documents that are really the same document. They could be, for example, plagiarized, a mirror website, or a news story from the same source carried by multiple news outlets. When there are too many pairs of documents to efficiently compare them all, we can use a technique called locality sensitive hashing or LSH. Today I'll summarize my LSH notes.

In order to find these lexically similar documents, you need to represent each document as a set of sentences or phrases. One technique for this is called shingling and a k-shingle is any substring with length k in the document. The value of k needs to be large enough that the probability of a shingle appearing in any given document is low. To represent shingles more concisely, use a hash function to hash the substrings to a number. Then, for example, each shingle is represented as four bytes instead of a k byte substring.

Even with four byte shingles the set for a document still takes up more space than the document itself. We need to replace these large sets with smaller representations called signatures. A signature is the result of several hundred minhash calculations. Consider a matrix where there is a row for each shingle and a column for every document sets. The matrix has a 1 for a particular row and column if that shingle appears in the set. Pick a permutation of rows and then the minhash value for a column is the number of the first row (in permuted order) with a 1 in that column.

In practice, storing the sparse matrix and permuting and sorting millions of rows is too time-consuming, but it can be simulated by random hash functions that map row numbers to as many buckets as there are rows (and ignoring the small number of collisions). Instead of picking n random permutations you pick n randomly chosen hash functions. If a column has a 1 for row r, then the corresponding signature matrix column is updated with the bucket numbers as long as they are less than the current values.

From the signature matrix we can estimate the Jaccard similarities of the underlying sets. Mind = blown.

It still might not be possible to efficiently check the similarity of all pairs of documents because there are just too many pairs. To find the most similar pairs or all pairs above a certain similarity threshold, we need to focus only on pairs that are likely to be similar. The LSH approach here is to hash items several times and hope that similar pairs will end up in the same bucket at least once. Any pair that hashed to the same bucket in any of the hashings is a candidate pair (even though some of them are false positives).

Divide the signature matrix into b bands where each band consists of r rows. Hash each vector (the portion of each column in a band) to a large number of buckets. Each band has its own buckets. The similarity threshold is an S-curve and is approximately:

For a Jaccard similarity s, the probability of a false negative, i.e. missing a candidate pair, is given by:

Finally, examine the candidate pairs to determine if they are above the previously determined similarity threshold.

Besides the minhash family of functions, there are also other function families that apply to other distance measures like Hamming distance or edit distance. LSH works well for fingerprint matching and entity-resolution.

UPDATE:

Spark implements several LSH operations and has more info on how they can be used.


Resources:
http://infolab.stanford.edu/~ullman/mmds/ch3.pdf