03_PCA

• 참고 자료

  • 선형대수학(2-1)
    • 07-3_SVD & PCA
  • LG AI연구원
    • 03_PCA

• PCA는 데이터 공분산 행렬의 상위 고유벡터(=가장 큰 고유값 방향)로 데이터를 사영해 분산을 최대로 보존하면서 차원을 줄이는 기법

• 이는 SVD를 통한 최적 저차원 근사와 동치

• 고차원·소표본 상황에서는 작은 $N\times N$ 행렬로 효율적으로 계산할 수 있다.

1. 문제 설정

• 차원 축소(dimensionality reduction)의 필요성

  • 고차원 데이터는 저장·연산·시각화·분석이 어렵고, 중복된 차원이 많기 때문에, 압축처럼 더 간결한 표현을 얻는 것이 목표이다.
  • PCA는 대표적인 차원 축소 기법이다.

• PCA 알고리즘 5단계

  1. 중심화(Centering): 평균을 빼서 데이터를 0 중심으로 만듦
  2. 표준화(Standardization): 각 차원을 표준편차로 나눔
  3. 고유값/고유벡터: 공분산 행렬의 가장 큰 M개 고유값과 고유벡터 계산
  4. 사영(Projection): 고유벡터가 정의하는 주부분공간 $z_n=B^T{x}_n$으로 사영
  5. 표준화·중심화 되돌리기

1.1. 핵심 표기

• 데이터 행렬 $X=[x_1,\dots ,x_N]\in {\mathbb{R}}^{D\times N}$ (N개 샘플, D차원)

• 이 데이터 행렬에 대한 공분산 행렬은 $S=\frac{1}{N}X{X}^T=\frac{1}{N}{\sum }_{n=1}^N{x}_n{x}_n^T\in {\mathbb{R}}^{D\times D}$이다.

• 저차원 코드는 $z_n=B^T{x}_n$, $B^T$는 인코더 역할

• 복원은 $\tilde{x}=Bz$, $B$는 디코더 역할

• 여기서 $B$의 열들은 정규직교(orthonormal) 라고 가정한다.

2. 최대 분산 관점

• 핵심 아이디어는

  • “데이터가 많이 퍼져 있을수록 정보량이 많다”는 것이며,
  • PCA는 저차원 표현에서 분산을 최대화하는 알고리즘이다.

• 목표

  • 분산을 최대화하는 정규직교 기저 $B=(b_1,\dots ,b_M)$ 찾기
  • 결론은 공분산 행렬 $S$의 가장 큰 M개 고유값에 대응하는 고유벡터들이 바로 $b_1,\dots ,b_M$이 된다는 것이다.

2.1. 증명

• 증명은 귀납법으로 진행된다.

• Step 1. (첫 번째 주성분)

  • 사영된 데이터의 분산은 $V_1=b_1^{T}S{b}_1,\text{s.t.}|b_1{|}^2=1$
  • 라그랑주 승수법을 쓰면 $S{b}_1={\lambda }_1{b}_1$
  • 즉 $b_1$은 고유벡터, ${\lambda }_1$은 고유값이고, 분산 $V_1={\lambda }_1$
  • 따라서 분산을 최대화하려면 가장 큰 고유값에 해당하는 고유벡터를 택하면 되고, 이것이 첫 번째 주성분이다.

• Step k. (k번째 주성분)

  • $b_1,\dots ,b_{k-1}$에 직교한다는 제약 하에 분산을 최대화
  • 라그랑지안에 직교 제약 항을 추가해 미분하면, 직교 조건으로부터 모든 ${\eta }_j=0$이 됨을 보일 수 있고, 결국 $S{b}_{k+1}=\lambda b_{k+1}$ 이 된다.
  • 스펙트럼 정리에 의해 이전 벡터들과 직교하도록 선택할 수 있으므로, k번째로 큰 고유값의 고유벡터가 k번째 주성분이 된다.

3. 고유벡터 계산과 저차원 근사

3.1. 고유벡터 계산

고유벡터를 구하는 두 가지 방법

1. EVD

   • 대칭 행렬 $S$를 직접 고유분해

2. SVD

   • 데이터 행렬을 $X=U\Sigma V^T$로 분해
   • 이때 $S=\frac{1}{N}U\Sigma {\Sigma }^T{U}^T$가 되어,
   • $U$의 열이 $S$의 고유벡터가 되고
   • 고유값은 특이값과 ${\lambda }_d=\frac{{\sigma }_d^2}{N}$의 관계를 가진다.

3.2. 저차원 근사

• SVD에서 $U$가 사영 행렬 $B$에 해당한다.
• Eckart-Young 정리에 따라 상위 M개 특이값에서 SVD를 잘라내면 최적의 rank-M 근사를 얻는다. ${\tilde{X}}_M=U_M{\Sigma }_M{V}_M^T={\sum }_{i=1}^M{\sigma }_i{u}_i{v}_i^T$
• 이는 분산 최대화와 재구성 오차 최소화가 동일한 목적임을 보여준다.

4. 고차원에서의 PCA

• 문제 상황은 $D$가 매우 클 때이다. (예: 100×100 이미지면 D=10,000)

• 특히 샘플 수가 차원보다 훨씬 작을 때($N\ll D$) 가 핵심이다.

• 이 경우 중복 없는 데이터면 $\text{rk}(S)=N$ 이고 $D-N+1$ 개의 고유값이 0이 된다.

• 즉 거대한 $D\times D$ 행렬을 다룰 필요가 없다.

• 트릭

  • $S{b}_m={\lambda }_m{b}_m$ 양변을 변형하면
  • $\frac{1}{N}{X}^{T}X,c_m={\lambda }_m{c}_m,c_m:=X^T{b}_m$ 이 되어,
  • 훨씬 작은 $N\times N$ 행렬 $\frac{1}{N}{X}^{T}X$의 고유 문제로 바뀐다.
  • 계산이 크게 쉬워지며, 원래 $S$의 고유벡터는 양변에 $X$를 곱해 복원할 수 있다.