#6 선형대수를 이용한 주성분 유도

❗️블로그 옮김:  https://www.taemobang.com

방태모

비지도 학습중 하나인 간단한 알고리즘 주성분 분석(PCA : principal components analysis)은 선형대수의 기본적인 개념들을 이용하여 유도할 수도 있다. $\mathbb{R}^n$의 공간에 m개의 점들(points) $\left \{ \boldsymbol{x}^{(1)}, \cdots, \boldsymbol{x}^{(m)} \right \}$이 있고, 이 점들에 대해 손실 압축(lossy compression)을 적용하길 원한다고 하자. 손실압축은 정보손실이 있지만 메모리를 줄이는 방식으로 점들을 저장하는 것을 의미하며, 정보손실을 최대한 줄이고자한다. 이것이 PCA의 목적이다. 이 점들은 encode하는 한 가지 방법은 이들을 저차원 공간으로 나타내는 것이다. 각 점(point) $\boldsymbol{x}^{(i)} \in \mathbb{R}^n$에 대한 code 벡터 $\boldsymbol{c}^{(i)} \in \mathbb{R}^l$를 찾을 예정이고, $l < n$이면 code points들은 원 데이터(원래 점들)보다 적은 메모리를 가지게 된다. 결론적으로 우리는 encoding 함수 $f\left ( \boldsymbol{x} \right ) = \boldsymbol{c}$와 code된 점을 원 데이터로 되돌리는 decoding 함수 $\boldsymbol{x} \approx g\left ( f\left ( \boldsymbol{x} \right ) \right )$을 찾고자한다.^[각주:1] PCA는 decoding 함수의 선택에의해 정의된다. decoder를 간단하게 하기위해 행렬곱을 선택한다. $g\left ( \boldsymbol{c} \right ) = \boldsymbol{Dc}$라 하자. 여기서 $\boldsymbol{D} \in \mathbb{R}^{n \times l}$는 decoding을 정의하는 행렬이다(차원이 $n \times l$이므로, 결과적으로 $\boldsymbol{c}$는 원 데이터의 공간 $\mathbb{R}^n$으로 복원된다). 이 decoder에 대한 최적의 encoder를 찾는 것은 어려운 문제일 수 있다. 이를 쉽게하기 위해 PCA에서는 몇몇 제약들이 필요하다.

 

○ PCA는 $\boldsymbol{D}$의 열들이 서로 직교한다고 제약을 둔다. 다만 $\boldsymbol{D}$는 $l=n$이 아니면, 여전히 직교행렬은 아님을 주의해라.

○ $l<n$이면 무수히 많은 해가 존재할 수 있다. 이 문제를 해결하고, unique한 해를 제공하기 위해서 $\boldsymbol{D}$의 모든 열들은 unit norm을 가진다고 가정한다(즉, 모든 열들이 단위벡터).

 

위와 같은 두가지 기본적인 idea를 알고리즘에 적용하기 위해서, 첫번째로 해야할 일은 원 데이터의 각 점 $\boldsymbol{x}$에 대한 최적의 code point $\boldsymbol{c}^*$를 발생시키는 방법을 찾는것이다. 이를 하기위한 한가지 방법은 원데이터의 점 $\boldsymbol{x}$와 $\boldsymbol{c}^*$에 decoding 함수를 걸어주어 복원시킨 점인 $g\left ( \boldsymbol{c}^* \right )$간의 거리를 최소화 하는 것이다(차원 축소를 시행하여 메모리를 줄이는데, 정보손실은 최소화하고자하는 idea). 이 거리는 앞서배운 norm 개념을 이용하여 측정할 수 있으며, PCA에서는 $L^2$ norm을 사용한다. 즉, $\boldsymbol{c}^*$는 다음과 같이 구해진다:

 

$\boldsymbol{c}^* = \underset{\boldsymbol{c}}{arg\; min}\left \| \boldsymbol{x} - g\left ( \boldsymbol{c} \right ) \right \|_2$

 

