09wk-1: 마코프체인 (6)

최규빈

2023-04-27

강의영상

youtube: https://youtube.com/playlist?list=PLQqh36zP38-xbWjXgaQNqqqZDzuV1QsgL

imports

import numpy as np 

aperiodic

Motivating Examples (cont)

예제3

- 아래의 전이확률을 고려하자.

P =np.array([0.0, 1.0, 0.0, 0.0, 
             1/2, 0.0, 1/2, 0.0,
             0.0, 0.0, 0.0, 1.0,
             0.0, 1.0, 0.0, 0.0]).reshape(4,4)
P

array([[0. , 1. , 0. , 0. ],
       [0.5, 0. , 0.5, 0. ],
       [0. , 0. , 0. , 1. ],
       [0. , 1. , 0. , 0. ]])

- 다이어그램

flowchart LR
  0 -->|1| 1
  1 -->|1/2| 0
  1 -->|1/2| 2
  2 -->|1| 3
  3 -->|1| 1

- 특징1,2:

np.matrix(P)**500

matrix([[0.2, 0.4, 0.2, 0.2],
        [0.2, 0.4, 0.2, 0.2],
        [0.2, 0.4, 0.2, 0.2],
        [0.2, 0.4, 0.2, 0.2]])

- 특징3: 정상분포를 가짐

- 특징4: 초기분포가 정상분포라면 정상확률과정

- 특징5: irr

- 특징6: 주기가 없음

flowchart LR
  0 -->|1| 1
  1 -->|1/2| 0
  1 -->|1/2| 2
  2 -->|1| 3
  3 -->|1| 1

1에서 시작한다면?

• \(1 \to 0 \to 1\), 2번만에 리턴
• \(1 \to 2 \to 3 \to 1\), 3번만에 리턴

이 경우 2와 3의 최대공약수는 1이므로 주기는 1이다. 그리고 finite state space를 가지는 HMC는 모든 state가 항상 같은 주기를 가지므로 이 마코프체인의 모든 주기는 1이다.

주기가 1인 경우는 aperiodic 하다고 표현한다. (언제 올지 몰라)

꿀팁: 자기자신으로 1턴만에 되돌아올 확률이 있다면 항상 aperiodic 하다.

정의 및 이론

- 정의:

- 느낌: 상태 \(i\)에서 \(i\)로 되돌아오는 횟수들의 최대공약수를 HMC \(\{X_t\}\)의 period라고 하고, period=1인 경우를 aperiodic 이라고 한다.

- 이론: HMC \(\{X_t\}\)이 IRR이면, 모든 상태가 항상 같은 주기를 가진다.

에르고딕 마코프체인

정의 및 이론

- Thm: HMC \(\{X_t\}\)가 (1) finite state space를 가지고 (2) irreduciable 하고 (3) aperiodic 이라면, \({\bf P}\)가 수렴하고 수렴한 matrix의 모든 row는 같다. 따라서 임의의 초기분포 \({\boldsymbol \mu}\) 에 대하여

\[\lim_{t\to \infty}{\boldsymbol \mu}^\top{\bf P}^t = {\boldsymbol \pi}^\top \]

이 성립한다. 여기에서 \({\boldsymbol \pi}\)는 \(\{X_t\}\)의 정상분포이다.

- 정의: 아래의 식을 만족하는 HMC \(\{X_t\}\)을 에르고딕하다고 말한다.

\[\lim_{t\to \infty}{\boldsymbol \mu}^\top{\bf P}^t = {\boldsymbol \pi}^\top \]

구글의 페이지랭크

intro

- Google

• Google은 사용자의 검색어와 일치하는 검색 결과를 제공
• Google은 웹사이트들 사이에서 “더 나은” 또는 “더 중요한” 웹사이트가 검색 결과 상위에 나타나도록 순위를 유지
• 이 순위는 전체 문제를 한 번에 해결하는 것이 아니라 먼저 전체적으로 수립되고(검색어와는 독립적으로), 그 후에 검색어와 일치하는 웹사이트들만 해당 순위에 따라 정렬된다고 함

- 이 강의에서는 순위 매기기에 초점을 맞추어 생각해보자. (이는 마코프체인과 관련이 있음)

• ref: https://en.wikipedia.org/wiki/PageRank

- 페이지랭크

