Visualizing Data using t-SNE

2008년

[Abtract]

이 논문에서 제안하는 t-SNE는 Stochastic Neighbor Embedding의 변형으로, 데이터의 여러 다른 스케일의 구조를 잘 표현하는 단일 맵을 만들 수 있는 방법이다.

[1] Introduction

이전에도 차원을 축소해서 데이터의 관계를 보여주는 연구들은 있었는데, 선형 방법과 비선형 방법이 있다. 차원을 축소하는 방법은 기본적으로 고차원 데이터의 구조를 최대한 보전하는 데에 있다. 선형 방법은 PCA, MDS등의 방법으로, 서로 다른 특성의 데이터를 멀리 표현할 수 있다. 단, 서로 비슷한 특성의 데이터를 가깝게 유지하는 것은 선형 방법으로는 할 수 없고 비선형 방법으로만 할 수 있다. 비선형 방법도 많은 방법들이 연구되었지만, 이들 중 대부분은 지역적 구조와 글로벌 구조를 단일 맵에 다 담지 못한다는 단점이 있다. t-SNE는 이들과 반대로 고차원 데이터의 지역적 구조와 글로벌 구조도 담을 수 있다.

[2] Stochastic Neighbor Embedding (SNE)

SNE는 고차원 데이터의 점 사이 유클리드 거리를 유사도를 나타내기 위한 조건부 확률로 변환하는 것에서 시작한다.

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

저차원 데이터에 대해서는 비슷한 $q_{j|i}$를 계산할 수 있는데, 이때는 $q_{j\mid i}=\frac{\exp(-\|y_i-y_j\|^2)}{\sum_{k\not{=}i} \exp(-\|y_i-y_k\|^2)}$ 을 사용한다. 만약 제대로 맵핑이 되었다면, $p_{j|i}$와 $q_{j|i}$는 같을 것이다. 여기서 착안해, SNE에서는 KL-Divergence를 cost function으로 잡고 GD를 이용해 cost를 최소화하는 맵핑을 찾는다. 그러나 KL-Divergence는 대칭이 아니기 때문에, 데이터의 글로벌 구조보다 지역적 구조를 표현하는 것에 더 집중한다. SNE에서 사용하는 cost function은 다음과 같다.

$C=\sum_i\text{KL}(P_i\|Q_i)=\sum_i\sum_jp_{j\mid i}\log\frac{p_{j\mid i}}{q_{j\mid i}}$

$\sigma_i$를 정하는 일이 남았는데, 모든 점에 대해 고정된 $\sigma_i$가 존재하는 것이 아니고 데이터의 쏠림에 따라 다른 값이 적절하다. SNE는 사용자가 정의한 perplexity ($\text{Perp}(P_i)=2^{H(P_i)}$, $H(P_i)=-\sum_j p_{j|i}\log_2 p_{j|i}$)를 만족하는 $\sigma_i$를 찾는데, 이진 탐색을 사용한다.

그리고 GD를 이용해 cost를 최소화해야 하는데, 이때의 gradient는 다음과 같이 정의되고, 그 다음 식을 이용해 update된다.

$\frac{\delta C}{\delta y_i}=2\sum_j(p_{j\mid i}-q_{j\mid i}+p_{i\mid j}-q_{i\mid j})(y_i-y_j)$ $\mathcal{Y}^{(t)}=\mathcal{Y}^{(t-1)}+\eta\frac{\delta C}{\delta\mathcal{Y}}+\alpha(t)(\mathcal{Y}^{(t-1)}-\mathcal{Y}^{(t-2)})$

추가로, 최적화의 초기 단계에서는 반복마다 Gaussian noise를 추가하고, 점차 그 분산을 줄여 simulated annealing의 효과가 나게 한다. 이렇게 하면 나쁜 local minima에 빠지는 것을 막을 수 있다. 그러나 Gaussian noise의 초기값을 선택하는 것과 각 반복마다 얼마나 줄일지에 결과가 민감하게 반응하며, momentum $\alpha(t)$와 step size $\eta$도 선택해야 한다.

[3] t-Distributed Stochastic Neighbor Embedding

SNE는 cost function이 최적화하기 어려운 형태이며, crowding problem이라는 문제가 있다. t-SNE에서 사용하는 cost function은 SNE에서 사용하느 것과 두 가지의 차이점이 있는데, 다음과 같다.

SNE에서 사용하는 cost function의 대칭 버전을 사용하고, gradient도 더 간단하다.
저차원 공간에서의 유사도를 계산할 때는 Gaussian noise 대신 Student-t 분포를 사용한다.

[3.1] Symmetric SNE

대칭 SNE에서 사용하는 cost function은 다음과 같다.

