PCA는 왜 분산이 큰 방향을 주축으로 잡을까?

들어가기 앞서…

이 내용을 이해하기 위해서는 기초 선형 대수(linear algebra)의 지식과 선형 대수의 고유 벡터(eigenvector), 고유 값(eigenvalue), 그리고 대각화(Diagonalization)에 대한 지식이 있어야합니다.

Principal Component Analysis가 뭔데?

데이터를 분석하기 위해 전처리 할 때, 웬만한 변수들이 모두 의미가 있어 종속 변수 $y$에 유의한 영향을 주면 좋겠지만 사실 그런 경우는 흔하지 않습니다. 많은 경우, raw data에는 라벨링이 붙어있어 각각에 대해 one-hot encoding을 해줘야하고, 그렇게 되는 경우 대부분 값이 0이 되는 sparse matrix가 되기 때문입니다.

피쳐가 많으면 많을수록, 데이터를 저장하는 용량이 커지고, 계산 속도가 느리게 되며, overfitting의 우려가 생기기 마련입니다. 따라서 여러가지 차원 축소 기법을 통해 변수를 줄이는 노력을 하게 되는데, 이 때 보통 사용하는 방법이 Principal Component Analysis; PCA 입니다. 머신 러닝을 공부하신 분이라면 unsupervised machine-learning으로도 알려져있는 대표적인 방법 중 하나이기도 합니다.

많은 블로그들은 PCA의 의미를 다음과 같이 서술합니다.

PCA는 가장 데이터의 분산이 큰 방향으로 주축을 잡아서 좌표 변환을 한다.

의미가 꽤 그럴듯 합니다. 그러나, PCA를 계산하는 경우에는 뜬금없이 다음과 같은 식이 나타납니다.

\[Cov(X, X)=\{Cov(X_i, X_j)\}_{ij}=PDP^T\]

이 식과 PCA의 의미는 어떤 관계가 있을까요? 아쉽게도, 많은 블로그들은 이것에 대해 상세하게 다루지 않습니다. 이번 포스팅에서는 왜 변수의 공분산 행렬을 대각화하고, 이를 통해 나온 고유 벡터가 주축에 대한 벡터가 되는지, 그리고 그 주축은 왜 분산이 큰 방향인지, 이런 것들에 대해 설명합니다.

Preliminary - Linear Algebra

• 앞으로, $u$ 벡터와 $v$ 벡터의 내적 $u\cdot v=u^Tv$을 $\langle u, v\rangle$로 표시합니다.

일반적으로, $A$ 행렬이 symmetric하면 ($A=A^T$) orthogonal eigenvalue decomposition이 가능하다는 것이 알려져있습니다.

\[A=PDP^T\text{ for }P^{-1}=P^T, D: \text{diagonal w/ eigenvalue of }A\]

• 중요하지 않은 증명 $A=A^T$이기 때문에 $\langle Au, v\rangle=\langle u, A^Tv\rangle = \langle u, Av \rangle$입니다. 이 때, $e_i$를 $A$의 eigenvector로 두게 되면, $\langle \lambda_ie_i, e_j \rangle = \langle Ae_i, e_j \rangle = \langle e_i, Ae_j \rangle = \langle e_i, \lambda_je_j \rangle$이고, $\lambda_i\not=\lambda_j$이므로 $\langle e_i, e_j \rangle=0$이 됩니다. 즉, $A$의 eigenvector는 orthogonal하며, 따라서 이는 $\text{col}(A)$의 basis가 됩니다. 이 때 $P=[e_1 | e_2|\cdots|e_n]$인 augment matrix라고 둡시다. 즉, $P$는 $A$의 basis change matrix가 되며, $P^{-1}=P^T$인 orthogonal matrix가 됩니다. 그렇다면 $A=PBP^T$로 구성할 수 있습니다. 이 때 $Ae_i=\lambda_ie_i$이기 때문에, $PBP^Te_i=PB1_i=Pb_i=\lambda_ie_i$가 되므로, $b_i=\lambda_i1_i$가 될 수 밖에 없다는 것을 보였습니다. 따라서 $B=D$가 되며, $D$의 entry는 $P$에 대응되는 eigenvalue로 구성됩니다.

그리고, 우연히도, $Cov(X, Y)=\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y]=Cov(Y, X)$이므로

\[Cov(X, X)=\{Cov(X_i, X_j)\}_{ij}=Cov(X, X)^T\]

따라서 $Cov(X, X)$는 symmetric matrix입니다. 편의상 $\Sigma = Cov(X, X)$로 기술하겠습니다. 그런데, $\Sigma$에 벡터 곱을 하는 것, $\Sigma u$는 과연 어떤 의미일까요? 이를 알기 위해서는 선형 대수적인 직관이 필요합니다.

\[\text{For all matrix }A\in\mathbb{R}^{n\times n},\] \[\text{ there is an unique linear map }T: V\longrightarrow W\\\text{ so that }\] \[\text{dim}(V)= \text{dim}(W)=n\]

이 말인 즉슨, 모든 행렬을 선형 함수로서 생각할 수 있다는 이야기입니다. 우리의 원래 문제를 풀기 위해서 이런 선형 대수적인 직관을 가지고 와서 의미를 해석해보도록 하겠습니다.

