Math Behind PCA

2019-05-17
Jun Sok Huhh | 🏠lostineconomics.com

tl; dr

• PCA를 차원을 축소하는 방법으로 막연하게 이해하지 말자. PCA 역시 다른 방법처럼 어떤 목적 함수를 최적화하는 방법의 하나다.
• PCA는 $k$ 개의 피처를 어떤 스크린 벡터 위에 쏴서 이를 단순화하겠다는 것이다. 이렇게 투영된 이미지와 원래 벡터와의 거리를 최소화하는 과정에서 분산 최대화라는 PCA의 새로운 목적 함수가 도출된다.
• PCA가 스크린으로 활용할 벡터가 하나가 아니라고 할 때, 이 여러 개의 스크린 벡터를 활용해 거리를 최소화하는 과정(즉 분산의 합을 극대화하는 과정)에서 eigenvalue와 eigenvector가 등장한다.

PCA

"차원의 저주"라는 표현이 있다. 언뜻 보면 자명한 이야기 같지만, 곰곰이 생각해보면 모호한 구석이 많다. 관찰 수는 많을수록 좋은데 차원은 관찰과 어떻게 다를까? 쉽게 생각해보자. 관찰 수란 활용할 수 있는 샘플의 수다. 이는 당연히 많을수록 좋다. (물론 미칠 듯이 많으면 새로운 문제가 발생하긴 하나, 대체로 우리는 샘플이 부족해서 문제를 겪는다) 하나의 샘플에서 관찰 가능한 변수가 7개라고 해보자. 샘플 수에 따라서는 적당해 보일 수 있다.

그런데, 샘플은 100 개인데, 한 샘플에서 관찰할 수 있는 포인트가 1,000 개라고 치자. 이 데이터 셋은 10만 개의 개별 포인트를 지닌 제법 큰 데이터 셋이지만 별 쓸모는 없다. 관찰 수에 비해서 개체의 차원이 지나치게 크기 때문이다. 이럴 경우 어떻게 차원을 줄이면 좋을까? 쉽게 생각할 수 있는 방법은 1,000 개의 특징들을 좀 줄여보는 것이다. 주성분분석(Principal Component Analysis)은 이를 위해 필요한 방법이다.

Objective function for PCA?

대체로 많은 PCA에 관한 설명들이 원래 하고 싶은 게 무엇인지에 관해 묻지 않는다. PCA란 데이터의 특성을 압축하는 방법이라는 이야기만 할 뿐. 수학적으로 말하면 목적함수에 관한 질문이고 우리는 먼저 이 질문에 집중하겠다.

대체로 통계학의 알고리듬은 목적 함수를 최적화하는 형태이다. PCA도 마찬가지다. 관찰 대상 $i$(for $i = 1, \dotsc, n$)에 관한 $k$ 차원의 피처 벡터 $x_i$가 있다고 하자. $x_i$는 $k \times 1$의 칼럼 벡터이다. 앞으로 특별한 언급이 없는 이상 앞으로 $x_i$ 벡터는 $n$개의 관찰에 대한 평균으로 구성된 벡터 $\mu = [\mu^1~\mu^2~\dotsc~\mu^k]^T$를 뺀 값이라고 간주하자. 즉, $X_i$가 평균을 빼지 않은 $i$ 라고 할 때,

$\underset{k \times 1}{x_i} = \left[\begin{array}{c}{X^1_i - \mu^1} \\ {X^2_i - \mu^2} \\ {\vdots} \\ {X^k_i - \mu^k}\end{array}\right]$

이제 해당 피쳐를 쏠 스크린으로 활용할 유닛 벡터를 $w$라고 하자. 유닛 벡터란 $w \cdot w = 1$를 의미한다. 여기서 스크린이라는 의미는 개별 관찰이 지니는 특징을 이 벡터로 프로젝션해서 그 특징을 요약하겠다는 것이다. 우리에게 익숙한 회귀분석 역시 $y_i$라는 관찰을 설명변수 $\mathbf X$가 형성하는 선형 부분공간으로 프로젝션하는 방법이다. $x_i$를 $w$로 프로젝션 하면 다음과 같다.

$\operatorname{Proj}_{w}(x_i) = \dfrac{w \cdot x_i}{\Vert w \Vert} = w \cdot x_ i$

