MML chap.10 을 참고함
Introduction
- 차원을 왜 축소하는가?
- 축소하지 않으면 용량이 너무 큼
- 분석과 해석, 시각화가 어려움
- 어떻게 축소하는가?
- 고차원의 데이터는 보통 overcomplete
- 중요하지 않은 차원이 많고 차원들끼리 correlated
- 이런 걸 제거하는, 일종의 노이즈 제거로 볼 수도 있음 - bottleneck
- instrinsic lower-dimensional structure, compact representation of data
- KLT, jpeg, mp3 등
- 알아두면 좋은 것
- eigen-, change of basis, coordinate, projection
- contrainted optimization
Problem setting
- i.i.d dataset $\mathcal X=\{\boldsymbol x_1, \cdots, \boldsymbol x_N\}, \ \boldsymbol x \in \mathbb R^D$. 평균은 $\boldsymbol 0$ 이라고 생각
- \[\text{covariance matrix: }\ S=\frac{1}{N}\sum_{n=1}^N \boldsymbol x_n\boldsymbol x_n^\intercal\]
- low dimensional compressed representation of $\boldsymbol x_n$
- \[\boldsymbol z_n = B^\intercal \boldsymbol x_n \in \mathbb R^M\]
- 이때 $B$는 다음과 같다.
-
\[\boldsymbol B := [\boldsymbol b_1, \cdots, \boldsymbol b_M], \ \mathbb R^{D \times M}\]
- $\boldsymbol B$ 의 각 column 들은 orthonormal 하다고 가정한다
- 이때, $\boldsymbol B$ 의 각 column 들은, $\boldsymbol{\tilde x} = \boldsymbol B \boldsymbol B^\intercal \boldsymbol x \in \mathbb R^D$ 가 있는 $M$-dimensional subspace 의 basis 를 이룬다.
- $M$-dimensional subspace $U \subseteq \mathbb R^D, \ \text{dim}(U) = M < D$
-
\[\boldsymbol z = \boldsymbol B^\intercal \boldsymbol x \\
\boldsymbol{\tilde x} = \boldsymbol B \boldsymbol z\]
- 이때, $\boldsymbol B$ 를 decoder, $\boldsymbol B^\intercal$ 를 encoder 라고 볼 수도 있다
-
\[\boldsymbol B := [\boldsymbol b_1, \cdots, \boldsymbol b_M], \ \mathbb R^{D \times M}\]
Maximum Variance Perspective
- ‘데이터의 정보’ 라는 것을 ‘space filling’ 으로 해석한다면, 정보는 곧 그 데이터가 퍼진 정도를 의미할 것이다
- 그리고 variance 는 데이터의 퍼짐을 잘 나타낸다.
- 따라서, PCA 를 low-dimensional representation of data 의 variance 를 최대화하는 차원 축소 알고리즘이라 볼 수 있다.
- 먼저 앞서 서술한 것처럼 평균을 $\boldsymbol 0$ 이라고 가정한다.
- 평균이 $\boldsymbol 0$ 이어도 variance 는 영향을 받지 않음
- \[\mathbb V_z[z] = \mathbb V_x[\boldsymbol B^\intercal(\boldsymbol x - \boldsymbol \mu)] = \mathbb V_x[\boldsymbol B^\intercal\boldsymbol x - \boldsymbol B^\intercal \boldsymbol \mu] = \mathbb V_x[\boldsymbol B^\intercal\boldsymbol x]\]
- 평균이 $\boldsymbol 0$ 이어도 variance 는 영향을 받지 않음
- 먼저 variance 를 최대화시키는 $\boldsymbol b_1 \in \mathbb R^D$ 를 구해야 한다 -> first coordinate $z_1$ 의 variance 를 최대화시키는!!
- \[V_1 := \mathbb V[z_1] = \frac{1}{N}\sum_{n=1}^N z^2_{1n}\]
- 를 maximize!
- 이때 $z_{1n}$ 은 다음과 같다. $z_{1n} = \boldsymbol b_1^\intercal \boldsymbol x_n$
- $z_{1n}$ 은 $\boldsymbol x_n$ 을 $\boldsymbol b_1$ 이 span 하는 subspace 로 정사영내렸을 때, 그 subspace 에서의 coordinate 를 의미한다.
- 여기서 coordinate 라는 개념이 헷갈린다면 찾아보고 오는 것이 좋다.
원래 처음에 엄청 헷갈리는 개념이다. 나중에 관련해서 한 번 글을 써봐야겠다.
- 여기서 coordinate 라는 개념이 헷갈린다면 찾아보고 오는 것이 좋다.
- $z_{1n}$ 은 $\boldsymbol x_n$ 을 $\boldsymbol b_1$ 이 span 하는 subspace 로 정사영내렸을 때, 그 subspace 에서의 coordinate 를 의미한다.
- 식 전개를 계속해보자.
-
\[V_1 = \frac{1}{N}\sum_{n=1}^N (\boldsymbol b_1^\intercal \boldsymbol x_n)^2 = \frac{1}{N}\sum_{n=1}^N \boldsymbol b_1^\intercal \boldsymbol x_n \boldsymbol x_n^\intercal \boldsymbol b_1 \\
= \boldsymbol b_1^\intercal \left(\sum_{n=1}^N \boldsymbol x_n \boldsymbol x_n^\intercal \right) \boldsymbol b_1 = \boldsymbol b_1^\intercal\boldsymbol S\boldsymbol b_1\]
- 이때 $\boldsymbol S$ 는 공분산 행렬이다.
- 그럼, 우리가 풀어야 할 문제는 다음과 같다.
- \[\max_{b_1} \ \boldsymbol b_1^\intercal \boldsymbol S \boldsymbol b_1 \\ \text{subject to } ||\boldsymbol b_1||^2 = 1\]
- 라그랑주 승수법을 통해
- \[\mathfrak L(\boldsymbol b_1, \lambda) = \boldsymbol b_1^\intercal \boldsymbol S \boldsymbol b_1 + \lambda_1(1-\boldsymbol b_1^\intercal \boldsymbol b_1)\]
- \[\frac{\partial \mathfrak L}{\partial \boldsymbol b_1} = 2\boldsymbol b_1^\intercal \boldsymbol S - 2\lambda_1 \boldsymbol b_1^\intercal, \\ \frac{\partial \mathfrak L}{\partial \lambda_1} = 1 - \boldsymbol b_1^\intercal \boldsymbol b_1\]
- 각 partial derivatives 를 $\boldsymbol 0$ 이라고 두고 풀면,
- \[\boldsymbol S \boldsymbol b_1 = \lambda_1 \boldsymbol b_1, \\ \boldsymbol b_1^\intercal \boldsymbol b_1 = 1\]
- 따라서, $\boldsymbol b_1$ 은 data covariance matrix $\boldsymbol S$ 의 고유벡터이고 $\lambda_1$ 은 그에 대응하는 고유값이다.
- 그리고 이때
- \[V_1 = \boldsymbol b_1^\intercal\boldsymbol S\boldsymbol b_1 = \lambda_1\boldsymbol b_1^\intercal\boldsymbol b_1 = \lambda_1\]
- 그러니까, $\boldsymbol b_1$ 이 span 하는 1차원 부분공간에 project 된 데이터의 variance 는 그 $\boldsymbol b_1$ 의 고유값과 같다.
- 따라서 $V_1$ 을 maximize 하기 위해선 $S$ 의 가장 큰 고유값을 가지는 고유벡터를 $\boldsymbol b_1$ 으로 사용하면 되고, 이 고유벡터를 first principal component 라고 한다.
아래부턴 추가 예정
$M$-dimensional Subspace with Maximal Variance
- 1차원을 M 차원으로 확장한 것이고, sequential 하게 구하면 됩니다. pc1 을 구하고, pc2 를 구하고.. 이런 식으로요. -
- 이후 다른 해석도 추가할 예정 - reconstruction error minimize 의 측면
In practice
first draft: 2023.03.01 19:42