$C=\text{KL}(P\|Q)=\sum_i\sum_jp_{ij}\log\frac{p_{ij}}{q_{ij}}$

이때, $p_{ij}=p_{ji}, q_{ij}=q_{ji}, \forall i,j$의 성질을 갖는다. (위에서는 $\sigma_i$때문에 보통 다르다.) 이때의 $p_{ij}, q_{ij}$는 $p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2n}$ , $q_{ij}=\frac{\exp(\|y_i-y_j\|^2)}{\sum_{k\not{=}l}\exp(\|y_k-y_l\|^2)}$ 로 정의된다. 새로운 gradient는

$\frac{\delta C}{\delta y_i}=4\sum_j(p_{ij}-q_{ij})(y_i-y_j)$

로, 원래의 gradient보다 훨씬 간단한 모양을 띤다.

[3.2] The Crowding Problem

2차원 맵의 pairwise distance가 10차원 맵의 pairwise distance를 표현할 수 없는 이유중 하나가 crowding problem인데, 이 문제는 중간 거리의 데이터들을 표현할 수 있는 공간이 가까운 거리의 데이터들을 표현할 수 있는 공간에 비해 충분하지 않다는 문제이다. (10차원의 공간에서는 $r^{10}$이나 되지만, 2차원에서는 $r^2$밖에 없다.)

[3.3] Mismatched Tails can Compensate for Mismatched Dimensionalities

crowding problem을 해결하기 위해 t-SNE에서는 거리를 확률로 변환하는 데에 Gaussian 대신 long tail을 가진 Student t 분포를 사용한다. 이를 사용하면 적당히 다른 점들을 적당한 거리로 띄워놓을 수 있다. 이 때 $q_{ij}$의 식은 $q_{ij}=\frac{(1+\|y_i-y_j\|^2)^{-1}}{\sum_{k\not{=}l}(1+\|y_k-y_l\|^2)^{-1}}$ 로 바뀐다. 이 방식으로 구한 gradient는 다음과 같다.

$\frac{\delta C}{\delta y_i}=4\sum_j(p_{ij}-q_{ij})(y_i-y_j)(1+\|y_i-y_j\|^2)^{-1}$

고차원 거리와 저차원 거리에 따른 gradient를 그래프로 나타내어 보았는데, t-SNE가 기존 방법보다 나은 점은 두 가지로 볼 수 있다.

저차원 공간에서 작은 거리로 맵핑되었지만 비슷하지 않은 두 점을 밀어내는 힘이 더 크다.
밀어내는 힘이 크지만 무한히 커지진 않는다. (UNI-SNE에서는 무한히 커진다)

또한 t-SNE의 cost function은 최적화하기가 더 쉬우며, 최적화 초기에 떨어져 있었지만 비슷한 두 점을 끌어당길 수 있는 long-range force가 있다.

[3.4] Optimization Methods for t-SNE

t-SNE에서의 최적화는 두가지의 방법을 통해 더 개선될 수 있다. 하나는 early compression이라고 불리는데, 최적화 초기에 점들이 붙어있도록 한다. 이렇게 하면 점들의 거리가 작아지는데, 클러스터들이 서로를 잘 통과할 수 있게 해주어 데이터의 글로벌 구조를 더 잘 탐색할 수 있게 해준다. 구현은 cost function에 L2-penalty를 추가하는 것으로 할 수 있다.

다른 하나는 early exaggeration인데, 최적화 초기에 모든 $p_{ij}$에 특정 상수를 곱하는 것이다. 이렇게 하면 원래 값이 작은 $p_{ij}$가 $q_{ij}$와 대등하게 취급되는 것을 도와주어 점들을 멀리 퍼지게 한다. 이렇게 하면 빈 공간이 많아지기 때문에 클러스터들이 좋은 글로벌 구조를 찾을 수 있게 해준다.

[4] Experiments

이 논문에서 main paper에 시각화할 데이터셋은 MNIST, Olivetti faces, COIL-20이다. Olivetti faces는 40명의 사람을 10가지의 표정, 안경의 다양성을 준 데이터셋이다. COIL-20은 20개의 대상을 72개의 시점에서 본 데이터셋이다. 각 방법을 비교할 때 우선 PCA를 이용해 30차원까지 줄인 다음 각 방법을 비교한다.

[4.3] Results

우선 MNIST를 가지고 t-SNE, Sammon mapping, Isomap, LLE를 비교했는데, Sammon mapping은 전체적으로 하나의 공 모양을 형성해 클래스를 분리하기 어렵게 보였다. Isomap과 LLE는 여러 클래스 사이에 오버랩이 많았다. 반면 t-SNE는 서로 다른 클래스를 잘 분리했다. t-SNE가 분리한 결과에서 잘못된 클래스로 클러스터링된 결과가 몇개 있는데, 이들은 대부분 숫자가 왜곡되어 사람이 보기에도 다른 클래스처럼 보이는 것들이다.