사실 $L^2$ norm 대신에 squared $L^2$ norm을 사용할 수도 있는데, $L^2$ norm은 비음 함수이며, 이에 대한 제곱 연산은 비음의 인수($L^2$ norm)에 대해 단조증가(monotonically increasing)이므로 둘다 $\boldsymbol{c}$를 같은 값으로 최소화 시킨다. 계산의 편의를 위해 squared $L^2$ norm을 사용해 $\boldsymbol{c}^*$를 정의하자.

 

$\boldsymbol{c}^* = \underset{\boldsymbol{c}}{arg\; min}\left \| \boldsymbol{x} - g\left ( \boldsymbol{c} \right ) \right \|_2^2$

 

그럼 위 함수는 다음의 연산을 최소화하는 것과 같다.

 

$\left ( \boldsymbol{x}-g\left ( \boldsymbol{c} \right ) \right )^T\left ( \boldsymbol{x} - g\left ( \boldsymbol{c} \right ) \right )$

$=\boldsymbol{x}^T\boldsymbol{x} - \boldsymbol{x}^Tg\left ( \boldsymbol{c} \right ) - g\left ( \boldsymbol{c} \right )^T\boldsymbol{x} + g\left ( \boldsymbol{c} \right )^Tg\left ( \boldsymbol{c} \right )$

$=\boldsymbol{x}^T\boldsymbol{x} - 2\boldsymbol{x}^Tg\left ( \boldsymbol{c} \right ) + g\left ( \boldsymbol{c} \right )^Tg\left ( \boldsymbol{c} \right )$  ($\because g\left ( \boldsymbol{c} \right )^T\boldsymbol{x}$ is scalar)

 

첫번째 항은 $\boldsymbol{c}$에 무관하기 때문에 제거하고 $\boldsymbol{c}^*$를 다시 쓰면:

 

$\boldsymbol{c}^* = \underset{c}{arg\; min}-2\boldsymbol{x}^Tg\left ( \boldsymbol{c} \right ) + g\left ( \boldsymbol{c} \right )^Tg\left ( \boldsymbol{c} \right )$

 

이제 $g\left ( \boldsymbol{c} \right )$를 다시 쓰자.

 

$\boldsymbol{c}^* = \underset{c}{arg\; min}-2\boldsymbol{x}^T\boldsymbol{Dc} + \boldsymbol{c}^T\boldsymbol{D}^T\boldsymbol{Dc}$

$ = \underset{c}{arg\; min}-2\boldsymbol{x}^T\boldsymbol{Dc} + \boldsymbol{c}^T\boldsymbol{c}$  ($\because \boldsymbol{D}$의 모든 열들은 직교)

 

이제 이 최적화 문제는 벡터 미분을 이용하여 풀 수 있다.

 

$\boldsymbol{\bigtriangledown}_{\boldsymbol{c}}\left (-2\boldsymbol{x}^T\boldsymbol{Dc} + \boldsymbol{c}^T\boldsymbol{c} \right ) = 0$

$-2\boldsymbol{D}^Tx + 2\boldsymbol{c} = 0$

$\boldsymbol{c} = \boldsymbol{D}^T\boldsymbol{x}$

 

알고리즘이 매우 효율적이다. $\boldsymbol{x}$를 최적으로 encode하기위해서는 단지 행렬-벡터 곱연산만 해주면된다. 정리하면 encoder 함수는 다음과 같이 정의된다.

 

$f\left ( \boldsymbol{x} \right ) = \boldsymbol{D}^T\boldsymbol{x}$

 

encode된 점을 다시 원 데이터의 차원으로 복원하는 PCA reconstruction 연산은 행렬 곱만 사용하면 다음과 같이 쉽게 정의된다:

 

$r\left ( \boldsymbol{x} \right ) = g\left ( f\left ( \boldsymbol{x} \right ) \right ) = \boldsymbol{DD}^T\boldsymbol{x}$

 

