t-SNE 의 개념 및 알고리즘 설명

t-SNE 의 개념 및 알고리즘 설명

/* DeepPlay 2022-09-11 */

 

t-SNE (t-distributed Stochastic Neighbor Embedding) 는 고차원 데이터를 저차원 데이터로 변환하는 차원 축소 (dimensionality reduction) 기법이며, 대표적이며, 좋은 성능을 보이는 기법이다. 

 

차원 축소을 하는 목적은 시각화, 클러스터링, 예측 모델의 일반화 성능 향상 등의 목적을 들 수 있다. t-SNE 의 경우, 고차원 공간상의 데이터 포인트들의 위치를 저차원 공간상에서의 극적으로 표현을 해주기 때문에 데이터에 존재할 수 있는 군집들을 시각화해서 표현해주는데 강점을 갖고, 시각화에 주로 사용된다. t-SNE 는 직접적으로 클러스터를 만들어서 레이블링까지 해주는 클러스터링 알고리즘은 아니다. 따라서 클러스터링에 직접적으로 활용되기 보다는 t-SNE 의 결과에 다시 k-means 와 같은 알고리즘을 적용하는 방식으로 클러스터링을 수행하기도 한다 (참고: https://www.quora.com/Can-TSNE-be-used-for-clustering). t-SNE 는 PCA 와 같이 저차원에서 요약된 변수에 의미가 있는 것은 아니다. (PCA 의 경우, 저차원 공간의 변수가 고차원 공간상의 변수들의 선형 결합이라는 의미가 있다.)

 

차원 축소의 3가지 카테고리

1) feature selection: univariate association test, ensemble feature selection, step-wise regression 등

2) matrix factorization: SVD (singluar vector decomposition)

3) neighbor graphs: t-sne, UMAP (Uniform Manifold Approximation and Projection) 등

 

우선, t-sne 는 비선형 차원 축소 (nonlinear dimensionality reduction) 기법이다. 따라서 아래와 같은 데이터에 대해서도 적용할 수 있다. 반면 PCA (principle component analysis) 와 같은 선형 차원 축소 방법의 경우 아래 데이터에 적용하여 유의미한 결과를 내기는 어렵다.

 

선형 차원 축소 기법으로 차원 축소가 어려운 형태의 데이터

 

t-SNE 알고리즘

 

sne, t-sne, UMAP 과 같은 차원 축소 방법은 아래의 공통된 절차를 수행한다.

원래 데이터가 있는 공간을 high dimension, 축소된 공간을 low dimension 이라고 하자. 

 

------------------------------------------------------------------------------------------------

1) high dimensional probabilities p 를 계산한다.
2) low dimensional probabilities q 를 계산한다.
3) 두 분포의 차이를 반영하는 cos function C(p,q) 를 정의한다. 
4) Cost function 이 최소화 되도록 저차원 공간상의 데이터를 변환한다. 

------------------------------------------------------------------------------------------------

 

대략적인 절차는 매우 심플하다. t-sne 에서는 각 절차를 실제로 어떻게 수행하는지 알아보자. 

 

1) high dimensional probabilities p 를 계산한다.

p_(i,j) 를 어떤 데이터 포인트 i,j의 similarity 를 반영하는 스코어라고 하자. 두 포인트가 가까이 위치할 수록 p_(i,j) 의 값은 커지게 된다. 그리고 i,j 의 euclidean distance 를 e_(i,j) 라고 하자. 다른 데이터들에 대해서도 서로의 eucliean distance 를 계산할 수가 있고, 그 값들이 어떤 분포 g 를 따른다고 가정하자. p_(i,j) 는 그 분포상에서의 likelihood 라고 할 수 있는, g(e(i,j)) 로 정의해보자. 

예를 들어 설명하면, 위 두 데이터 포인트를 각각 (2,9) 와 (3,10) 이라고 하자. e= sqrt((3-2)^2 + (10-9)^2)=sqrt(2) = 1.41 이다. 

 

t-sne 에서 사용하는 g 확률 분포는 아래와 같다.

 

$$ g(x) = exp(-x^2 / 2\sigma_i^2) $$ 

$$ g(e(i,j)) = exp(-||x_i-x_j||^2 / 2\sigma_i^2) $$ 

 

모든 g 값의 합이 1이 되도록 아래 식으로 변환한다. 

 

$$ p_{j|i} = \frac{exp(-||x_i-x_j||^2 / 2\sigma_i^2)}{\sum_{k \neq l} exp(-||x_k-x_l||^2 / 2\sigma_i^2)} $$

 

그러면, p(j|i) 의 값이 p(i|j) 의 값은 다른데, 최종적으로 두 값의 평균을 취하고, 마찬가지로 모든 값의 합이 1이 되도록 하기 위하여 최종적인 i,j 의 similarity score p(i,j) 를 아래와 같이 계산한다 (N은 계산 가능한 쌍의 수). 이러면, p 를 이산확률분포처럼 다룰 수 있게 된다. 

 

