추천시스템과 Matrix Decompositions — 3. 고유값과 고유벡터, Cholesky Decomposition

이번엔 내용이 좀 많고 어려웠습니다..! Matrix decomposition의 원리를 다 이해해보려고 며칠동안 독기품고 정리했습니다..!! 말투를 반말로 바꾸겠습니다 😄

좌표를 잃지 않기 위해 4단원 ‘Matrix Decompositions의 목차를 다시 한 번 정리하고 오늘 다룰 부분을 알아보자.

4.1 Determinant and Trace

4.2 Eigenvalues and Eigenvectors ← 여기 끝부분

4.3 Cholesky Decomposition ← 여기

4.4 Eigendecomposition and Diagonalization ← 여기

4.5 Singular Value Decomposition

이번 글에서 다룰 내용은 4.2의 끝부분, 4.3, 4.4 단원이다.

뒤에도 더 있지만, SVD까지 정리하는 것을 목표로 하고 있다!

Eigenvector 이야기가 아직 끝나지 않았다!

Example 4.9 (Google’s PageRank - Webpages as Eigenvectors) 구글은 행렬 $A$의 고유값 중 최대값에 대응되는 고유벡터를 이용하여 검색 시 페이지에 대한 랭크를 결정한다. 이러한 ‘PageRank’라고 불리는 알고리즘은 1996년 스탠포드 대학교의 래리 페이지(Larry Page)와 세르게이 브린(Sergey Brin)에 의해 탄생했다. 어느 웹페이지의 중요도는 해당 웹페이지를 링크한 페이지의 중요도에 의해 계산될 수 있다. 개발자들은 모든 웹사이트들을 하나의 거대한 directed graph로 만든 후, 각 페이지가 어디에 링크되는지 보았다. PageRank는 웹사이트 $a_i$의 가중치(중요도) $x_i \geqslant 0$로 $a_i$를 가리키는 페이지의 수를 사용한다. 추가적으로, $a_i$를 가리키는 웹사이트의 중요도도 고려한다. 어느 유저의 탐색은 이 그래프의 전이 행렬(transition matrix) $A$로 나타낼 수 있을 것이다. 그럼 이 행렬은 누군가가 얼마의 확률로 어느 페이지에 도달할지 알려준다. 어느 웹사이트의 초기 중요도 벡터를 $x$라고 해보자. $x$, $Ax$, $A^2x$, $\cdots$ 가 $x^*$라는 벡터로 수렴한다. $A$의 특성이 그렇다. 이 벡터 $x^*$를 PageRank라고 부르며, $Ax^*=x^*$를 만족한다. 즉, 어느 웹사이트의 중요도 벡터는 행렬 $A$의 고유값 1에 상응하는 고유벡터인 셈이다. $x^*$를 정규화하면($||x^* || = 1$), 각 요소는 확률로 해석될 수 있다. 상세한 사항은 원논문 Page et al., 1999에서 찾아볼 수 있다.

Graphical Intuition in Two Dimensions

determinants, eigenvectors, 그리고 eigenvalues에 대해 직관적인 이해로 들어가보자. Figure 4.4는 행렬 $\mathbf{A}_1$, …, $\mathbf{A}_5$와 이들에 의한 점들의 변형을 보여주고 있다.

