Linear Algebra 9 - Principal Component Analysis
Before starting
“Class” 카테고리에 있는 포스팅들은 실제로 수업에서 배운 내용을 정리하려는 목적으로 작성되었다. 이 글은 그 중 Linear Algebra 과목의 수업을 다룬다…만, 과목명은 페이크고 사실은 생성형 모델을 다루는 수업이다.
Recap.
Gaussian Distribution
먼저 Gaussian Distribution에 대해서 되짚어보자. 평균 $\mu$, 분산 $\sigma$인 Univariate Gaussian Distribution은 다음과 같이 정의된다.
\[p_X(x)=\dfrac{1}{\sqrt{2\pi\sigma^2}}e^{-\dfrac{1}{2}\left(\dfrac{x-\mu}{\sigma}\right)^2}\]이를 확장한게 다음과 같은 Multivariate Gaussian Distribution이다.
\[p_{\vec{X}}(\vec{x})=\dfrac{1}{(2\pi)^{D/2}\vert\Sigma\vert^{1/2}}e^{-\dfrac{1}{2}\left(\vec{x}-\vec{\mu}\right)^T\Sigma^{-1}\left(\vec{x}-\vec{\mu}\right)}\]여기서도 평균은 $\vec{\mu}$, 분산은 $\Sigma$인데, Multivariate이므로 다음과 같이 정의된다.
\[\vec{x}=\begin{pmatrix}x_0 \\ x_1 \\ \vdots \\ x_{D-1}\end{pmatrix},\vec{\mu}=\mathbb{E}[\vec{x}]=\begin{pmatrix}\mu_0 \\ \mu_1 \\ \vdots \\ \mu_{D-1}\end{pmatrix},\Sigma=\begin{pmatrix}\sigma_0^2 & \rho_{0,1} & \cdots & \rho_{0,D-1} \\ \rho_{1,0} & \sigma_1^2 & \cdots & \rho_{1,D-1} \\ \vdots & \vdots & \ddots & \vdots \\ \rho_{D-1,0} & \rho_{D-1,1} & \cdots & \sigma_{D-1}^2 \end{pmatrix}\]여기서 $\rho_{i,j}=\mathbb{E}[(x_i-\mu_i)(x_j-\mu_j)], \sigma_i^2=\mathbb{E}[(x_i-\mu_i)^2]$이다. 여기서 이 Covariance Matrix $\Sigma$가 Symmetric임을 확인하자.
LLN / Statistical Estimator
그런데 우리가 다뤄야 하는 문제는 대부분 이 평균과 분산을 알 수 없다. 그 대신 데이터셋 $D=\lbrace \vec{x_0},\vec{x_1},\cdots,\vec{x_{M-1}} \rbrace$이 주어져서 이들을 가지고 가장 가능성이 높은 평균과 분산을 구해야 하는데, 이것이 Maximum Likelihood Estimation, 즉 MLE이다. 이는 다음과 같이 구할 수 있다.
\[\begin{aligned} \lbrace \hat{\mu}_{ML},\hat{\Sigma}_{ML} \rbrace &= \arg\max\prod_{m=0}^{M-1}p(\vec{x_m}\vert\vec{\mu},\Sigma) \\ &= \arg\max\sum_{m=0}^{M-1}\ln p(\vec{x_m}\vert\vec{\mu},\Sigma) \end{aligned}\]그리고 이 식을 잘 계산해보면 다음과 같은 Closed Form을 구할 수 있다.
\[\hat{\mu}_{ML}=\dfrac{1}{M}\sum_{m=0}^{M-1}\vec{x_m}, \hat{\Sigma}_{ML}=\dfrac{1}{M}\sum_{m=0}^{M-1}(\vec{x_m}-\vec{\mu})(\vec{x_m}-\vec{\mu})^T\]그리고 이와는 별개로, 통계학적으로 같은 문제를 푸는 Statistical Estimator의 경우에는 다음과 같이 Sample Mean과 Sample Covariance를 구할 수 있다.
\[\vec{\mu}=\dfrac{1}{M}\sum_{m=0}^{M-1}\vec{x_m}, \Sigma=\dfrac{1}{M-1}\sum_{m=0}^{M-1}(\vec{x_m}-\vec{\mu})(\vec{x_m}-\vec{\mu})^T\]그런데 $\Sigma$에서 $M$으로 나누느냐 $M-1$로 나누느냐의 차이를 제외하면 이 두가지 방법으로 구한 결과가 동일함을 알 수 있다.
여담으로 MLE의 $\hat{\Sigma}_{ML}$이 실제 $\Sigma$를 과소추정하는 Biased Estimator이기 때문에 통계학적으로는 이를 보정하여 계산하는데, 이 때문에 이 Statistical Estimator를 Unbiased Estimator라고도 부른다.
Eigenvector / Eigenvalue
$D\times D$ 행렬 $A$에 대해 다음을 만족하는 벡터 $\vec{v}$와 상수 $\lambda$가 존재하면 이를 각각 Eigenvector, Eigenvalue라고 부른다.
\[A\vec{v}=\lambda\vec{v}\]그리고 이러한 Eigenvector와 Eigenvalue가 존재하려면 $\det(A-\lambda I)=0$이어야 한다.
그리고 위와는 반대로, 다음과 같이 방향을 바꿔서 계산해본 경우도 생각해볼 수 있다.
\[\vec{u}^T A=\kappa\vec{u}^T\]이렇게 얻어진 $\vec{u}$와 $\kappa$를 각각 Left Eigenvector, Left Eigenvalue라고 부른다. 그리고 이와 구분하기 위해, 일반적인 Eigenvector, Eigenvalue를 각각 Right Eigenvector, Right Eigenvalue라고도 부른다.
그러면 Right Eigenvector/Eigenvalue와 Left Eigenvector/Eigenvalue는 어떤 관계가 있을까? 우선 Left/Right 둘 다 Eigenvector/Eigenvalue의 쌍은 각각 $D$개이다. 또한 Left Eigenvalue의 집합과 Right Eigenvalue의 집합은 동일하다. 이는 Left Eigenvalue나 Right Eigenvalue나 전부 $\det(A-\lambda I)=0$, 혹은 $\det(A-\kappa I)=0$으로 구할 수 있기 때문이다.
그래서 Eigenvalue를 기준으로 하여 (Eigenvalue, Eigenvector)의 쌍을 생각해서 각각 $i$번째 쌍을 각각 $(\vec{v_i},\lambda_i), (\vec{u_i},\kappa_i)$라고 하자. 그러면 임의의 $i,j$에 대해서 다음이 성립한다.
\[\vec{u_i}^T A\vec{v_j}=\vec{u_i}^T(A\vec{v_j})=\vec{u_i}^T(\lambda_j\vec{v_j})=\lambda_j\vec{u_i}^T\vec{v_j}\] \[\vec{u_i}^T A\vec{v_j}=(\vec{u_i}^T A)\vec{v_j}=(\kappa_i\vec{u_i}^T)\vec{v_j}=\kappa_i\vec{u_i}^T\vec{v_j}\] \[\therefore \lambda_j\vec{u_i}^T\vec{v_j}=\kappa_i\vec{u_i}^T\vec{v_j}\]따라서 $\kappa_i=\lambda_j$ 혹은 $\vec{u_i}^T\vec{v_j}=0$이어야 한다. 그런데 위에서 정한 것과 같이 $i\neq j$라면 $\kappa_i\neq\lambda_j$이므로, 이 경우엔 $\vec{u_i}^T\vec{v_j}=0$을 만족해야 한다. 이는 곧 두 벡터의 내적이 0, 즉 직교해야 한다는 의미이다.
Symmetric matrices
그렇다면 만일 $A$가 Symmetric하다면, 즉 $A=A^T$라면 어떨까?
\[\lambda_i \vec{u_i}^T=\vec{u_i}^T A=(A^T\vec{u_i})^T=(A\vec{u_i})^T\]따라서 $\vec{u_i}$ 역시 $A$의 Right Eigenvector가 된다. 즉 Right Eigenvector와 Left Eigenvector는 동일하다.
그리고 모든 Eigenvector를 정규화하자. 즉, $\vec{v_i}^T\vec{v_i}=1$로 만들자. 어차피 Eigenvector는 방향이 중요하기 때문에 이렇게 정규화해도 그 본질적인 의미가 손상되지 않는다.
이상의 정보들을 종합해보면, $D\times D$ Symmetric Matrix $A$의 Eigenvector를 $\vec{v_0},\vec{v_1},\ldots,\vec{v_{D-1}}$라 하면, 다음이 성립한다.
\[\vec{v_i}^T\vec{v_i}=\begin{cases}1 & i=j \\ 0 & i\neq j\end{cases}\]즉, 모든 $\vec{v_i}$는 전부 서로에게 수직인 Orthonormal 상태가 되고, 이러한 Eigenvector를 모아놓은 행렬 $V=\left[\vec{v_0},\vec{v_1},\ldots,\vec{v_{D-1}}\right]$는 $V^TV=I$를 만족하게 된다.
또한 $V^TV=I$에서 다음의 과정을 통해 $VV^T=I$임을 알 수 있다.
\[VV^T=VIV^T=V(V^TV)V^T=(VV^T)^2, \therefore VV^T=I\]마지막으로, $V^TAV$라는 행렬을 생각해보자. 이 행렬의 각 원소는 다음과 같이 구할 수 있다.
\[\vec{v_i}^TA\vec{v_j}=\vec{v_i}^T(\lambda_j\vec{v_j})=\lambda_j\vec{v_i}^T\vec{v_j}=\begin{cases}\lambda_j & i=j \\ 0 & i \neq j\end{cases}\]즉, $\Lambda=V^TAV$라고 하면, 이 행렬 $\Lambda$는 다음과 같이 생겼다.
\[\Lambda=V^TAV=\begin{pmatrix}\lambda_0 & 0 & \cdots & 0 \\ 0 & \lambda_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_{D-1}\end{pmatrix}\]또한 $VV^T=V^TV=I$이므로, 다음이 성립한다.
\[A=VV^TAVV^T=V\Lambda V^T\]Principal Component Analysis
우선 앞에서 살펴본 Multivariate Gaussian Distribution의 Sample Covariance를 다시 보자.
\[\Sigma=\dfrac{1}{M-1}\sum_{m=0}^{M-1}(\vec{x_m}-\vec{\mu})(\vec{x_m}-\vec{\mu})^T\]여기서 $\vec{x_m}-\vec{\mu}$을 계속 쓰긴 불편하니, 다음과 같이 간단하게 표현하자.
\[\Sigma=\dfrac{1}{M-1}X^TX,X=\begin{pmatrix}(\vec{x_0}-\vec{\mu})^T \\ (\vec{x_1}-\vec{\mu})^T \\ \vdots \\ (\vec{x_{M-1}}-\vec{\mu})^T \end{pmatrix}\]이렇게 $X^TX$ 형태의 행렬을 Sum-of-Squares Matrix라고 부른다. 그리고 이 행렬은 Symmetric하다.
따라서 위에서 얻은 Symmetric Matrix의 성질을 적용할 수 있다.
\[X^TX=V\Lambda V^T\]여기서 $X^TX$의 Eigenvector의 행렬 $V=\left[\vec{v_0},\vec{v_1},\ldots,\vec{v_{D-1}}\right]$는 Principal Component Axes, 혹은 Principal Component Directions라고 부른다.
다시 본래 논의로 돌아가서, $X^TX=V\Lambda V^T$이므로 다음이 성립한다.
\[\Sigma=\dfrac{1}{M-1}X^TX=V\left(\dfrac{1}{M-1}\Lambda\right)V^T\]즉, $V=\left[\vec{v_0},\vec{v_1},\ldots,\vec{v_{D-1}}\right]$는 Sum-of-Squares Matrix와 Covariance Matrix 모두의 Eigenvector 행렬이다. 여기서 $\Lambda$는 Sum-of-Squares Matrix의 Eigenvalue 행렬이면서 $M-1$배를 하면 Covariance Matrix의 Eigenvalue 행렬이 된다.
그런데 $V\Lambda V^T=X^TX$이므로, 다음이 성립한다.
\[V^TX^TXV=\Lambda, \vec{v_i}^TX^TX\vec{v_j}=\begin{cases}\lambda_j & \lambda_i=\lambda_j \\ 0 & \lambda_i \neq \lambda_j \end{cases}\]여기서 원래 $X$의 각 행이 $(\vec{x_m}-\vec{\mu})^T$였음을 기억하자. 따라서
\[(\vec{x_m}-\vec{\mu})^TV=\vec{y_m}^T, Y=\begin{pmatrix}\vec{y_0}^T \\ \vec{y_1}^T \\ \vdots \\ \vec{y_{M-1}}^T\end{pmatrix}\]와 같이 정의하면, $Y^TY=\Lambda$가 된다. 즉, $\vec{y}$의 Covariance Matrix는 대각행렬이 된다.
이제 $Y=XV$라고 하자. 그러면 $Y^T=V^TX^T$가 된다. 따라서,
\[\begin{aligned} (\vec{x_m}-\vec{\mu})^TV&=\vec{y_m}^T \\ XV&=Y \\ V^TX^TXV&=Y^TY=\Lambda \end{aligned}\]즉, $\vec{y_m}=\begin{pmatrix}y_{m,0} & y_{m,1} & \cdots & y_{m,D-1}\end{pmatrix}^T$는 $\vec{x_m}$의 Principal Component가 된다. 이를 전체 행렬에 대해 적용하면, 이렇게 얻어진 각각의 $\vec{y_m}$들은 원래 데이터셋을 직교함을 알 수 있다.
이 과정을 Principal Component Analysis, 즉 PCA라고 한다. 구체적으로, 데이터 $\vec{x_m}$이 주어졌을 때, 이를 $\vec{y_m}=V^T(\vec{x_m}-\vec{\mu})$를 만족하는 $\vec{y_m}$을 찾는 것이다. 여기서 행렬 $V$를 $\vec{x_m}$을 $\vec{y_m}$으로 투영시킨다는 점에서 Projection Matrix라고도 부른다.
여담으로, Sum-of-squares Matrix인 $X^TX$ 대신에 $XX^T$도 생각해볼 수 있는데, 이것은 Gram Matrix라고 부른다. Gram Matrix도 역시 Symmetric하므로 위의 모든 논의를 다 진행할 수 있는데, Sum-of-squares Matrix와 동일한 Eigenvalue를 갖고 있으나 그에 해당하는 Eigenvector는 달라서 PCA의 결과 또한 다르게 나온다. 그로 인해 다음과 같이 Eigenvector의 행렬을 다르게 표현한다.
\[X^TX=V\Lambda V^T, XX^T=U\Lambda U^T\]Singular Value Decomposition
그렇다면 PCA를 실제로 어떻게 수행할 수 있을까? 이를 위한 방법 중 하나가 Singular Value Decomposition (SVD)이다.
우선 행렬 $X$에 대해, $X$의 Sum-of-squares Matrix $X^TX$ 혹은 Gram Matrix $XX^T$의 Eigenvalue의 Square root를 $X$의 Singular Value라고 한다. 따라서 Singular Value의 행렬을 $S$라고 하면 다음과 같이 표현할 수 있다.
\[S=\begin{pmatrix}s_0 & 0 & \cdots & 0 \\ 0 & s_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & s_{D-1} \end{pmatrix}, \Lambda=S^2\]$\Lambda=SS$를 Sum-of-squares Matrix에 대한 PCA에 대입해보면 다음과 같다.
\[\begin{aligned} X^TX&=V\Lambda V^T \\ &=VSSV^T \\ &=VSISV^T \\ &=VSU^TUSV^T \\ &=(USV^T)^T(USV^T) \end{aligned}\]같은 방식으로, Gram Matrix에 대한 PCA에 대입해보면 다음과 같다.
\[\begin{aligned} XX^T&=U\Lambda U^T \\ &=USSU^T \\ &=USISU^T \\ &=USV^TVSU^T \\ &=(USV^T)(USV^T)^T \end{aligned}\]즉, 위의 두 식으로부터 임의의 $M\times D$ 행렬 $X$는 항상 $X=USV^T$ 형태로 분해가 됨을 알 수 있다. 여기서 $U$는 $XX^T$의 Eigenvector의 행렬이고, $V$는 $X^TX$의 Eigenvector의 행렬이며, $S$는 Singular Value의 행렬이다.
따라서 SVD 알고리즘은 다음과 같이 수행된다. 우선 $M\times D$ 행렬 $X$에 대한 SVD를 수행하려고 하고, $M<D$라고 하자.
- $XX^T$를 계산한다. $XX^T=U\Lambda U^T$, $S=\sqrt{\Lambda}$이므로 여기서 $U$와 $S$를 구할 수 있다.
- $X^T=VSU^T$이므로 $VS=X^TU$이다. $X$, $U$, $S$를 이미 알고 있고 $S$는 대각행렬이므로 여기서 $V$를 쉽게 구할 수 있다.
만일 $M>D$라면 $U$와 $V$를 구하는 순서를 바꾸면 빠르게 계산할 수 있다. 그 후 $\lambda_k$의 값이 큰 순서대로 정렬하면 SVD를 통한 PCA가 완료된다.
Nearest-Neighbors Classifier
Nearest-Neighbors Classifier는 PCA를 실용적으로 활용할 수 있는 한 가지 예제이다. 아직 컴퓨터의 성능이 그리 좋지 않았을 때, 얼굴 인식을 위해 사용한 기법 중 Eigenface라는 것이 있다. 이는 각각의 얼굴 사진을 벡터의 집합으로 보고, 이 사진을 대상으로 PCA를 수행한 것이다.
위의 사진은 주어진 얼굴 사진에 대해 Eigenface를 수행한 것이다. 여기서 $r$이 남길 차원의 개수인데, 실제 얼굴 사진을 차원으로 변환하면 매우 고차원의 데이터라서 마지막 케이스와 같이 1600개의 주성분을 남겨도 원본과 일치하지는 않음을 알 수 있다. 하지만 1600개 정도면 원래 데이터에 비해 상당히 적은 수이고, 이거만 가지고도 적어도 표현하고자 하는 바는 어느 정도 복구가 되었음을 알 수 있다.
이렇게 원본 데이터에서 PCA를 통해 중요한 정보만 뽑아내어 압축을 한 이후엔, 다음과 같이 가장 가까운 벡터를 찾는 식으로 얼굴 사진을 분류했다.
\[\hat{y_test}=y_{m^{\ast}}, m^{\ast}=\arg\min\lVert\vec{x_m}-\vec{x_{test}}\rVert\]여기서 “가까운” 벡터라는 것은 다음과 같이 유클리드 거리를 의미한다.
\[\lVert\vec{x_m}-\vec{x_{test}}\rVert=\sqrt{\sum_{d=0}^{D-1}(x_{md}-x_{test,d})^2}\]PCA는 이런 식으로 데이터의 중요한 정보를 찾아내는 도구이며, 이를 통해 핵심적인 정보를 살리면서 차원만 낮추게 할 수 있다.