t-SNE
28 Apr 2017 | t-SNE
이번 글에서는 데이터 차원축소(dimesionality reduction)와 시각화(visualization) 방법론으로 널리 쓰이는 t-SNE(Stochastic Neighbor Embedding)에 대해 살펴보도록 하겠습니다. 단어 벡터와 같이 고차원 데이터를 시각화하는 데 가장 인기있는 알고리즘이기도 합니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
Stochastic Neighbor Embedding
Stochastic Neighbor Embedding(SNE)란 고차원의 원공간에 존재하는 데이터 $x$의 이웃 간의 거리를 최대한 보존하는 저차원의 $y$를 학습하는 방법론입니다. stochastic이란 이름이 붙은 이유는 거리 정보를 확률적으로 나타내기 때문인데요. 이 설명만 봐서는 제대로 알 수 없으니 일단 수식 먼저 보겠습니다.
\[{ p }_{ j|i }=\frac { { e }^{ -\frac { { \left| { x }_{ i }-{ x }_{ j } \right| }^{ 2 } }{ 2{ \sigma }_{ i }^{ 2 } } } }{ \sum _{ k }^{ }{ { e }^{ -\frac { { \left| { x }_{ i }-{ x }_{ k } \right| }^{ 2 } }{ 2{ \sigma }_{ i }^{ 2 } } } } }\]
\[{ q }_{ j|i }=\frac { { e }^{ -{ \left| { y }_{ i }-{ y }_{ j } \right| }^{ 2 } } }{ \sum _{ k }^{ }{ { e }^{ -{ \left| { y }_{ i }-{ y }_{ k } \right| }^{ 2 } } } }\]
첫번째 식의 $p$는 고차원 원공간에 존재하는 $i$번째 개체 $x_i$가 주어졌을 때 $j$번째 이웃인 $x_j$가 선택될 확률을 의미합니다. 두번째 식의 $q$는 저차원에 임베딩된 $i$번째 개체 $y_i$가 주어졌을 때 $j$번째 이웃인 $y_j$가 선택될 확률을 뜻합니다.
SNE의 목적은 $p$와 $q$의 분포 차이가 최대한 작게끔 하고자 합니다. 차원축소가 제대로 잘 이뤄졌다면 고차원 공간에서 이웃으로 뽑힐 확률과 저차원 공간에서 선택될 확률이 비슷할테니까요.
두 확률분포가 얼마나 비슷한지 측정하는 지표로 Kullback-Leibler divergence라는 것이 있습니다. 두 분포가 완전히 다르면 1, 동일하면 0의 값을 갖게 되는데요, SNE는 아래 비용함수를 최소화하는 방향으로 학습을 진행하게 됩니다.
\[\begin{align*}
Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }||{ Q }_{ i }) } \\ &=\sum _{ i }^{ }{ \sum _{ j }^{ }{ { p }_{ j|i }\log { \frac { { p }_{ j|i } }{ { q }_{ j|i } } } } }
\end{align*}\]
그런데 SNE 연구진은 계산 속도를 높이기 위해 몇 가지 학습 트릭을 도입했습니다. $σ_i$는 각 개체마다 데이터 밀도가 달라서 이웃으로 뽑힐 확률이 왜곡되는 현상을 방지하기 위한 값인데요, 반복 실험 결과 $p$를 계산할 때 쓰는 $σ_i$는 고정된 값을 써도 성능에 큰 차이를 보이지 않았다고 합니다. $σ_i$ 계산을 생략하게 된 것이죠.
아울러 $i$번째 개체가 주어졌을 때 $j$번째 개체가 이웃으로 뽑힐 확률과 $j$번째 개체가 주어졌을 때 $i$번째 개체가 선택될 확률을 동일하다고 놓고 풀어도 성능이 그리 나쁘지 않았다고 합니다. 그러면 $p$와 $q$를 아래와 같이 다시 쓸 수 있습니다.
\[{ p }_{ ij }=\frac { { p }_{ j|i }+{ p }_{ i|j } }{ 2 } ,\quad { q }_{ ij }=\frac { { q }_{ j|i }+{ q }_{ i|j } }{ 2 }\]
새로 쓴 비용함수와 $y_i$의 그래디언트는 아래와 같습니다.
\[\begin{align*}
Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }||{ Q }_{ i }) } \\ &=\sum _{ i }^{ }{ \sum _{ j }^{ }{ { p }_{ ij }\log { \frac { { p }_{ ij } }{ { q }_{ ij } } } } } \\ \frac { \partial C }{ \partial { y }_{ i } } &=4\sum _{ j }^{ }{ ({ y }_{ j }-{ y }_{ i })({ p }_{ ij }-{ q }_{ ij }) }
\end{align*}\]
우리가 최종적으로 구하고자 하는 미지수는 저차원에 임베딩된 좌표값 $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와 같습니다.
\[{ q }_{ ij }=\frac { { (1+{ \left| { y }_{ i }-{ y }_{ j } \right| }^{ 2 }) }^{ -1 } }{ \sum _{ k\neq l }^{ }{ { (1+{ \left| { y }_{ k }-{ y }_{ l } \right| }^{ 2 }) }^{ -1 } } }\]
t-SNE 시각화
t-SNE는 보통 word2vec으로 임베딩한 단어벡터를 시각화하는 데 많이 씁니다. 문서 군집화를 수행한 뒤 이를 시각적으로 나타낼 때도 자주 사용됩니다. 저자가 직접 만든 예시 그림은 아래와 같습니다.
이번 글에서는 데이터 차원축소(dimesionality reduction)와 시각화(visualization) 방법론으로 널리 쓰이는 t-SNE(Stochastic Neighbor Embedding)에 대해 살펴보도록 하겠습니다. 단어 벡터와 같이 고차원 데이터를 시각화하는 데 가장 인기있는 알고리즘이기도 합니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
Stochastic Neighbor Embedding
Stochastic Neighbor Embedding(SNE)란 고차원의 원공간에 존재하는 데이터 $x$의 이웃 간의 거리를 최대한 보존하는 저차원의 $y$를 학습하는 방법론입니다. stochastic이란 이름이 붙은 이유는 거리 정보를 확률적으로 나타내기 때문인데요. 이 설명만 봐서는 제대로 알 수 없으니 일단 수식 먼저 보겠습니다.
\[{ p }_{ j|i }=\frac { { e }^{ -\frac { { \left| { x }_{ i }-{ x }_{ j } \right| }^{ 2 } }{ 2{ \sigma }_{ i }^{ 2 } } } }{ \sum _{ k }^{ }{ { e }^{ -\frac { { \left| { x }_{ i }-{ x }_{ k } \right| }^{ 2 } }{ 2{ \sigma }_{ i }^{ 2 } } } } }\] \[{ q }_{ j|i }=\frac { { e }^{ -{ \left| { y }_{ i }-{ y }_{ j } \right| }^{ 2 } } }{ \sum _{ k }^{ }{ { e }^{ -{ \left| { y }_{ i }-{ y }_{ k } \right| }^{ 2 } } } }\]첫번째 식의 $p$는 고차원 원공간에 존재하는 $i$번째 개체 $x_i$가 주어졌을 때 $j$번째 이웃인 $x_j$가 선택될 확률을 의미합니다. 두번째 식의 $q$는 저차원에 임베딩된 $i$번째 개체 $y_i$가 주어졌을 때 $j$번째 이웃인 $y_j$가 선택될 확률을 뜻합니다.
SNE의 목적은 $p$와 $q$의 분포 차이가 최대한 작게끔 하고자 합니다. 차원축소가 제대로 잘 이뤄졌다면 고차원 공간에서 이웃으로 뽑힐 확률과 저차원 공간에서 선택될 확률이 비슷할테니까요.
두 확률분포가 얼마나 비슷한지 측정하는 지표로 Kullback-Leibler divergence라는 것이 있습니다. 두 분포가 완전히 다르면 1, 동일하면 0의 값을 갖게 되는데요, SNE는 아래 비용함수를 최소화하는 방향으로 학습을 진행하게 됩니다.
\[\begin{align*} Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }||{ Q }_{ i }) } \\ &=\sum _{ i }^{ }{ \sum _{ j }^{ }{ { p }_{ j|i }\log { \frac { { p }_{ j|i } }{ { q }_{ j|i } } } } } \end{align*}\]그런데 SNE 연구진은 계산 속도를 높이기 위해 몇 가지 학습 트릭을 도입했습니다. $σ_i$는 각 개체마다 데이터 밀도가 달라서 이웃으로 뽑힐 확률이 왜곡되는 현상을 방지하기 위한 값인데요, 반복 실험 결과 $p$를 계산할 때 쓰는 $σ_i$는 고정된 값을 써도 성능에 큰 차이를 보이지 않았다고 합니다. $σ_i$ 계산을 생략하게 된 것이죠.
아울러 $i$번째 개체가 주어졌을 때 $j$번째 개체가 이웃으로 뽑힐 확률과 $j$번째 개체가 주어졌을 때 $i$번째 개체가 선택될 확률을 동일하다고 놓고 풀어도 성능이 그리 나쁘지 않았다고 합니다. 그러면 $p$와 $q$를 아래와 같이 다시 쓸 수 있습니다.
\[{ p }_{ ij }=\frac { { p }_{ j|i }+{ p }_{ i|j } }{ 2 } ,\quad { q }_{ ij }=\frac { { q }_{ j|i }+{ q }_{ i|j } }{ 2 }\]새로 쓴 비용함수와 $y_i$의 그래디언트는 아래와 같습니다.
\[\begin{align*} Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }||{ Q }_{ i }) } \\ &=\sum _{ i }^{ }{ \sum _{ j }^{ }{ { p }_{ ij }\log { \frac { { p }_{ ij } }{ { q }_{ ij } } } } } \\ \frac { \partial C }{ \partial { y }_{ i } } &=4\sum _{ j }^{ }{ ({ y }_{ j }-{ y }_{ i })({ p }_{ ij }-{ q }_{ ij }) } \end{align*}\]우리가 최종적으로 구하고자 하는 미지수는 저차원에 임베딩된 좌표값 $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와 같습니다.
\[{ q }_{ ij }=\frac { { (1+{ \left| { y }_{ i }-{ y }_{ j } \right| }^{ 2 }) }^{ -1 } }{ \sum _{ k\neq l }^{ }{ { (1+{ \left| { y }_{ k }-{ y }_{ l } \right| }^{ 2 }) }^{ -1 } } }\]t-SNE 시각화
t-SNE는 보통 word2vec으로 임베딩한 단어벡터를 시각화하는 데 많이 씁니다. 문서 군집화를 수행한 뒤 이를 시각적으로 나타낼 때도 자주 사용됩니다. 저자가 직접 만든 예시 그림은 아래와 같습니다.
Comments