• $\mathbf{A}_1 = \begin{bmatrix} \frac{1}{2} & 1 \\ 0 & 2 \end{bmatrix}$. 두 고유벡터들의 방향이 2차원 canonical basis 벡터들과 나란한 상황이다. 수직축 방향으로 2만큼 늘어나고(고유값 $\lambda_1=2$), 수평축 방향으로 $\frac{1}{2}$만큼 압축된다. 넓이는 보존된다.
• $\mathbf{A}_2 = \begin{bmatrix} 1 & \frac{1}{2} \\ 0 & 1 \end{bmatrix}$은 전단 매핑(sheering mapping)인데, 즉, y축의 양의 방향에 있다면 오른쪽으로, 음의 방향에 있다면 왼쪽으로 전단한다. 이 매핑도 넓이를 보존한다. 고유값은 두 값이 동일한 $\lambda_1=1=\lambda_2$이며, 고유 벡터들은 collinear이다. 즉, 그림처럼 수평 축 방향으로만 늘어나거나 줄어든다.
• $\mathbf{A}_3 = \begin{bmatrix} \cos{\frac{\pi}{6}} & -\sin{\frac{\pi}{6}} \\ \sin{\frac{\pi}{6}} & \cos{\frac{\pi}{6}} \end{bmatrix}=\frac{1}{2}\begin{bmatrix} \sqrt{3} & --1 \\ 1 & \sqrt{3} \end{bmatrix}$은 점들을 $\frac{\pi}{6}$, 즉 30도만큼 반시계 방향으로 회전시키다. 그리고 허수의 고유값을 갖는다.
• $\mathbf{A}_4 = \begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix}$은 표준 기저에서의 2차원 도메인을 1차원으로 줄이는 매핑이다. 한 고유값이 0이기 때문에, 이에 해당하는 파란색 고유벡터 방향의 점들은 넓이가 0이 된다. 반면 이와 수직인 빨간색 고유벡터 방향으로는 고유값인 $\lambda_2=2$만큼 늘어난다.
• $\mathbf{A}_5 = \begin{bmatrix} 1 & \frac{1}{2} \\ \frac{1}{2} & 1 \end{bmatrix}$는 전단도 하고 늘리기도 하는 매핑이다. 이 행렬의 determinant는 $|\det(\mathbf{A}_5)|=\frac{3}{4}$이기 때문에, 넓이를 75%로 만든다. 빨간 고유벡터 방향의 넓이는 $\lambda_2=1.5$에 의해 늘어나고, 파란 고유벡터 방향의 넓이는 $\lambda_1=0.5$에 의해 줄어든다.

---

Theorem 4.12. 서로 다른 고유값 $\lambda_1, ..., \lambda_n$을 갖는 행렬 $\mathbf{A}\in \mathbb{R}^{n\times n}$의 고유벡터 $x_1, ..., x_n$는 선형 독립이다.

위 정리는 n개의 서로 다른 고유값을 갖는 행렬의 고유 벡터들은 $\mathbb{R}^n$의 기저를 형성한다는 것이 된다.

Definition 4.14. 만약 정방행렬 $\mathbf{A} \in \mathbb{R}^{n \times n}$이 $n$보다 적은 선형 독립의 고유 벡터를 갖는다면 $defective$이다.

$non-defective$ 행렬 $\mathbf{A} \in \mathbb{R}^{n \times n}$이 필수적으로 $n$개의 서로 다른 고유값을 필요로 하는 것은 아니다. 하지만, 고유 벡터들이 $\mathbb{R}^n$의 기저를 형성해야한다.

---

4.3 Cholesky Decomposition

머신러닝에서 우리가 자주 마주하는 특별한 유형의 행렬을 분해하는데는 다양한 방법들이 있다. 양의 실수에서 $9$가 $3\cdot 3$으로 분해되는걸 생각해보자. 행렬에 대해서 비슷하게 하려면 좀 조심해야한다. symmetric, positive definite matrices에 대해서는, Cholesky 분해가 유용하다!

Theorem 4.18 (Cholesky Decomposition). Symmetric, positive definite 행렬 $\mathbf{A}$는 $\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}$로 분해될 수 있다. $\mathbf{L}$은 양의 대각 요소를 가진 lower triangular 행렬이다.

$$\begin{bmatrix}a_{11} & \cdots & a_{1n} \\\vdots & \ddots & \vdots \\a_{n1} & \cdots & a_{nn}\end{bmatrix}=\begin{bmatrix}l_{11} & \cdots & 0 \\\vdots & \ddots & \vdots \\l_{n1} & \cdots & l_{nn}\end{bmatrix}\begin{bmatrix}l_{11} & \cdots & l_{1n} \\\vdots & \ddots & \vdots \\0 & \cdots & l_{nn}\end{bmatrix}$$

이 때의 $\mathbf{L}$을 $\mathbf{A}$의 Cholesky factor라고 부르며, $\mathbf{L}$은 유일하다.

Symmetric positive definite 행렬은 3단원에 나오는데, 잠시 살펴보자.