$$ p_{i,j} = \frac{p(j|i) + p(i|j)}{2N} $$

 

2) low dimensional probabilities q 를 계산한다.

마찬가지의 방법으로 q(i,j) 를 다음과 같이 구한다. 

 

$$ q_{j|i} = \frac{(1+||y_i - y_j||^2)^{-1})}{\sum_{k \neq l} (1+||y_k - y_l||^2)^{-1})  } $$ 

$$ q_{i,j} = \frac{q(j|i) + q(i|j)}{2N} $$ 

 

σ 는 어떻게 정해지는가?

이를 위해하기 위해 우선, entropy 와 perplexity 라는 개념에 대한 설명이 필요하다. perplexity = 2^entropy 로 정의되며, entropy 는 '어떠한 확률 분포에 대하여, 관측값을 예측하기 어려운 정도' 를 의미하는 수치이다. 어떤 분포 q 에대한 entropy 는 아래와 같다. 

 

$$ H(q) = -\sum_{c=1}^{C} q(y_c)log(q(y_c)) $$ 

 

entropy 를 설명하기 위해, 빨간공과 녹색공이 20:80 으로 들어 있는 가방에서 1개의 공을 꺼내서 관찰 값을 확인하는 이산 확률 분포를 예로 들어보자. 그 확률 분포 q의 entropy 는 H(q)=-(0.2log(0.2)+0.8log(0.8))=0.5 이다. 그리고, perplexity = 2^0.5 = 1.41 이다. 

 

perplexity 값에 따라 t-SNE 의 결과가 민감하게 반응하기 때문에 perplexity 는 중요한 파라미터이다. 보통 t-SNE 는 입력받은 perplexity 를 맞추는 σ 를 찾기 위하여 binary search 를 수행한다. 일반적으로 perplexity 를 조정하면서 시각화를 해보고, 가장 군집을 잘 보여주는 값을 최종적으로 선정하는 방법을 택한다. 

 

왜 p, q 분포는 위와 같이 정해지는가?

p분포는 정규 분포와 유사하며, q분포는 t분포와 유사한 형태를 띈다. q 분포의 경우, p 분포 대비 빠르게 하락하고, 꼬리가 두터운 형태의 분포를 갖는다.  q분포를 썼을 때의 효과는 한 점에 데이터가 뭉치는 crowding problem 을 완화시킨다는데 있다. 따라서, 시각화시 저차원 공간상에서 너무 한 점에 뭉치지 않도록 하는 효과가 있기 때문에 p 분포를 썼을 때보다 이점이 있다. (이는 개인적인 이해를 위한 해석이며, 이와 관련한 좀 더 디테일한 설명은 original paper 를 참고) 

 

구현 레벨에서의 최적화

t-SNE 는 데이터가 커질수록 연산량이 기하급수적으로 늘어나는 O(n^2) 의 시간 복잡도를 갖는다. 실제 구현 레벨에서는 Barnes hut t-SNE 라는 방법을 통해 더 계산 효율적인 구현 방식을 택한다. scikit-learn 의 t-sne 구현체는 이 방식을 활용한다.

 

t-SNE 의 optimization

t-SNE 에서의 optimization 이란 고차원 공간상에서의 p분포 (high dimensional probabilities p) 와 저차원 공간상의 q분포 (low dimensional probabilities q ) 의 차이를 줄이는 것이다. 이 때, cost function 을 정의하고, 이를 최소화하는 방식으로 optimization 이 수행된다. 

 

3) 두 분포의 차이를 반영하는 cos function C(p,q) 를 정의한다. 

cost function C(p,q) 로는 Kullback-Leibler divergence 를 사용한다. p,q는 이산확률분포이고, KL divergence의 식에 적용하면 cost 를 실제로 구해볼 수도 있다. 

 

4) Cost function 이 최소화 되도록 저차원 공간상의 데이터를 변환한다. 

KL divergence 을 최소화 시키는 저차원 공간상의 데이터의 위치를 gradient optimization 방식을 통해 구할 수 있다. 설명하자면, 결국 저차원 공간상에 랜덤하게 뿌려진 데이터 포인트들이 각각 어떤 방향으로 가야지 cost function 을 줄일 수 있을지 알아야 하는 것인데, 이는 cost function 을 미분한 뒤에 각 데이터 포인트 별로 gradient 를 구함으로써 알 수 있다. 

 

참고자료

• https://arize.com/blog/t-sne-vs-umap/
• https://towardsdatascience.com/t-sne-clearly-explained-d84c537f53a
• https://distill.pub/2016/misread-tsne/
• https://towardsdatascience.com/t-sne-machine-learning-algorithm-a-great-tool-for-dimensionality-reduction-in-python-ec01552f1a1e
• https://lovit.github.io/nlp/representation/2018/09/28/tsne/
• https://towardsdatascience.com/t-sne-python-example-1ded9953f26