• 페이지랭크(PageRank)는 구글 검색에서 웹 페이지의 순위를 결정하는 알고리즘으로 이는 “웹 페이지”와 구글 공동 창업자인 라리 페이지(Larry Page)의 이름을 따서 지어졌음
• 페이지랭크는 웹사이트 페이지의 중요성을 측정하는 방법이며 기본적으로 더 중요한 웹사이일수록 다른 웹사이트에서 더 많은 링크를 받을 가능성이 높다는 점에 착안함
• 페이지랭크는 구글이 검색 결과를 정렬하는 데 사용하는 유일한 알고리즘이 아니지만, 구글에서 사용한 최초의 알고리즘이며, 가장 잘 알려진 알고리즘임

toy example

- 아래는 7개의 website에 대한 web graph이다.

flowchart LR
  0 -->|1/2| 1
  1 -->|1/2| 0
  0 -->|1/2| 2
  1 -->|1/2| 2
  2 -->|1| 3 
  4 -->|1| 3
  3 -->|1| 5 
  6 -->|1| 5

- 여기에서 가장 중요한 웹사이트는 무엇일까?

• 구글의 아이디어는 기본적으로 더 많은 화살표를 받는 쪽이 더 중요한 웹사이트이다 라는 것이었다.
• 이 논리대로라면 노드 2,3,5가 똑같이 중요해보인다.
• 좀 더 생각해보니까 노드2보다 노드3과 노드5가 더 중요해보인다. 왜냐하면 노드2는 확률 1/2 짜리 화살표 2개이지만 노드3과 노드5는 확률 1짜리 화살표가 2개임
• 그렇지만 또 노드3보다는 노드5가 더 중요해보인다. 왜냐하면 노드3을 방문한 사람은 결국은 노드5로 갈테니까 노드3보다 노드5가 더 중요한 사이트라고 볼 수 있다.
• 그럼 노드3의 중요도가 1일때 노드5의 중요도는 얼마정도 될까?

- 구글의 아이디어: random surfer

• 무작위로 웹사이트를 방문하는 가상의 유저를 만들자.
• 그리고 이 유저가 많이 방문하게 되는 웹사이트를 기록하자.

- 구글의 아이디어는 결국 위의 다이어그램을 토대로 transition matrix \({\bf P}\)를 만들고 임의의 초기상태 \({\boldsymbol \mu}\)에 대하여

\[\lim_{t\to\infty}{\boldsymbol \mu}^\top{\bf P}^{t}\]

를 계산하겠다는 의미이다.

- 문제점1: 이 상황은 transition matrix를 만들 수 없는걸?

P = np.array([0.0, 1/2, 1/2, 0.0, 0.0, 0.0, 0.0,
              1/2, 0.0, 1/2, 0.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, ### 이 부분은 다 0이다. 
              0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0]).reshape(7,7)
P

array([[0. , 0.5, 0.5, 0. , 0. , 0. , 0. ],
       [0.5, 0. , 0.5, 0. , 0. , 0. , 0. ],
       [0. , 0. , 0. , 1. , 0. , 0. , 0. ],
       [0. , 0. , 0. , 0. , 0. , 1. , 0. ],
       [0. , 0. , 0. , 1. , 0. , 0. , 0. ],
       [0. , 0. , 0. , 0. , 0. , 0. , 0. ],
       [0. , 0. , 0. , 0. , 0. , 1. , 0. ]])

- 문제점1의 해결: 이러한 경우 상태5에서 다른상태로 갈 확률은 랜덤으로 다시 뿌린다.

P = np.array([0.0, 1/2, 1/2, 0.0, 0.0, 0.0, 0.0,
              1/2, 0.0, 1/2, 0.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0,
              1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7, ### 이렇게 고쳐버리자~
              0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0]).reshape(7,7)
P

array([[0.        , 0.5       , 0.5       , 0.        , 0.        ,
        0.        , 0.        ],
       [0.5       , 0.        , 0.5       , 0.        , 0.        ,
        0.        , 0.        ],
       [0.        , 0.        , 0.        , 1.        , 0.        ,
        0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        ,
        1.        , 0.        ],
       [0.        , 0.        , 0.        , 1.        , 0.        ,
        0.        , 0.        ],
       [0.14285714, 0.14285714, 0.14285714, 0.14285714, 0.14285714,
        0.14285714, 0.14285714],
       [0.        , 0.        , 0.        , 0.        , 0.        ,
        1.        , 0.        ]])