Definition 3.4 (Symmetric, Positive Definite Matrix)

$$\forall x \in V \setminus \left\{ \mathbf{0}\right\} : x^{\top}\mathbf{A} x > 0$$

위 식을 만족하는 대칭 행렬 $\mathbf{A} \in \mathbb{R}^{n \times n}$을 symmetric, positive definite, 또는 그냥 positive definite이라고 부른다.

예를 들어 $\mathbf{A} = \begin{bmatrix} 9 & 6 \\ 6 & 5 \end{bmatrix}$의 경우, $\begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 9 & 6 \\ 6 & 5 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = (3x_1 + 2x_2)^2 + x_2^2 > 0$이기 때문에 symmetric, positive definite이다.

이제 symmetric positive definite 행렬에 대해 Cholesky 분해하는 예제를 보자.

Example 4.10 (Cholesky Factorization) Symmetric, positive definite 행렬 $\mathbf{A} \in \mathbb{R}^{3 \times 3}$이 있다고 하자. Cholesky 분해 $\mathbf{A}=\mathbf{L}\mathbf{L}^\top$을 해보자.

$$\mathbf{A} = \begin{bmatrix}a_{11} & a_{21} & a_{31} \\ a_{21} & a_{22} & a_{32} \\a_{31} & a_{32} & a_{33}\end{bmatrix}=\mathbf{L}\mathbf{L}^{\top}=\begin{bmatrix}l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\l_{31} & l_{32} & l_{33}\end{bmatrix} \begin{bmatrix}l_{11} & l_{21} & l_{31} \\ 0 & l_{22} & l_{32} \\0 & 0 & l_{33}\end{bmatrix}$$

우변을 곱한 결과는

$$\mathbf{A} = \begin{bmatrix}l_{11}^2 & l_{21}l_{11} & l_{31}l_{11} \\ l_{21}l_{11} & l_{21}^2 + l_{22}^2 & l_{31}l_{21} + l_{32}l_{22} \\l_{31}l_{11} & l_{31}l_{21} + l_{32}l_{22} & l_{31}^2 + l_{32}^2 + l_{33}^2\end{bmatrix}$$

그럼 다음과 같은 관계가 도출된다.

$$l_{11} = \sqrt{a_{11}},\;\; l_{22}=\sqrt{a_{22}-l_{21}^2}, \;\; l_{33}=\sqrt{a_{33} - (l_{31}^2) + l_{32}^2)}$$

이런 방식으로 어떠한 symmetric, positive definite $3 \times 3$ 행렬에 대하여도 Cholesky 분해를 할 수 있다.

Cholesky 분해는 머신러닝에서 수 계산을 할 때 매우 중요한 도구이다! 예를 들어, 공분산 행렬은 symmetric positive definite 행렬인데, 많은 곱셈이 필요하다. 하지만 Cholesky 행렬을 통하면 가우시안 분산으로부터 샘플들을 생성할 수 있다든가(?), 랜덤 변수의 선형 변환을 가능하게 해서 오토인코더같은 통계 모델에서 그래디언트를 계산할 때 널리 사용된다든가 하는 것이다. (음..어렵네)

또, Cholesky 분해를 통해 determinant를 쉽게 계산할 수 있다. $A=L L^{\top}$일 때, $\det{A} = \det({L})\det({L}^{\top})=\det(L)^2$라는 걸 알고있다(이전 글에서 전치를 해도 determinant는 변하지 않는다고 배웠다). $L$은 triangular 행렬이기 때문에, determinant는 단지 대각요소들의 제곱의 곱인 $\det(A)=\Pi_i l_{ii}^2$가 된다! 대각행렬의 determinant는 대각 요소들의 곱이기 때문이다.

4.4 Eigendecomposition and Diagonalization

대각 행렬(diagonal matrix)은 대각 위치가 아닌 요소들이 모두 0인 행렬이다. 즉,

$$D=\begin{bmatrix} c_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & c_n \end{bmatrix}$$