이 프로젝션의 벡터 $w$ 위의 이미지는 $(w \cdot x_i) w$가 된다.

이 프로젝션 스칼라 값 혹은 프로젝션 벡터의 기댓값은 아래와 같이 0이 된다.
$\dfrac{1}{n} \sum^n_{i=1} (w \cdot x_i) = \left( \dfrac{1}{n} \sum_{i=1}^n x_i \right)\cdot w = \boldsymbol{0} \cdot w = 0$

벡터 $x_i$와 이 프로젝션 이미지 사이의 유클리드 거리를 구해보자.

$\begin{aligned} \Vert x_i - (w \cdot x_i) w \Vert^2 & = \Vert x_i \Vert^2 - 2 (w \cdot x_i)(w \cdot x_i) + \Vert w \Vert^2 \\ & = \Vert x_i \Vert^2 - 2 (w \cdot x_i)^2 + 1 \end{aligned}$

모든 관찰 수 $n$에 대해서 거리를 구해 더하면 이것이 일종의 MSE(Mean Squared Error)가 된다.

$\begin{aligned} \mathrm{MSE}(w) & = \dfrac{1}{n}\sum_{i=1}^n \left( \Vert x_i \Vert^2 - 2(w \cdot x_i)^2 + 1 \right) \\ & = \underbrace{1 + \dfrac{1}{n}\sum_{i=1}^n \Vert x_i \Vert^2}_{(\ast)} - 2\dfrac{1}{n}\sum_{i=1}^n (w \cdot x_i)^2 \end{aligned}$

MSE를 최소화하는 게 목표라고 하자. 목적함수를 최적화 하기 위해서는 $w$를 조정할 수 있다. $(*)$는 $w$를 포함하고 있지 않으므로 나머지 부분을 최소화하면 MSE가 극대화된다.

$\dfrac{1}{n} \sum_{i=1}^n (w \cdot x_i)^2 = \left(\dfrac{1}{n} \sum_{i=1}^n w \cdot x_i \right)^2 + \underset{i}{\mathrm{Var}}[w \cdot x_i]$

이 식이 성립하는 이유는 일반적으로 $\mathrm{Var}(y)= \mathrm{E}(y^2) - (\mathrm{E}(y))^2$이 성립하기 때문이다. 그리고 앞에서 보았듯이 $\mathrm{E} (w \cdot x_i) = 0$ 성립한다. 따라서 MSE를 최소화한다는 것은 $\mathrm{Var}_i [\cdot]$을 최대화하는 것과 같게 된다. PCA에 분산에 관한 이야기가 자꾸 나오는 것은 이 때문이다.

Variance Maximization

Variance-covariance matrix

왜 분산이 등장하는지를 파악했으니 분산 최대화를 계산해볼 차례다. 아래 행렬 $X$를 통해 쉽게 분산-공분산 행렬을 나타낼 수 있다. $x_i^j$ 에서 $i (=1,2,\dotsc, n)$는 관찰을, $j(=1,2,\dotsc,k)$는 피쳐를 나타낸다.

$\underset{n \times k}{X} = \begin{bmatrix} {x_1}^T \\ {x_2}^T \\ \vdots \\ {x_n}^T \end{bmatrix} = \begin{bmatrix} {x_1^1} & {x_1^2} & {\cdots} & {x_1^k} \\ {x_2^1} & {x_2^2} & {\cdots} & {x_2^k}\\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {x_n^1} & {x_n^2} & {\cdots} & {x_n^k} \end{bmatrix}$

$\begin{aligned} \dfrac{1}{n-1} \underset{(k \times n) (n \times k)}{X^{T} X} = \begin{bmatrix} \text{cov}(x^1, x^1) & \text{cov}(x^1, x^2) & \cdots & \text{cov}(x^1, x^k) \\ \text{cov}(x^2, x^1) & \text{cov}(x^2, x^2) & \cdots & \text{cov}(x^2, x^k) \\ \text{cov}(x^k, x^1) & \text{cov}(x^k, x^2) & \cdots & \text{cov}(x^k, x^k) \end{bmatrix} = \Sigma, \text{~where} \end{aligned}$

$\text{cov}(x^i, x^j) = \dfrac{1}{n-1}\sum_{k=1}^{n} x^i_k x^j_k$

eigenvalue는 어떻게 등장하나?