- 문제점2: \(\lim_{t\to\infty}{\boldsymbol \mu}^\top{\bf P}^{t}\)이게 수렴한다는 보장이 어디있지?

수렴의 트릭

- 생각: HMC \(\{X_t\}\)가 에르고딕이려면 (1) finite state space를 가지고 (2) irreducible (3) aperiodic 해야한다.

- 그런데 (N,N) 차원을 가지는 임의의 transition matrix \({\bf P}\)를 아래와 같이 \(\tilde{\bf P}\)로 변형한다면 이 transition matrix는 aperiodic하고 irreducible하게 된다.

\[\tilde{\bf P} = 0.99 \cdot {\bf P} + 0.01 \cdot \frac{1}{N}{\bf J}\]

여기에서 \({\bf J}\)는 \({\bf P}\)와 차원이 같고 모든 원소가 1인 매트릭스이다. 즉

\[{\bf J} = \begin{bmatrix} 1 & 1 & \dots & 1 \\ 1 & 1 & \dots & 1 \\ \dots & \dots & \dots & \dots \\ 1 & 1 & \dots & 1 \end{bmatrix}\]

이다.

- 위의 수식에서 \(\tilde{\bf P}\)는 \({\bf P}\)와 매우 비슷하지만 에르고딕한 마코프체인이다.

- 이러한 \(\tilde{\bf P}\)를 구글매트릭스라고 부르자. 위의 식을 좀 더 간결하게 쓰면

\[{\bf GoogleMatrix}:= \alpha\cdot {\bf P} + (1-\alpha)\cdot\frac{1}{N}{\bf J}\]

와 같이 된다. 여기에서 \(\alpha \in (0,1)\) 이다.

- 여기에서 \(\alpha\)는 수렴의 속도를 결정한다.

• \({\bf P}\)가 원래 수렴안하는 조건이었다면 \(\alpha \approx 1\) 일수록 구글매트릭스는 매우 느리게 수렴할 것이다.
• \(\alpha=0\) 이라면 구글매트릭스는 이미 수렴되어 있다.

구현

P = np.array([0.0, 1/2, 1/2, 0.0, 0.0, 0.0, 0.0,
              1/2, 0.0, 1/2, 0.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0,
              1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7,
              0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0]).reshape(7,7)
P

array([[0.        , 0.5       , 0.5       , 0.        , 0.        ,
        0.        , 0.        ],
       [0.5       , 0.        , 0.5       , 0.        , 0.        ,
        0.        , 0.        ],
       [0.        , 0.        , 0.        , 1.        , 0.        ,
        0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        ,
        1.        , 0.        ],
       [0.        , 0.        , 0.        , 1.        , 0.        ,
        0.        , 0.        ],
       [0.14285714, 0.14285714, 0.14285714, 0.14285714, 0.14285714,
        0.14285714, 0.14285714],
       [0.        , 0.        , 0.        , 0.        , 0.        ,
        1.        , 0.        ]])

alpha= 0.85 
J = np.ones(49).reshape(7,7)
GoogleMatrix = alpha*P + (1-alpha)/7 

np.linalg.matrix_power(GoogleMatrix,100)[0].round(3).tolist()

[0.102, 0.102, 0.145, 0.231, 0.058, 0.304, 0.058]

import pandas as pd 
pd.DataFrame({'website':['state'+i for i in '0123456'], 
             'pagerank': np.linalg.matrix_power(GoogleMatrix,100)[0].round(3).tolist()})

	website	pagerank
0	state0	0.102
1	state1	0.102
2	state2	0.145
3	state3	0.231
4	state4	0.058
5	state5	0.304
6	state6	0.058

다른풀이

_, eigen_vector_matrix = np.linalg.eig(GoogleMatrix.T)

abs(eigen_vector_matrix[:,0])/ abs(eigen_vector_matrix[:,0]).sum()

array([0.10154862, 0.10154862, 0.14470678, 0.2310231 , 0.05839045,
       0.30439198, 0.05839045])

페이지랭크의 약점

- 아래와 같은 상황을 고려하자.

flowchart LR
  0 -->|1/2| 1
  1 -->|1/2| 0
  0 -->|1/2| 2
  1 -->|1/2| 2
  2 -->|1| 3 
  4 -->|1| 3