그럼 이제 마지막으로 encoding 행렬 $\boldsymbol{D}$를 유도해보자. 앞서 말했던 원데이터 $\boldsymbol{x}$와 차원 축소후 복원시킨점 $g\left ( \boldsymbol{c} \right )$간에 $L^2$ norm을 최소화시키는 idea를 이용해 $\boldsymbol{c}^*$를 구한것을 떠올려보자. 이번에도 똑같다. 모든 점들을 동일한 $\boldsymbol{D}$를 이용해 decode할 것이므로, 모든 점들의 Errors를 성분으로 갖는 행렬의 Frobenious norm을 최소화 시키면된다. 즉:

 

$\boldsymbol{D}^* = \underset{\boldsymbol{D}}{arg\;min}\sqrt{\sum_{i, j}\left ( \boldsymbol{x}_j^{(i)} - r\left ( \boldsymbol{x}^{(i)} \right )_j \right )^2}$ subject to $\boldsymbol{D}^T \boldsymbol{D} = \boldsymbol{I}_l$

 

앞서 했던 것과 마찬가지로 계산의 편의를 위해 squared $L^2$ norm으로 바꾸고, 줄이고자하는 차원을 $l=1$로 고려하자. 그럼 $\boldsymbol{D}$는 single vector $\boldsymbol{d}$가 된다. 위 식을 다시쓰면:

 

$\boldsymbol{d}^* = \underset{\boldsymbol{d}}{arg\;min}\sum_i\left \| \boldsymbol{x}^{(i)} - \boldsymbol{dd}^T\boldsymbol{x}^{(i)} \right \|_2^2$ subject to $\left \| \boldsymbol{d} \right \|_2 = 1$

$ = \underset{\boldsymbol{d}}{arg\;min}\sum_i\left \| \boldsymbol{x}^{(i)} - \boldsymbol{d}^T\boldsymbol{x}^{(i)} \boldsymbol{d} \right \|_2^2$ subject to $\left \| \boldsymbol{d} \right \|_2 = 1$

 

스칼라는 벡터의 왼쪽에 써주는게 관례(convention)이며, $\boldsymbol{d}^T \boldsymbol{x}^{(i)}$가 스칼라여서 위와같이 바꿔서 써줬다. 또한 스칼라는 전치를 수행해도 동일하며, 식을 좀더 간소화 하기위해서 행렬 형태로 적자. 이 두 가지를 적용하면 다음과 같이 쓸 수 있다.

 

$= \underset{\boldsymbol{d}}{arg \; min}\sum_i \left \| \boldsymbol{x}^{(i)} - \boldsymbol{x}^{(i)\: T}\boldsymbol{dd}\right \|_2^2$ subject to $\left \| \boldsymbol{d} \right \|_2 = 1$

$= \underset{\boldsymbol{d}}{arg \; min}\left \| \boldsymbol{X} - \boldsymbol{Xdd}^T \right \|_F^2$ subject to $\left \| \boldsymbol{d} \right \|_2 = 1$

$\left ( \boldsymbol{X} \in \mathbb{R}^{m \times n }, \boldsymbol{X}_{i, :} = \boldsymbol{x}^{(i)\: T} \right )$

 

제약은 잠깐 생략하고, Frobenius norm 부분을 간소화하기위해 Trace 연산자를 이용해 다시쓰자. 이 과정이 이해가 안되면 앞선 Trace 연산자 설명부분을 다시 보자.

 

$ =\underset{\boldsymbol{d}}{arg \; min}\textrm{Tr}\left ( \left ( \boldsymbol{X}-\boldsymbol{Xdd}^T \right )^T \left ( \boldsymbol{X}-\boldsymbol{Xdd}^T \right ) \right )$

 

Trace 연산자 안의 식을 모두 전개하고, $\boldsymbol{d}$와 무관한 부분은 생략해서 쓰면 다음과 같다.

 

