t-SNE (t-distributed Stochastic Neighborhood Embedding)
1. 개요
t-SNE에 대해서 들어본 적은 많을 것이다. 고차원의 데이터를 2차원으로 축소시켜 시각화하고 싶을때 사용하는 유용한 알고리즘이다. 이 알고리즘 외에도 시각화를 위한 다른 알고리즘들이 있지만 (ex. MDS, ISOMAP,LLE 등) , t-SNE는 이들에 비해 안정적인 임베딩 결과를 보여준다. t-SNE를 포함한 이러한 알고리즘들은, 오늘 날 딥러닝에서 학습된 weight들이 고차원의 distributed representation인 경우가 많다는 점에서, 이러한 시각화 알고리즘은 중요하다고 할 수 있다.
아래 그림은 28x28(=756)차원의 MNIST 손글씨체 숫자 (0~9) 데이터를 t-SNE를 통해 2차원으로 축소하여 시각화 한 결과이다. 756차원에서 2차원으로 크게 줄였음에도 불구하고, 숫자들 간의 구분이 잘 이루어 진 것을 확인할 수 있다!
https://nlml.github.io/images/tsne/tsne-mnist.png
2. Algorithm
위에서도 언급했듯, 이러한 역할을 하는 알고리즘들의 종류는 다양하고, 그 중에서도 non-linear하게 차원을 축소하는 방법들을 통틀어서 Manifold Learning이라고 한다. 이러한 다양한 알고리즘들이 시각화를 하는 데에 있어서 핵심으로 잡는 포인트들이 다 다르다. MDS(Multi-Dimensional Scaling)의 경우, 기존 차원에서 멀리 위치한 두 점은 차원 축소 이후에도 멀리 위치하길 바라고, Isomap의 경우에는 각 점과 가장 가까운 이웃을 연결하는 식으로 그래프를 만들고, 그래프 상에서 정의되는 두 점의 사이의 거리가 유지되기를 원한다. t-SNE와 유사한 목표를 가진 LLE(Localy Linear Embedding)은 , 원본 공간에서 서로 가깝게 위치한 k개의 점들이, 저차원으로 임베딩 된 이후에도 서로 가깝게 위치하기를 바란다.
아래 그림은, 다양한 알고리즘을 사용하여 왼쪽의 원본 데이터를 2차원의 평면으로 시각화한 결과이다. 각각의 알고리즘들이 중요시 여기는 포인트에 따라 시각화가 달리짐을 확인할 수 있다.
https://scikit-learn.org/stable/_images/sphx_glr_plot_compare_methods_0011.png
3. Algorithm 1 : Distance Between Two Points
그렇다면 t-SNE는 어떻게 고차원의 데이터를 저차원(2차원)으로 축소시켜 나타낼 수 있을까? 한마디로 요약하면, 기존 공간에서의 데이터 간의 유사도와 임베딩 공간에서의 데이터 간의 유사도가 서로 비슷하게끔 만드는 것이다. 여기서, 두 점 \(x_i\)와 \(x_j\)의 기존 공간에서의 유사도는 \(p_{ij}\), 임베딩 공간에서의 유사도는 \(q_{ij}\)라고 한다.
(1) 기존 공간에서의 유사도 : \(p_{ij}\)
\(p_{ij}\)를 구하기에 앞서, 우선 점 \(x_i\)에서 \(x_j\)로의 유사도(\(p_{j \mid i}\))를 구해야 한다. \(p_{j \mid i}\)를 계산 하기 위해, 점 \(x_i\)와 다른 모든 점들 사이의 거리 (Euclidean distance)를 구해야 한다. 그리고 이 값들의 총 합을 \(x_i\)에서 \(x_j\) 사이의 거리에서 나눠주게 되면, \(x_i\)와 \(x_j\)사이의 거리를 확률(0~1)로써 나타낼 수 있다. 여기에서, 모든 거리 값은 \(\sigma_i\)로 나눈 뒤 negative exponential을 취한다. 지금까지 이야기한 것을 식으로 나타내면 아래와 같다.
\[p_{j\mid i} = \frac{exp(-\mid x_i - x_j \mid^2) / 2\sigma_i^2}{\sum_{k\neq i}exp(-\mid x_i - x_j \mid^2) / 2\sigma_i^2}\] 여기서 모든 점마다 \(\sigma_i\)를 다르게 정의하는 이유는, \(p_{j\mid i}\)의 값이 안정적이게 만들기 위해서이다. (즉, outlier에 의해 영향을 크게 받지 않게 만들기 위해) 예를들어, 점 \(x_i\)가 다른 점들과의 거리가 멀다면, \(exp(-\mid x_i - x_j \mid^2)\)는 매우 작아질 것이다. 이러한 상황을 고려하여, 각 점마다 \(\sigma_i\)를 다르게 설정하는 것이다.
하지만 위 식을 보면 의아한 생각이 들 수 있다. 우리가 거리(distance)라고 정의하기 위한 조건 중 하나는, 바로 대칭성이다. (대칭성이란, 쉽게 말해 “A와 B사이의 거리 = B와 A사이의 거리”여야 한다는 것이다) 하지만 위 식에서 정의한 \(p_{j\mid i} \neq p_{i \mid j}\)이다. 따라서 우리가 두 점 \(x_i\)와 \(x_j\) 사이의 거리인 \(p_{ij}\)는 이 두 값 ( \(p_{j\mid i}\) 와 \(p_{i \mid j}\) )의 평균으로 정의한다.
\[p_{ij} = \frac{p_{i\mid j}+p_{j\mid i}}{2n}\](2) 임베딩 공간에서의 유사도 : \(q_{ij}\)
이제는 임베딩 공간에서의 거리(유사도)라고 할 수 있는 \(q_{ij}\)를 정의할 것이다. 임베딩 공간 상의 두 점 \(y_i\)와 \(y_j\)사이의 Euclidean distance 인 \(\mid y_i - y_j \mid^2\) 가 커질수록 유사도가 낮아지게끔 이에 역수 꼴을 취할 것인데, 이것이 무한대로 발산하지 않게 하기 위해 1을 더하여 다음과 같이 \((1 + \mid y_i - y_j \mid^2)^{-1}\)로 나타낸다. 이것도 위에서 기존 공간에서의 유사도를 계산햇던 방식과 유사하게, 점 \(y_i\)에서 다른 모든 점들 사이의 유사도를 계산한 뒤 이것의 총 합을 나눠주는 식으로 정의한다. 따라서, 임베딩 공간에서의 유사도인 \(q_{ij}\)는 다음과 같이 정의할 수 있다.
\[q_{ij} = \frac{(1+\mid y_i - y_j \mid^2)^{-1}}{\sum_{i\neq j} (1+\mid y_i - y_j \mid^2)^{-1}}\]위 \(q_{ij}\)가 t-distribution을 따른다는 점에서 이 알고리즘의 이름이 t-SNE (t-distributed Stochastic Neighborhood Embedding)으로 불리는 것이다.
4. Algorithm 2 : Optimization
위에서 \(p_{ij}\)와 \(q_{ij}\)를 정의했다. 우리의 목표는, \(p_{ij}\)와 \(q_{ij}\)가 서로 비슷하게끔 만들어야 한다. ( 임베딩된 공간에서의 유사도가, 실제 데이터의 원본공간에서의 유사도를 잘 반영하게끔 설게되어야 한다 ) 이를 위해, 우리는 KL-Divergence를 사용한다. ( KL-Divergence에 대해 간략히 이야기하자면, 두 분포 사이의 차이를 나타내는 지표이다 ) 그런 뒤, gradient descent method를 사용하여 학습한다.
아래의 \(C\)는, 우리가 최적화하기 위해 minimize해야하는 Cost Function으로써, 두 분포 \(p_{ij}\)와 \(q_{ij}\)의 KL Divergence ( \(KL(P \mid \mid Q)\) )로 정의한다.
\[\begin{align*} C &= \sum_{i, j\neq i}p_{ij} log \frac{p_{ij}}{q_{ij}} = \sum_{i, j\neq i}(p_{ij} logp_{ij} - p_{ij}logq_{ij}) \\ &= \sum_{i, j\neq i}(p_{ij}logp_{ij} - p_{ij}logE_{ij}^{-1} + p_{ij}logZ)\\ \end{align*}\]( 위 식에서 \(E_{ij} = exp(-\mid y_i - y_j \mid^2)\)이고, \(Z = \sum_{i,j \neq i}E_{ij}^{-1}\)이다 )
이 \(C\)를 \(y_i\)에 대해 미분하여 정리하면 아래 식과 같다.
\[\begin{align*} \frac{\partial C}{\partial y_i} &= \sum_{k,l\neq k}-p_{lk}\partial logE_{lk}^{-1} + \sum_{l,k\neq k}p_{lk}\partial log Z \\ &= -2 \sum_{j \neq i}p_{ji}\partial log E_{ij}^{-1} +\frac{1}{Z}\sum_{k',l'\neq k'}\partial E_{kl}^{-1} \\ &= -2\sum_{j\neq i}p_{ji}\frac{1}{E_{ij}^{-1}}E_{ij}^{-2}(-2(y_i-y_j)) + 2\sum_{j\neq i}\frac{E_{ji}^{-2}}{Z}(-2(y_j-y_i))\\ &= 4\sum_{j\neq i}p_{ji}E_{ij}^{-1}(y_i-y_j) -4\sum_{j\neq i}q_{ij}E_{ji}^{-1}(y_i - y_j)\\ &= 4\sum_{j\neq i}(p_{ji} - q_{ji})E_{ji}^{-1}(y_i-y_j)\\ &= 4\sum_{j\neq i}(p_{ji}-q_{ji})(y_i - y_j)\frac{1}{(1+\mid y_i - y_j \mid^2)^{-1}} \end{align*}\]5. Perplexity
Perplexity는 t-SNE에서 사용하는 알고리즘의 파라미터 중 하나로, 특정 점의 nearest neighbors를 정하는 데에 있어서 영향을 미친다. 보다 자세한 것은 https://lovit.github.io/nlp/representation/2018/09/28/tsne/의 블로그를 참고하면 좋을 것 같다.
참고
- https://lovit.github.io/nlp/representation/2018/09/28/tsne/
- http://pages.di.unipi.it/errica/assets/files/sne_tsne.pdf