8.79 PCA의 수학적 유도와 최적성
1. PCA의 두 가지 관점
PCA는 두 가지 동치인 관점에서 유도될 수 있다.
- 분산 최대화: 투영된 데이터의 분산을 최대화하는 방향을 선택
- 재구성 오차 최소화: 원본 데이터를 저차원 부분 공간으로 투영한 후 재구성했을 때의 오차를 최소화
두 관점이 동일한 결과를 산출하는 것이 PCA의 수학적 우아함이다.
2. 분산 최대화 유도
2.1 제1 주성분
중심화된 데이터 \{\mathbf{x}_1, \ldots, \mathbf{x}_n\}의 방향 \mathbf{w} (\lVert\mathbf{w}\rVert = 1)로의 투영의 분산을 최대화한다.
\max_\mathbf{w} \frac{1}{n}\sum_{i=1}^{n}(\mathbf{w}^T\mathbf{x}_i)^2 = \mathbf{w}^T\boldsymbol{\Sigma}\mathbf{w}
\text{s.t.} \quad \mathbf{w}^T\mathbf{w} = 1
라그랑주 함수:
\mathcal{L}(\mathbf{w}, \lambda) = \mathbf{w}^T\boldsymbol{\Sigma}\mathbf{w} - \lambda(\mathbf{w}^T\mathbf{w} - 1)
\mathbf{w}에 대한 미분을 영으로 놓으면:
\boldsymbol{\Sigma}\mathbf{w} = \lambda\mathbf{w}
이는 \boldsymbol{\Sigma}의 고유값 문제이다. 분산 \mathbf{w}^T\boldsymbol{\Sigma}\mathbf{w} = \lambda이 최대가 되려면 \lambda가 최대 고유값 \lambda_1이고 \mathbf{w}가 대응 고유벡터 \mathbf{w}_1이어야 한다.
2.2 후속 주성분
제2 주성분은 \mathbf{w}_1과 직교하는 방향 중 분산을 최대화하는 방향이다.
\max_\mathbf{w}\mathbf{w}^T\boldsymbol{\Sigma}\mathbf{w}, \quad \text{s.t.} \quad \mathbf{w}^T\mathbf{w} = 1, \quad \mathbf{w}^T\mathbf{w}_1 = 0
해는 두 번째로 큰 고유값에 대응하는 고유벡터이다. 일반적으로 k번째 주성분은 k번째로 큰 고유값의 고유벡터이다.
3. 재구성 오차 최소화 유도
3.1 저차원 표현
d차원 데이터를 k차원으로 투영하고 재구성할 때의 오차를 최소화하는 부분 공간을 찾는다.
\hat{\mathbf{x}}_i = \mathbf{W}_k\mathbf{W}_k^T\mathbf{x}_i
여기서 \mathbf{W}_k \in \mathbb{R}^{d \times k} (\mathbf{W}_k^T\mathbf{W}_k = \mathbf{I})는 정규 직교 기저이다.
3.2 재구성 오차
J(\mathbf{W}_k) = \frac{1}{n}\sum_{i=1}^{n}\lVert\mathbf{x}_i - \mathbf{W}_k\mathbf{W}_k^T\mathbf{x}_i\rVert^2
이를 전개하면:
J = \text{tr}(\boldsymbol{\Sigma}) - \text{tr}(\mathbf{W}_k^T\boldsymbol{\Sigma}\mathbf{W}_k)
J를 최소화하는 것은 \text{tr}(\mathbf{W}_k^T\boldsymbol{\Sigma}\mathbf{W}_k)를 최대화하는 것과 동치이며, 이는 분산 최대화 관점과 일치한다.
최적 해는 \mathbf{W}_k = [\mathbf{w}_1, \ldots, \mathbf{w}_k]로, 상위 k개 고유벡터로 구성된다.
4. PCA의 최적성
4.1 에카르트-영(Eckart-Young) 정리
k차원 부분 공간에 대한 저차원 근사에서 PCA는 프로베니우스 노름 측면에서 최적이다.
\mathbf{X} \approx \mathbf{U}_k\mathbf{S}_k\mathbf{V}_k^T
여기서 \mathbf{U}_k, \mathbf{S}_k, \mathbf{V}_k는 SVD의 상위 k개 특이값/벡터이다. 이 근사는 계수 k의 모든 행렬 중에서 \lVert\mathbf{X} - \hat{\mathbf{X}}\rVert_F를 최소화한다.
\lVert\mathbf{X} - \mathbf{U}_k\mathbf{S}_k\mathbf{V}_k^T\rVert_F^2 = \sum_{i=k+1}^{r}s_i^2
즉, 재구성 오차는 버려진 특이값의 제곱합이다.
4.2 스펙트럼 노름
에카르트-영 정리는 스펙트럼 노름(spectral norm)에서도 성립한다.
\lVert\mathbf{X} - \mathbf{U}_k\mathbf{S}_k\mathbf{V}_k^T\rVert_2 = s_{k+1}
5. 확률적 PCA(PPCA)
Tipping과 Bishop(1999)이 제안한 PCA의 확률론적 해석이다. 관측 모델:
\mathbf{x} = \mathbf{W}\mathbf{z} + \boldsymbol{\mu} + \boldsymbol{\epsilon}
여기서 \mathbf{z} \sim \mathcal{N}(\mathbf{0}, \mathbf{I})는 잠재 변수, \boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \sigma^2\mathbf{I})는 잡음이다. \mathbf{W}와 \sigma^2의 최대 가능도 추정은 표준 PCA와 밀접히 관련된다.
확률적 PCA의 이점:
- 베이지안 확장 가능
- 결측 데이터 처리
- 모델 선택(잠재 차원 k)에 가능도 사용
6. 고유값의 해석
고유값 \lambda_i는 i번째 주성분 방향으로의 분산이다. 분산의 비율 \lambda_i/\sum_j\lambda_j가 해당 주성분이 설명하는 전체 분산의 비율이다.
스크리 플롯(Scree Plot): 고유값을 내림차순으로 그려 “팔꿈치(elbow)” 지점에서 주성분 수를 결정한다.
7. 계산 복잡도
7.1 직접 계산
공분산 행렬 \boldsymbol{\Sigma} \in \mathbb{R}^{d \times d}의 고유값 분해는 O(d^3)이다. n \gg d이면 효율적이다.
7.2 SVD 기반
데이터 행렬 \mathbf{X} \in \mathbb{R}^{n \times d}의 SVD는 O(\min(nd^2, n^2d))이다. d \gg n이면 이중 트릭으로 O(n^3)에 축소 가능하다.
7.3 무작위화 PCA
대규모 데이터에서 상위 k개 주성분만 필요할 때, 무작위화 방법(randomized PCA)이 O(ndk)의 복잡도로 근사한다.
8. 참고 문헌
- Jolliffe, I. T. (2002). Principal Component Analysis (2nd ed.). Springer.
- Eckart, C., & Young, G. (1936). “The Approximation of One Matrix by Another of Lower Rank.” Psychometrika, 1(3), 211–218.
- Tipping, M. E., & Bishop, C. M. (1999). “Probabilistic Principal Component Analysis.” Journal of the Royal Statistical Society: Series B, 61(3), 611–622.
- Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
version: 1.0