PageRank as Markov Chain

마르코프 체인에서 페이지랭크를 보다.

tl;dr

• 페이지와 브린이 창안한 페이지랭크 알고리듬은 수학적으로 보면 마르코프 체인의 극한 분포다.

PageRank?

페이지랭크 알고리듬의 핵심이 사실 마르코프 체인이다. 페이지와 브린의 논문에 보면 “random surfer”라는 표현이 나온다. 이게 딱 확률 과정(stochastic process)을 연상시키지 않나? 문득 이런 생각이 들더라.

페이지와 브린의 논문 자체가 마르코프 프로세스를 연상시키지는 않는다. 논문을 보면 페이지랭크 스코어링을 위한 몇 가지 원칙들이 언급되어 있을 뿐이다. 더 많은 아웃바운드 링크를 지닌 웹페이지에 내 페이지가 연결되어 있을 때 내 페이지의 스코어를 계산할 때 해당 페이지의 중요성을 낮춘다. 많은 인바운드 링크를 지닌 페이지에 내 페이지가 연결되어 있다면 이 페이지의 중요성을 높인다. 대략 이런 내용들이다. 사실 페이지랭크를 계산하는 과정 자체는 재귀적인 내용을 포함하고 있기 때문에 직관적으로 이해하기는 쉽지 않다. 페이지랭크 스코어링의 함의를 추리고 그 계산 과정은 잘 돌아보지 않는다. 나도 그랬다.

페이지랭크라는 스코어, 즉 한 웹 페이지가 링크로 구성된 웹 풍경에서 지니는 중요도라는 개념이 마르코프 체인의 극한 분포(limiting distribution)와 개념적으로 연결된다. 내용을 간단히 살펴보도록 하자.

PageRank Model

일단 페이지와 브린의 논문에서 다룬 모델링의 세팅을 간단히 살펴보자.

• \(L_{ij}\): 인디케이터 함수다. \(j \to i\)의 링크가 존재하면 1, 그렇지 않으면 0이다.
• \(m_j = \sum_{k=1}^n L_{kj}\): \(j\)가 지닌 아웃바운드 링크의 합을 나타낸다.

이제 웹페이지 \(i\)의 Broken Rank \(p_i\)은 다음과 같다.

\[ p_i = \sum_{j \to i} \dfrac{p_j}{m_j} = \sum_{k=1}^{n}L_{ik}\dfrac{p_{k}}{m_k} \]

\(i\) 웹사이트의 ’Broken Rank’는 \(i\)로 연결된 페이지들의 Broken Rank에 의해 정해진다. 이를 계산하는 방법은 다음과 같다. 해당 페이지들의 Broken Rank가 높을수록 나의 랭크도 높아진다. 해당 페이지가 더 많은 링크를 가질수록 그 Broken Rank는 낮게 평가된다. \(m_j\)로 나눠진 부분이 이를 반영한다.

여기서 왜 굳이 “broken”이라는 표현을 썼는지는 잠시 후에 나오니 조금만 기다려주시라.

Broken rank as matrix

Broken rank를 매트릭스로 표현해보자.

\[ p = [p_1, \dotsc, p_n]^T \]

\[ L = \begin{bmatrix} L_{11}& \dotsc& L_{1n} \\ \vdots& \ddots& \vdots \\ L_{n1}& \dotsc& L_{nn} \end{bmatrix} \]

\[ M = \begin{bmatrix} m_{1}& \dotsc& 0 \\ \vdots& \ddots & \vdots \\ 0& \dotsc& m_{n} \end{bmatrix} \]

이를 활용하면,

\[ p = LM^{-1} p \]

\(LM^{-1} = A\)라고 두면 \(A\)가 마르코프 체인의 확률 행렬과 유사하다는 점을 쉽게 파악할 수 있다.

\[ A^T = \begin{bmatrix} \dfrac{L_{11}}{m_1}& \dotsc& \dfrac{L_{n1}}{m_1} \\ \vdots& \ddots& \vdots \\ \dfrac{L_{1n}}{m_n}& \dotsc& \dfrac{L_{nn}}{m_n} \end{bmatrix} \]

