[Machine Learning] Dimensionality Reduction(PCA)

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

 

[Data Compression]

엄청 많은 feature가 있는 training set이 있다고 하자. 그리고 그 중에서 아래와 같이 cm와 inch의 feature만을 뽑아서 그래프로 나타내보았다. 

이와 같이 cm와 inch는 길이에 대한 feature이며, 두 feature가 연관성이 높다고 볼 수 있다. 우리는 2차원의 data를 1차원으로 줄여서 합칠 수 있다. 

이렇게 차원을 줄이면 data의 양이 감소해서 사용되는 메모리를 절약할 수 있으며 학습 알고리즘의 속도를 높여준다.

 

3차원에서 2차원으로 감소하는 것은 위와 같다. feature $x_1, x_2, x_3$을 2차원의 평면에 투영해서 feature $z_1, z_2$로 감소하였다.

 

[Data Visualization]

우리가 만약 50개, 즉, 50차원의 feature가 있다면 어떻게 이 특성을 visualizing 할 수 있을까?

데이터의 차원이 3차원이 넘으면 시각적으로 표시하기 어렵고, 고차원 데이터를 2차원 또는 3차원으로 감소시켜서 시각화하여야 한다.

여기서는 $x^{(i)} \in \mathbb{R}^{50}$에서 $z^{(i)} \in \mathbb{R}^2$로 차원을 축소하였다. 이렇게 차원을 축소하면 아래 그래프와 같이 시각적으로 쉽게 표현되며, 우리는 기존 feature를 효과적으로 요약해주는 새로운 feature $z_1, z_2, z_3$를 찾으면 된다.

 

- Principal Component Analysis(PCA)

차원 축소에 가장 널리 사용되는 알고리즘은 Principal Component Analysis(PCA) : 주성분분석이다.

 

2차원에서 1차원으로 줄이는 예제를 한번 살펴보자. PCA에서는 우선 projection(투영)하기 좋은 line을 찾아야 한다. 

projection하기 좋은 line은 projection error가 가장 작도록하는 line을 선택하면 된다.

만약 우리가 위 그래프에서 빨간색 line을 선택했다면, projection error는 빨간색 line에서 sample들의 거리의 합이 될 것이다. 만약 분홍색 line을 선택했다면 projection error의 크기가 커지기 때문에 적절하지 않다고 볼 수 있다.

요약하면 아래와 같다.

만약 2차원에서 1차원으로 감소하는 문제가 있다면, 우리는 projection error를 최소로 만드는 하나의 벡터($u^{(1)}$)를 찾으면 된다.

확장해서 n차원에서 k차원으로 감소하는 문제가 있다면, 우리는 projection error를 최소로 만드는 k개의 벡터($u^{(1)}, u^{(2)}, ..., u^{(k)}$)를 찾는다. 

 

PCA는 Linear Regression과 유사하게 보이지만 전혀 다르다.

왼쪽 : Linear Regression, 오른쪽 : PCA

Linear Regression은 각 sample data와 line 사이의 square error(vertical distance)를 최소화하는 것이고, y를 예측하기 위한 함수이다.

PCA는 각 sample data와 line 사이의 shortest orthogonal distance를 최소화하며, y와는 전혀 관계없다.

 

[PCA Algorithm]

PCA 알고리즘을 적용하기 전에 우선 Data preprocessing이 필요하다.

첫 번째로 mean normalization을 해서 $\mu_j$를 구한 후에, 각 $x_j^{(i)}$를 $x_j - u_j$로 변경한다.

두 번째는 feature scaling이며, $x_j^{(i)} \leftarrow \frac{x_j^{(i)} - \mu_j}{s_j}$로 범위를 scaling 한다. $s_j$는 standard deviation(표준편차)이다.

 

PCA 알고리즘에서 우리는 벡터 $u^{(i)}$와 새로운 feature $z^{(i)}$ 구해야 한다. 

우리는 이 두 가지를 구하기 위해서 아래와 같은 방법을 사용한다.

1. 아래의 식으로 covariance matrix(공분산행렬)을 계산한다. 여기서 $\Sigma$는 summation $\sum$이 아니라 matrix를 의미하며, 만약 feature $x \in \mathbb{R}^n$이라면 covariance matrix는 n x n 행렬이 된다.

$$\Sigma = \frac{1}{m}\sum_{i = 1}{n}(x^{(i)})(x^{(i)})^T$$

2. 1번에서구한 covariance matrix의 eigenvectors를 계산한다.

(여기서는 단순히 Octave의 라이브러리를 사용해서 구한다고 설명한다. 다음에 PCA를 다시 한번 살펴보면서 정리가 필요할 것 같다...)

Octave에서 사용하는 방법은 아래와 같다.

[U, S, V] = svd(Sigma);

여기서 Sigma는 n x n의 covariance matrix이다.

이 식을 통해서 우리는 n x n의 $U$ matrix를 구할 수 있고, $U$ matrix의 1에서 k번째 열까지가 우리에게 필요한 matrix이다.

3. 2번에서 구한 $U$ matrix에서 1 ~ k열까지를 취하고, $z$를 계산한다. $z$는 아래와 같이 Ureduce(k번째 열까지 취한 $U$ matrix)를 Transform해서 $x$의 곱으로 구한다. 결국 $z$는 k차원의 vector가 된다.

 

요약하면 아래와 같다.

 

- Applying PCA

[Reconstruction from Compressed Representation]

위에서 우리는 n-차원에서 k-차원으로 축소하는 것을 배웠는데, 다시 k-차원에서 n-차원으로 어떻게 돌아갈 수 있을까?

$z$를 구할 때의 식에서 $U_{reduce}$ matrix를 곱해준다. 

