PCA (Principal Component Analysis)

Unsupervised learning algorithm

How to?

• Dimension reduction
  • Save memory / computation
  • Reduce overfitting
  • Visualize in 2 Dimension (must 2? well,,not necessary)
• Linear model with closed form

Dimension reduction

Projection onto a subspace

\(Set-up : D=\{X^{(1)},\cdots,X^{(N)} \}\)

\(\mu=\frac{1}{N}\sum_{i=1}^N X^i\)

 

Goal : find a K-dimensional subspace \(S \in R^D s\cdot t X^i-\mu\) is well represented by \(S\)

간단히 요약하자면 데이터 분포를 원점 중심으로 모은뒤 각 class 분포를 가장 잘 표현하는 부분공간 S를 찾는 방법이 PCA이다. 잘 표현한다는 의미는 각 class가 결정경계를 기준으로 잘 구분되어 식별하기 용이하고 차원축소하기전 데이터들의 분포를 잘 반영해야 한다.

 

Let \(\{u_k\}_{k=1}^K\) be an orthonormal basis of the subspace \(S\)

Then \(\hat{X} = \mu + proj_S (X-\mu)\) which \(\hat{X}\) is on \(S\) for every each data point \(X\)

\(\hat{X} = \mu + \sum_{k=1}^K z_k u_k\), also \(z_k = u_k^T(x-\mu)\)

 

각 \(X\)점은 \(S\)위에서 \(\hat{X}\)으로 reconstruction되었고, subspace \(S\)의 기저들로 span 된다. 각 기저들의 coefficent들은 \(z\)이며 representation or code라고 불린다.

 

이제 최적의 K와 K-dim에서의 basis들을 찾으면 끝이다. 최적의 K는 어떻게 정의되어야 할까?

위에서 언급했듯이 차원 축소 이전의 데이터 분포를 잘 표현해야하므로 K-dim에서의 \(\hat{X}\)와 N-dim에서의 \(X\)의 거리 차이의 합이 최소인 K와 basis가 최적이리고 할 수 있다.

 

Two criteria

minimize reconstruction error

\(min\frac{1}{N}\sum_{i=1}^N||X^{(i)}-\hat{X}^{(i)}||^2\)

 

maximize the variance of the code vector

\(max\sum_j Var(z_j)=\frac{1}{N}\sum_j \sum_i (z_j^{(i)}-\bar{z})^2\)

 

첫번째식은 정의에 의해 쉽게 이해가지만 두번째 식은 와닿지 않을 수 있다. 분산이 작아지면 분포가 밀집되므로 기존의 데이터 분포를 잘 표현하지 못한다. 그래서 분산을 최대한 크게하려는 것이다. 사실 두 식은 동치 관계인데 수식전개를 통해 이해해보자.

 

projection relarionship

\(min\frac{1}{N}\sum_{i=1}^N||X^{(i)}-\hat{X}^{(i)}||^2 = \frac{1}{N}\sum_{i=1}^N (||X^{(i)}-\mu||^2-||\hat{X}^{(i)}-\mu||^2)\)

