Tuesday, September 26, 2006

Page Rank digression.. [Nothing really to do with 471]

Someone in the class (Betul?) mentioned that the convergence of value iteration algorithm reminded him of the convergence of pagerank.

Like I said, the theory of convergence of pagerank is quite different. Basically, pagerank corresponds to the primary eigen vector of the page transition matrix. As you probably learned in your linear algebra class, multiplying any random vector v by a matrix M has the effect of (1) first
taking the projection of the v along the eigenvectors of M and (2) stretching each projection by the
corresponding eigen value. Thus, v gets transformed by having its components along eigen vector directions stretched by an amount proportional to the eigen values. Since primary eigen value is larger (or equal) to all the other eigen values, v gets stretched more in the pimary eigen vector direction. Thus, if you repeatedly multiply v by M, then v mostly gets stretched and rotated into the primary eigen vector direction. This is a well known way of computing primary eigen vector (Called power iteration method). The rate of convergence is exponential in the difference between primary and secondary eigen values.

Anyways, if this sort of thing strikes your fancy, you might want to check out CSE494--Information Retrieval, Mining and Integration ( http://rakaposhi.eas.asu.edu/cse494 ) which will be offered next spring.

No comments: