코딩 더 매트릭스 - 13장 고유벡터 (2)

필립 클라인의 저서 코딩 더 매트릭스 13장 고유벡터

---

1. Markov 체인에 대해 알아봅니다.
2. 행렬식에 대해 알아봅니다.
3. 행렬식 함수에서 고유값의 특성을 파악합니다.
4. 모든 정방행렬은 고유값을 가짐을 증명합니다.
5. Markov 체인을 PageRank 알고리즘에 적용해 봅니다.

---

Markov 체인

한 무도회장이 있습니다. 일부 사람들은 무대 위에 있고 다른 사람들은 무대 옆에 서 있습니다. 사람들은 무대 옆에 서 있다가 마음에 드는 노래가 나오면 무대 위에 올라가기도 하고 마음에 들지 않는 노래에 무대 옆으로 내려가기도 합니다. 매번 곡이 시작될 때 무대 옆에 있는 사람들 중 56%가 무대 위로 올라가고 무대 위에 있는 사람들 중 12%가 내려옵니다. 행렬을 사용하여 장기적으로 사람들이 어떤 비율을 보이는지 연구할 수 있습니다.

$$\begin{bmatrix} x_{1(t + 1)} \\ x_{2(t + 1)} \end{bmatrix} = \begin{bmatrix} 0.44 & 0.12 \\ 0.56 & 0.88 \end{bmatrix} \begin{bmatrix} x_{1t} \\ x_{2t} \end{bmatrix}$$

위 식에서 $x_1$은 무대 옆에 있는 사람의 수를, $x_2$는 무대 위에 있는 사람의 수를 나타냅니다. 이 시스템은 전체 개체 수가 변하지 않습니다. 이것은 이전의 토끼 개체 수와 다른 점입니다. 행렬 $A = \begin{bmatrix} 0.44 & 0.12 \\ 0.56 & 0.88 \end{bmatrix}$은 1과 0.32를 고유값으로 가집니다. 따라서 $A = S \Lambda S^{-1}$을 만족하는 행렬 $S$가 존재하고 그 중 하나는 $S = \begin{bmatrix}0.21 & -1 \\ 0.98 & 1 \end{bmatrix}$ 입니다. 대각 행렬 $\Lambda = \begin{bmatrix}1 & 0 \\ 0 & 0.32 \end{bmatrix}$와 행렬 $S$에 대해 다음과 같이 쓸 수 있습니다.

$$\begin{aligned} \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} & = (S \Lambda S^{-1})^t \begin{bmatrix} x_{1(0)} \\ x_{2(0)} \end{bmatrix} \\ & = S \Lambda^t S^{-1} \begin{bmatrix} x_{1(0)} \\ x_{2(0)} \end{bmatrix} \\ & = \begin{bmatrix} 0.21 & -1 \\ 0.98 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 0.32 \end{bmatrix}^t \begin{bmatrix} 0.84 & 0.84 \\ -0.82 & 0.18 \end{bmatrix} \begin{bmatrix} x_{1(0)} \\ x_{2(0)} \end{bmatrix} \\ & = 1^t (0.84 x_{1(0)} + 0.84 x_{2(0)}) \begin{bmatrix} 0.21 \\ 0.98 \end{bmatrix} + 0.32^t (-0.82 x_{1(0)} + 0.18 x_{2(0)}) \begin{bmatrix} -1 \\ 1 \end{bmatrix} \\ & = 1^t (x_{1(0)} + x_{2(0)}) \begin{bmatrix} 0.18 \\ 0.82 \end{bmatrix} + 0.32^t (-0.82 x_{1(0)} + 0.18 x_{2(0)}) \begin{bmatrix} -1 \\ 1 \end{bmatrix} \end{aligned}$$

위 식의 마지막에서 두번째 항은 $0.32^t$가 곱해져 점점 작아지게 됩니다. 위 식은 결국 첫번째 항의 행렬 $\begin{bmatrix} 0.18 \\ 0.82 \end{bmatrix}$ 가 사람 수 벡터에 곱해져 무대 위의 사람 수는 82%에 가까워 집니다.

이번에는 전체 사람의 수가 아닌 한 사람의 관점에서 분석해 보겠습니다. Bob이 무도회장에 있을 때 그가 무대 옆에 있다가 위로 올라갈 확률은 56%이고 무대 위에 있다가 옆으로 내려올 확률은 12%입니다. 이러한 상태 천이가 일어날 확률을 천이 확률(transition probability)라 합니다. 천이 확률의 특성상 $x_{1(t)} + x_{2(t)} = 1$입니다. 또 열벡터의 원소의 합이 1인 행렬을 확률 행렬이라 합니다. Bob의 위치는 초기값과 상관없이 행렬 $\begin{bmatrix} 0.18 \\ 0.82 \end{bmatrix}$에 빠르게 접근하게 됩니다.