\(=\frac{1}{N}\sum_{i=1}^N(const - ||\hat{X}^{(i)}-\mu||^2\)

\(=\frac{1}{N}\sum_{i=1}^N(const -||Uz||^2\)

\(=\frac{1}{N}\sum_{i=1}^N(const -||z-\bar{z}||^2, \bar{z}=mean(z)=\frac{1}{N}\sum_{i=1}^N U(X-\mu)=0\)

\(=\frac{1}{N}\sum_{i=1}^N(const -var(z))\)

\(max\frac{1}{N}\sum_{i=1}^N var(z)\)

 

\(X\)의 평균은 \(\mu\)이므로 항이 상쇄되어 \(z\)의 평균은 0이 된다. 수식의 의미상 상수값에서 \(z\)의 분산 차이를 최소화 하는것이므로 분산을 최대화하는 문제로도 해석할 수 있게 되는 것이다. 각 데이터의 변수들은 multi variables이므로 공분산을 기준으로 생각해야한다.

 

정의가 더 정밀해졌다, 원래 분포에서 재구성한 데이터의 거리의 합이나 혹은 재구성된 분포들의 분산이 최대가 되도록 하는 부분공간 \(S\)를 찾는것이 PCA이다.

 

Spectral decompostion

symmetric matrix를 고윳값 분해 하는것을 말한다. symmetric matrix는 대각화가 가능한데, 대각화를 진행했을때 각 행렬이 eigenvector X eigenvalue X eigenvector 형태로 분해가 된다. 추가로 vector들은 서로 ortohgonal하다는 특징이 있다.

\(A=Q\Lambda Q^T, Q : eigenvector, \Lambda : eigenvalue\)

\(\lambda_j (\in \Lambda) \geq 0\) iff \(A\) is positive semi-definite

 

Basis는 한가지만 존재하지 않고 여러개 존재할 수 있다. 따라서 standard basis가 아닌 eigenvector들을 또다른 basis로 생각할 수 있다.

basis condition

• Span target space
• Independent

N-dim의 모든 점 \(X\)는 eigenvector들의 선형결합으로 표현될 수 있으므로 spanning을 만족하며, 각각이 orthogonal이므로 independent도 만족한다. 따라서 eigenvector 집합은 basis가 된다.

 

더 알아야 할 특징으로 eigenvector에 match되는 \(lambda\)를 생각해보면 해당 eigenvector들이 \(\lambda\)만큼 scale해준다는 의미를 가진다. 다시말해 \(\lambda\)가 클수록 데이터 분포에 영향을 많이 준다는 뜻이다.

 

우리가 찾고자 하는 Optimal K-space는 top-k \(\lambda\)의 eigenvector들로 구성된다고 볼 수 있다. 그러한 주요 eigenvector들은 principal component라고 불린다. 이제 PCA의 어원의 의미가 이해갈 것이라 생각한다.

 

이론적인 이해를 원한다면 Courant-Fischer Theorem을 찾아보면 좋다.

 

 

 

 

\(max\frac{1}{N}\sum_{i=1}^N var(z)\)

\(=\frac{1}{N}\sum_i [z^{(i)}]^2\)

\(=\frac{1}{N}\sum_i (u^T(X^{(i)}-\mu))^2\)

\(=\frac{1}{N}\sum_i u^T(X^{(i)}-\mu)(X^{(i)}-\mu)^T u\)

\(=u^T [\frac{1}{N}\sum_i (X^{(i)}-\mu)(X^{(i)}-\mu)^T]u\)

\(=u^T\sum u\)

\(=u^T Q\Lambda Q^T u\)

\(=a^T \Lambda a, a = Q^T u\)

\(\sum_{j=1}^D \lambda_j a_j^2\)

 

\(\lambda_i\)가 sorting되어 있고 모두 distinct하다고 가정하자. 그러면 우리는 top-K개를 뽑아 subspace를 구현하면 된다.

Decorrelation

 만약 공분산 행렬이 대각행렬이라면 모든 변수들은 각각 독립적이며 상관관계가 없다는 걸 의미한다. PCA는 어떻게 보면 데이터를 비상관하게 변환시키기도 한다. top-k를 고르게 되면 나머지는 0이 되어 상관관계를 고려하지 않게 되기 때문이다.

그러면 데이터 feature에 손실이 있으니 안좋은게 아닐까?

현실적인 부분으로 차원의 저주와 생각해보아야 한다. 차원이 높아질수록 데이터의 양만 충분히 주입할 수 있다면 데이터의 feature는 풍부한 표현을 하는것이 맞다. 하지만 real에서 고차원에서 다룰수 있을만큼 데이터를 확보하기란 불가능에 가깝다. 그 대안으로 데이터의 특징을 최대한 잘 보존하면서 차원을 축소시키는 방법론이 탄생하게 된 것이다.

top-K 개수 선택에 따라 구현되는 performance가 달라짐을 알 수 있다.