P = np.arrfffq/5, 1/5,
              0.0, 0.0, 0.0, 1.0, 0.0]).reshape(5,5)
P

array([[0. , 0.5, 0.5, 0. , 0. ],
       [0.5, 0. , 0.5, 0. , 0. ],
       [0. , 0. , 0. , 1. , 0. ],
       [0.2, 0.2, 0.2, 0.2, 0.2],
       [0. , 0. , 0. , 1. , 0. ]])

GoogleMatrix = P*0.85 + 0.15/5 

np.linalg.matrix_power(GoogleMatrix,100)

array([[0.15936255, 0.15936255, 0.22709163, 0.3625498 , 0.09163347],
       [0.15936255, 0.15936255, 0.22709163, 0.3625498 , 0.09163347],
       [0.15936255, 0.15936255, 0.22709163, 0.3625498 , 0.09163347],
       [0.15936255, 0.15936255, 0.22709163, 0.3625498 , 0.09163347],
       [0.15936255, 0.15936255, 0.22709163, 0.3625498 , 0.09163347]])

- 우리는 여기에서 1번네트워크의 page rank를 올리고 싶다고 가정하자. (현재는 5개중 0.15936255)

flowchart LR
  0 -->|1/2| 1
  1 -->|1/2| 0
  0 -->|1/2| 2
  1 -->|1/2| 2
  2 -->|1| 3 
  4 -->|1| 3

Step1: 먼저 1번에서 다른쪽으로 가는 모든 링크를 끊는다. (다른 웹사이트의 page rank를 올려줄 이유가 없음)

flowchart LR
  0 -->|1/2| 1
  0 -->|1/2| 2
  2 -->|1| 3 
  4 -->|1| 3

P = np.array([0.0, 1/2, 1/2, 0.0, 0.0,
              1/5, 1/5, 1/5, 1/5, 1/5,
              0.0, 0.0, 0.0, 1.0, 0.0,
              1/5, 1/5, 1/5, 1/5, 1/5,
              0.0, 0.0, 0.0, 1.0, 0.0]).reshape(5,5)

GoogleMatrix = P*0.85 + 0.15/5 
np.linalg.matrix_power(GoogleMatrix,100)

array([[0.12640228, 0.18012324, 0.18012324, 0.38694897, 0.12640228],
       [0.12640228, 0.18012324, 0.18012324, 0.38694897, 0.12640228],
       [0.12640228, 0.18012324, 0.18012324, 0.38694897, 0.12640228],
       [0.12640228, 0.18012324, 0.18012324, 0.38694897, 0.12640228],
       [0.12640228, 0.18012324, 0.18012324, 0.38694897, 0.12640228]])

Step2: 3개의 더미사이트 5,6,7을 만들어서 1번네트워크와 서로 연결시킨다.

flowchart LR
  0 -->|1/2| 1
  0 -->|1/2| 2
  2 -->|1| 3 
  4 -->|1| 3
  1 -->|1/3| 5
  5 -->|1| 1
  1 -->|1/3| 6
  6 -->|1| 1
  1 -->|1/3| 7 
  7 -->|1| 1 

P = np.array([0.0, 1/2, 1/2, 0.0, 0.0, 0.0, 0.0, 0.0,
              0.0, 0.0, 0.0, 0.0, 0.0, 1/3, 1/3, 1/3,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0,
              1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8,
              0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0,
              0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
              0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
              0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]).reshape(8,8)

GoogleMatrix = P*0.85 + 0.15/8
pagerank =np.linalg.matrix_power(GoogleMatrix,100)[0]
pagerank

array([0.02778839, 0.39804992, 0.03959846, 0.08506721, 0.02778839,
       0.14056921, 0.14056921, 0.14056921])

website = ['state'+i for i in '01234567']
website

['state0',
 'state1',
 'state2',
 'state3',
 'state4',
 'state5',
 'state6',
 'state7']

pd.DataFrame({'pagerank':pagerank,'website':website})

	pagerank	website
0	0.027788	state0
1	0.398050	state1
2	0.039598	state2
3	0.085067	state3
4	0.027788	state4
5	0.140569	state5
6	0.140569	state6
7	0.140569	state7

- 약점을 극복한 구글의 아이디어: 저도 몰라용..