n-state Markov 체인은 다음 특징을 가지는 이산 랜덤 프로세스(discrete-time random process) 입니다.

• 매시간 시스템은 n개 상태 중 하나에 있습니다.
• 어떤 시간 $t$에 시스템이 상태 j에 있을 경우 $t + 1$에 시스템이 상태 i에 있을 확률은 확률 행렬 $A$의 원소 $A[i,j]$입니다.

2-state Markov 체인은 실제 컴퓨터의 메모리와 캐시 접근 문제에서 비롯되었습니다. 컴퓨터 시스템은 메모리에서 데이터를 가져오는데 걸리는 지연 시간이 클 수 있어 캐시를 사용합니다. 시간 $t$에 CPU가 메모리 주소 $a$에 있는 데이터를 요청하면 시간 $t + 1$에 주소 $a + 1$에 있는 데이터를 요청할 가능성이 높습니다. 프로그램 실행은 종종 배열을 반복적으로 접근하기 때문입니다. 시간상 연속적으로 이루어지는 메모리 접근 요청이 실제 연속된 메모리 주소에서 이루어지는지 여부를 예측하기 위한 모델이 있으면 컴퓨터를 설계하는 사람에게 도움이 될 것입니다.

CPU가 시간 $t$에 주소 $a$에 접근하고, $t + 1$에 $a$에 근접한 주소에 접근할 확률이 56%이고, 캐시에 $a$에 근접한 주소를 담아 놓은 뒤 다시 또 다른 근접한 주소에 접근할 확률이 88%라면 Bob의 무도회 예시와 같은 모델을 만들 수 있습니다.

Markov 체인의 시불변 분포

시불변 분포는 시간적으로 변하지 않는 Markov 체인의 확률 분포입니다. 만약 Bob의 상태에 대한 확률 분포가 어떤 시간 $t$에서 시불변 분포이면 그 후 어떤 시간에도 확률 분포는 동일할 것입니다. $v$를 천이행렬 $A$를 가지는 Markov 체인의 상태에 대한 확률 분포라 하면 $v$가 시불변 분포인 것은 다음과 같이 쓸 수 있습니다.

$$v = Av$$

위 식은 행렬 $A$의 고유값이 1일 때 대응하는 고유 벡터가 $v$임을 의미합니다.

$A$를 열확률 행렬이라 하면 각 열의 모든 원소의 합은 1입니다. 그리고 $A -I$의 열의 합은 0이 됩니다. 아래는 열확률 행렬에 대한 한 예시입니다.

$$\begin{aligned} A & = \begin{bmatrix} 0.6 & 0.2 \\ 0.4 & 0.8 \end{bmatrix} \\ A - I & = \begin{bmatrix} -0.4 & 0.2 \\ 0.4 & -0.2 \end{bmatrix} \end{aligned}$$

위 예시는 $A - I$가 비가역적임을 의미하고 식 $(I - A)v = 0$에서 $v$가 고유값 1에 대한 고유벡터임을 보여줍니다.

무도회장 예시와 컴퓨터의 메모리 캐시 접근 문제를 웹페이지의 순위를 정하는 PageRank 개념에 적용할 수 있습니다. Bob은 어떤 웹페이지에서 시작하여 다음과 같이 다음 페이지를 선택합니다.

• Bob은 현재 웹페이지에서 85%의 확률로 어느 링크를 선택하여 방문합니다.
• Bob은 현재 웹페이지에서 15%의 확률로 어떤 랜덤 웹페이지를 방문합니다.

위 정리를 적용하면 시불변 분포가 있으며 누승법으로 근사 고유벡터를 찾을 수 있습니다.

행렬식

$A$를 2 x 2 행렬이라 하고 이 행렬의 열 $a_1$, $a_2$가 직교한다면 다음과 같이 직사각형을 그릴 수 있습니다.

$\{\alpha_1 a_1 + \alpha_2 a_2 : 0 \le \alpha_1, \alpha_2 \le 1 \}$

직사각형의 면적은 두 변의 길이의 곱이므로 $\parallel a_1 \parallel \parallel a_2 \parallel$ 입니다. 좀 더 일반적으로 $A$는 n x n 행렬이고 행렬의 열 $a_1, ..., a_n$이 직교한다고 하면 이 경우 hyper rectangle의 부피는 n개 변의 길이의 곱 $\parallel a_1 \parallel \parallel a_2 \parallel ... \parallel a_n \parallel$ 입니다.

