고유벡터 계산 및 저랭크 근사

이전 절에서 우리는 주 부분공간(principal subspace)의 기저를 데이터 공분산 행렬의 가장 큰 고윳값들과 연관된 고유벡터들로 도출했다.

$$ \boldsymbol{S} = \frac{1}{N} \sum_{n=1}^N \boldsymbol{x}_n \boldsymbol{x}_n^\top = \frac{1}{N} \boldsymbol{X}\boldsymbol{X}^\top, \quad (10.45) $$
$$ \boldsymbol{X} = [\boldsymbol{x}_1, \dots, \boldsymbol{x}_N] \in \mathbb{R}^{D \times N}. \quad (10.46) $$

$\boldsymbol{X}$ 가 $D \times N$ 행렬임에 유의하라. 즉, 이는 “일반적인” 데이터 행렬의 전치(transpose) 형태이다 (Bishop, 2006; Murphy, 2012). $\boldsymbol{S}$ 의 고윳값(및 대응하는 고유벡터)을 얻기 위해, 두 가지 접근법을 따를 수 있다.

  • 고윳값 분해(eigendecomposition, 4.2절 참조)를 수행하여 $\boldsymbol{S}$ 의 고윳값과 고유벡터를 직접 계산한다.
  • 특이값 분해(singular value decomposition, 4.5절 참조)를 사용한다. $\boldsymbol{S}$ 는 대칭 행렬이며 $\boldsymbol{X}\boldsymbol{X}^\top$ 로 인수분해 되므로(상수 인자 $\frac{1}{N}$ 은 무시), $\boldsymbol{S}$ 의 고윳값은 $\boldsymbol{X}$ 의 특이값(singular values)의 제곱이다.

$\quad$ 더 구체적으로, $\boldsymbol{X}$ 의 SVD는 다음과 같이 주어진다.

$$ \underbrace{\boldsymbol{X}}_{D \times N} = \underbrace{\boldsymbol{U}}_{D \times D} \underbrace{\boldsymbol{\Sigma}}_{D \times N} \underbrace{\boldsymbol{V}^\top}_{N \times N}, \quad (10.47) $$

여기서 $\boldsymbol{U} \in \mathbb{R}^{D \times D}$ 와 $\boldsymbol{V}^\top \in \mathbb{R}^{N \times N}$ 은 직교 행렬(orthogonal matrices)이고, $\boldsymbol{\Sigma} \in \mathbb{R}^{D \times N}$ 은 유일한 비영(nonzero) 성분이 특이값 $\sigma_{ii} \ge 0$ 인 행렬이다. 그러면 다음이 성립한다.

$$ \boldsymbol{S} = \frac{1}{N}\boldsymbol{X}\boldsymbol{X}^\top = \frac{1}{N} \boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^\top \boldsymbol{V}\boldsymbol{\Sigma}^\top\boldsymbol{U}^\top = \frac{1}{N} \boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{\Sigma}^\top\boldsymbol{U}^\top. \quad (10.48) $$

( $\boldsymbol{V}^\top \boldsymbol{V} = \boldsymbol{I}_N$ )
4.5절의 결과를 바탕으로, $\boldsymbol{U}$ 의 열(columns)이 $\boldsymbol{X}\boldsymbol{X}^\top$ (따라서 $\boldsymbol{S}$ )의 고유벡터임을 알 수 있다. 또한, $\boldsymbol{S}$ 의 고윳값 $\lambda_d$ 는 다음을 통해 $\boldsymbol{X}$ 의 특이값과 연관된다.

$$ \lambda_d = \frac{\sigma_d^2}{N}. \quad (10.49) $$

$\boldsymbol{S}$ 의 고윳값과 $\boldsymbol{X}$ 의 특이값 사이의 이러한 관계는 최대 분산 관점(10.2절)과 특이값 분해 사이의 연결성을 제공한다.

10.4.1 PCA Using Low-Rank Matrix Approximations

저랭크 근사를 이용한 PCA

사영된 데이터의 분산을 최대화(또는 평균 제곱 재구성 오차를 최소화)하기 위해, PCA는 (10.48)의 $\boldsymbol{U}$ 의 열들을 데이터 공분산 행렬 $\boldsymbol{S}$ 의 가장 큰 $M$ 개의 고윳값과 연관된 고유벡터들로 선택한다. 이를 통해 $\boldsymbol{U}$ 를 원본 데이터를 $M$ 차원의 더 낮은 차원의 부분공간으로 사영하는 (10.3)의 투영 행렬 $\boldsymbol{B}$ 와 동일시한다. 에카르트-영 정리(Eckart-Young theorem, 4.6절의 정리 4.25)는 저차원 표현을 추정하는 직접적인 방법을 제공한다. $\boldsymbol{X}$ 의 최적 랭크- $M$ 근사를 다음과 같이 고려하자.

