선형 차원 축소법: PCA

PCA의 목적은 고차원 데이터 $x \in \mathbb{R}^D$를 차원이 $M$인 특정 부분공간으로 사영시키는데 이때 사영된 데이터들의 분산이 최대화되도록 하는 선형 부분공간을 찾는 것이다.

1차원 주성분 공간

먼저, 문제를 간단히 접근하기 위해 사영시키는 공간의 차원을 1차원으로 한정해보자. 고차원의 공간내에서 1차원 선형 부분공간은 유닛 벡터 $u_1 \in \mathbb{R}^D$으로 정의할 수 있다. 그리고 어떤 데이터 $x \in \mathbb{R}^D$를 그 부분공간으로 사영시킨 데이터는 $u_1^\top x \in \mathbb{R}^1$으로 표현할 수 있다.

$$ u_1 \in \mathbb{R}^D \;\; such \; that \;\; u_1^\top u_1 = 1 $$

이 때 사영된 데이터의 분산은 다음과 같이 정의된다.

$$ \frac{1}{N} \sum_{n=1}^{N} \left( u_1^\top x_n - u_1^\top \bar{x} \right)^2 = u_1^\top S u_1 \;\; where \; \bar{x} = \frac{1}{N} \sum_{n=1}^{N} x_n, \; S = \frac{1}{N} \sum_{n=1}^{N} \left( x_n - \bar{x} \right) \left( x_n - \bar{x} \right)^\top $$

따라서 최적화 문제는 다음과 같이 정의된다.

$$ \underset{u_1}{\text{maximize}} \; u_1^\top S u_1 \;\; such \; that \; u_1^\top u_1 = 1 $$

이를 라그랑지안을 이용하여 표현하면 $u_1^\top S u_1 + \lambda_1 \left( 1 - u_1^\top u_1 \right)$가 되고, 이를  최대화하는 라그랑지 듀얼 함수를 고려하기 위해 미분해서 0이 되는 조건을 찾는다.

$$ \frac{\partial}{\partial u_1} \left( u_1^\top S u_1 + \lambda_1 \left( 1 - u_1^\top u_1 \right) \right) = \left( S + S^\top \right) u_1 - 2 \lambda_1 u_1 = 0 $$

공분산 행렬을 전치행렬이므로 다음과 같이 작성할 수 있다.

$$ S u_1 = \lambda_1 u_1 $$

이를 원래 최적화 문제에 넣어보면 다음과 같고 최적화가 완료되었을 때, 최적화 값은 공분산 행렬의 가장 큰 고윳값이  되고 이 때 해는 연관된 고유벡터임을 응용선형대수 지식을 통해 알 수 있다.

$$ \underset{u_1}{\text{maximize}} \; \lambda_1 u_1^\top u_1 \;\; such \; that \; u_1^\top u_1 = 1 $$

M차원 주 성분 공간

우리는 $M$차원의 공간을 단순히 행렬 $U=\left[ u_1, ..., u_M \right] \in \mathbb{R}^{D \times M}$으로 표현하고 $U^\top x$를 $x$를 해당 공간으로 사영한 결과로 볼 수 있다. 여기서, 각각의 벡터가 겹치지 않게끔 벡터 간에 직교한다는 제한을 걸어둔다.

$$ u_i^\top u_j = \delta_{ij} \;\; ^\forall i, j \in \left[ M \right] $$

이를 가지고 최적화 문제를 정의하면 다음과 같다. 이 때, 각 분산에 대해서 모든 분산의 합을 최대화하게끔 정의한다.

$$ \underset{U}{\text{maximize}}\sum_{i=1}^{M} u_i^\top S u_i \;\; such \; that \; u_i^\top u_j = \delta_{ij} $$

이것 또한, $M$개의 큰 고유벡터의 합으로 나타나지게 된다. $S$가 positive semi-definite이기 때문에 모든 고윳값은 음이 아니기 때문에 가능하다.

다른 방식으로 PCA 접근하기

우리는 $D$차원을 span할 수 있는 완벽한 직교 유닛 basis $U=\left[u_1, ..., u_D \right] \in \mathbb{R}^{D \times D}$를 생각해볼 수 있다. 이를 이용하면 우리는 각각의 데이터 $x_n$에 대해 $U$의 선형 결합으로 나타낼 수 있게 된다.

