Notes/Machine Learning

차원 축소화 알고리즘 t-SNE, PCA

muliphen 2021. 4. 10. 23:53

차원 축소에 많이 쓰이는 t-SNE(Stocahstic Neighbor Embedding)과 PCA(Principle Component Analysis)에 대해서 알아보고 비교를 해보려고 한다.

t-SNE

t-distributed stochastic neighbor embedding (t-SNE)란?

  • t 분포를 활용해 고차원의 원공간에 존재하는 data xx의 neighbor간의 distance를 최대한 보존하며 대응되는 저차원의 yy를 학습하는 방법론
  • dimensionality reduction과 visualization에 많이 쓰이는 고차원 data 시각화 하는데에 인기가 많은 알고리즘

Stochastic neighbor embedding (SNE)

sne에 stochastic 이 붙는 이유는 거리정보를 확률적으로 나타내기 때문인데 일단 수식은 아래와 같다.

pj∣i=e−∣xi−xj∣22σi2Σke−∣xi−xk∣22σi2p_=\frac}}{\Sigma_k e^{-\frac{|x_i-x_k|^2}}}
qj∣i=e−∣yi−yj∣2Σke−∣yi−yk∣2q_=\frac}{\Sigma_k e^{-|y_i-y_k|^2}}

pp는 xix_i가 주어졌을때 본래 차원에서의 상대적인 거리를 이용해 xjx_j가 xix_i의 이웃으로 선택될 확률을 나타내고 qq는 yiy_i가 주어졌을때 축소된 차원에서의 상대적인 거리를 이용해 yjy_j가 yiy_i가 이웃으로 선택될 확률을 나타낸다. 그래서 SNE의 목적은 pp와 qq의 분포 차이를 최소화 하여 원래 차원에서와 축소된 차원에서의 이웃으로 뽑힐 확률을 같게 만드는 것이다.

두 확률 분포를 같게 만들기 위해서 두 확률 분포의 유사도를 측정하는 분포인 Kullback-Leibler Divergence를 cost function으로 사용해서 이를 최소화 하는 방향으로 학습을 진행한다. KL Divergence식과 gradient는 다음과 같다.

∑iKL(Pi∣∣Qi)=∑i∑jpj∣ilog⁡pj∣iqj∣i\sum_KL(P_i||Q_i)=\sum_i\sum_jp_\log\frac}}

여기서 SNE의 속도를 높이기 위해 몇가지 트릭들이 존재했는데

  • 개체의 데이터 밀도를 보정하기 위한 σi\sigma_i는 고정된 값을 사용해도 성능에 큰 영향이 없어서 고정값을 사용
  • ii가 주어졌을때 jj가 이웃으로 선택될 확률 = jj가 주어졌을때 ii가 이웃으로 선택될 확률 이라 가정해도 성능에 큰 영향이 없었다. 따라서 다음과 같이 사용 pi∣j=pj∣i+pi∣j2,qi∣j=qj∣i+qi∣j2p_=\frac+p_}, q_=\frac+q_}

위의 트릭을 적용해 새로 cost function을 정의하면 다음과 같다.

∑iKL(Pi∣∣Qi)=∑i∑jpijlog⁡pijqij∂C∂yi=4∑j(yj−yi)(pij−qij)\sum_i KL(P_i||Q_i)=\sum_i\sum_jp_\log\frac}} \\ \frac{\partial C}{\partial y_i}=4\sum_j(y_j-y_i)(p_-q_)

최종적으로 구하고자 하는 값은 축소된 차원에 embedding된 값 yiy_i이고 random initialize 이후에 gradient descent를 이용해 이 값을 업데이트 한다.

Crowding Problem과 t-SNE

sne는 gaussian distribution을 전제로 해서 확률을 계산하는데 gaussian distribution은 분포가 sharp해서 적당히 떨어져있는 이웃 jj와 아주 멀리 있는 이웃 kk가 선택될 확률의 차이가 크게 안 나게 된다. 이 문제를 crowding problem이라고 하는데 이를 해결하기 위해서 gaussian 보다 덜 sharp한 Student's t-distribution에서 ν=1\nu=1인 special case를 사용한것이 t-SNE라고 한다. t-SNE에서는 qijq_에만 이 distribution을 적용하고 pijp_는 기존 SNE와 같은 식을 사용한다. Student's t-distribution과 qijq_의 식은 다음과 같다.

