[데이터분석] t-SNE

 

t-SNE는 PCA와 UMAP과 더불어 고차원 데이터를 시각화할 때 많이 사용하는 방법이다.

 

이 글은 Journal of Machine Learning Research에 실린 Visualizing Data using t-SNE 논문을 정리한 것이다. (검색하기 쉽게 복사 가능한 코드 블럭에 인용을 넣어놓는다)

van der Maaten, L. & Hinton, G. Visualizing data using t-SNE. Journal of Machine Learning Research 9, 2579–2605 (2008).

 

 

1. Dimensionality reduction

 

Dimensionality reduction 문제 : high-dimensional data set $X=\left\{ x_1,x_2,\ldots,x_n \right\}$를 two or three-dimensional data $Y=\{y_1,y_2,\ldots,y_n\}$으로 변환하는 것을 dimensionality reduction이라고 한다.

 

Principal Components Analysis (PCA)

Classicial multidimensional scaling (MDS)

이 두 방법이 대표적인 Linear technique다. 이 방법은 비슷하지 않은 데이터 포인트들의 저차원 표현을 멀리 떨어뜨려놓는 데에 집중한다.

 

그러나 nonlinear manifold에 있는 고차원 데이터들의 경우, 비슷한 데이터일지라도 linear mapping으로 저차원으로 변환할 때 해당하는 데이터포인트들이 가까이 있게 할 수 없다고 한다. 

 

그래서 제안된 nonlinear dimensionality reduction은 다음과 같다.

 

1. Sammon mapping

2. Curvilinear components analysis

3. Stochastic Neighbor Embedding (SNE)

4. Isomap

5. Maximum Variance Unfolding (MVU)

6. Locally Linear Embedding (LLE)

7. Laplacian Eigenmaps

 

 

이 논문에서는 당연히 새로운 방법인 t-SNE를 소개한다. 이 방법과 위의 일곱 가지 방법들과도 비교한다. 

In this paper, we describe a way of converting a high-dimensional data set into a matrix of pairwise similarities and we introduce a new technique, called “t-SNE”, for visualizing the resulting similarity data. t-SNE is capable of capturing much of the local structure of the high-dimensional data very well, while also revealing global structure such as the presence of clusters at several scales.

 

 

위의 방법들에서 눈치챘을 수도 있는데 3번 방법이 SNE고 제시한 방법은 t-SNE다. (그리고 저자도 같다.) 즉, SNE 방법을 먼저 설명하고 여기서 더 발전된 형태가 t-SNE 라고 할 수 있다.

 

 

2. Stochastic Neighbor Embedding (SNE)

 

데이터 $x_i$에 대한 $x_j$의s similarity를 conditional probability로 표현해서 정의한다.

 

또한 우리가 변환한 저차원 데이터 $y_i$와 $y_j$에 대해서도 다음과 같이 conditional probability $q_{j|i}$를 정의한다.

 

우리가 만들 mapping은 오리지널 데이터인 $x_i,x_j$의 similarity를 보존하고 싶기 때문에 다음과 같은 Kullback-Leibler divergences를 모든 데이터 포인트에 대해 합산한 값을 최소화하고자 한다. 즉, $p_{j|i}$와 $q_{j|i}$ 분포를 동일하게 만들고 싶은 것이다.

 

 

문제는 이 KL divergence가 symmetry가 아니기 때문에 데이터에 따라 가중치가 달라지게 된다.

예를 들면 원래는 굉장히 가까운 데이터인데 멀리 떨어지게 mapping된 포인트들은 훨씬 큰 cost 값을 갖고, 원래는 멀리 있는 데이터는 mapping된 포인트가 가까운 경우에는 작은 cost를 갖게 된다. 즉, 원래 가까운 데이터들을 mapping에서도 가깝게 있도록 하는 데에 집중된 목적 함수라고 볼 수 있다. (그래서 저자는 local structure of the data in the map을 retain하는 데에 집중한다고 설명)

 

 

