t-SNEとは

t-SNE（t-distributed Stochastic Neighbor Embedding）は高次元空間に存在する点の散らばり具合を可視化するためによく使われる手法です．t-SNEでは，直接ユークリッド距離を再現するのではなく，確率密度を用いて「近接度」と呼ばれる距離を定義し，近接度に応じて3次元、又は2次元上に点を配置することで点を可視化します．

この記事では，t-SNEが具体的にどのようなアルゴリズムになっているか解説します．

アルゴリズム

t-SNEで重要となるのが「近接度」という概念です．t-SNEでは「近接度」を使って点同士の近さを表現し可視化します．
近接度の定義をまずは述べます．

定義（近接度）

今，$X=\{ x_1, \dots , x_n\} \in \mathbb{R}^N$が与えられたとします．各々の点$x_i$が「隣人」として$x_j$を選ぶ確率$p_{j|i}$を次のように定義します．
$$
p_{j|i} =
\begin{cases}
\displaystyle\frac{\exp (-||x_i – x_j||^2/2s_i^2)}{ \displaystyle\sum_{k\neq i}^n \exp (-||x_i – x_k||^2/2s_i^2)} & (i\neq j) \\
0& (i=j)
\end{cases}
$$
つまり，$x_i$を中心とする正規分布の$x_j$における確率密度として定義します．また，分散$s_i$は確率分布$P_i : j\mapsto p_{j|i}$のエントロピーがあらかじめ定めた定数$h$に等しくなるように定義します．$P_i$のエントロピー
$$
H(P_i) = – \sum_{j=1}^n p_{j|i} \log p_{j|i}
$$
は$s_i^2$について単調増加である為，$H(P_i)=h$となる$s_i$は一意に定まり，二分探索によって求めることが出来ます．

以上の記号を用いて，$i,j$間の近接度を
$$
p_{ij}=\frac{p_{j|i}+p_{i|j}}{2n}
$$
と定義します．$\sum_{i,j} p_{ij}=1$である為，近接度$P : (i,j)\mapsto p_{ij}$はオブジェクト対$I\times I \ (I:={ 1,2,\dots , n})$上の確率密度とみなすことが出来ます．

定義（写像先の近接度）

高次元空間$\mathbb{R}^N$上の近接度が定義出来たところで，今度は写像先の空間（可視化するために落とし込む低次元空間）$\mathbb{R}^2$又は$\mathbb{R}^3$上の点$Y={ y_1, y_2 \dots y_n}$における近接度$Q$について定義します．
近接度$Q$は高次元空間の場合とは異なり，コーシー分布（自由度1のt-分布）の確率密度に基づいて定義します．このように定義する理由は，コーシー分布は正規分布と比較して裾が重い分布であり，これを利用して，写像元の高次元空間と写像先の低次元空間の性質の違いを吸収するのを狙うことにあります（※）．$Q : (i,j)\mapsto q_{ij}$を
$$
q_{ij} =
\begin{cases}
\displaystyle\frac{(1+|| y_i – y_j ||^2)^{-1}}{\displaystyle\sum_{k,l k\neq l}^n(1+||y_k – y_l||^2)^{-1}} & (i\neq j) \\
0& (i=j)
\end{cases}
$$
と定義します．

可視化点の定め方

近接度 $P.Q$ の定義ができたところで，t-SNEのアルゴリズムは次のようになります．
$P.Q$はいずれも$I\times I$上の確率分布とみなせるので，カルバックライブラー情報量を用いて二つの分布間の乖離度を測ることが出来ます．
$$
\mathop{\rm KL}(P||Q)= \sum_{i,j=1}^n p_{ij} \log \frac{p_{ij}}{q_{ij}}
$$
このKL情報量が最小となるように$y_i \in Y$を求めるのが t-SNEのアルゴリズムです．$y_i$の最適化の手法としては一般の勾配降下法を用います．

参考文献

Visualizing Data using t-SNE
数理科学 2019年 06 月号 [雑誌] | |本 | 通販 | Amazon

※例えば，「次元の呪い」という言葉でよく知られている現象がある．各辺が1の立方体の対角線の長さを考えると，3次元では$\sqrt3 = 1.73\dots $に対し，100次元では$\sqrt100 = 10$となり距離は5倍以上になる．よって、高次元空間は低次元空間に比べ広がり具合が各段に大きいと考えられる．その為，低次元空間では裾の重い確率分布を採用し，その広がり具合を吸収しよう、というわけである．