$$ x_n = \sum_{i=1}^{D} \alpha_{ni} u_i \;\; where \; \alpha_{ni} = x_n^\top u_i $$

여기서 우리는 첫 $M$개의 벡터만 사용해서 $M$차원 공간으로 근사할 것이다.

$$ \tilde{x}_n = \sum_{i=1}^{M} z_{ni} u_i + \sum_{i=M+1}^{D} b_i u_i $$

그리고 이 근사값과 원래 값 간의 오차를 최소화하는 목적식을 정의한다.

$$ \underset{z_{ni}, b_i}{\text{minimize}} \frac{1}{N} \sum_{n=1}^{N} \left| x_n - \tilde{x}_n \right|^2 $$

이 식을 미분해보면 다음과 같아진다.

$$ \frac{\partial}{\partial z_{ni}} \frac{1}{N} \sum_{n=1}^{N} \left| x_n - \tilde{x}_n \right|^2 = \frac{\partial}{\partial z_{ni}} \frac{1}{N} \left( x_n - \tilde{x}_n \right)^\top \left( x_n - \tilde{x}_n \right) = \frac{\partial}{\partial z_{ni}} \frac{1}{N} \left( -2\tilde{x}_n^\top x_n + \tilde{x}_n^\top \tilde{x}_n \right) $$

$$ \frac{\partial}{\partial z_{ni}} \tilde{x}_n^\top x_n = \frac{\partial}{\partial z_{ni}} \left( \sum_{i=1}^{M} \alpha_{ni} z_{ni} + \sum_{i=M+1}^{D} \alpha_{ni} b_i \right) = \alpha_{ni} $$

$$ \frac{\partial}{\partial z_{ni}} \tilde{x}_n^\top \tilde{x}_n = \frac{\partial}{\partial z_{ni}} \left( \sum_{i=1}^{M} z_{ni}^2 + \sum_{i=M+1}^{D} b_i^2 \right) = 2 z_{ni} $$

$$ \frac{\partial}{\partial z_{ni}} \frac{1}{N} \sum_{n=1}^{N} \left| x_n - \tilde{x}_n \right|^2 = \frac{1}{N} \left( -2 \alpha_{ni} + 2 z_{ni} \right) = 0 $$

따라서, 목적식이 최소가 되려면 $z_{ni} = \alpha_{ni} = x_n^\top u_i$가 되어야 한다. 마찬가지로, $b_i$에 대해서 진행한다.

$$ \frac{\partial}{\partial b_{i}} \frac{1}{N} \sum_{n=1}^{N} \left| x_n - \tilde{x}_n \right|^2 = \frac{\partial}{\partial b_{i}} \frac{1}{N} \sum_{n=1}^{N} \left( -2\tilde{x}_n^\top x_n + \tilde{x}_n^\top \tilde{x}_n \right) $$

$$ \frac{\partial}{\partial b_{i}} \tilde{x}_n^\top x_n = \frac{\partial}{\partial b_{i}} \left( \sum_{i=1}^{M} \alpha_{ni} z_{ni} + \sum_{i=M+1}^{D} \alpha_{ni} b_i \right) = \alpha_{ni} $$

$$ \frac{\partial}{\partial b_{i}} \tilde{x}_n^\top \tilde{x}_n = \frac{\partial}{\partial b_{i}} \left( \sum_{i=1}^{M} z_{ni}^2 + \sum_{i=M+1}^{D} b_i^2 \right) = 2 b_{i} $$

$$ \frac{\partial}{\partial b_{i}} \frac{1}{N} \sum_{n=1}^{N} \left| x_n - \tilde{x}_n \right|^2 = \frac{1}{N} \sum_{n=1}^{N} \left( -2 \alpha_{ni} + 2 b_{i} \right) = 0 $$

따라서, 목적식이 최소가 되려면 $b_i = \frac{1}{N} \sum_{n=1}^{N} \alpha_{ni} = \frac{1}{N} \sum_{n=1}^{N} x_n^\top u_i = \bar{x}^\top u_i$가 되야 한다.

이를 가지고 목적식을 다시 작성해보면, 다음과 같아진다.