COIL-20 데이터셋에서도 t-SNE를 이용했을 때의 결과는 72개의 시점이 원의 모양이 되도록 잘 클러스터링 되어있다.

[5] Applying t-SNE to Large Data Sets

t-SNE는 데이터 개수의 제곱에 해당하는 계산복잡도를 갖고 있기 때문에 그냥 t-SNE를 매우 큰 데이터셋에 적용하면 계산량이 엄청나게 많다. 따라서 랜덤으로 고른 랜드마크만을 t-SNE로 시각화하는데, 전체 데이터셋을 다 이용하는 방법을 사용한다.

우선 적당한 이웃의 수를 설정하고 이웃 그래프를 그리는 것에서부터 시작한다. 이 방법에서는 $p_{j|i}$를 랜드마크 $x_i$에서 시작해서 랜덤 워크를 수행해 $x_j$에서 끝나는 비율로 정의한다. 이때 노드 $x_a$에서 $x_b$로 가는 길을 선택할 확률은 $e^{-\|x_a-x_b\|^2}$ 에 비례한다.

이 방법이 잘 작동된다는 증거는 일반화 test error에서 찾을 수 있는데, 원래 차원에서의 1-NN test error와 t-SNE를 사용해 축소된 차원에서의 1-NN test error가 거의 비슷했다.

[6] Discussion

Classical scaling은 PCA와도 연관되어 있는데, 고차원상의 거리와 저차원상의 거리의 SSE를 줄이는 것이 목표인 방법이다. 이 방법의 문제점은 curved manifold모델링에는 성능이 좋지 않으며, 가까이에 있는 점들 사이의 거리보다는 멀리 있는 점들 사이의 거리를 유지하는 데에 중점을 더 둔다. 이 방법을 개선한 방법이 Sammon mapping이다.

Sammon mapping의 약점은 매우 가까운 고차원의 두 점이 cost function에 큰 영향을 미친다는 점이다. 이 cost function은 분모에 $\|x_i-x_j\|$ 가 나눠지기 때문에 매우 가까운 고차원의 두 점이 있으면 cost function값이 엄청나게 커진다.

Isomap의 단점은 short-circuiting이다. 또한 Isomap은 큰 측지 거리를 모델링하는데에만 초점을 맞춘다. LLE를 사용할 때는 모든 점이 한 점으로 맵핑될 수 있다는 문제가 있는데, 이것을 막아줄 수 있는 공분산 제약이 있다. 문제는 이 제약이 이 문제를 해결하는 쪽이 아닌, 우회하는 방향으로 쉽게 충족될 수 있다는 점이다. 또한 Isomap과 LLE는 이웃 그래프 기반 방법으로 분류되는데, 이들은 여러개의 널리 퍼진 submanifold를 시각화하기 어렵다.

t-SNE의 랜덤워크 버전도 이웃 그래프를 사용하지만, 모든 경우의 수를 고려하기 때문에 short-circuiting 문제를 피할 수 있다. t-SNE의 랜덤워크 버전은 diffusion map과도 비교될 수 있는데, diffusion map은 classical scaling과 마찬가지의 단점이 있고 또한 $t$라는 하이퍼파라미터를 결정해야 한다.

[6.2] Weaknesses

t-SNE의 약점은 세가지가 있다.

t-SNE가 일반적인 차원 축소(2, 3차원이 아닌 더 높은 차원)에 사용될 수 있는지 확실하지 않다. 이 논문에서의 연구는 시각화를 하기 위한 것이기 때문에 2차원으로만 축소했는데, 그 이상 차원으로 축소하면 결과를 평가할 수 없다. 또한 Student t분포는 heavy tail을 갖고있기 때문에 데이터의 local 구조를 잘 보존하지 못하는 결과가 나올 수도 있다.
내재된 차원의 저주에 민감할 수도 있다. 만약 데이터를 온전히 표현하기 위한 차원이 매우 큰데 그것을 2차원으로 나타내려 하면 제대로 표현이 안될 수도 있다. t-SNE는 선형성만 가정하기 때문에, 오토인코더 등의 비선형 레이어로 표현된 데이터는 t-SNE로 시각화가 가능하다.
cost function이 convex가 아니기 때문에 global optima로 수렴하는 것이 확실하지 않다. classical scaling, Isomap, LLE, diffusion map은 cost function이 convex이다. cost function이 convex하지 않으면 몇몇 최적화 파라미터를 선택해야 한다. 하지만 여러번 실행했을 때 결과가 많이 차이나지 않기 때문에 이 논문에서는 이 점이 큰 약점이 아니라고 주장한다.