임의의 단위 벡터 $w$와 그 프로젝션을 다시 적어보자. 표기를 간단히 하기 위해서 상첨자는 생략한다. 이제 하나의 벡터가 아니라 $X$라는 매트릭스 전체에 대해서 프로젝션을 하면 아래와 같다.

$\operatorname{Proj}_{w} (X) = \dfrac{X w}{\Vert w \Vert} \in {\mathbb R}^{n \times 1}$

이제 극대화의 목적은 이렇게 프로젝션된 이미지의 분산을 가장 크게 만드는 것이다. 앞서의 가정에 따라서 $\mathrm{E}(X) = 0$가 성립함을 기억해두자.

$\begin{aligned} \mathrm{Var}(X {w}) &= \frac{1}{n-1}(X {w})^{T}(X {w}) \\ &=\frac{1}{n-1} {w}^{T} X^{T} X {w} =\frac{1}{n-1} {w}^{T}\left(X^{T} X\right) {w} \\ &={w}^{T}\left(\frac{X^{T} X}{n-1}\right) {w} \\ &={w}^{T} \Sigma {w} \end{aligned}$

그런데, $w$는 단위벡터임으로 $w \cdot w = 1$이다. 이를 제약 조건으로 두고 제약 하의 극대화 문제를 정식화하면 다음과 같다.

${\mathcal L} =w^{\operatorname T} \Sigma w - \lambda (w \cdot w -1)$

$\begin{aligned} \dfrac{\partial \mathcal L}{\partial w} & = 0 = 2 \Sigma w - 2\lambda w \\ \dfrac{\partial \mathcal L}{\partial \lambda} & = 0 = w \cdot w - 1 \end{aligned}$

1계 조건을 다시 보자.¹ $\Sigma w = \lambda w$ 조건이 흥미롭다. 1계 조건이 정확하게 아이겐밸류(eigenvalue, 고유값)와 아이겐벡터(eigenvector, 고유벡터)를 구하는 방법이다. 어떤 매트릭스가 있을 때 해당 매트릭스의 분산-공분산 행렬의 아이겐밸류와 아이겐벡터를 구하면 그 아이겐밸류와 벡터가 바로 MSE를 최적화해주는 값이 된다. 이때 $w$는 아이겐벡터이며 $\lambda$는 아이겐밸류가 된다. 아이겐밸류는 아래 식에서 보듯이 분산이다.²

$\operatorname{Var}(X w) = w^{\mathrm T} \Sigma w = w^{\mathrm T} (\lambda w) = \lambda w \cdot w = \lambda$

아마도 최적화 공부를 해본 사람이라면 갸우뚱할지 모르겠다. 1계 조건은 필요 조건이다. 즉, 극대화, 극소화 모두를 그 안에 담고 있을 수 있다. 그렇다면 2계 충분 조건을 따져야 하지 않을까? 그런데, 위 식에 대해서 사실 2계 충분 조건을 따지는 것이 쉽지 않다. 다만 이 문제는 다행스럽게도 지름길이 있다. 위에서 보듯이 1계 조건을 만족하는 $w$는 $\Sigma$의 아이겐벡터다. 따라서 이 아이겐벡터에서만 극대값과 극소값이 존재한다. 1계 조건을 만족하는 아이겐벡터를 $\omega$라고 하자.

$\begin{aligned} {\mathcal L}(\omega) & =\omega^{T} \Sigma \omega - \lambda (\omega \cdot \omega -1) \\ & = \omega^T (\Sigma w - \lambda w) + \lambda \\ & = \lambda \end{aligned}$

즉, 1계 조건을 만족하는 값에서 목적 함수의 값은 아이겐밸류 $\lambda$가 된다. 그리고 위에서 보았듯이 $\lambda$는 $Xw$의 분산이 되기 때문에 분산이 큰 값의 아이겐벡터가 목적 함수를 극대화하는 $w$가 된다.

앞서 $\lambda$가 분산이 된다고 말했다. 잠깐, 분산이라면 항상 0보다 커야 하는데, $\lambda$가 0보다 크다는 보장이 있는가? 이 문제를 포함하여 앞에서 정리하지 못한 몇 가지 문제를 모아서 살펴보자.

Properties of var-cov matrix

분산-공분산 행렬은 아래와 같은 두 가지 특징을 지닌다.

대칭 행렬