다음과 같이 그래디언트를 구하면 이 값이 spring force와 비슷하다고 볼 수 있다. $y_i-y_j$가 힘의 방향이고 앞에 곱해진 값이 스프링계수 같은 것이다. $y_i$와 $y_j$ 사이의 스프링이 당기는지 미는지는 두 데이터 포인트의 similarities에 따라 결정된다.

 

최적화 관점에서는 다음과 같이 gradient 값과 모멘텀 $\alpha(t)$가 결합된 형태로 mapping points를 업데이트한다.

 

 

위 formulation에서 알 수 있듯이 $\sigma_i$값이 최적화에 영향을 주게 된다. 이러한 값들의 초이스가 결과값에 영향을 주기 때문에 저자는 시간을 아끼고 파라미터에 덜 민감한 알고리즘을 생각하게 된다.

 

 

3. t-Distributed Stochastic Neighbor Embedding

 

3.1. Symmetric SNE

conditional probability 대신 a single KL divergence between a joint probability distribution $P$와 $Q$를 사용하고자 한다.

 

pairwise similarity는 다음과 같이 정의된다.

 

그런데 이렇게 정의할 경우에 문제가 생길 수 있는 상황이 있다. $x_i$가 outlier일 경우에 p_{ij}가 너무 크게 나온다는 것이다. 그래서 $y_i$ 값이 cost function에 거의 영향을 주지 않게 된다. 그래서 

$$p_{ij}=\frac{p_{j|i}+p_{i|j}}{2}$$로 정의해서 문제를 해결하고자 하였다. 이러면 $\sum_j p_{ij}> 1/2n$이 보장된다.

 

그러나 이 방법은 asymmetric SNE에 비해 그렇게 크게 좋아지는 것은 아니다.

 

 

다음 수식을 이용해서 $y_i$를 업데이트할 수 있다.

 

3.2 The Crowding Problem

 

그러나 저자는 다음 문제를 제기한다. Dimensionality mismatch문제이다. 우리가 10차원에서 2차원으로 압축한다고 하자. 10차원에서 11 equidistant point가 존재한다. 그러나 2차원에서는 이를 모두 표현할 수 없다. 따라서 SNE는 원래 차원에서 적당히 떨어진 두 점이 저차원에서 너무 멀리 떨어져있게 되는 상황에서 그 작은 거리를 모사하기 위해 너무 크게 저차원에서 잡아당기는 효과가 생긴다. 따라서 이 문제를 해결하기 위해 t-SNE를 도입하였다.

 

3.3 Mistmatched Tails can Compensate for Mismatched Dimensionalities

 

위의 문제를 해결하기 위해 제시된 것이 t-SNE다.

 

기존의 SNE는 고차원 거리를 가우시안 분포를 이용한 확률로 표현했다. t-SNE는 대신 student t-distribution with one degree of freedom (Cauchy distribution)을 저차원에 활용했다.

 

 

 

가우시안 분포와 Cauchy 분포를 비교해보면 후자의 tail이 더 무겁다는 것을 알 수 있다. 이 특성 때문에 고차원의 moderate distance가 저차원에서 아주 큰 거리여도 괜찮도록 허용한다.

따라서 불필요하게 적당한 고차원 거리를 좁히기 위해 다른 데이터포인트를 망가뜨리면서까지 업데이트를 하지 않게 된다.

 

 

 

 

 

다음과 같이 업데이트 알고리즘고 기술했으나 실제로는 좀 더 테크닉이 들어가긴 한다. (strong long-range forces라고 해서 비슷한 포인트들의 클러스터가 갑자기 초기에 멀어지면 이를 당기기 위한 force를 추가한다.)

 

 

4. Experiments

MNIST data (0부터 9 숫자로 이루어진 그림데이터셋)을 다음과 같이 저차원으로 보일 수 있다. 

 

 

뒤에 다른 dimensionality reduction 과 비교한 것도 있고 (t-SNE 퍼포먼스가 가장 좋음) discussion도 있는데 그건 관심있는 분들이 참고하시길!