Eigenvector of Stochastic Matrix

Vector = Stochastic Matrix * Arbitrary Vector
Keep multiplying as above and eventually, the vector doesnt change anymore. The vector then is the eigen vector of the stochastic matrix with eigenvalue of 1.

Probability & Linear Algebra Review
Google Web Search Algorithm
  • Page rank is based on probability a user goes to a website.
  • Rank propogates -- more important website points to a website, the importance is higher.
  • The algorithm finds the largest eigenvector of the conditional probability (stochastic) matrix
  • Conditional probability matrix is initialized based on links going out -- adds a small number to avoid closed graphs -- normalized to make it stochastic matrix
  • Sparse matrix notation still too large to multiply, so Google created Mapreduce to make huge matrix calculations.
  • Keep multiplying till vector converges and the result is the probability (or page rank) vector
  • Then somebody searches for "cat", Google finds all documents containing that word and then orders them by the Pagerank

Concepts

Conditionalization

P(A|B) = P(A & B)/P(B)

Marginalization

P(B) = Sum {P(B|A) P(A)} over all values of A

Baye's Rule:

It enables us to reverse probabilities.

P(A|B) = P(B|A)*P(A)/P(B)

 

   Login to remove ads X
Feedback | How-To