$\{\alpha_1 a_1 + ... + \alpha_n a_n : 0 \le \alpha_1, ..., \alpha_n \le 1 \}$

이제 행렬의 열들이 직교한다는 가정을 없애면 집합 $\{\alpha_1 a_1 + \alpha_2 a_2 : 0 \le \alpha_1, \alpha_2 \le 1 \}$은 평행사변형입니다.

$\{\alpha_1 a_1 + \alpha_2 a_2 : 0 \le \alpha_1, \alpha_2 \le 1 \}$

$a_2^{*}$는 $a_2$의 $a_1$에 대한 직교 투영이고 평행사변형의 면적은 $\parallel a_1^{*} \parallel \parallel a_2^{*} \parallel$ 입니다.

평행사변형의 면적은 다음과 같은 성질을 가집니다.

• 만약 $a_1$과 $a_2$가 직교이면 면적은 $\parallel a_1 \parallel \parallel a_2 \parallel$ 입니다.
• 좀 더 일반적으로 면적은 $\parallel a_1^{*} \parallel \parallel a_2^{*} \parallel$와 같이 표현되며 $a_1^{*}$, $a_2^{*}$는 $a_1$, $a_2$를 직교화한 벡터입니다.
• 임의의 한 벡터 $a_i$에 스칼라 $\alpha$를 곱하는 것은 $a_i^{*}$에 $\alpha$를 곱하는 것과 같으며 면적에 $|\alpha|$를 곱하는 것과 같습니다.
• $a_1$의 임의의 스칼라배를 $a_2$에 더해도 $a_2^{*}$는 변하지 않고 따라서 면적도 변하지 않습니다.

$a_1$의 임의의 스칼라배를 $a_2$에 더한 평행사변형

• $a_1$과 $a_2$가 일차종속이면 $a_2^{*}$는 영벡터이므로 면적은 영입니다.
• $a_1$과 $a_2$를 바꾸어도 평행사변형은 바뀌지 않으며 면적도 바뀌지 않습니다.

평행육면체의 경우 열을 직교화 해 $a_1^{*}, a_2^{*}, ..., a_n^{*}$를 구하고 이들의 길이를 곱하면 부피를 구할 수 있습니다. 평행육면체의 성질은 평행사변형의 면적의 성질과 같습니다.

아래와 같은 다각형의 면적은 평행사변형의 면적을 이용해 구할 수 있습니다.

하지만 아래와 같은 다각형은 평행사변형을 이용해 면적을 구하기가 어려워 보입니다.

이런 이유 때문에 부호를 가진 면적(signed area)을 고려합니다. 벡터 $a_i$와 $a_{i + 1}$로 형성된 평행사변형의 부호를 가진 면적은 벡터가 어떻게 배열되었는지에 따라 결정됩니다. 아래와 같이 두 벡터가 반시계방향으로 배열되어 있다면 그 면적은 양수입니다.

반면에 아래와 같이 두 벡터가 시계방향으로 배열되어 있다면 그 면적은 음수입니다.

이는 벡터의 외적의 부호가 오른손의 법칙을 따르는 것과 같습니다.

앞서 봤던 다각형을 다시 살펴보겠습니다. 벡터 $a_2$와 $a_3$가 시계 방향으로 배열되어 있으므로 두 벡터가 이루는 면적은 음수입니다. 빼어진 면적은 후에 $a_3$와 $a_4$, $a_4$와 $a_5$, $a_5$와 $a_6$가 이루는 면적이 더해져 결국 원하는 면적만 더해집니다.

2 x 2 행렬 $A$의 열을 $a_1$, $a_2$라 하면 부호를 가지는 면적은 $A[1,1] A[2,2] - A[2,1] A[1,2]$입니다. 이는 다음 그림을 통해 증명할 수 있습니다.

그림에서 평행사변형의 면적은 회색으로 칠해진 면적의 2배입니다. 그리고 회색으로 칠해진 면적은 직사각형의 넓이 $ad$에서 다른 삼각형들의 면적을 뺀 넓이입니다. 이를 식으로 쓰면 다음과 같습니다.

$$2 \cdot (ad - \frac{ab}{2} - \frac{cd}{2} - \frac{(a - c)(d - b)}{2}) = ad - bc$$

부호를 가지는 면적은 2 x 2 행렬의 행렬식(determinant)입니다. 좀 더 일반적으로 행렬식은 일종의 함수입니다.

