Principal Component Analysis
강화학습 글들을 마쳤으니 이제 PCA로 넘어가려 한다. 이 주제에 대해 공부하려고 했었던 이유는, 회사에서 PLS 모델을 자주 쓰는데 이 모델에 대해 내가 잘 알고 있지 못하기 때문이다. PLS와 많이 연관이 있는 것이 PCA라고 들었고 PCA에 대해 모르는 것은 아니지만 그래도 정확하게 알고 넘어가고 싶다는 생각이 들었다.
워낙 데이터과학에서 자주 쓰이는 알고리즘이고 선형대수에서 바로 이어질 수 있는 기법이기 때문에 설명된 자료들이 많다.
- A Tutorial on Principal Component Analysis
- Pattern Recognition and Machine Learning (12.1절)
- Principal Component Analysis(2ed, Jolliffe)
- Principal component analysis with linear algebra
1. motivation
2차원 평면 위의 $n$개의 점들 $X^{(1)}$, $\cdots$ $X^{(n)}$을 생각하자.
이 $n$개의 점들을 가장 잘 설명할 수 있는 직선 $l$을 그어보자. ‘잘 설명할 수 있다’는 것의 의미는
(a) 각 점에서 직선 $l$까지의 거리의 제곱의 평균이 최소가 되는 경우
를 의미한다. (a)는 다음 그림에서 빨간 선들의 길이의 제곱의 평균이 최소가 되는 경우를 뜻한다.
일반성을 잃지 않고 $n$개의 점들의 무게중심이 원점이라고 하자. 원점을 지나는 직선은 방향벡터로 결정되므로, (a)는 빨간 선들의 길이의 제곱의 평균이 최소가 되는 방향벡터 $v$를 구하는 문제가 된다.
조건 (b)를
(b) 직선 $l$ 방향의 분산이 최대가 되는 경우
라고 하자. 다시 말해, 각 점들의 직선 $l$로의 수선의 발들의 원점까지의 거리의 제곱의 평균이 최대가 되는 경우를 뜻한다. 그러면 (a)와 (b)는 동치이다.
그 이유를 설명하기 위해 다음 그림과 같이 한 점 $X^{(i)}$를 생각하면
피타고라스정리로부터 빨간 선분의 길이의 제곱과 파란 선분의 길이의 제곱의 합은 $\overline{OX^{(i)}}^2$ 으로 일정하다는 사실을 사용할 수 있다.
즉, 점 $X^{(i)}$에서 $l$로의 수선의 발은 $H^{(i)}=\left(X^{(i)}\cdot v\right)v$라고 할 수 있는데 이때, $\lVert H^{(i)}\rVert=X^{(i)}\cdot v$이고 (a)에서 최소화해야 하는 값 $A$는
\[A=\frac1n\sum_{i=1}^n\lVert X^{(i)}-H^{(i)}\rVert^2\]이고 (b)에서 최대화해야 하는 값 $B$는
\[B=\frac1n\sum_{i=1}^n\lVert H^{(i)}\rVert^2\]이다. 그러면 피타고라스 정리로부터
\[\begin{align*} A+B &=\frac1n\sum_{i=1}^n \left(\lVert X^{(i)}-H^{(i)}\rVert^2+\lVert H^{(i)}\rVert^2\right)\\ &=\frac1n\sum_{i=1}^n \lVert X^{(i)}\rVert^2 \end{align*}\]이고 $A+B$의 값이 $v$에 관계없이 일정하다. 따라서 $A$를 최소화하는 것과 $B$를 최대화하는 것은 서로 같은 말이 된다. $v$를 바꿔가면서 $A$(MSE)와 $B$(variance)를 표시해보면, 정말로 MSE가 최소가 될 때 variance가 최대가 됨을 알 수 있다.
이와 같이 (a) 또는 (b) 조건을 만족시키는 방향 $v$를 주성분이라고 부른다.
이것은 $n$개의 2차원 데이터에서 주성분 1개를 찾는 과정에 해당한다. Pattern Recognition and Machine Learning의 12.1.1, 12.1.2에서는 $N$개의 $D$차원 데이터에서 주성분 $M$개를 찾는 과정에서 Variance를 최대화하는 것이 MSE를 최소화하는 것과 동등함을 설명하고 있다.
2. Preliminaries
2.1 dataset, variance, covariance
다음과 같은 데이터셋이 있다고 하자. 세 학생의 물리 성적과 생물 성적을 나열한 표이다.
| students | physics | biology |
|---|---|---|
| A | 92 | 80 |
| B | 60 | 30 |
| C | 100 | 70 |
각 열은 feature를, 각 행은 datapoint를 의미한다. 이 데이터셋이 나타내는 $3\times 2$ 행렬을 $X$라고 하자;
\[X= \begin{bmatrix} 92&80\\ 60&30\\ 100&70 \end{bmatrix}\]이 행렬의 $i$번째 행벡터를 $X^{(i)}$로, $j$번째 열벡터를 $X_j$로 표기하자. 또한, $j$번째 feature의 평균을 $\mu_j$라고 하자 ($\mu_1=84$, $\mu_2=60$). 그러면 $X_1$, $X_2$의 분산(variance)은 각각
\[\begin{align*} \text{var}(X_1)&=\frac13\left[(92-84)^2+(60-84)^2+(100-84)^2\right]=\frac{896}3\\ \text{var}(X_2)&=\frac13\left[(80-60)^2+(30-60)^2+(70-60)^2\right]=\frac{1400}3 \end{align*}\]으로 계산된다. (여기에서 표본평균과 표본분산이 아닌 모평균과 모분산을 사용하였다.) $X_1$, $X_2$ 사이의 공분산(covariance)은
\[\begin{align*} \text{cov}(X_1,X_2) &=\frac13\left[(92-84)(80-60)+(60-84)(30-60)+(100-84)(70-60)\right]\\ &=\frac{1040}3 \end{align*}\]이다.
일반적으로 $m$개의 feature와 $n$개의 datapoint가 있다고 하면 그 데이터셋은 $n\times m$ 행렬이다. 각 feature들의 평균이 0이라고 하자. 행벡터 $X^{(i)}$는
\[X^{(i)}= \begin{bmatrix} x_{i1}& \cdots& x_{im} \end{bmatrix}\]이고, 열벡터 $X_j$는
\[X_j= \begin{bmatrix} x_{1j}\\ \vdots\\ x_{nj} \end{bmatrix}\]이다. 그러면, $j$번째 feature에 대한 분산은
\[\begin{align*} \text{var}(X_j) &=\frac1n\left({x_{1j}}^2+\cdots+{x_{nj}}^2\right)\\ &=\frac1n\sum_{k=1}^n{x_{kj}}^2\\ &=\frac1n{X_j}^TX_j \tag1 \end{align*}\]이고 $i$번째와 $j$번째 feature 사이의 공분산은
\[\begin{align*} \text{cov}(X_i,X_j) &=\frac1n\left(x_{1i}x_{1j}+\cdots+x_{ni}x_{nj}\right)\\ &=\frac1n\sum_{k=1}^nx_{ki}x_{kj}\\ &=\frac1n{X_i}^TX_j \tag2 \end{align*}\]이다.
2.2 covariance matrix
이번에는 공분산 행렬을 정의해보려 한다. 이 행렬은 $m\times m$ 행렬로서, $i=j$인 경우에는 그 성분이 $X_i$의 분산이고 $i\ne j$인 경우에는 그 성분이 $X_i$와 $X_j$의 공분산인 행렬을 말한다. 그러면 공분산행렬 $C$는 (1)과 (2)로부터
\[C = \frac1n X^TX\tag3\]으로 정의된다. 혹은 다음과 같이 행벡터로서 정의될 수도 있다.
\[\begin{align*} C &=\frac1n\sum_{k=1}^n \begin{bmatrix}x_{k1}\\\vdots\\x_{km}\end{bmatrix} \begin{bmatrix}x_{k1}&\cdots&x_{km}\end{bmatrix}\\ &=\frac1n\sum_{k=1}^n {X^{(k)}}^TX^{(k)} \end{align*}\]당연히, 행렬 $C$는 대칭행렬(symmetric matrix)이다.
2.3 some matrix calculations
$m$차원 벡터 $v=\begin{bmatrix}v_1&\cdots&v_m\end{bmatrix}^T$에 대하여 $v$의 norm은
\[\lVert v\rVert =\sqrt{v^Tv}=\sqrt{v_1^2+\cdots+v_m^2}\]이다. $v^Tv$를 $v$에 대해 미분하면, 즉 gradient를 구하면
\[\frac{\partial}{\partial v}v^Tv =\begin{bmatrix} 2v_1\\\vdots\\2v_m \end{bmatrix} =2v \tag4\]이다. $m\times m$ 행렬 $A$에 대하여 $A$와 $v$의 이차형식(quadratic form)은 $v^TAv$으로 정의된다. 이것을 계산하면
\[\begin{align*} v^TAv &= \begin{bmatrix}v_1&\cdots&v_m\end{bmatrix} \begin{bmatrix} a_{11}&\cdots&a_{1m}\\ \vdots&\ddots&\vdots\\ a_{m1}&\cdots&a_{mm} \end{bmatrix} \begin{bmatrix}v_1\\\vdots\\v_m\end{bmatrix}\\ &= \begin{bmatrix} \sum_{i=1}^ma_{i1}v_i&\cdots\sum_{i=1}^ma_{im}v_i \end{bmatrix} \begin{bmatrix}v_1\\\vdots\\v_m\end{bmatrix}\\ &=\sum_{i=1}^m\sum_{j=1}^ma_{ij}v_iv_j \end{align*}\]이것을 $v$의 한 성분 $v_k$에 대하여 편미분하면
\[\begin{align*} \frac\partial{\partial v_k}a_{kk}v_kv_k&=2a_{kk}v_k\\ \frac\partial{\partial v_k}a_{ik}v_iv_k&=a_{ik}v_i (i\ne k)\\ \frac\partial{\partial v_k}a_{kj}v_kv_j&=a_{kj}v_j (j\ne k) \end{align*}\]로부터
\[\frac\partial{\partial v_k}v^TAv=\sum_{i=1}^ma_{ik}v_i+\sum_{j=1}^ma_{kj}v_j\]이다. 만약 $A$가 대칭행렬이면
\[\frac\partial{\partial v_k}v^TAv=2\sum_{j=1}^ma_{kj}v_j\]이다. $v^TAv$를 $v$에 대해 미분하면, 즉 gradient를 구하면,
\[\begin{align*} \frac\partial{\partial v}v^TAv &=2\begin{bmatrix} \sum_{j=1}^ma_{1j}v_j\\ \vdots\\ \sum_{j=1}^ma_{mh}v_j \end{bmatrix}\\ &=2\begin{bmatrix} a_{11}&\cdots&a_{1m}\\ \vdots&\ddots&\vdots\\ a_{m1}&\cdots&a_{mm}\\ \end{bmatrix} \begin{bmatrix} v_1\\\vdots\\v_m \end{bmatrix}\\ &=2Av \tag5 \end{align*}\]2.4 real symmetric matrices
만약 $A$가 real symmetric이면 (실수로 이루어진 대칭행렬이면) 다음이 성립한다.
- (a) $A$의 모든 eigenvalue는 실수이다
- (b) $A=BDB^{-1}$를 만족시키는 대각행렬 $D$와 직교행렬 $B$가 존재한다. (직교대각화 가능)
이에 관한 설명은 행렬의 직교대각화 포스팅에서 정리 19와 성질 20으로 갈음한다.
2.5 Lagrange multiplier method
두 함수 $f:\mathbb R^n\to\mathbb R$와 $g:\mathbb R^n\to\mathbb R^m$에 대하여 ($f,g\in C^1$) 최적화 문제
는 함수 $\mathcal L:\mathbb R^n\times\mathbb R^m\to\mathbb R$을
\[\mathcal L\left(\boldsymbol x,\boldsymbol\lambda\right)=f(\boldsymbol x)+\boldsymbol\lambda^Tg(\boldsymbol x)\]로 정의하여 ($\boldsymbol\lambda\in\mathbb R^m$)
를 풀어도 된다. 이에 관해서는 직전 포스트에 자세히 설명해놓았다.
댓글남기기