이론적 배경

Stochastic Neighbor Embedding(SNE)

고차원 원공간에 존재하는 데이터 x의 이웃간의 거리를 최대한 보존하는 저차원의 y를 학습하는 방법론

• 원래의 고차원 공간에 존재하는 i번째 object가 주어졌을 때, j번째 object가 선택될 확률
  • $${ p }_{ j\vert i }=\frac { { e }^{ -\frac { { \left\vert { x }_{ i }-{ x }_{ j } \right\vert }^{ 2 } }{ 2{ \sigma }_{ i }^{ 2 } } } }{ \sum _{ k }^{ }{ { e }^{ -\frac { { \left\vert { x }_{ i }-{ x }_{ k } \right\vert }^{ 2 } }{ 2{ \sigma }_{ i }^{ 2 } } } } }$$
• 저차원의 공간에서 i번째 object가 주어졌을 때, j번째 object가 선택될 확률
  • $${ q }_{ j\vert i }=\frac { { e }^{ -{ \left\vert { y }_{ i }-{ y }_{ j } \right\vert }^{ 2 } } }{ \sum _{ k }^{ }{ { e }^{ -{ \left\vert { y }_{ i }-{ y }_{ k } \right\vert }^{ 2 } } } }$$

SNE는 위 두 확률이 비슷해지면 저차원이 잘 모델링된다고 가정을 한다. 확률의 비슷함은 당연히 KL divergence!

그래서 다음 식을 최소화시키도록 학습을 한다. $\begin{align*} Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }\vert \vert { Q }_{ i }) } \\ &=\sum _{ i }^{ }{ \sum _{ j }^{ }{ { p }_{ j\vert i }\log { \frac { { p }_{ j\vert i } }{ { q }_{ j\vert i } } } } } \end{align*}$

t-SNE

• SNE에서 $\sigma_i$는 원래 dense한 곳에서는 작고, sparse한 곳에서는 크게 하려고 했는데, 상수로 고정하여도 성능에 큰 차이가 없었음.
• $p_{i\vert j}$와 $p_{j\vert i}$를 같이 놓고 풀어도 성능이 그리 나쁘지 않았음.
  • 그래서 요렇게 변경
    • $${ p }_{ ij }=\frac { { p }_{ j\vert i }+{ p }_{ i\vert j } }{ 2 } ,\quad { q }_{ ij }=\frac { { q }_{ j\vert i }+{ q }_{ i\vert j } }{ 2 }$$
• 그래서 다시 계산하면
  • $$\begin{align*} Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }\vert \vert { 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*}$$
  • 요리 나온다. 이거는 유도해보지 않았고… 어차피 gradient descent로 풀어버리니까…
• gaussian은 꼬리가 얇아서 적당히 떨어진 것과 멀리 떨어진 것의 확률이 모두 작다.(crowding problem) 그래서 $q_{ij}$에 대해서 t-분포를 사용했음.
  • $${ q }_{ ij }=\frac { { (1+{ \left\vert { y }_{ i }-{ y }_{ j } \right\vert }^{ 2 }) }^{ -1 } }{ \sum _{ k\neq l }^{ }{ { (1+{ \left\vert { y }_{ k }-{ y }_{ l } \right\vert }^{ 2 }) }^{ -1 } } }$$

실제 쓸 때 필요한 정보

요거 쓰면 빠른데 dimension이 2일때만 된다…ㅠㅠ

multicore-TSNE 이 코드를 받아서 써야한다. scikit-learn의 t-sne와 여러 다른 t-sne 구현체에 대해서 [40164 x 512]로 실험했는데 다들 잘 안나온다. 심지어 segfault까지 나옴.. 요놈을 가져다 쓰자!

10분안에 끝남 (다른 녀석들은 몇시간 기다려도 안됨 ㅠ)

from MulticoreTSNE import MulticoreTSNE as TSNE
import numpy as np

def normalize_data(d):
    row_sums = d.sum(axis=1)
    return (d.T / row_sums).T

tsne = TSNE(n_jobs=16, metric="cosine")  # 16코어, cosine metric
emb = np.load("testKrEn/en_pair.npy")
emb2 = emb.astype(np.double)
Y = tsne.fit_transform(emb2)
np.save("out_2.npy", Y)
Y_norm = normalize_data(Y)
np.save("out_norm_2.npy", Y_norm)

http://techfly.top/2017/03/09/machine_learning_tensorflow_tsne_data_nonlinear_dimensionality_reduction/ 요거 보고 구현해봐야하나…ㅠㅠ

https://github.com/maestrojeong/t-SNE/blob/master/t-SNE.ipynb