$$det : 실수의\text{ }정방행렬 \to \Bbb{R}$$

열 $a_1, ..., a_n$을 가지는 n x n 행렬 $A$에 대해 $det\text{ }A$는 벡터 $a_1, ..., a_n$에 의해 정의되는 평행육면체의 부호를 가지는 부피입니다. 아래에서는 행렬식의 간단한 예를 소개합니다.

• $a_1, ..., a_n$은 표준 기저벡터 $e_1, ..., e_n$이라 하면 $A$는 단위행렬입니다. 이 경우 평행육면체는 $n$차원 큐브이고 $det\text{ }A = 1$입니다.
• 여러가지 양수로 벡터들을 확대/축소할 때 평행육면체는 더이상 큐브가 아니게 되고 $A$는 양의 대각원소를 가지는 대각행렬이 되고 $det\text{ }A$는 대각원소들의 곱입니다.

행렬식의 성질은 평행육면체의 부피의 성질과 같습니다. $A = \begin{bmatrix} \text{ } & \text{ } & \text{ } \\ a_1 & ... & a_n \\ \text{ } & \text{ } & \text{ } \end{bmatrix}$이라 하면,

• 만약 $a_1, ..., a_n$이 직교하면 $det\text{ }A = \parallel a_1 \parallel ... \parallel a_n \parallel$입니다.
• 일반적으로 $det\text{ }A = \parallel a_1^{*} \parallel ... \parallel a_n^{*} \parallel$입니다.
• 열 $a_i$에 $\alpha$를 곱하는 것은 행렬식에 $\alpha$를 곱하는 것과 같습니다.
• 임의의 $i < j$에 대해 $a_i$의 배수를 $a_j$에 더하여도 행렬식은 변하지 않습니다.

정방행렬 $A$가 가역적일 필요충분조건은 $A$의 행렬식이 0이 아닐 때 입니다. 행렬식은 평행육면체의 부피이고 벡터들 중 일차종속인 경우가 있다면 부피는 0이 될 것입니다. 이는 $det\text{ }A = 0$임을 의미합니다.

한편 상삼각행렬의 행렬식은 대각원소의 곱입니다. 상삼각행렬은 다음과 같은 형태를 가집니다.

$$\begin{bmatrix} a_{11} & a_{12} & a_{13} & ... & a_{1n} \\ & a_{22} & a_{23} & ... & a_{2n} \\ & & a_{33} & ... & a_{3n} \\ & & & ... & \\ & & & & a_{nn} \end{bmatrix}$$

기본 열연산을 수행하면 상삼각행렬을 대각행렬로 바꿀 수 있고 이 때 대각원소들은 값을 유지합니다. 따라서 상삼각행렬의 행렬식은 대각원소들의 곱입니다.

한편 행렬식은 다음 두 성질을 가집니다.

• $det\text{ }A$ 는 A의 원소의 일차 함수입니다.
• $det\text{ }(AB) = det\text{ }A \text{ }det\text{ }B$

행렬식 함수를 통해 나타낸 고유값의 특성

n x n 행렬 $A$와 스칼라 $x$에 대한 행렬 $xI - A$가 있습니다.

$$\begin{bmatrix} x & \text{ } & \text{ } \\ \text{ } & ... & \text{ } \\ \text{ } & \text{ } & x \end{bmatrix} - \begin{bmatrix} \text{ } & \text{ } & \text{ } \\ \text{ } & A & \text{ } \\ \text{ } & \text{ } & \text{ } \end{bmatrix}$$

$det\text{ }(xI - A)$는 $x$의 n 또는 그 이하 차수 다항식이고 이 것을 $A$의 특성다항식이라 합니다. 아래와 같이 다시 쓸 수 있습니다.

$$p_A(x) = det\text{ }(xI - A)$$

$p_A(\lambda) = 0$일 필요충분조건은 행렬 $\lambda I - A$가 일차종속인 열을 가지는 경우, $(\lambda I - A)v$가 영벡터인 영이 아닌 벡터 $v$가 존재하는 경우, $\lambda$가 고유값인 경우입니다.

복소필드 $\Bbb{C}$상의 모든 정방행렬은 고유값을 가짐

복소필드 $\Bbb{C}$상의 모든 정방행렬은 고유값을 가집니다. 이 명제의 증명은 다항식의 두 가지 형태로 전개됩니다. 아래와 같은 다항식이 있습니다.

$$\alpha_0 + \alpha_1 x + \alpha_2 x^2 + ... + \alpha_k x^k$$

위 식은 다음과 같이 쓸 수도 있습니다.