$= \underset{\boldsymbol{d}}{arg \; min} -\textrm{Tr}\left ( \boldsymbol{X}^T \boldsymbol{Xdd}^T\right ) - \textrm{Tr}\left ( \boldsymbol{dd}^T\boldsymbol{X}^T\boldsymbol{X} \right ) + \textrm{Tr}\left ( \boldsymbol{dd}^T\boldsymbol{X}^T\boldsymbol{Xdd}^T \right)$

 

Trace 연산자는 전치에 대해 불변하므로:

 

$= \underset{\boldsymbol{d}}{arg \; min} -2\textrm{Tr}\left ( \boldsymbol{X}^T\boldsymbol{Xdd}^T \right ) + \textrm{Tr}\left ( \boldsymbol{dd}^T\boldsymbol{X}^T\boldsymbol{Xdd}^T \right )$

 

이제 거의 다왔다. 앞서 설명했던 Trace 연산자의 순서에대해 불변하는 성질과 제약을 이용하면 식이 다음과 같이 크게 간소화된다.

 

$= \underset{\boldsymbol{d}}{arg \; min} -2\textrm{Tr}\left ( \boldsymbol{X}^T\boldsymbol{Xdd}^T \right ) + \textrm{Tr}\left ( \boldsymbol{X}^T \boldsymbol{X} \boldsymbol{dd}^T \boldsymbol{dd}^T \right )$ subject to $\boldsymbol{d}^T \boldsymbol{d} = 1$

$= \underset{\boldsymbol{d}}{arg \; min} -2\textrm{Tr}\left ( \boldsymbol{X}^T\boldsymbol{Xdd}^T \right ) + \textrm{Tr}\left ( \boldsymbol{X}^T \boldsymbol{X} \boldsymbol{dd}^T \right )$ subject to $\boldsymbol{d}^T \boldsymbol{d} = 1$

$= \underset{\boldsymbol{d}}{arg \; min} -\textrm{Tr}\left ( \boldsymbol{X}^T\boldsymbol{Xdd}^T \right )$ subject to $\boldsymbol{d}^T \boldsymbol{d} = 1$

$= \underset{\boldsymbol{d}}{arg \; \textrm{max}}\:  \textrm{Tr}\left ( \boldsymbol{X}^T\boldsymbol{Xdd}^T \right )$ subject to $\boldsymbol{d}^T \boldsymbol{d} = 1$

$= \underset{\boldsymbol{d}}{arg \; \textrm{max}}\:  \textrm{Tr}\left ( \boldsymbol{d}^T \boldsymbol{X}^T \boldsymbol{Xd} \right)$ subject to $\boldsymbol{d}^T \boldsymbol{d} = 1$

 

최종식에 어디서 많이보던 반가운 식 고윳값 분해(eigenvalue decomposition)가 있다($\boldsymbol{d}^T \boldsymbol{X}^T \boldsymbol{Xd} = \lambda_1$, $\boldsymbol{X}^T \boldsymbol{X}$는 항상 대칭 행렬). 즉 PCA의 최적화 문제는 고윳값분해로 풀릴 수 있으며, 최적의 $\boldsymbol{d}$는 가장 큰 고윳값을 가지는 $\boldsymbol{X}^T \boldsymbol{X}$의 고유벡터로 주어진다. 이는 줄이고자 하는 차원이 $l=1$인 경우이며, 여기서는 첫번째 주성분(principal component)만 유도된다. 첫번째 주성분이 가장 큰 고윳값을 가지게된다. 이를 일반화하여 주성분들의 기저(basis)를 유도하면, 행렬 $\boldsymbol{D}$는 고윳값 크기 순대로 배열된 $l$개의 고유벡터를 열로 가지게된다.

 

📝 참고 문헌

[1] Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep Learning. The MIT Press, 2016

---

1. PCA의 목적을 짧게 정리하면, 정보손실을 최대한 줄여 원 데이터의 차원을 축소하는 것이라 할 수 있음 [본문으로]