과 같은 형태이다. 대각 행렬의 determinant, powers, inverse는 빠르게 계산할 수 있다. determinant는 대각 요소들의 곱이며, 거듭제곱 $D^k$는 각 요소들의 $k$ 제곱으로 표현되며, 대각 요소들이 모두 0이 아닐 경우 역함수 $D^{-1}$는 대각 요소들의 역수로 표현된다.

행렬을 어떻게 diagonal 형태로 변환할 수 있는지 살펴보자. $A$, $D$가 similar 관계라고 하자.

Definition 2.22 (Similarity). 만약 $\tilde{A}=S^{-1}AS$인 regular(=invertible) 행렬 $S \in \mathbb{R}^{n \times n}$가 존재한다면, 두 행렬 $A$, $\tilde{A}$은 similar하다.

Similarity에 대해서는 추후에 자세히 다뤄보도록 하고… 일단 $D = P^{-1}AP$를 만족하는 invertible 행렬 $P$가 있다고 하자. 좀 더 구체적으로는, $A$의 고유값들을 대각 요소로 갖는 대각 행렬 $D$이다. $A$, $D$는 similar하다는 것을 잊지 말자.

Definition 4.19 (Diagonalizable). 만약 행렬 $A \in \mathbb{R}^{n \times n}$가 diagonal matrix와 similar이면, 즉, $D = P^{-1}AP$를 만족하는 invertible 행렬 $P \in \mathbb{R}^{n \times n}$이 존재하면 $A$는 diagonalizable하다.

이제부터 $A \in \mathbb{R}^{n \times n}$을 대각화(diagonalizing)하는 것이 다른 기저에서의 선형 매핑(Section 2.6.1)을 표현하는 방법이라는 것을 알아볼 것이다. 이는 $A$의 고유벡터로 구성된 기저가 된다는 사실!

$A \in \mathbb{R}^{n \times n}$, $\lambda_1, \cdots, \lambda_n$라는 스칼라 집합, $p_1, \cdots , p_n \in \mathbb{R}^{n}$이라는 벡터 집합이 있다고 하자. $P:=[p_1, \cdots, p_n]$, $D \in \mathbb{R}^{n \times n}$을 $\lambda_1, \cdots, \lambda_n$라는 대각 요소를 가진 대각 행렬이라고 정의하자. 만약 $\lambda_1, \cdots, \lambda_n$가 $A$의 고유벡터이고 $p_1, \cdots, p_n$가 이에 상응하는 $A$의 고유벡터라면, 다음을 보일 수 있다:

$$AP=PD$$

말은 복잡하지만, 결국 다음과 같이 표현만 바꾼 것이라고 보인다.

$$Ap_1 = \lambda_1 p_1 \\ Ap_2 = \lambda_2 p_2 \\ \vdots \\ Ap_n = \lambda_np_n$$

대각화(diagonalization) 정의는 $P \in \mathbb{R}^{n \times n}$가 invertible이어야만 한다.즉, $P$는 full rank(Theorem 4.3)여야 한다. $n$개의 선형 독립 고유벡터 $p_1, \cdots, p_n$, 즉, $p_i$가 $\mathbb{R}^{n}$의 기저를 형성해야한다.

Theorem 4.20 (Eigendecomposition). 정방 행렬 $A \in \mathbb{R}^{n\times n}$은 다음과 같이 분해될 수 있다.

$$A = PDP^{-1}$$

$P\in \mathbb{R}^{n \times n}$이고 $D$는 대각 요소가 $A$의 고유값인 대각 행렬, $A$의 고유벡터가 $\mathbb{R}^n$의 기저를 형성해야 한다.

Theorem 4.20은 non-defective인 행렬만이 대각화 될 수 있고 $P$의 열벡터는 $A$의 $n$개의 고유벡터여야 한다는 것을 내포한다.

Symmetric 행렬에 대하여, 우리는 고유값 분해에 대해 심지어 더욱 강력한 결과를 얻을 수 있다.

Theorem 4.21. Symmetric 행렬 $S \in \mathbb{R}^{n \times n}$은 항상 대각화 될 수 있다.

위 정리는 spectral 정리 4.15로부터 곧바로 정리되는 것이다. 추가적으로, spectral 정리는 우리가 $\mathbb{R}^n$의 고유벡터의 ONB를 찾을 수 있다는 것을 의미한다. 즉, $P$는 orthogonal matrix(직교 행렬)가 되어, $D=P^{\top}AP$를 만족하게 된다.