$$\beta (x - \lambda_1) (x - \lambda_2) ... (x - \lambda_k)$$

위 두 식의 형태를 선형결합으로서 표현해 보겠습니다. $A$를 $\Bbb{C}$상의 n x n 행렬이고 $v$를 $\Bbb{C}$상의 n-벡터라 하겠습니다. 벡터 $v, Av, A^2v, ..., A^nv$가 있을 때 이들은 $\Bbb{C}^n$ 상의 n + 1 개 벡터이므로 일차종속입니다. 따라서 다음과 같이 자명하지 않은 일차결합으로 표현할 수 있습니다.

$$\begin{aligned} 0 & = \alpha_0 v + \alpha_1 Av + \alpha_2 A^2 v + ... + \alpha_n A^n v \\ & = v(\alpha_0 + \alpha_1 A + \alpha_2 A^2 + ... + \alpha_n A^n) \end{aligned}$$

식 $\alpha_0 + \alpha_1 A + \alpha_2 A^2 + ... + \alpha_n A^n$은 다항식의 두 가지 형태처럼 아래와 같이 바꿔 쓸 수 있습니다.

$$\beta (A - \lambda_1 I) (A - \lambda_2 I) ... (A - \lambda_k I)$$

따라서 다음과 같은 식을 얻습니다.

$$0 = \beta (A - \lambda_1 I) (A - \lambda_2 I) ... (A - \lambda_k I) v$$

일차종속의 선형결합이므로 $v$는 $\beta (A - \lambda_1 I) (A - \lambda_2 I) ... (A - \lambda_k I)$의 영공간에 포함됩니다. 따라서 $A - \lambda_i I$중 하나는 비가역적이고 이 때 $\lambda_i$는 $A$의 고유값입니다. 따라서 $\Bbb{C}$상의 정방행렬은 고유값을 가집니다.

PageRank

Bob은 매 이터레이션마다 현재 웹페이지에서 다른 페이지로 나가는 링크를 선택하여 방문합니다. 만약 현재 웹페이지에서 다른 페이지로 나가는 링크가 없다면 현제 웹페이지에 머무릅니다. 예를 들어 다음 링크 그래프는 아래와 같은 Markov 체인 천이행렬을 갖습니다.

$$\begin{bmatrix} 1 & \text{ } & \text{ } & \frac{1}{2} & \text{ } & \text{ } \\ \text{ } & \text{ } & 1 & \frac{1}{2} & \frac{1}{3} & \frac{1}{2} \\ \text{ } & 1 & \text{ } & \text{ } & \text{ } & \text{ } \\ \text{ } & \text{ } & \text{ } & \text{ } & \frac{1}{3} & \text{ } \\ \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \frac{1}{2} \\ \text{ } & \text{ } & \text{ } & \text{ } & \frac{1}{3} & \text{ } \end{bmatrix}$$

누승법을 사용하여 확정적인 페이지 순위를 계산하려 하면 두 가지 잘못된 점이 있습니다.

• 어떤 상태에서는 빠져 나올 수 없는 곳이 있습니다. 하나는 페이지 2와 3 상태이고 다른 하나는 페이지 1 입니다.
• Markov 체인의 일부가 주기적인 동작을 유발합니다. Bob이 페이지 2와 3 상태에 들어가면 확률 분포는 각 이터레이션마다 변경됩니다.

첫번째 잘못된 점은 복수의 시불변 분포가 존재함을 의미합니다. 두번째 잘못된 점은 누승법이 수렴되지 않을 수 있음을 의미합니다. 바람직하게는 Markov 체인은 하나의 시불변 분포를 가지고 있어야 합니다.

이번에는 다음과 같은 행렬이 있습니다.

$$\begin{bmatrix} \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$

이 Markov 체인에서 웹 사용자는 어느 페이지에 있든 균등한 확률로 선택된 어떤 페이지로 이동합니다. 즉 웹 사용자는 어떤 상태에 고착되지 않으며 고정된 주기적 동작이 없습니다. 첫번째 Markov 체인과 두번째 체인을 결합하면 앞서 발견한 두 가지 잘못된 점을 해결할 수 있습니다. 즉 하나의 유일한 시불변 분포를 가지고 누승법을 적용하면 시불변 분포에 수렴합니다. 새로운 체인은 다음과 같은 식으로 쓸 수 있습니다.

$$A = 0.85 A_1 + 0.15 A_2$$

$A_1$의 각 열의 원소의 합은 1이고 $A_2$의 열의 원소의 합도 1이므로 $0.85 A_1 + 0.15 A_2$의 원소의 합도 1입니다.