\(A^T\)를 들어다보자. 일단, 행을 더하면 1이 된다. 즉, \(i\)에서 \(i\)를 포함해서 어디론가는 가야 한다는 뜻이다. 다음으로 \(L_\cdot\)의 정의를 살펴보면 \(j \to i\)의 이행확률은 \(j\)가 \(i\)로 향하는 링크를 지닐 경우는 \(\frac{1}{m_i}\)가 되고, 그렇지 않으면 0이다. 페이지와 브린이 정의한 random surfer의 의미가 이것이다. \(m_i\)의 링크 중에서 특별히 선호하는 링크 없이 무작위로 하나를 골라서 나간다는 가정이다. 아울러 해당 링크를 선택하는 데에는 현재의 가능성 이외에 그 전의 선택은 고려되지 않는다. 이점에서 이번 기의 선택에 바로 전기만 영향을 끼치는 마르코프 프로세스의 가정과 일치한다.

한편 행 \(i\)는 \(j \to i\)로 들어오는 링크를 의미한다. \(L_{\cdot j}\)가 1이 많을수록 \(i\)로 오는 링크가 많다는 뜻이다. 즉, 이 링크는 영향력이 높은 링크를 뜻한다.

Why broken?

왜 깨진 링크인가? 눈치가 빠른 사람이라면 마르코프 체인에서 해당 체인이 수렴하는 분포를 지니기 위한 조건을 알고 있을 것이다. 극한 분포를 지니려면 마르코프 확률 행렬이 우선 irreducible 행렬이어야 한다.

이 조건을 말로 풀면 어떻게 될까? 해당 상태에서 언젠가는 다른 모든 상태로 갈 수 있어야 한다. 이를 웹사이트 간의 링크로 다시 풀어보자. A 사이트에서 B 사이트로 갈 수 없으면 안된다. 마르코프 체인에서 확률 행렬이 reducible 행렬이면 수렴하는 유일한 극한 분포를 찾을 수 없다. 다음의 예를 보자.

\[ A = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} \]

아이겐밸류 1에 해당하는 아이겐벡터는 두 개가 존재한다. 각각

\[ p = [\dfrac{1}{3}, \dfrac{1}{3} , \dfrac{1}{3} , 0, 0 ] \text{~or~} p = [0, 0, 0, \dfrac{1}{2}, \dfrac{1}{2} ] \]

확률 행렬이 기약 행렬(reducible matrix)이면, 웹 페이지에 관해서 유일한 극한 분포를 찾을 수 없다. 시작이 어디인지에 따라서 전혀 다른 극한 분포를 얻게 된다. 위의 예에서 만일 1,2,3 사이트에서 시작했다면 첫번째 극한 분포를, 4,5 사이트에서 출발했다면 두번째 극한 분포를 얻게 될 것이다.

PageRank score as share

마르코프 체인을 다루는 분석에서 이런 경우는 종종 생길 수 있다. 이를 해결하는 가장 쉬운 방법은 어떤 상태에 고착되어 벗어날 수 없을 때, 벗어날 수 있는 어떤 기제를 마련해주는 것이다. 예를 들어, 플레이어가 일정한 확률로 실수를 하게 허용한다거나 하는 이론적인 장치가 많이 활용된다.

페이지랭크 역시 비슷한 해법을 모델에 넣었다. 링크가 없더라도 일정한 확률로 다른 모든 링크로 넘어갈 확률을 임의로 부여하는 것이다. 이를 반영한 페이지랭크의 정의는 아래와 같다.

\[ p_i = \overset{(A)}{(1-d)\dfrac{1}{n}} + \overset{(B)}{\vphantom{\dfrac{1-d}{n}} d \cdot \sum_{j \to i} \dfrac{p_j}{m_j}} = \dfrac{1-d}{n} + d \sum_{k=1}^{n}L_{ij}\dfrac{p_{j}}{m_j} \]

