for textmining

t-SNE

|

이번 글에서는 데이터 차원축소(dimesionality reduction)시각화(visualization) 방법론으로 널리 쓰이는 t-SNE(Stochastic Neighbor Embedding)에 대해 살펴보도록 하겠습니다. 단어 벡터와 같이 고차원 데이터를 시각화하는 데 가장 인기있는 알고리즘이기도 합니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

Stochastic Neighbor Embedding

Stochastic Neighbor Embedding(SNE)란 고차원의 원공간에 존재하는 데이터 $x$의 이웃 간의 거리를 최대한 보존하는 저차원의 $y$를 학습하는 방법론입니다. stochastic이란 이름이 붙은 이유는 거리 정보를 확률적으로 나타내기 때문인데요. 이 설명만 봐서는 제대로 알 수 없으니 일단 수식 먼저 보겠습니다.

첫번째 식의 $p$는 고차원 원공간에 존재하는 $i$번째 개체 $x_i$가 주어졌을 때 $j$번째 이웃인 $x_j$가 선택될 확률을 의미합니다. 두번째 식의 $q$는 저차원에 임베딩된 $i$번째 개체 $y_i$가 주어졌을 때 $j$번째 이웃인 $y_i$가 선택될 확률을 뜻합니다.

SNE의 목적은 $p$와 $q$의 분포 차이가 최대한 작게끔 하고자 합니다. 차원축소가 제대로 잘 이뤄졌다면 고차원 공간에서 이웃으로 뽑힐 확률과 저차원 공간에서 선택될 확률이 비슷할테니까요.

두 확률분포가 얼마나 비슷한지 측정하는 지표로 Kullback-Leibler divergence라는 것이 있습니다. 두 분포가 완전히 다르면 1, 동일하면 0의 값을 갖게 되는데요, SNE는 아래 비용함수를 최소화하는 방향으로 학습을 진행하게 됩니다.

그런데 SNE 연구진은 계산 속도를 높이기 위해 몇 가지 학습 트릭을 도입했습니다. $σ_i$는 각 개체마다 데이터 밀도가 달라서 이웃으로 뽑힐 확률이 왜곡되는 현상을 방지하기 위한 값인데요, 반복 실험 결과 $p$를 계산할 때 쓰는 $σ_i$는 고정된 값을 써도 성능에 큰 차이를 보이지 않았다고 합니다. $σ_i$ 계산을 생략하게 된 것이죠.

아울러 $i$번째 개체가 주어졌을 때 $j$번째 개체가 이웃으로 뽑힐 확률과 $j$번째 개체가 주어졌을 때 $i$번째 개체가 선택될 확률을 동일하다고 놓고 풀어도 성능이 그리 나쁘지 않았다고 합니다. 그러면 $p$와 $q$를 아래와 같이 다시 쓸 수 있습니다.

새로 쓴 비용함수와 $y_i$의 그래디언트는 아래와 같습니다.

우리가 최종적으로 구하고자 하는 미지수는 저차원에 임베딩된 좌표값 $y_i$입니다. SNE는 그래디언트 디센트(gradient descent) 방식으로 $y_i$들을 업데이트합니다. 즉, 처음에 $y_i$를 랜덤으로 초기화해놓고 위에서 구한 그래디언트의 반대방향으로 조금씩 $y_i$들을 갱신해 나가는 것입니다. $y_i$의 그래디언트를 보면 우리가 이미 모두 알고 있는 값들이므로 업데이트를 여러번 반복 수행하기만 하면 됩니다.

Crowding Problem과 t-SNE

SNE가 전제하는 확률분포는 가우시안 분포입니다. 그런데 가우시안 분포는 꼬리가 두텁지 않아서 $i$번째 개체에서 적당히 떨어져 있는 이웃 $j$와 아주 많이 떨어져 있는 이웃 $k$가 선택될 확률이 크게 차이가 나지 않게 됩니다. 이를 crowding problem이라고 합니다.

이들 구분을 좀 더 잘하기 위해 가우시안분포보다 꼬리가 두터운 t분포를 쓴 것이 바로 t-SNE입니다. t-SNE는 $q_{ij}$에만 아래와 같이 t분포를 적용하고, $p_{ij}$는 SNE와 같습니다.

t-SNE 시각화

t-SNE는 보통 word2vec으로 임베딩한 단어벡터를 시각화하는 데 많이 씁니다. 문서 군집화를 수행한 뒤 이를 시각적으로 나타낼 때도 자주 사용됩니다. 저자가 직접 만든 예시 그림은 아래와 같습니다.

Comments