[Statistics 110] Lecture 33: Markov Chains Continued Further

Reversible Markov Chains

$i,j$ state 간 edge가 없으면 가중치 $w_{ij}$=0.

i에서 j state로 $w_{ij}$에 비례하는 확률로 이동.

$$q_{ij} = \frac{w_{ij}}{\sum_kw_{ik}}$$

$s_i$는 $\sum_Kw_{ik}$에 비례

간단하게 말하면 모든 가역적 마르코프 체인을 아래 형태(가중치가 있는 Random walk)로 나타낼 수 있다.

$$P(X_{n+1}=j|X_n=i) = \frac{w_{ij}}{\sum_kw_{ik}} = q_{ij}$$

Non-reversible Markov Chains

Google PageRank

모든 페이지에 중요도 점수를 주고 그에 따라 검색 결과를 노출. 점수는 참조된 페이지의 수와 그 페이지들의 중요도에 의해 결정

$$Score = S\\s_j = \sum_i s_iq_{ij}\\ \vec SQ = \vec S$$

링크가 걸려있는 페이지들의 점수의 합을 해당 페이지의 점수로 지정

하지만 다른 페이지로의 링크가 1000개 존재하는 사이트의 경우 다른 페이지로의 링크가 1개인 사이트보다 링크의 중요도를 낮게 주어야 함. 아래와 같이 Q 전이행렬을 통해 이를 조정, 고정적 분포

 

Google Chain

$G = \alpha Q + (1-\alpha)\frac JM$.

$M$은 전체 페이지의 수, $J$는 모든 원소가 1로 이루어진 행렬

$\alpha$는 다른 링크로 넘어가는 행위를 하고, $1-\alpha$는 링크를 따르지 않고 다른 페이지로 teleportation

구글은 0.85를 $\alpha$값으로 사용

$\vec t$를 시작 벡터라고 하면

$$\vec t G = \alpha \vec t Q+ (1-\alpha)\vec t \frac JM$$

$\vec t G^n$에서 n이 커지면 Pagerank Vector에 수렴

 

Reference

[0] https://www.youtube.com/playlist?list=PL2SOU6wwxB0uwwH80KTQ6ht66KWxbzTIo 

Statistics 110: Probability