t-SNEの仕組み・理論

t-SNEはSNE(Stochastic Neighbor Embedding)に下記の二つの修正を行った手法です。

・「対称性の追加(Symmetric SNE)
・確率計算にあたって正規分布の代わりにスチューデントのt分布を用いる

以下では「SNE」、「Symmetric SNE」、「Student t-distribution」の三点についてそれぞれ確認します。

・SNE(Stochastic Neighbor Embedding)論文
・t-SNE論文

SNE(Stochastic Neighbor Embedding)

SNE(Stochastic Neighbor Embedding)は主成分分析(PCA; Principal Component Analysis)と同様にベクトルの次元削減を行う手法です。主成分分析では固有ベクトルに基づいて次元削減を行いますが、SNEではKL-Divergenceに基づく学習によって次元削減を行います。

$N$個のサンプルについて下記のように入力ベクトルと出力ベクトルを定義します。

\begin{align}
\mathbf{x}_{i} & \in \mathbb{R}^{n} \\
\mathbf{y}_{i} = f_{\theta}(\mathbf{x}_{i}) & \in \mathbb{R}^{m} \\
m << n
\end{align}

$m$は$n$より大幅に小さい値で、可視化が行えるように$m=2$か$m=3$のどちらかが用いられることが多いです。二次元平面の方が可視化しやすいので以下では基本的に$m=2$を前提とします。次に下記のように確率の$p_{ij}$と$q_{ij}$を定義します。

\begin{align}
p_{ij} &= \frac{\exp{(-d_{ij}^{2})}}{\sum_{k \neq i} \exp{(-d_{ik}^{2})}} \\
q_{ij} &= \frac{\exp{(-|| \mathbf{y}_{i} - \mathbf{y}_{j} ||^{2})}}{\sum_{k \neq i} \exp{(-|| \mathbf{y}_{i} - \mathbf{y}_{k} ||^{2})}} \\
d_{ij}^{2} &= \frac{|| \mathbf{x}_{i}-\mathbf{x}_{j} ||^{2}}{2 \sigma_{i}^{2}}
\end{align}

t-SNEに関連する上記の式の解釈にあたっては、$d_{ij}^{2}$が正規分布の$\exp$の中の項に対応することは確認しておくと良いです。また、$p_{ij} \neq p_{ji}$である一方で$q_{ij} = q_{ji}$が成立することは合わせて抑えておくと良いと思います。

このように定義された$p_{ij}$と$q_{ij}$を元にKL-divergenceを計算することで、$\mathbf{y}_{i}$の評価指標の$C$を下記のように定義します。

\begin{align}
C &= \sum_{i} \sum_{j} p_{ij} \log{\frac{p_{ij}}{q_{ij}}} = \sum_{i} \mathrm{KL}(P_{i}||Q_{i}) \\
P_{i} &= \left( \begin{array}{c} p_{i1} \\ \vdots \\ p_{iN} \end{array} \right) , \quad Q_{i} = \left( \begin{array}{c} q_{i1} \\ \vdots \\ q_{iN} \end{array} \right)
\end{align}

SNEでは上記の$C$が小さくなるように関数$f_{\theta}$の学習を行うことで、次元削減の関数を得ることができます。

Symmetric SNE

前項で確認したようにSNEでは$p_{ij} \neq p_{ji}$である$p_{ij}$を用います。一方で対称的な$p_{ij}$を用いる方がCost functionの(C)の勾配がシンプルになって良い(Visualizing Similarity Data with a Mixture of Maps)という研究を受けて、t-SNEでは下記のように$p_{ij}$を定義します。

\begin{align}
p_{ij} &= \frac{\exp{(-d_{ij}^{2})}}{\sum_{k \neq i} \exp{(-d_{ik}^{2})}} \\
d_{ij}^{2} &= \frac{|| \mathbf{x}_{i}-\mathbf{x}_{j} ||^{2}}{2 \sigma^{2}}
\end{align}

上記のように$p_{ij}$を定義することで$p_{ij} = p_{ji}$が成立します。

Student t-distribution

SNEでは$p_{ij}$や$q_{ij}$の計算にあたって、正規分布の内部の式(Mahalanobis Distanceに対応)を用いていましたが、t-SNEでは低次元ベクトルの$q_{ij}$の計算にあたって自由度1のt分布(コーシー分布に対応)を用います。$q_{ij}$は下記のように定義されます。

q_{ij} = \frac{(1+||\mathbf{y}_{i}-\mathbf{y}_{j}||^{2})^{-1}}{\sum_{i \neq k} (1+||\mathbf{y}_{i}-\mathbf{y}_{k}||^{2})^{-1}}

上記は、t分布の方が裾野の広い分布であるので、低次元ベクトルの差が少々大きい場合も確率の値を持つようにできると解釈すると良いと思います。

t-SNEの実装

scikit-learn

下記のプログラムを実行することでirisデータセットをt-SNEを用いて2次元に次元削減することができます。

import numpy as np

from sklearn.manifold import TSNE
from sklearn.datasets import load_iris

import matplotlib.pyplot as plt
import seaborn as sns
sns.set_theme()


data = load_iris().data

model = TSNE(n_components=2, random_state=0)
embedded = model.fit_transform(data)

plt.scatter(embedded[:50,0], embedded[:50,1])
plt.scatter(embedded[50:100,0], embedded[50:100,1])
plt.scatter(embedded[100:,0], embedded[100:,1])
plt.legend()
plt.savefig("iris.png")

・実行結果

PyTorch