Lecture 24. 마코브 행렬 Markov Matrices — 서술
성분이 모두 음이 아니고 각 열의 합이 1인 행렬을 마코브 행렬 이라 한다. 조건이 둘뿐이고
둘 다 대단해 보이지 않는다. 그런데 이 둘만으로 다음이 따라 나온다.
첫째, 고윳값 1이 반드시 존재한다. 둘째, 나머지 고윳값의 절댓값은 1을 넘지 못한다.
L22에서 우리는 A k A^k A k 절댓값이 1보다 작은 것들은 전부 사라지고 고윳값 1의 방향만 살아남는다.
어디서 출발하든 결국 한 곳으로 모인다는 뜻이다. 이것이 마코브 과정의 정상상태이며,
구글의 페이지랭크가 작동하는 원리이기도 하다.
1. 두 조건과 그 뜻 ¶ 먼저 말을 정하자.
두 조건 모두 성분에 대한 조건이라 눈으로 확인할 수 있다. 그런데 왜 하필 열 의 합인가.
열의 합이 1이어야 하는 이유 ¶ 마코브 행렬을 쓰는 목적은 확률분포를 한 걸음 앞으로 밀어 보내는 것이다. 그러니
확률벡터에 곱했을 때 다시 확률벡터가 나와야 한다. 두 조건이 정확히 그것을 보장한다.
p \vv{p} p A p A\vv{p} A p
첫째, 성분이 음이 아닌가. A A A p \vv{p} p A p A\vv{p} A p
둘째, 성분의 합이 1인가. 성분의 합은 모든 성분이 1인 행벡터를 왼쪽에 곱한 것이다.
그 행벡터를 1 T \vv{1}^{\mathsf T} 1 T
( A p 의 성분의 합 ) = 1 T ( A p ) = ( 1 T A ) p (A\vv{p} \text{ 의 성분의 합})
= \vv{1}^{\mathsf T}\left(A\vv{p}\right)
= \left(\vv{1}^{\mathsf T}A\right)\vv{p} ( A p 의 성분의 합 ) = 1 T ( A p ) = ( 1 T A ) p 가운데에서 오른쪽으로 갈 때 결합법칙을 썼다. 괄호를 옮긴 것이 이 절의 핵심이다.
그런데 1 T A \vv{1}^{\mathsf T}A 1 T A j j j A A A j j j
( 1 T A ) j = a 1 j + a 2 j + ⋯ + a n j = 1 ⟹ 1 T A = 1 T \left(\vv{1}^{\mathsf T}A\right)_j = a_{1j} + a_{2j} + \cdots + a_{nj} = 1
\qquad\Longrightarrow\qquad
\vv{1}^{\mathsf T}A = \vv{1}^{\mathsf T} ( 1 T A ) j = a 1 j + a 2 j + ⋯ + a nj = 1 ⟹ 1 T A = 1 T 열의 합이 1이라는 조건이 이 한 줄로 압축된다. 이것을 (3)
1 T ( A p ) = 1 T p = 1 \vv{1}^{\mathsf T}\left(A\vv{p}\right) = \vv{1}^{\mathsf T}\vv{p} = 1 1 T ( A p ) = 1 T p = 1 이다. 합이 1로 보존된다.
이번 강의의 앵커 ¶ 두 지역 사이의 인구 이동을 보자. 해마다 지역 1에 있던 사람의 10%가 지역 2로 가고,
지역 2에 있던 사람의 20%가 지역 1로 온다.
A = [ 0.9 0.2 0.1 0.8 ] A = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix} A = [ 0.9 0.1 0.2 0.8 ] 열을 읽는 법 이 중요하다. j j j j j j ( 0.9 , 0.1 ) (0.9, 0.1) ( 0.9 , 0.1 ) a i j a_{ij} a ij j j j i i i
Figure 1: 왼쪽이 모형이고 오른쪽이 답이다. 두 초기 상태가 같은 곳에 도착한다.
2. 고윳값 1은 우연이 아니다 ¶ A A A
tr ( A ) = 0.9 + 0.8 = 1.7 , det A = 0.9 × 0.8 − 0.2 × 0.1 = 0.72 − 0.02 = 0.7 \operatorname{tr}(A) = 0.9 + 0.8 = 1.7,
\qquad
\det A = 0.9 \times 0.8 - 0.2 \times 0.1 = 0.72 - 0.02 = 0.7 tr ( A ) = 0.9 + 0.8 = 1.7 , det A = 0.9 × 0.8 − 0.2 × 0.1 = 0.72 − 0.02 = 0.7 λ 2 − 1.7 λ + 0.7 = 0 ⟹ ( λ − 1 ) ( λ − 0.7 ) = 0 \lambda^2 - 1.7\lambda + 0.7 = 0
\qquad\Longrightarrow\qquad
(\lambda - 1)(\lambda - 0.7) = 0 λ 2 − 1.7 λ + 0.7 = 0 ⟹ ( λ − 1 ) ( λ − 0.7 ) = 0 고윳값이 1과 0.7이다. 그런데 왜 하필 1인가. 숫자를 잘 골라서 우연히 나온 것인가.
아니다. 세 걸음이면 증명된다.
첫째 걸음 — 전치하면 행의 합이 1이다 ¶ (4) 1 T A = 1 T \vv{1}^{\mathsf T}A = \vv{1}^{\mathsf T} 1 T A = 1 T
( 1 T A ) T = ( 1 T ) T ⟹ A T 1 = 1 \left(\vv{1}^{\mathsf T}A\right)^{\mathsf T} = \left(\vv{1}^{\mathsf T}\right)^{\mathsf T}
\qquad\Longrightarrow\qquad
A^{\mathsf T}\vv{1} = \vv{1} ( 1 T A ) T = ( 1 T ) T ⟹ A T 1 = 1 오른쪽 식을 다시 읽어 보자. A T A^{\mathsf T} A T 1 \vv{1} 1 1 \vv{1} 1 A T x = 1 ⋅ x A^{\mathsf T}\vv{x} = 1 \cdot \vv{x} A T x = 1 ⋅ x
A T 는 고윳값 1 을 가지며, 그 고유벡터가 1 이다 A^{\mathsf T} \text{ 는 고윳값 } 1 \text{ 을 가지며, 그 고유벡터가 } \vv{1} \text{ 이다} A T 는 고윳값 1 을 가지며 , 그 고유벡터가 1 이다 당연한 이야기이다. A T A^{\mathsf T} A T 행 의 합이 1이라는 말은 각 행을 1 \vv{1} 1 A T 1 = 1 A^{\mathsf T}\vv{1} = \vv{1} A T 1 = 1
둘째 걸음 — A A A A T A^{\mathsf T} A T ¶ 우리가 알고 싶은 것은 A A A A T A^{\mathsf T} A T
특성다항식을 나란히 놓아 보자. 먼저 A − λ I A - \lambda I A − λ I I T = I I^{\mathsf T} = I I T = I
( A − λ I ) T = A T − λ I T = A T − λ I \left(A - \lambda I\right)^{\mathsf T} = A^{\mathsf T} - \lambda I^{\mathsf T}
= A^{\mathsf T} - \lambda I ( A − λ I ) T = A T − λ I T = A T − λ I 이다. 이제 L18의 det M T = det M \det M^{\mathsf T} = \det M det M T = det M M = A − λ I M = A - \lambda I M = A − λ I
det ( A − λ I ) = det ( ( A − λ I ) T ) = det ( A T − λ I ) \det(A - \lambda I)
= \det\left(\left(A - \lambda I\right)^{\mathsf T}\right)
= \det\left(A^{\mathsf T} - \lambda I\right) det ( A − λ I ) = det ( ( A − λ I ) T ) = det ( A T − λ I ) 두 특성다항식이 글자 하나 다르지 않다. 다항식이 같으면 근도 같고 중복도까지 같다.
그러므로 A A A A T A^{\mathsf T} A T
셋째 걸음 — 결론 ¶ A T A^{\mathsf T} A T A A A A T A^{\mathsf T} A T A A A
Figure 2: 세 걸음을 한 장에 담았다. 아래쪽의 경고가 특히 중요하다.
다른 길로도 갈 수 있다 ¶ 같은 결론에 더 짧게 도달하는 길도 있다. 고윳값 1이 있다는 말은 A − I A - I A − I A − I A - I A − I A A A I I I
1 T ( A − I ) = 1 T A − 1 T = 1 T − 1 T = 0 T \vv{1}^{\mathsf T}(A - I) = \vv{1}^{\mathsf T}A - \vv{1}^{\mathsf T}
= \vv{1}^{\mathsf T} - \vv{1}^{\mathsf T} = \vv{0}^{\mathsf T} 1 T ( A − I ) = 1 T A − 1 T = 1 T − 1 T = 0 T 왼쪽을 읽으면 A − I A - I A − I A − I A - I A − I
det ( A − I ) = 0 ⟹ λ = 1 이 고윳값 \det(A - I) = 0
\qquad\Longrightarrow\qquad
\lambda = 1 \text{ 이 고윳값} det ( A − I ) = 0 ⟹ λ = 1 이 고윳값 앵커에서 눈으로 확인해 보자. A − I = [ − 0.1 0.2 0.1 − 0.2 ] A - I = \begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2\end{bmatrix} A − I = [ − 0.1 0.1 0.2 − 0.2 ]
고윳값은 같아도 고유벡터는 다르다 ¶ 여기가 이 강의에서 가장 흔한 오해가 생기는 자리이다.
1 \vv{1} 1 A T A^{\mathsf T} A T A A A 아니다.
(12)
A T [ 1 1 ] = [ 1 1 ] 그러나 A [ 1 1 ] = [ 1.1 0.9 ] ≠ [ 1 1 ] A^{\mathsf T}\begin{bmatrix} 1 \\ 1 \end{bmatrix}
= \begin{bmatrix} 1 \\ 1 \end{bmatrix}
\qquad\text{그러나}\qquad
A\begin{bmatrix} 1 \\ 1 \end{bmatrix}
= \begin{bmatrix} 1.1 \\ 0.9 \end{bmatrix}
\neq \begin{bmatrix} 1 \\ 1 \end{bmatrix} A T [ 1 1 ] = [ 1 1 ] 그러나 A [ 1 1 ] = [ 1.1 0.9 ] = [ 1 1 ] 정상상태를 ( 1 , 1 , … , 1 ) (1, 1, \dots, 1) ( 1 , 1 , … , 1 ) 그것은 A T A^{\mathsf T} A T A A A
앵커에서 A A A λ = 1 \lambda = 1 λ = 1
A − I = [ − 0.1 0.2 0.1 − 0.2 ] ⟹ − 0.1 x 1 + 0.2 x 2 = 0 ⟹ x 1 = 2 x 2 ⟹ x 1 = [ 2 1 ] A - I = \begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2 \end{bmatrix}
\;\Longrightarrow\;
-0.1x_1 + 0.2x_2 = 0
\;\Longrightarrow\;
x_1 = 2x_2
\;\Longrightarrow\;
\vv{x}_1 = \begin{bmatrix} 2 \\ 1 \end{bmatrix} A − I = [ − 0.1 0.1 0.2 − 0.2 ] ⟹ − 0.1 x 1 + 0.2 x 2 = 0 ⟹ x 1 = 2 x 2 ⟹ x 1 = [ 2 1 ] λ = 0.7 \lambda = 0.7 λ = 0.7
A − 0.7 I = [ 0.2 0.2 0.1 0.1 ] ⟹ x 1 + x 2 = 0 ⟹ x 2 = [ 1 − 1 ] A - 0.7I = \begin{bmatrix} 0.2 & 0.2 \\ 0.1 & 0.1 \end{bmatrix}
\;\Longrightarrow\;
x_1 + x_2 = 0
\;\Longrightarrow\;
\vv{x}_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix} A − 0.7 I = [ 0.2 0.1 0.2 0.1 ] ⟹ x 1 + x 2 = 0 ⟹ x 2 = [ 1 − 1 ] 3. 나머지는 1을 넘지 못한다 ¶ 두 번째 사실을 증명하자. 마코브 행렬의 모든 고윳값에 대해 ∣ λ ∣ ≤ 1 |\lambda| \le 1 ∣ λ ∣ ≤ 1
2절에서 A A A A T A^{\mathsf T} A T A T A^{\mathsf T} A T A T A^{\mathsf T} A T 행 의 합이 1이라 한 행씩
따로 보기 좋다.
A T y = λ y A^{\mathsf T}\vv{y} = \lambda\vv{y} A T y = λ y y ≠ 0 \vv{y} \neq \vv{0} y = 0 y \vv{y} y 절댓값이 가장 큰 것 을 골라 그 자리를 m m m y ≠ 0 \vv{y} \neq \vv{0} y = 0 ∣ y m ∣ > 0 |y_m| > 0 ∣ y m ∣ > 0
m m m
λ y m = ∑ j ( A T ) m j y j \lambda\, y_m = \sum_{j} \left(A^{\mathsf T}\right)_{mj} y_j λ y m = j ∑ ( A T ) mj y j 양변의 절댓값을 재고 오른쪽에 삼각부등식을 쓴다. 성분이 음이 아니라
∣ ( A T ) m j ∣ = ( A T ) m j \left|\left(A^{\mathsf T}\right)_{mj}\right| = \left(A^{\mathsf T}\right)_{mj} ∣ ∣ ( A T ) mj ∣ ∣ = ( A T ) mj
∣ λ ∣ ∣ y m ∣ = ∣ ∑ j ( A T ) m j y j ∣ ≤ ∑ j ( A T ) m j ∣ y j ∣ |\lambda|\,|y_m|
= \left|\sum_{j} \left(A^{\mathsf T}\right)_{mj} y_j\right|
\le \sum_{j} \left(A^{\mathsf T}\right)_{mj}\,|y_j| ∣ λ ∣ ∣ y m ∣ = ∣ ∣ j ∑ ( A T ) mj y j ∣ ∣ ≤ j ∑ ( A T ) mj ∣ y j ∣ 이제 ∣ y j ∣ ≤ ∣ y m ∣ |y_j| \le |y_m| ∣ y j ∣ ≤ ∣ y m ∣ m m m
≤ ∑ j ( A T ) m j ∣ y m ∣ = ∣ y m ∣ ∑ j ( A T ) m j = ∣ y m ∣ ⋅ 1 \le \sum_{j} \left(A^{\mathsf T}\right)_{mj}\,|y_m|
= |y_m| \sum_{j} \left(A^{\mathsf T}\right)_{mj}
= |y_m| \cdot 1 ≤ j ∑ ( A T ) mj ∣ y m ∣ = ∣ y m ∣ j ∑ ( A T ) mj = ∣ y m ∣ ⋅ 1 마지막 등호에서 행의 합이 1 이라는 조건이 쓰였다. 양 끝을 이으면
∣ λ ∣ ∣ y m ∣ ≤ ∣ y m ∣ |\lambda|\,|y_m| \le |y_m| ∣ λ ∣ ∣ y m ∣ ≤ ∣ y m ∣ ∣ y m ∣ > 0 |y_m| > 0 ∣ y m ∣ > 0
∣ λ ∣ ≤ 1 |\lambda| \le 1 ∣ λ ∣ ≤ 1 두 사실을 합치면 그림이 완성된다. 고윳값 하나는 정확히 1이고 나머지는 단위원을 벗어나지
못한다. L22의 언어로는 폭발하는 방향이 없다 는 뜻이다.
4. 다른 고유벡터는 성분의 합이 0이다 ¶ 정상상태로 가는 마지막 재료가 하나 남았다. 조금 뜻밖의 사실이다.
A x = λ x A\vv{x} = \lambda\vv{x} A x = λ x λ ≠ 1 \lambda \neq 1 λ = 1 1 T \vv{1}^{\mathsf T} 1 T
오른쪽부터 하면 1 T ( λ x ) = λ ( 1 T x ) \vv{1}^{\mathsf T}(\lambda\vv{x}) = \lambda\left(\vv{1}^{\mathsf T}\vv{x}\right) 1 T ( λ x ) = λ ( 1 T x ) (4) A A A
1 T ( A x ) = ( 1 T A ) x = 1 T x \vv{1}^{\mathsf T}\left(A\vv{x}\right)
= \left(\vv{1}^{\mathsf T}A\right)\vv{x}
= \vv{1}^{\mathsf T}\vv{x} 1 T ( A x ) = ( 1 T A ) x = 1 T x 두 결과가 같아야 하므로
1 T x = λ ( 1 T x ) ⟹ ( 1 − λ ) ( 1 T x ) = 0 \vv{1}^{\mathsf T}\vv{x} = \lambda\left(\vv{1}^{\mathsf T}\vv{x}\right)
\qquad\Longrightarrow\qquad
(1 - \lambda)\left(\vv{1}^{\mathsf T}\vv{x}\right) = 0 1 T x = λ ( 1 T x ) ⟹ ( 1 − λ ) ( 1 T x ) = 0 곱이 0이니 둘 중 하나는 0이다. λ ≠ 1 \lambda \neq 1 λ = 1 1 − λ ≠ 0 1 - \lambda \neq 0 1 − λ = 0
1 T x = 0 ( λ ≠ 1 인 모든 고유벡터에 대해 ) \vv{1}^{\mathsf T}\vv{x} = 0
\qquad (\lambda \neq 1 \text{ 인 모든 고유벡터에 대해}) 1 T x = 0 ( λ = 1 인 모든 고유벡터에 대해 ) 앵커에서 확인된다. x 2 = ( 1 , − 1 ) \vv{x}_2 = (1, -1) x 2 = ( 1 , − 1 ) 1 + ( − 1 ) = 0 1 + (-1) = 0 1 + ( − 1 ) = 0
5. 어디서 출발하든 같은 곳으로 ¶ 이제 조각이 다 모였다. u k + 1 = A u k \vv{u}_{k+1} = A\vv{u}_k u k + 1 = A u k u 0 \vv{u}_0 u 0
u k = A k u 0 = c 1 ⋅ 1 k ⋅ x 1 + c 2 λ 2 k x 2 + ⋯ + c n λ n k x n \vv{u}_k = A^k\vv{u}_0
= c_1 \cdot 1^k \cdot \vv{x}_1
+ c_2\lambda_2^k\,\vv{x}_2 + \cdots + c_n\lambda_n^k\,\vv{x}_n u k = A k u 0 = c 1 ⋅ 1 k ⋅ x 1 + c 2 λ 2 k x 2 + ⋯ + c n λ n k x n 1 k = 1 1^k = 1 1 k = 1 k k k c 1 x 1 c_1\vv{x}_1 c 1 x 1 ∣ λ i ∣ < 1 |\lambda_i| < 1 ∣ λ i ∣ < 1
u k ⟶ c 1 x 1 \vv{u}_k \longrightarrow c_1\vv{x}_1 u k ⟶ c 1 x 1 남은 물음은 c 1 c_1 c 1 놀랍게도 초기 상태와 무관하게 정해진다.
c 1 c_1 c 1 ¶ x 1 \vv{x}_1 x 1 ( 2 , 1 ) (2,1) ( 2 , 1 ) ( 2 3 , 1 3 ) \left(\tfrac23, \tfrac13\right) ( 3 2 , 3 1 )
이제 (25) k = 0 k = 0 k = 0
1 T u 0 = c 1 ( 1 T x 1 ) + c 2 ( 1 T x 2 ) + ⋯ + c n ( 1 T x n ) \vv{1}^{\mathsf T}\vv{u}_0
= c_1\left(\vv{1}^{\mathsf T}\vv{x}_1\right)
+ c_2\left(\vv{1}^{\mathsf T}\vv{x}_2\right) + \cdots
+ c_n\left(\vv{1}^{\mathsf T}\vv{x}_n\right) 1 T u 0 = c 1 ( 1 T x 1 ) + c 2 ( 1 T x 2 ) + ⋯ + c n ( 1 T x n ) 여기서 4절이 일한다. i ≥ 2 i \ge 2 i ≥ 2 1 T x i = 0 \vv{1}^{\mathsf T}\vv{x}_i = 0 1 T x i = 0 통째로 사라진다. 그리고 정규화 덕분에 1 T x 1 = 1 \vv{1}^{\mathsf T}\vv{x}_1 = 1 1 T x 1 = 1
1 T u 0 ⏟ = 1 = c 1 ⋅ 1 + 0 + ⋯ + 0 ⟹ c 1 = 1 \underbrace{\vv{1}^{\mathsf T}\vv{u}_0}_{= \,1} = c_1 \cdot 1 + 0 + \cdots + 0
\qquad\Longrightarrow\qquad
c_1 = 1 = 1 1 T u 0 = c 1 ⋅ 1 + 0 + ⋯ + 0 ⟹ c 1 = 1 왼쪽이 1인 것은 u 0 \vv{u}_0 u 0 (26)
u k ⟶ x 1 \vv{u}_k \longrightarrow \vv{x}_1 u k ⟶ x 1 어디서 출발하는가는 중요하지 않다. 무엇이 살아남는가만 중요하다.
초기 상태 u 0 \vv{u}_0 u 0 c 2 , … , c n c_2, \dots, c_n c 2 , … , c n c 1 c_1 c 1
x 1 \vv{x}_1 x 1 정상상태 라 한다. A x 1 = x 1 A\vv{x}_1 = \vv{x}_1 A x 1 = x 1
앵커를 끝까지 ¶ u 0 = ( 1 , 0 ) \vv{u}_0 = (1, 0) u 0 = ( 1 , 0 ) c 1 = 1 c_1 = 1 c 1 = 1 c 2 c_2 c 2
[ 1 0 ] = 1 ⋅ [ 2 / 3 1 / 3 ] + c 2 [ 1 − 1 ] ⟹ 2 3 + c 2 = 1 ⟹ c 2 = 1 3 \begin{bmatrix} 1 \\ 0 \end{bmatrix}
= 1 \cdot \begin{bmatrix} 2/3 \\ 1/3 \end{bmatrix}
+ c_2\begin{bmatrix} 1 \\ -1 \end{bmatrix}
\qquad\Longrightarrow\qquad
\tfrac23 + c_2 = 1
\qquad\Longrightarrow\qquad
c_2 = \tfrac13 [ 1 0 ] = 1 ⋅ [ 2/3 1/3 ] + c 2 [ 1 − 1 ] ⟹ 3 2 + c 2 = 1 ⟹ c 2 = 3 1 u k = [ 2 / 3 1 / 3 ] + 1 3 ( 0.7 ) k [ 1 − 1 ] \vv{u}_k
= \begin{bmatrix} 2/3 \\ 1/3 \end{bmatrix}
+ \frac13 (0.7)^k \begin{bmatrix} 1 \\ -1 \end{bmatrix} u k = [ 2/3 1/3 ] + 3 1 ( 0.7 ) k [ 1 − 1 ] 몇 걸음 적어 보자.
k k k 0 1 2 3 5 10 ∞ \infty ∞ u 1 u_1 u 1 1 0.9 0.83 0.781 0.7227 0.6784 2 / 3 2/3 2/3 u 2 u_2 u 2 0 0.1 0.17 0.219 0.2773 0.3216 1 / 3 1/3 1/3 합 1 1 1 1 1 1 1
총량은 처음부터 끝까지 1이고, 배분만 바뀐다. 그리고 최종 배분은 초기 상태와 상관없이
( 2 3 , 1 3 ) \left(\tfrac23, \tfrac13\right) ( 3 2 , 3 1 ) Figure 1 ( 0 , 1 ) (0,1) ( 0 , 1 )
상태가 셋이면 ¶ n = 3 n = 3 n = 3 ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) ( 0 , 1 , 0 ) (0,1,0) ( 0 , 1 , 0 ) ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) 심플렉스 라 한다.
P = [ 0.8 0.1 0.1 0.1 0.7 0.3 0.1 0.2 0.6 ] P = \begin{bmatrix}
0.8 & 0.1 & 0.1 \\
0.1 & 0.7 & 0.3 \\
0.1 & 0.2 & 0.6
\end{bmatrix} P = ⎣ ⎡ 0.8 0.1 0.1 0.1 0.7 0.2 0.1 0.3 0.6 ⎦ ⎤ 세 열이 모두 합이 1이다. 고윳값을 구하면 1 , 0.7 , 0.4 1, 0.7, 0.4 1 , 0.7 , 0.4 ( 1 3 , 7 18 , 5 18 ) \left(\tfrac13, \tfrac{7}{18}, \tfrac{5}{18}\right) ( 3 1 , 18 7 , 18 5 )
Figure 3: 아홉 개의 서로 다른 출발점에서 시작한 궤적이 모두 같은 빨간 점으로 모인다.
삼각형 밖으로 나가는 궤적은 하나도 없다. 1절에서 확인한 대로 마코브 행렬이
확률벡터를 확률벡터로 보내기 때문이다.
수렴이 얼마나 빠른가 ¶ (31) ( 0.7 ) k (0.7)^k ( 0.7 ) k 두 번째로 큰
고윳값의 절댓값 ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣
∥ u k − x 1 ∥ ∼ ∣ λ 2 ∣ k \left\|\vv{u}_k - \vv{x}_1\right\| \sim \left|\lambda_2\right|^k ∥ u k − x 1 ∥ ∼ ∣ λ 2 ∣ k ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣ 혼합 시간 이라 부른다. 네트워크로 비유하면 ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣ 어딘가에 병목이 있어 확률이 잘 흘러 다니지 못한다 는 뜻이다.
6. 수렴하지 않는 경우 ¶ 앞 절의 결론에는 "나머지가 전부 단위원 안쪽"이라는 전제가 있었다. 그 전제가 깨지면
어떻게 되는지 두 가지를 보자.
진동하는 경우 ¶ 두 상태를 반드시 번갈아 오가는 사슬을 생각하자.
B = [ 0 1 1 0 ] B = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} B = [ 0 1 1 0 ] 성분이 음이 아니고 열의 합이 1이니 어엿한 마코브 행렬이다. 고윳값을 구해 보자.
tr ( B ) = 0 \operatorname{tr}(B) = 0 tr ( B ) = 0 det B = − 1 \det B = -1 det B = − 1
λ 2 − 1 = 0 ⟹ λ = 1 , − 1 \lambda^2 - 1 = 0
\qquad\Longrightarrow\qquad
\lambda = 1, \; -1 λ 2 − 1 = 0 ⟹ λ = 1 , − 1 이다. ∣ λ 2 ∣ = ∣ − 1 ∣ = 1 |\lambda_2| = |-1| = 1 ∣ λ 2 ∣ = ∣ − 1∣ = 1 죽지 않는다. (21) ∣ λ ∣ ≤ 1 |\lambda| \le 1 ∣ λ ∣ ≤ 1 < 1 < 1 < 1
u 0 = ( 1 , 0 ) \vv{u}_0 = (1, 0) u 0 = ( 1 , 0 ) ( 0 , 1 ) , ( 1 , 0 ) , ( 0 , 1 ) , … (0,1), (1,0), (0,1), \dots ( 0 , 1 ) , ( 1 , 0 ) , ( 0 , 1 ) , … ( 1 2 , 1 2 ) \left(\tfrac12, \tfrac12\right) ( 2 1 , 2 1 ) 존재하지만 도달하지 못한다.
Figure 4: λ = − 1 \lambda = -1 λ = − 1
B B B
정상상태가 유일하지 않은 경우 ¶ A = I A = I A = I I p = p I\vv{p} = \vv{p} I p = p 모든 확률벡터가 정상상태 이다. 고윳값 1이 n n n
뜻으로 읽으면 당연하다. I I I
두 반례를 합치면 조건이 정리된다. 아무 데서 아무 데로든 몇 걸음 안에 갈 수 있고
(연결), 되돌아오는 걸음 수에 공통의 주기가 없어야 (비주기) 유일한 정상상태로 수렴한다.
성분이 전부 양수이면 한 걸음에 어디로든 갈 수 있으므로 두 조건이 한꺼번에 만족된다.
7. 응용 ¶ 인구 이동 ¶ 앵커가 그것이었다. 결론이 실용적이다. 장기적인 인구 배분은 초기 배분과 무관하며,
이동률의 비만으로 정해진다. 앵커에서 지역 1로 오는 비율이 0.2이고 나가는 비율이 0.1이라
비가 2대 1이었고, 정상상태가 정확히 ( 2 3 , 1 3 ) \left(\tfrac23, \tfrac13\right) ( 3 2 , 3 1 )
이것은 우연이 아니다. 정상상태에서는 흘러 나가는 만큼 흘러 들어온다.
0.1 × x 1 = 0.2 × x 2 ⟹ x 1 x 2 = 0.2 0.1 = 2 0.1 \times x_1 = 0.2 \times x_2
\qquad\Longrightarrow\qquad
\frac{x_1}{x_2} = \frac{0.2}{0.1} = 2 0.1 × x 1 = 0.2 × x 2 ⟹ x 2 x 1 = 0.1 0.2 = 2 A x = x A\vv{x} = \vv{x} A x = x
페이지랭크 ¶ 웹 문서에 순위를 매기는 문제를 생각하자. 구글의 아이디어는 이것이다. 웹을 무작위로
떠도는 사람을 상상하고, 그 사람이 각 페이지에 머무는 시간의 비율을 순위로 삼는다.
페이지 j j j d j d_j d j 1 / d j 1/d_j 1/ d j
j j j d j d_j d j 1 / d j 1/d_j 1/ d j 마코브 행렬이다.
그리고 우리가 원하는 순위는 정상상태 x 1 \vv{x}_1 x 1
그런데 실제 웹에서는 세 가지가 어긋난다.
막다른 페이지. 나가는 링크가 없으면 그 열이 통째로 0이라 열의 합이 1이 아니다.
갇힌 무리. 자기들끼리만 링크하는 무리가 있으면 확률이 그리로 빨려 들어가
6절의 I I I
주기. 링크 구조에 주기가 있으면 6절의 B B B
해결책이 감쇠 이다. 무작위 서퍼가 확률 1 − α 1 - \alpha 1 − α 아무 페이지로나
순간이동 한다고 두는 것이다.
G = α A + ( 1 − α ) 1 n J ( J 는 성분이 전부 1인 n × n 행렬 ) G = \alpha A + (1 - \alpha)\,\frac{1}{n}J
\qquad (J \text{ 는 성분이 전부 1인 } n \times n \text{ 행렬}) G = α A + ( 1 − α ) n 1 J ( J 는 성분이 전부 1 인 n × n 행렬 ) G G G α ⋅ 1 + ( 1 − α ) ⋅ 1 = 1 \alpha \cdot 1 + (1-\alpha) \cdot 1 = 1 α ⋅ 1 + ( 1 − α ) ⋅ 1 = 1 G G G 1 − α n > 0 \frac{1-\alpha}{n} > 0 n 1 − α > 0
덤도 있다. 이렇게 만든 G G G
∣ λ 2 ( G ) ∣ ≤ α \left|\lambda_2(G)\right| \le \alpha ∣ λ 2 ( G ) ∣ ≤ α 를 만족한다는 것이 알려져 있다. 곧 감쇠 인자가 곧 수렴 속도 이다. α \alpha α α = 0.85 \alpha = 0.85 α = 0.85
8. 열의 합 0과 열의 합 1 ¶ 지난 강의의 앵커를 다시 보자.
A 연속 = [ − 1 2 1 − 2 ] ( 열의 합이 0 ) A_{\text{연속}} = \begin{bmatrix} -1 & 2 \\ 1 & -2 \end{bmatrix}
\qquad (\text{열의 합이 } 0) A 연속 = [ − 1 1 2 − 2 ] ( 열의 합이 0 ) 그리고 이번 강의의 앵커이다.
A 이산 = [ 0.9 0.2 0.1 0.8 ] ( 열의 합이 1 ) A_{\text{이산}} = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}
\qquad (\text{열의 합이 } 1) A 이산 = [ 0.9 0.1 0.2 0.8 ] ( 열의 합이 1 ) 닮았다고 느꼈다면 맞다. 두 행렬은 이렇게 이어져 있다.
A 이산 = I + 0.1 A 연속 A_{\text{이산}} = I + 0.1\,A_{\text{연속}} A 이산 = I + 0.1 A 연속 곱해 보면 확인된다. I + 0.1 [ − 1 2 1 − 2 ] = [ 1 − 0.1 0.2 0.1 1 − 0.2 ] I + 0.1\begin{bmatrix} -1 & 2 \\ 1 & -2\end{bmatrix}
= \begin{bmatrix} 1 - 0.1 & 0.2 \\ 0.1 & 1 - 0.2\end{bmatrix} I + 0.1 [ − 1 1 2 − 2 ] = [ 1 − 0.1 0.1 0.2 1 − 0.2 ]
왜 열의 합이 0이 1로 바뀌는가 ¶ A c A_c A c 1 T A c = 0 T \vv{1}^{\mathsf T}A_c = \vv{0}^{\mathsf T} 1 T A c = 0 T I + h A c I + hA_c I + h A c
1 T ( I + h A c ) = 1 T + h ( 1 T A c ) = 1 T + h 0 T = 1 T \vv{1}^{\mathsf T}\left(I + hA_c\right)
= \vv{1}^{\mathsf T} + h\left(\vv{1}^{\mathsf T}A_c\right)
= \vv{1}^{\mathsf T} + h\,\vv{0}^{\mathsf T}
= \vv{1}^{\mathsf T} 1 T ( I + h A c ) = 1 T + h ( 1 T A c ) = 1 T + h 0 T = 1 T 열의 합이 0인 행렬에 I I I 다만 마코브 행렬이 되려면
성분도 음이 아니어야 하므로 h h h 1 − h 1 - h 1 − h 1 − 2 h 1 - 2h 1 − 2 h h ≤ 1 2 h \le \tfrac12 h ≤ 2 1
고윳값도 함께 옮겨 간다 ¶ A c x = λ x A_c\vv{x} = \lambda\vv{x} A c x = λ x
( I + h A c ) x = x + h λ x = ( 1 + h λ ) x \left(I + hA_c\right)\vv{x} = \vv{x} + h\lambda\vv{x} = (1 + h\lambda)\,\vv{x} ( I + h A c ) x = x + hλ x = ( 1 + hλ ) x 이다. 고유벡터는 그대로이고 고윳값만 λ ↦ 1 + h λ \lambda \mapsto 1 + h\lambda λ ↦ 1 + hλ
앵커에서 h = 0.1 h = 0.1 h = 0.1
λ = 0 ⟼ 1 , λ = − 3 ⟼ 1 − 0.3 = 0.7 \lambda = 0 \;\longmapsto\; 1,
\qquad
\lambda = -3 \;\longmapsto\; 1 - 0.3 = 0.7 λ = 0 ⟼ 1 , λ = − 3 ⟼ 1 − 0.3 = 0.7 이고, 실제로 두 강의의 고윳값이 그렇다. 고유벡터도 두 강의 모두 ( 2 , 1 ) (2,1) ( 2 , 1 ) ( 1 , − 1 ) (1,-1) ( 1 , − 1 )
연속 (L23) 이산 (L24) 문제 d u d t = A u \dfrac{d\vv{u}}{dt} = A\vv{u} d t d u = A u u k + 1 = A u k \vv{u}_{k+1} = A\vv{u}_k u k + 1 = A u k 조건 열의 합 = 0 = 0 = 0 열의 합 = 1 = 1 = 1 ≥ 0 \ge 0 ≥ 0 한 줄로 1 T A = 0 T \vv{1}^{\mathsf T}A = \vv{0}^{\mathsf T} 1 T A = 0 T 1 T A = 1 T \vv{1}^{\mathsf T}A = \vv{1}^{\mathsf T} 1 T A = 1 T 보존되는 것 1 T u \vv{1}^{\mathsf T}\vv{u} 1 T u 1 T u \vv{1}^{\mathsf T}\vv{u} 1 T u 특별한 고윳값 λ = 0 \lambda = 0 λ = 0 λ = 1 \lambda = 1 λ = 1 죽는 조건 Re ( λ ) < 0 \operatorname{Re}(\lambda) < 0 Re ( λ ) < 0 ∣ λ ∣ < 1 \lvert\lambda\rvert < 1 ∣ λ ∣ < 1 경계 허수축 단위원 정상상태 그 고윳값의 고유벡터 그 고윳값의 고유벡터
경계가 허수축에서 단위원으로 옮겨 간 것도 (44) λ ↦ 1 + h λ \lambda \mapsto 1 + h\lambda λ ↦ 1 + hλ h h h
9. 자주 하는 오해 ¶ 정상상태를 ( 1 , 1 , … , 1 ) (1, 1, \dots, 1) ( 1 , 1 , … , 1 ) ¶ 가장 흔하다. 2절에서 본 대로 1 \vv{1} 1 A T A^{\mathsf T} A T A A A A ( 1 , 1 ) = ( 1.1 , 0.9 ) A(1,1) = (1.1, 0.9) A ( 1 , 1 ) = ( 1.1 , 0.9 )
모든 마코브 행렬이 수렴한다는 오해 ¶ 6절의 B = [ 0 1 1 0 ] B = \begin{bmatrix} 0 & 1 \\ 1 & 0\end{bmatrix} B = [ 0 1 1 0 ] ∣ λ ∣ ≤ 1 |\lambda| \le 1 ∣ λ ∣ ≤ 1 < 1 < 1 < 1
정규화를 잊는 것 ¶ 고유벡터는 스케일이 자유이다. numpy.linalg.eig 는 길이를 1로 맞춰 주므로
( 2 , 1 ) (2,1) ( 2 , 1 ) ( 0.894 , 0.447 ) (0.894, 0.447) ( 0.894 , 0.447 ) 반드시 성분의 합으로 나눠야 한다.
행 기준과 열 기준을 섞는 것 ¶ 1절에서 경고했다. 어느 쪽인지 정하고 끝까지 그것만 써야 한다. 헷갈리면 열의 합을
찍어 보면 된다.
마치며... ¶ 이번 강의에서 다룬 것을 정리하면 다음과 같다.
대상 내용 두 조건 성분 ≥ 0 \ge 0 ≥ 0 = 1 = 1 = 1 한 줄로 1 T A = 1 T \vv{1}^{\mathsf T}A = \vv{1}^{\mathsf T} 1 T A = 1 T 고윳값 1 A T 1 = 1 A^{\mathsf T}\vv{1} = \vv{1} A T 1 = 1 A A A A T A^{\mathsf T} A T 다리 det A T = det A \det A^{\mathsf T} = \det A det A T = det A 경고 고윳값은 같아도 고유벡터는 다르다 나머지 고윳값 ∣ λ ∣ ≤ 1 \lvert\lambda\rvert \le 1 ∣ λ ∣ ≤ 1 다른 고유벡터 성분의 합이 0이다 c 1 = 1 c_1 = 1 c 1 = 1 확률벡터라는 조건 하나로 못박힌다 정상상태 초기 상태와 무관하게 x 1 \vv{x}_1 x 1 속도 ∣ λ 2 ∣ \lvert\lambda_2\rvert ∣ λ 2 ∣ 예외 주기적이면 진동, 갈라져 있으면 유일하지 않다 페이지랭크 감쇠가 성분을 전부 양수로 만들어 준다. ∣ λ 2 ∣ ≤ α \lvert\lambda_2\rvert \le \alpha ∣ λ 2 ∣ ≤ α L23과의 관계 I + h A c I + hA_c I + h A c
열의 합이 1이라는 조건 하나가 고윳값 1의 존재를 보장하고, 그 결과 어떤 초기 상태에서
출발하든 정상상태로 수렴한다는 것을 확인하였다. 증명의 핵심은 여섯 강의 전에 배운
det A T = det A \det A^{\mathsf T} = \det A det A T = det A
지금까지 우리가 다룬 행렬들은 저마다 사정이 있었다. 어떤 것은 고유벡터가 모자랐고
(L21의 결함 행렬), 어떤 것은 고윳값이 복소수였으며(회전행렬), 어떤 것은 고윳값이
단위원 위에 걸터앉아 진동했다(6절).
다음 강의부터는 가장 좋은 행렬을 다룬다. 대칭행렬이다. S = S T S = S^{\mathsf T} S = S T
사실 우리는 이 현상을 이미 목격했다. L21의 앵커 [ 2 1 1 2 ] \begin{bmatrix} 2 & 1 \\ 1 & 2\end{bmatrix} [ 2 1 1 2 ] ( 1 , 1 ) (1,1) ( 1 , 1 ) ( 1 , − 1 ) (1,-1) ( 1 , − 1 )
이번 강의의 내용을 파이썬으로 확인해 보려면 L24 실습 노트북 으로 넘어가면 된다.
무작위 마코브 행렬을 잔뜩 만들어 고윳값 1이 늘 있는지 확인하고, 세 상태의 확률분포가
삼각형 위를 움직여 한 점으로 모이는 것을 보며, 작은 웹을 만들어 페이지랭크를 직접
계산해 볼 수 있다.