\(d\)는 어떤 사이트에서 링크가 존재하는 다른 사이트로 옮겨갈 확률을 의미한다. 따라서 \((1-d)\)는 링크 유무와 관계 없이 \(n\) 개의 사이트 중 임의의 다른 사이트로 옮겨갈 확률이다.

• \((A)\): 링크 유무와 관계없이 (\(i\) 자신을 포함해) 어디선가 \(i\)로 올 확률에 기반한 스코어링이다. 이때 스코어 값은 1이다.
• \((B)\): \(i\)로 오는 링크를 지닌 사이트 중에서 \(i\)로 올 확률에 기반한 스코어링이다. 각각의 스코어링 값은 \(p_j\)가 된다.

이를 행렬로 나타내면 다음과 같다. \(p_t\) 기의 페이지랭크가 주어져 있다면, 링크를 통한 페이지 이동을 거친 이후의 페이지랭크 \(p_{t+1}\) 다음과 같다.

\[ p_{t+1} = \overbrace{\left( \dfrac{1-d}{n} \boldsymbol{1}_n + d L M^{-1} \right)}^{(*)}p_{t} \]

\(\boldsymbol{1}_n\)은 모든 원소가 1인 \(n \times n\) 행렬이다. \((*)\)은 기약 행렬(irreducible matrix)이고, \(d>0\)이 만족하면 비주기 행렬(aperiodic matrix)이 된다. 특정한 사이트 \(i\)에서 다른 사이트로 갈 확률이 모두 양수가 되기 때문이다.

이 경우 \((*)\)을 확률 행렬로 지니는 마르코프 체인은 극한 분포 \(p^*\)를 지니게 된다. 마르코프 체인의 논리에 따라서 \(p^*\)는 초기값 혹은 웹사이트의 초기 지분 \(p_0\)와 무관하다.

이 극한 분포 \(p^*\)가 바로 페이지랭크다! 마르코프 체인의 관점에서 페이지랭크란 페론-프로베니우스 정리에 따라서 아이겐밸류 \(1\)에 해당하는 좌 아이겐벡터를 찾는 과정이다. 물론 구글이 구사하는 실제의 알고리즘은 여기 적은 내용보다 훨씬 복잡하고 정교하다. 다만 그 핵심이 마르코프 체인이라는 사실을 기억해두자.

🔗을 참고하라.

극한 분포가 페이지랭크가 된다는 의미는 무엇일까? 마르코프 체인에서 극한 분포란 무작위로 상태를 옮겨가는 것이 무한이 반복되었을 때 도달하게 되는 분포다. 이는 충분히 긴 장기에 각 상태가 지니게 되는 ‘지분’(share)으로 이해할 수 있다.

이러한 마르코프 체인에 기반을 둔 해석은 웹 사이트에도 잘 들어 맞는다. 그럴까? 개인의 입장에서는 그렇지 않다. 적어도 나는 그렇다. 구글에서 검색어를 친 뒤 검색 결과를 보면서 필요한 것을 찾아서 클릭, 클릭하기 때문이다.

하지만 내가 누른 검색어를 친 사람이 많다면 어떨까? 특정 검색어에 관해서 수많은 웹 서퍼가 존재하고 이들이 각자의 취향대로 페이지를 옮겨다닌다면? 전체적으로 이는 특정 사이트에서 다른 사이트로 무작위로 이동한다는 마르코프 체인의 가정과 크게 다르지 않을 수 있겠다. 이러한 상태에서 각 사이트가 차지하는 ‘지분’ 혹은 점유율이 해당 웹사이트가 전체 웹 풍경에서 누리는 ’중요성’이 될 것이다.

아울러 앞서 페이지랭크의 정의가 동어반복처럼 느껴졌던 이유도 이제 알 수 있다. 이는 장기에 도달하게 되는 일종의 수렴 상태인 셈이다. 이렇게 마르코프 체인과 페이지랭크가 연결된다!

Reference

Page, Larry, “The PageRank Citation Ranking: Bringing Order to the Web,” http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf. ↩︎

Tibshirani, Ryan, “PageRank,”
https://www.stat.cmu.edu/~ryantibs/datamining/lectures/03-pr.pdf.