Principal Component Analysis

PCA

$N$ 개의 i.i.d. 를 만족하는 데이터 포인트들 $\mathbf{X}={\left[{\mathbf{x}}_1,\dots ,{\mathbf{x}}_N\right]}^T$ 이 존재하고, 각 $\mathbf{x}$ 는 $D$ 차원 벡터라고 하자. 이때 PCA 는 projection matrix $\mathbf{P}={\left[{\mathbf{p}}_1,\dots ,{\mathbf{p}}_{D^{\prime }}\right]}^T$ 를 찾는 방법이다 ($D^{\prime }\le D$).

PCA 를 사용한다는 것은 기존의 $n$ 차원 데이터 ${\mathbf{x}}_n$ 와 유사한 projections ${\tilde{\mathbf{x}}}_n$ 를 찾는 것과 동일한 말이다. 좀 더 구체적으로 얘기해보면, 다음과 같은 식으로 $D$ 차원 데이터 ${\mathbf{x}}_n$ 의 저차원 ($M$) 변환을 수행할 수 있다.

$${\mathbf{z}}_n={\mathbf{B}}^{\top }{\mathbf{x}}_n\in {\mathbb{R}}^M$$

여기서 $\mathbf{B}$ 는 projection matrix 로, 다음과 같이 표현된다.

$$\mathbf{B}:=\left[{\mathbf{b}}_1,\dots ,{\mathbf{b}}_M\right]\in {\mathbb{R}}^{D\times M}$$

여기서 $M<D$ 를 만족한다.

$\mathbf{B}$ 을 이루는 열벡터들은 orthonormal 하다고 가정한다. 왜냐하면, projection 자체가 scaling 없이 rotation 만 하기 때문에 unit vector 여야 하기 때문이다.

A.1) Figure

B) PCA Derivation

projection matrix $\mathbf{P}={\left[{\mathbf{p}}_1,\dots ,{\mathbf{p}}_{D^{\prime }}\right]}^T$ 에서 $\mathbf{p}$ 는 $\mathbf{X}$ 의 variance 를 최대화 하는 방향으로 각 데이터를 저차원으로 mapping 시키는데, 여기서는 예시로 ${\mathbf{p}}_1$ 을 어떻게 유도하는지 살펴보자.

covariance matrix $\mathbf{C}$ 는 다음과 같이 계산된다.

$$\mathbf{C}=\frac{1}{N}\sum _{n=1}^N\left({\mathbf{x}}_n-\mu \right){\left({\mathbf{x}}_n-\mu \right)}^T$$

• $\mu =\frac{1}{N}{\sum }_{n=1}^N{\mathbf{x}}_n$ 는 mean

데이터 point 를 ${\mathbf{p}}_1$ 에 project 하고난 결과의 variance 를 계산하면, 다음과 같다

$$v^{\prime }=\frac{1}{N}\sum _{n=1}^N{\left({\mathbf{p}}_1^T{\mathbf{x}}_n-{\mathbf{p}}_1^T\mu \right)}^2={\mathbf{p}}_1^T\mathbf{C}{\mathbf{p}}_1$$

• $v^{\prime }$ 는 scalar 이다.

PCA 는 $v^{\prime }$ 값을 최대화할수 있는 unit vector ${\mathbf{p}}_1$ 를 찾는 것이 목적이므로, Lagrange multiplier method 를 활용하여 아래와 같이 식을 세울 수 있다.

$${\mathbf{p}}_1\leftarrow \max F={\mathbf{p}}_1^T\mathbf{C}{\mathbf{p}}_1+{\lambda }_1\left(1-{\mathbf{p}}_1^T{\mathbf{p}}_1\right)$$

data compression 을 통해 가장 많은 정보를 남긴다는 의미는 저차원 데이터에서 가장 큰 variance 값을 찾아내는 것과 동일하다.

위 식에서 $F$ 를 ${\mathbf{p}}_1$ 에 대해서 미분하여 0 으로 설정하면 다음과 같은 조건을 찾을 수 있다.

$$\frac{dF}{d{\mathbf{p}}_1}=0\Rightarrow \mathbf{C}{\mathbf{p}}_1={\lambda }_1{\mathbf{p}}_1$$

위 식은 $\mathbf{C}$ 의 eigen-decomposition 식을 푸는것과 동일하다 (${\mathbf{p}}_1$ 가 eigenvector 그리고 ${\lambda }_1$ 은 eigenvalue). 즉, $\det \left(\mathbf{C}-{\lambda }_1\mathbf{I}\right)=0$ 를 푸는 것과 동일하다.

나머지 projection column vector ${\mathbf{p}}_2,\dots ,{\mathbf{p}}_{D^{\prime }}$ 에 대해서도 풀면, $\mathbf{C}$ 은 eigen-decomposition 에 의해 다음과 같이 표현할 수 있다.

$$\mathbf{C}=\mathbf{P}\Lambda {\mathbf{P}}^T$$

$\Lambda$ 는 diagonal matrix with elements $\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_D\right\}$ and ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_D$

C) Relation with Singular Value Decomposition

SVD 와 PCA 는 동일한 방법이지만 좀 더 유연한 방법이다.

왜 동일한지 설명하기 위해, 모든 데이터가 zero mean 으로 전처리 되었다 (${\mathbf{x}}_n-\mu$) 는 가정 하에 얘기하자면 다음과 같다.

covariance matrix $\mathbf{C}=\frac{1}{n-1}{\mathbf{XX}}^{\top }$ 은 symmetric matrix 이고 diagonalizable 하므로, 다음과 같이 eigenvector 들은 normalized 될 수 있다.

$$\frac{1}{n-1}{\mathbf{XX}}^{\top }=\frac{1}{n-1}{\mathbf{WDW}}^{\top }$$

데이터 $\mathbf{X}$ 에 대해 SVD 를 적용한다면, 다음과 같다.

$$\frac{1}{n-1}{\mathbf{XX}}^{\top }=\frac{1}{n-1}\left(\mathbf{U\Sigma }{\mathbf{V}}^{\top }\right){\left(\mathbf{U\Sigma }{\mathbf{V}}^{\top }\right)}^{\top }=\frac{1}{n-1}\mathbf{U}{\mathbf{\Sigma }}^2{\mathbf{U}}^{\top }$$

즉, $\frac{1}{n-1}{\mathbf{WDW}}^{\top }=\frac{1}{n-1}\mathbf{U}{\mathbf{\Sigma }}^2{\mathbf{U}}^{\top }$ 이므로, $\mathbf{X}{\mathbf{X}}^{\top }$ 의 eigenvalue 들의 square root 를 씌운것이 $\mathbf{X}$ 의 singular value 와 동일함을 알 수 있다.

D) Further Reading

• Chapter 4.1.4–4.1.6 in Chris Bishop’s book on PRML covers LDA

E) Reference

• A Tutorial on Principal Component Analysis
• http://www.cs.cmu.edu/~tom/10601_fall2012/slides/pca.pdf
• StackExchange: intuitive relationship between SVD and PCA

F) Related

Probabilistic PCA