Geometric Intuition for the Eigendecomposition

행렬의 eigendecomposition을 다음과 같이 해석할 수 있다: $A$가 표준 기저 관점에서의 선형 매핑의 변환 행렬이라고 하자. $P^{-1}$는 표준 기저로부터 eigenbasis로의 기저로의 기저 변환을 수행한다. 이는 고유벡터 $p_i$ (빨간색, 오렌지색 화살표)를 표준 기저 벡터 $e_i$로 대응시킨다. 그 후, 대각행렬 $D$는 고유값 $\lambda_i$만큼 축방향으로 벡터의 크기를 변환시킨다. 마지막으로, $P$는 이렇게 크기가 바뀐 벡터들을 다시 표준 좌표계로 되돌리며 $\lambda_iP_i$로 만든다.

Example 4.11 (Eigendecomposition) $A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$의 eigendecomposition을 계산해보자. Step1 : 고유값과 고유벡터를 계산하자. $A$의 특성방정식은 다음과 같다.

$$\det(A - \lambda I) = \det \left( \begin{bmatrix} 2-\lambda & 1 \\ 1 & 2 - \lambda \end{bmatrix} \right) \\ =(2-\lambda)^2 - 1 \\ =\lambda^2 - 4\lambda + 3 \\ =(\lambda-3)(\lambda -1)$$

$A$의 고유값은 $\lambda_1=1$과 $\lambda_2=3$이 된다. 특성 방정식의 근이 곧 고유값이니 말이다. 그리고 고유벡터의 정의를 통해 다음을 계산하면,

$$\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}p_1 = 1p_1,\;\;\;\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}p_2=3p_2$$

를 계산한

$$p_1=\frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \;\;\; p_2=\frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}$$

가 고유벡터 $p_1$, $p_2$를 계산할 수있다.

Step2 : 존재여부 판단. 고유벡터 $p_1,$ $p_2$는 $\mathbb{R}^2$의 기저를 형성할 수 있다. 그러므로 $A$는 대각화 가능하다.

Step3 : $A$를 대각화하기 위해 행렬 $P$를 만든다. $A$의 고유벡터를 모아 $P$를 만들자.

$$P=[p_1, p_2] = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}$$

그러면 다음을 얻을 수 있다.

$$P^{-1}AP=\begin{bmatrix} 1 & 0 \\ 0 & 3 \end{bmatrix}=D$$

동일하게, 다음을 얻는다. (이 때는 $P=P^{\top}$이라는 것을 이용한다. 고유벡터 $p_1$과 $p_2$가 ONB를 구성하기 때문이다.)

$$\underbrace{\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}}_{A} = \underbrace{\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}}_{P} \underbrace{\begin{bmatrix} 1 & 0 \\ 0 & 3 \end{bmatrix}}_{D} \underbrace{\frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 \\ 0 & 3 \end{bmatrix}}_{P^{\top}}$$

• 대각행렬 $D$의 제곱은 효율적으로 이루어진다. 그러므로, eigenvalue decomposition(만약 존재한다면)을 통해서 행렬 $A \in \mathbb{R}^{n \times n}$에 대한 행렬 제곱을 찾을 수 있다

  $$A^k=(PDP^{-1})^k=PD^kP^{-1}$$

  $D^k$를 계산하는 것은 효율적인데, 각각의 대각 요소에 제곱만 하면 되기 때문이다!

• eigendecomposition $A=PDP^{-1}$이 존재한다고 가정하자. 그럼,

  $$\det(A)=\det(PDP^{-1}) = \det(P)\det(D)\det(P^{-1})=\det(D)=\Pi_i d_{ii}$$

  위처럼 $A$의 determinant 계산이 쉬워진다.

고유값 분해는 정방행렬에 대해서만 사용된다. 일반적인 형태의 행렬을 분해하면 매우 유용할 것이다! 다음 챕터에서 일반적인 형태의 행렬 분해 방법인 singular value decomposition에 대해 알아본다!