f(t)=Γ(ν+12)νπΓ(ν2)(1+t2ν)−ν+12,f(t)=1π(1+t2)(case: ν=1)qij=(1+∣yi−yj∣2)−1∑k≠l(1+∣yk−yl∣2)−1f(t)= \frac{\Gamma(\frac{\nu+1})}{\sqrt{\nu\pi}\Gamma(\frac{\nu})}(1+\frac{\nu})^{-\frac{\nu+1}}, f(t)=\frac{\pi(1+t^2)}(case: \ \nu=1) \\ q_=\frac{(1+|y_i-y_j|^2)^{-1}}{\sum_(1+|y_k-y_l|^2)^{-1}}

PCA

Principal Component Analysis(PCA)란?

  • 데이터의 variance를 최대한 보존할 수 있는 orthogonal한 basis들을 찾는 방법
  • Dimensionality reduction과 Feature extraction에 많이 쓰임

Method 1 (PCA의 목적을 보여주는 naive한 방법)

  1. n차원의 data들의 center를 origin으로 삼아 모든 data와의 거리를 최소화하거나 origin으로부터 line위에 projection된 data까지의 거리를 최대화하면서 이 origin을 가로지르는 line의 방향벡터가 주성분(PC1)벡터 된다. (여기서 최소화와 최대화 문제는 피타고라스 정리를 생각해보면 같은 문제이다.)
  1. PC1에 orthogonal하면서 origin을 지나는 n-1 차원의 hyperplane위에 data들을 projection하고 n-1차원 상에서 data들에 대해 1을 과정을 다시 진행하여 PC2를 구한다.
  1. 2를 계속 반복하여 PCn까지 구한다. 이렇게 하면 총 n개의 basis를 구하게 되고 PC1~PCn순으로 데이터들의 variance를 잘 보존하는 성분들이 된다.

Usage

  • Feature Extraction: 기존 data를 PCA를 통해 구한 basis들에 projection하여 새로운 linear combination을 만드는 linear transform이 일종의 feature extraction 역할을 하게 된다.
  • Dimension reduction: high dimension data의 visualization을 위해 2D plane 상에서 data들의 분포를 실제와 유사하게 나타내고 싶다면 PC1과 PC2에 대해 data들을 projection하게 되면 가장 variance를 잘 나타내는 2개의 basis상에서의 data들의 분포를 나타내게 되므로 어느 정도는 잘 표현할 수 있을 것이라 기대해 볼 수 있다.

PCA의 목적과 solution

PCA의 주목적은 원래 data의 variance를 최대한 보존을 하는 것이 목표이기 때문에 projection or transform 된 후의 variance가 최대화 되어야 한다. 원래 data를 XX, PCA를 통해 변환된 data를 ZZ라 하고 XX의 covariance matrix를 Σ\Sigma라고 하면 다음과 같은 식을 유도할 수 있다.

max⁡α{Var(Z)}=max⁡α{Var(αTX)}=max⁡α{αTΣα}\max_{\alpha}\=\max_{\alpha}\ = \max_{\alpha}\{\alpha^T\Sigma\alpha\}

여기서 ∣∣α∣∣=1||\alpha||=1 이다. 이를 lagrangian problem으로 변형하면 다음과 같아진다.

L=αTΣα−λ(αTα−1)L = \alpha^T\Sigma\alpha-\lambda(\alpha^T\alpha-1)

maximization problem을 풀면 다음과 같아진다.

∂L∂α=(Σ−λ)α=0\frac{\partial L}{\partial\alpha}=(\Sigma-\lambda)\alpha=0

여기서 α\alpha가 Σ\Sigma의 eigenvector가 됨을 알 수가 있고 이 α\alpha가 PCA가 된다.

그리고 여기서 maximum eigenvalue를 λ1\lambda_1, corresponding eigenvector를 α1\alpha_1이라 하면 변환된 data ZZ에서

z1=α1XVar(z1)=α1TΣα1z_1=\alpha_1 X \\ Var(z_1)=\alpha_1^T\Sigma\alpha_1

이고 Σα1=λ1α1\Sigma\alpha_1=\lambda_1\alpha_1이므로 Var(z1)=λ1Var(z_1)=\lambda_1이 된다. 즉, 변환된 data의 z1z_1축의 variance는 λ1\lambda_1이 되는 셈이고 다른 축 ziz_i에 대해서도 variance가 λi\lambda_i가 된다. 따라서 ∑iλi=\sum_\lambda_i= 원래 data XX의 variance가 된다.

- 참고

t-SNE: https://ratsgo.github.io/machine learning/2017/04/28/tSNE/

PCA: https://ratsgo.github.io/machine learning/2017/04/24/PCA/

Uploaded by Notion2Tistory v1.1.0