우선, $\Sigma$에 곱하는 벡터 $u$가 어떤 의미를 가지고 있는지를 생각해보겠습니다. $u=(u_1, u_2, \cdots, u_n)$이라는 것은 기본적으로 $\mathbb{R}^n$에 있지만, 사실은 $\text{Span}{X_i}$이라는 vector space 위의 벡터라는 것을 생각할 수 있습니다. 즉, $u=u_1X_1+u_2X_2+\cdots+u_nX_n$로 생각할 수 있습니다. 그렇다면, $\Sigma$를 linear map으로 생각한다면 ${X_i}$의 선형 결합으로 구성된 새로운 random variable을 어딘가 같은 차원의 다른 벡터로 보낸다는 것이군요! 이제 $\Sigma u$를 해보면, 다음과 같이 계산되는걸 알 수 있습니다.

\[\begin{align*} \Sigma u &= \begin{bmatrix} u_1Cov(X_1, X_1) + \cdots +u_nCov(X_1, X_n) \\ \vdots\\ u_1Cov(X_n, X_1) + \cdots +u_nCov(X_n, X_n) \\ \end{bmatrix}\\ &= \begin{bmatrix} Cov(X_1, u_1X_1+\cdots+u_nX_n) \\ \vdots\\ Cov(X_n, u_1X_1+\cdots+u_nX_n) \\ \end{bmatrix}\\ &= \begin{bmatrix} Cov(X_1, u) \\ \vdots\\ Cov(X_n,u) \\ \end{bmatrix} \end{align*}\]

$\Sigma$는 결국, $u$벡터가 각각 $X_i$와 얼마나 분산이 있는지에 대한 분산벡터로 가는 선형 함수였군요! 그렇다면, 가장 분산이 큰 방향은 바로 $|\Sigma u|$가 가장 큰 방향인것을 알 수 있습니다.

왜 PCA가 작동할까? - 증명

결론적으로 우리가 증명해야하는 것은 같은 크기를 가지는 $u$벡터에 대해 $\operatorname{argmax}|\Sigma u|$가 eigenvector임을 보이는 것입니다.

그런데 저희는 $\Sigma$가 symmetric matrix인것을 알고 있기 때문에, 어떤 좋은 orthonormal basis(orthogonal basis의 크기를 각각 1로 정규화) ${e_i}$가 존재한다는 것을 알 수 있습니다. 그러면 $u=u_1e_1+\cdots+u_ne_n$로 둘 수 있습니다. 그러면 다음을 생각해봅시다.

\[\|\Sigma u\|=\|\Sigma(u_1e_1+\cdots+u_ne_n)\|=\|u_1\lambda_1e_1+\cdots+u_n\lambda_ne_n\|\]

여기서 $u_i\lambda_i$는 모두 상수이고, $e_i$끼리는 모두 수직이므로 일반화된 피타고라스 정리를 사용해 다음과 같이 정리할 수 있습니다.

\[\|u_1\lambda_1e_1+\cdots+u_n\lambda_ne_n\|=\sqrt{\sum (u_i\lambda_i)^2}\]

이 때 $|u|=\sqrt{\sum u_i^2}=c$로 고정되어있기 때문에, greedy approach를 사용하면 가장 큰 크기를 가지는 $\lambda_i$에 대응하는 좌표 $u_i=c$로 두고, 나머지를 모두 0으로 두면 $\operatorname{argmax}|\Sigma u|$가 됩니다. 그러나 이는 $u=c_ie_i$가 되기 때문에 $\Sigma$의 eigenvector가 되는군요. 이렇게 얻은 eigenvector를 제외하고 계속 이렇게 iteration을 하면, 결국 주축이 모두 수직이면서 분산이 가장 큰 방향으로 향하는 새로운 좌표계가 만들어집니다.

따라서, 공분산행렬을 eigenvalue decomposition하는 것을 통해 분산이 큰 방향으로 주축을 잡을 수 있다는 명제는 사실이 됩니다.

결론

사실 이렇게 긴 스토리를 아는 것보다, 언제 PCA를 사용하느냐가 더 중요할 수 있습니다. 매번 할 때마다 이렇게 장황한 증명을 하는 것은 의미가 없기도 하고, 어쨌든 명제는 참인것이 밝혀졌으니까요. 그러나 얕게 배워서 사용하는 것이 효율적일 수 있으나, 그것은 꽤나 근시안적인 발상이라고 볼 수 있습니다.

그냥 쓰면 된다

쓰니까 되더라

이런 말을 하는 것이 초반 연구, 또는 예측 등에는 잘 먹힐 수 있습니다. 그러나 시간이 지날수록 “그래서 이게 왜 먹혀”라는 질문을 받는 경우가 종종 생길 것이고, 언제까지나 저런 결과 중심의 이유를 말할 수 없습니다. 그러기 위해서는 PCA를 비롯한 다른 method들이 왜 유용하고, 어떤 점에서 유용하며, 어느 경우에서 사용하면 안되는지를 생각하고 적용하는 것이 더더욱 중요해질 것입니다.

\[\]