Stochastic Neighbor Embedding

Stochastic Neighbor Embedding(SNE)는 전체적인 거리보다 가까운 거리(Neighbor)에 중요성을 부여하는 특성을 가지고 있으며, 그 local distance의 확률을 보존하면서 고차원에서 저차원으로 임베딩하는 방법론이다.

• $p_{j|i}$: $j$번째 데이터를 고차원(high-dimensional)에서 뽑을 확률

\[p_{j|i} = \frac{e^{-\frac{||x_i-x_j||^2}{2\sigma^2_i}}}{\sum_{k \neq t} e^{\frac{-||x_i-x_k||^2}{2\sigma^2_i}}}\]

• $q_{j|i}$: $j$번째 데이터를 저차원(low-dimensional)에서 뽑을 확률

\[q_{j|i} = \frac{e^{-||y_i-y_j||^2}}{\sum_{k \neq i} e^{-||y_i-y_k||^2}}\]

위 두 확률분포의 차이가 최소가 되도록하는 목적식은 KL-divergence로 정의 될 수 있다. 아래의 그림과 함께 이해하면 두 확률값이 같아 질때 cost가 0이 되는 것을 알 수 있고, 반대로 그 차이가 크면 cost가 커지는 그래프이다.

\[cost = \sum_i KL(P_i||Q_i) = \sum_i\sum_j p_{j|i} log\frac{p_{j|i}}{q_{j|i}}\]

가우시안 커널 $\sigma$ 정의

가우시안 커널은 $\sigma$에 따라서 얼마나 많은 이웃들을 고려할 것인가를 결정할 수 있다. 예를 들어 $\sigma$가 커지면 분포의 모양은 완만한 곡선을 가지게 되며 다른 분포들 보다 넓은 영역들을 고려하게 된다. 반면에 $\sigma$ 가 작아지면 분포의 모양이 뾰죡한 모양을 가지며 다른 분포들 보다 좁은 영역을 보게 된다.

t-SNE에서는 perplexity를 5~50사이에 있을 때 일관성있는 아웃풋을 내보낸다고 한다.

\[perplexity(p_i) = 2^{H(P_i)}\] \[H(P_i) = \sum_jp_{j|i}log_{2}(p_{j|i})\]

Gradient

\[C = \sum_i KL(P_i||Q_i) = \sum_i\sum_j p_{j|i} log\frac{p_{j|i}}{q_{j|i}}\]

$C = \sum_i\sum_j p_{j|i} log(p_{j|i}) - $ $\sum_i\sum_j p_{j|i} log ({q_{j|i}})$

• 수식에서 $p\log(p)$에 관련된 부분은 업데이트 되지 않는 constant이므로 오른쪽 $p\log(q)$에 대해서 최적화하면 됨

$C^{*} = $ $\sum_i\sum_j p_{j|i} log ({q_{j|i}})$

APPENDIX A 참조

\[\frac{\partial C}{\partial y_i} = 2\sum_j (y_j - y_i)(p_{j|i}- q_{j|i} + p_{i|j} - q_{i|j})\]

Symmetric SNE

조건부 확룰 $j|i$ 를 pairwise probabilities로 고려

\[p_{ij} = \frac{e^{-\frac{||x_i-x_j||^2}{2\sigma^2_i}}}{\sum_{k \neq t} e^{\frac{-||x_i-x_k||^2}{2\sigma^2_i}}}\] \[p_{ij} = \frac{p_{j|i}+p_{i|j}}{2n}\] \[\sum_j p_{ij} > \frac{1}{2n}\]

• cost function & gradient

\[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})\]

Crowding problem

SNE의 특성 상 2차원 상에서 가까운 거리의 데이터 집합과 먼 거리에 있는 데이터 집합이 구분될 정도로 뚜렷하지 않다. 하지만, 분포의 꼬리가 두꺼운 t 분포를 가정하면 이러한 가운데에 모이게 되는 문제점을 완화 시킬 수 있다.

t-SNE

• Low-dimensional space에 꼬리가 두꺼운 t-분포를 가정

\[f(t) = \frac{\Gamma(\frac{\nu+1}{2})}{\sqrt{\nu\pi}\ \Gamma(\frac{\nu}{2})} (1+\frac{t^2}{\nu})^{-\frac{\nu+1}{2}}\] \[\Gamma(n)=(n-1)!\] \[p_{j|i} = \frac{e^{-\frac{||x_i-x_j||^2}{2\sigma^2_i}}}{\sum_{k \neq t} e^{\frac{-||x_i-x_k||^2}{2\sigma^2_i}}}\] \[q_{j|i} = \frac{(1+||y_i - y_j||)^{-1}}{\sum_{k \neq l}(1+||y_k - y_l||^2)^{-1}}\]

• Gradient

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

Gradient Interpretation

그래디언트가 업데이트 될 때 데이터의 움직임을 직관적으로 해석해보자. 아래 수식을 쪼개서 보면 3가지 모션을 취한다는 것을 알 수 있다.

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

• Displacement(이동): 저차원상의 데이터 좌표이동

$(y_j - y_i)$

• Exertion(운동에너지) / Compression(압축): 여기서 표현하는 운동에너지는 고차원에서 발생할 확률과 저차원에서 발생할 확률의 차이로 t-분포에서 생성된 그래디언트로 Normalization을 시킨것으로 해석될 수 있다.

$(p_{ij}- q_{ij})(1+||y_i - y_j||^2)^{-1}$

• N개의 데이터, summation: 이웃하는 local한 데이터 포인트들을 고려해서 업데이트한다.

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

[예시]

일반적으로 t-SNE를 학습하면 원형으로 밀집되는 그림을 많이 볼 수 있는데 한 포인터를 기점으로 주변 데이터 포인트들이 위 방식대로 업데이트 되기 때문이다.

---