$$ \tilde{\boldsymbol{X}}_M := \text{argmin}_{\text{rk}(\boldsymbol{A}) \le M} \Vert \boldsymbol{X} - \boldsymbol{A}\Vert _2 \in \mathbb{R}^{D \times N} \quad (10.50) $$

여기서 $\Vert \cdot\Vert _2$ 는 (4.93)에서 정의된 스펙트럼 노름(spectral norm)이다. 에카르트-영 정리는 $\tilde{\boldsymbol{X}}_M$ 이 상위 $M$ 개의 특이값에서 SVD를 절단(truncating)함으로써 주어짐을 명시한다. 다시 말해, 다음을 얻는다.

$$ \tilde{\boldsymbol{X}}_M = \underbrace{\boldsymbol{U}_M}_{D \times M} \underbrace{\boldsymbol{\Sigma}_M}_{M \times M} \underbrace{\boldsymbol{V}_M^\top}_{M \times N} \in \mathbb{R}^{D \times N} \quad (10.51) $$

여기서 직교 행렬 $\boldsymbol{U}_M := [\boldsymbol{u}_1, \dots, \boldsymbol{u}_M] \in \mathbb{R}^{D \times M}$ 및 $\boldsymbol{V}_M := [\boldsymbol{v}_1, \dots, \boldsymbol{v}_M] \in \mathbb{R}^{N \times M}$ 이고, 대각 행렬 $\boldsymbol{\Sigma}_M \in \mathbb{R}^{M \times M}$ 의 대각 성분은 $\boldsymbol{X}$ 의 가장 큰 $M$ 개의 특이값이다.

10.4.2 Practical Aspects

실무적 측면

고윳값과 고유벡터를 찾는 것은 행렬 분해를 요구하는 다른 기본적인 기계학습 방법들에서도 중요하다. 4.2절에서 논의한 바와 같이, 이론적으로 우리는 특성 다항식(characteristic polynomial)의 근을 구함으로써 고윳값을 풀 수 있다. 그러나 $4 \times 4$ 보다 큰 행렬의 경우, 5차 이상의 다항식 근을 찾아야 하므로 이것이 불가능하다. 더욱이, 아벨-루피니 정리(Abel-Ruffini theorem; Ruffini, 1799; Abel, 1826)는 5차 이상의 다항식에 대해 이 문제를 해결할 수 있는 대수적 해법(algebraic solution)이 존재하지 않음을 명시한다. 따라서 실무에서는 모든 현대 선형대수 패키지에 구현되어 있는 반복법(iterative methods)을 사용하여 고윳값이나 특이값을 푼다.

$\quad$ (본 장에서 제시된 PCA와 같은) 많은 응용 분야에서 우리는 오직 소수의 고유벡터만을 필요로 한다. 전체 분해를 계산한 다음 처음 몇 개를 초과하는 고윳값을 가진 모든 고유벡터를 버리는 것은 연산 낭비이다. 가장 큰 고윳값을 가지는 처음 몇 개의 고유벡터에만 관심이 있다면, 이 고유벡터들을 직접 최적화하는 반복 과정이 전체 고윳값 분해(또는 SVD)보다 연산 측면에서 더 효율적이다. 오직 첫 번째 고유벡터만 필요한 극단적인 경우, 거듭제곱법(power iteration)이라 불리는 단순한 방법이 매우 효율적이다. 거듭제곱법은 $\boldsymbol{S}$ 의 영공간(null space)에 있지 않은 무작위 벡터 $\boldsymbol{x}_0$ 를 선택하고 다음 반복을 따른다.
( $\boldsymbol{S}$ 가 가역 행렬(invertible)이라면, $\boldsymbol{x}_0 \neq \boldsymbol{0}$ 임을 보장하는 것으로 충분하다.)

$$ \boldsymbol{x}_{k+1} = \frac{\boldsymbol{S}\boldsymbol{x}_k}{\Vert \boldsymbol{S}\boldsymbol{x}_k\Vert }, \quad k = 0, 1, \dots \quad (10.52) $$

이는 벡터 $\boldsymbol{x}_k$ 가 매 반복마다 $\boldsymbol{S}$ 와 곱해진 후 정규화됨을 의미한다. 즉, 항상 $\Vert \boldsymbol{x}_k\Vert = 1$ 이다. 이 벡터 수열은 $\boldsymbol{S}$ 의 가장 큰 고윳값과 연관된 고유벡터로 수렴한다. 초기의 구글 페이지랭크(Google PageRank) 알고리즘(Page 등, 1999)은 하이퍼링크를 기반으로 웹 페이지의 순위를 매기기 위해 이러한 알고리즘을 사용한다.