우선, 분산-공분산 행렬이므로 대칭이다. 행렬이 대칭일 경우 아이겐밸류는 모두 실수이며 아이겐벡터들은 서로 직교(orthogonal)한다.

For $i, j \in \{ 1, 2, \dotsc, k\}~\text{with}~i \ne j, w^i \cdot w^j = 0$, and for $i \in \{ 1, 2, \dotsc, k\}~, w^i \cdot w^i =1$

여러개의 프로젝션 스크린 벡터들이 존재할 경우 해당 벡터들이 서로 직교하면 분산값의 합을 최대화하는 것과 MSE를 최소화하는 것이 같은 의미를 지닌다. 이 조건이 분산-공분산 행렬의 속성을 통해 성립한다.

분산-공분산 행렬의 이 특징이 PCA의 흥미로운 점 하나를 드러난다. 2 차원 평면에서 사 분면을 떠올려보자. 사 분면을 구성하는 $x$, $y$ 축은 서로 직교한다. 2 차원 평면 위에 어떤 관찰에 대해서 PCA를 했다고 하자. PCA의 스크린으로 두 개를 사용했고, 해당 스크린이 아이겐벡터라면 이 두 벡터는 서로 직교한다. 즉, 원래 직교했던 두 축에서 직교하는 다른 두 축으로 좌표의 기준을 이동하는 개념이다. 즉 PCA는 분산을 가장 크게 하는 방식으로 좌표축을 이동하는 방법이라고 이해하면 좋겠다. PCA에 관한 소개에서 아래의 그림처럼 축을 돌린 예시가 자주 등장하는 까닭이기도 하겠다.³

Positive-definite

$\Sigma$는 준양정행렬(positive semi-definite) 행렬이다.⁴ 즉,

$x^T \Sigma x \geq 0 ~\text{for any $x$.}$

이 경우 모든 아이겐밸류의 값은 음수가 되지 않는다. 앞서 아이겐밸류가 분산이 된다는 사실을 보았다. 아이겐밸류가 음수가 될 수 없고 따라서 분산이 될 수 있다.

Principal component?

프로젝션 스크린 벡터 $w$에 따른 극대화 문제를 풀면 아이겐밸류와 아이겐벡터를 각각 하나씩 얻게 된다. $k$ 개의 스크린 벡터 혹은 아이겐벡터가 가능하다고 할 때, 분산(아이겐밸류)이 큰 순서대로 아이겐벡터를 정렬한다고 생각해보자. 이렇게 정렬하면 프로젝션 스크린 벡터 중에서 MSE를 더 줄일 수 있는 벡터 순으로 정렬하는 셈이다. 이렇게 분산이 큰 순서대로 나열한 서로 다른 스크린벡터가 바로 주성분(pricipal component)다.

$k$ 개의 주성분 중에서 임의로 $l$ 개를 취한다면(이게 차원 축소가 아닐까?), MSE를 낮추기 위해서는 분산이 큰 순서대로, 즉 아이겐밸류가 큰 순서대로 주성분을 취하면 된다. 이게 PCA를 직관적으로 이해하는 방법이다.

그런데 한 가지 찜찜한 점이 남는다. 주성분은 이렇게 순서대로 취할 수 있다는 것은 주성분을 결합해서 더 큰 분산을 얻을 수 없을 때만 가능하다. 예컨대, $w_1$과 $w_2$를 적당히 선형결합해 분산을 높일 수 있다면 분산이 큰 순서대로 아이겐벡터를 선택한다는 논의는 깨지게 된다. 이 가능성을 살펴봐야 하겠다.

프로젝션의 스크린으로 동원되는 벡터가 $w^1, w^2, \dotsc, w^k$라고 하자. 이 프로젝션을 통해 생성되는 벡터들이 이루는 부분공간은 다음과 같이 나타낼 수 있다.

$\sum_{j=1}^k \underset{\mathrm{가중치}}{( x_i \cdot w^j) } w^j$

$x_i$와 $w^j$ 모두 $k \times 1$ 벡터임을 확인하고 가자. 이 녀석과 $x_i$의 MSE를 최소화하는 문제는 어떻게 될까? 계산이 다소 복잡하니 직관만 짚고 넘어가자.