$$X_{approx} = U_{reduce}z$$

여기서 구해지는 값은 완벽하게 동일한 x값이 아니라 근사값이다. 즉, 완벽하게 원상태로는 돌아갈 수 없다.

만약 $X_{approx}^{(1)}$을 구하고 싶으면, $U_{reduce}z^{(1)}$을 구해주면 된다.

 

[Choosing the number of principal components]

이번에 알아볼 내용은 우리가 축소하길 원하는 차원 k(number of principal components)를 어떻게 정할 수 있느냐에 관한 것이다. 

우리는 아래와 같은 concept로 k의 값을 선택할 것이다.

1. Average squeared projection error: $\frac{1}{m}\sum_{i = 1}^{m}\left\| x^{(i)} - x_{approx}^{(i)} \right\|^2$

projection error의 제곱 평균을 구한다.

2. Total variation in the data: $\frac{1}{m}\sum_{i = 1}^{m}\left\| x^{(i)} \right\|^2$

분산을 구한다.

3. 다음 식을 만족하는 가장 작은 k값을 선택한다. 

$\begin{matrix} \frac{\frac{1}{m}\sum_{i = 1}^{m}\left\| x^{(i)} - x_{approx}^{(i)}\right\|^2}{\frac{1}{m}\sum_{i = 1}^{m}\left\|x^{(I)}\right\|^2} \leq 0.01  & (1\%) \end{matrix}$

위의 조건을 만족할 때, variance의 99%가 보존된다고 한다. 필요에 따라서 0.01이 아닌 0.05, 0.10 등 다른 값을 사용할 수 있고, 그때 보존되는 variance는 95%, 90%가 된다.

 

그래서 우리는 k를 점차 늘려가면서 위 알고리즘을 수행하면서 3번식의 값이 0.01보다 작은지 확인하는 방법(왼쪽)을 사용할 수 있다. 그러나 이것은 비효율적이고, 행렬 연산을 사용(오른쪽)하면 효율적으로 수행할 수 있게 된다.

오른쪽 방법처럼 SVD(Singular Value Decomposition)을 사용하면 효율적으로 k를 구할 수 있다.

먼저 covariance matrix Sigma를 구하고, Sigma에 대해서 SVD를 적용한다.([U, S, V] = svd(Sigma))

이때, $S$ matrix를 사용하면 retained variance가 99% 이상이 되는지 확인하는 과정을 쉽게 수행할 수 있다.

$S$ matrix는 다음과 같이 나타난다.

$\begin{matrix} S = \begin{bmatrix} S_{11} &  & 0 \\  & \vdots & \\ 0 & & S_{nn} \end{bmatrix} & ,S \in \mathbb{R}^{n \times n} \end{matrix}$

그리고 위 알고리즘에서 3번식은 다음 부등식으로 바꾸어서, 아래 부등식을 만족하는 가장 작은 k를 찾는다.

$1 - \frac{\sum_{i = 1}^{k}S_{ii}}{\sum_{i = 1}^{n}S_{ii}} \leq 0.01 \rightarrow \frac{\sum_{i = 1}^{k}S_{ii}}{\sum_{i = 1}^{n}S_{ii}} \geq 0.99$

 

[Advice for Applying PCA]

어떻게 우리가 PCA를 사용해서 학습 알고리즘의 속도를 높히는지 살펴보자.

Supervised Learning Problem에서 input $x$와 label $y$로 이루어진 training example이 있을 때, 이 input의 feature dimension이 10000인 경우를 보자. 만약 vision problem을 처리하기 위해서 100px x 100px image를 사용할 때, 10000pixel이 feature가 되고, 이런 경우에는 학습 알고리즘의 속도는 매우 느릴 수 밖에 없을 것이다.

이 때, 우리는 PCA를 사용해서 위와 같이 feature의 차원을 1000으로 축소하면 학습 알고리즘의 속도는 훨씬 빨라질 것이다. $x$에 대해서 $U_{reduce}$를 사용해서 $z$의 새로운 feature를 얻는다.

주의해야 것은 PCA는 Training Set에 대해서만 해야하며, 이후에 Training Set에서 적용한 Mapping을 CV Set이나 Test Set에 적용해야 한다.($U_{reduce}$를 구하는데에 training set만 사용해서 구하고, 이렇게 구한 $U_{reduce}$를 사용해서 $z_{cv}, z_{test}$를 구하라는 의미인 것 같다)

 

PCA를 적용함으로써 다음과 같은 이점을 얻을 수 있다.

1. 압축

- 저장되는 data의 memory/disk 감소

- 학습 알고리즘 속도 증가

2. 시각화

- k = 2 or k = 3으로 차원을 낮추어서 시각적으로 확인하기 용이해짐

 

Bad use of PCA : To prevent overfitting

PCA를 사용하면 feature dimension이 줄어들기 때문에 overfitting을 피하는데에도 사용할 수 있을 것 같지만, overfitting 문제를 해결하려고 PCA를 사용하는 것은 좋지 않다. PCA는 정보의 양을 감소시키고, 특히 예측값에 상관없이 차원을 축소하기 때문에 꼭 필요한 정보를 잃을 수도 있다. 

따라서, overfitting 문제를 해결하려면 regularzation을 사용하는 것이 권장된다.

- Regularization

$$\underset{\theta}{min}\frac{1}{2}\sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2 + \frac{\lambda}{2m}\sum_{j = 1}^{n}\theta_j^2$$

 

 

때때로 많은 사람들이 위와 같은 절차로 Machine Learning 시스템을 디자인한다. 

하지만, PCA 없이 original/raw data로 ML을 학습하고, 원하는데로 동작을 하지 않는다면 그때 PCA를 고려하는 것이 더 좋은 방법이다.