1. 앞서 스크린이 하나였던 경우와 마친가지로 $x_i$와 저 값의 내적의 분산을 최대화 해야 한다.
2. 만일 $w_\cdot$들이 서로 직교한다면, $w_i \cdot w_j (i \neq j)$는 0이 되어 사라질 것이고, $w_i \cdot w_i$(=1)로 구성된 텀만 만게 된다. 결국
3. 스크린을 이루는 축들과 $x_i$의 크로스 프로덕트 값의 분산($\mathrm{Var} (x_i \cdot w^j)$)을 더한 값을 최대화하는 것이 MSE를 극소화 문제가 된다. 즉, 각각 $w^j$와 $x_i$의 닷 프로덕트의 분산을 최대화하면 된다. 즉,

$\underset{i}{\text{Var}}[\sum_{j=1}^k {( x_i \cdot w^j) } w^j] = \sum_{j=1}^k {\lambda^j}$

마침내 차원 축소

이제 마침내 차원 축소를 다룰 수 있다! 앞서 MSE 최소화 문제에서 보았듯이 분산이 클수록 좋다. 임의의 갯수로 주성분을 취한다고 할 때 의 기준은 분산이 큰 순서이고 분산은 아이겐밸류와 같다. $l(<k)$ 개의 주성분을 취할 때 취할 때 아이겐밸류가 큰 순서대로 취하면 되겠다.⁵

Key Questions

Q1. MSE 최소화는 무엇으로 연결되는가?

$Xw$의 분산을 최대화하는 것이다.

Q2. 아이겐밸류 아이겐벡터는 어떻게 등장하는가?

$Xw$의 분산을 $w^T w =1$의 제약하에서 극대화할 때 1계 조건에서 등장한다.

Q3. 아이겐벡터와 아이겐밸류는 어떤 특징을 지니고 있는가?

1계 조건에서 아이겐벡터와 아이겐밸류를 찾아야 하는 매트릭스는 var-cov 행렬 $\Sigma$다. 그리고 이 행렬은 대칭행렬이며 Positive definite 행렬이다. 이 조건으로부터, 아이겐벡터들은 서로 orthogonal하고, 아이겐밸류는 모두 양수이다.

Q4. 결국 PCA란 무엇인가?

분산이 큰 순서대로 $k$ 개의 주성분 중에서 임의로 $l(<k)$ 개의 아이겐벡터를 선택하는 것이다. 그리고 이 아이겐벡터는 일종의 피처에 관한 가중치로 이해할 수 있다.

Resource

이 글은 아래 자료를 바탕으로 만들었습니다.

https://www.stat.cmu.edu/~cshalizi/350/lectures/10/lecture-10.pdf






🐾Jun Sok Huhh | 🏠lostineonomics.com

---

1. 사실 여기 적은 1계 조건은 엄밀하지 않다. 이해를 돕기 위해서 여러가지를 퉁쳤는데, 최적화의 결과는 동일하다. 보다 상세한 도출은 여기를 참고하시기 바란다. ↩︎

2. 흥미로운 일치를 확인하셨는지? 제약 하 극대화에서 라그랑쥬 승수와 아이겐밸류를 나타내는 수학 기호가 모두 $\lambda$다. 약간 소름 돋는 대목이다. 일치는 여기서 끝나지 않는다. 라그랑쥬 승수는 제약 하의 극대화에서 잠재 가격(shadow price)로 불리기도 한다. 이는 해당 조건이 제약하는 자원의 잠재적인 가치를 나타낸다. 이는 분산이 클수록 MSE가 작다는 PCA의 목적 함수의 해석과 일치한다. ↩︎

3. 하나 주의할 점이 있다. 이 그림은 차원 회전에 관한 것이지 차원 축소에 관한 것이 아니다. 즉, 변이가 잘 드러나도록 축을 회전할 수 있다는 예시다. 축소는 다른 문제인데, 아래 본문의 내용에서 보듯이 축을 돌려 변이를 상당 부분 설명했다면 변이의 설명력이 낮은 축들을 제거할 수 있다는 것이 차원 축소다. ↩︎

4. 증명은 몹시 간단하다. $w^T \Sigma w$ 라고 하자.
   $w^T X^T X w = \underset{\text{닷 프로덕트}}{ (Xw)^T (Xw) } \geq 0$ ↩︎

5. 주성분의 갯수를 취하는 방법은 PCA에 관한 튜토리얼에서 항상 등장하는 주제이니 구글링을 해서 확인하시면 되겠다. ↩︎