t-SNE

t-SNE とは

t-SNE (tsne) は、高次元データの可視化に適している次元削減アルゴリズムです。名前は、t-distributed Stochastic Neighbor Embedding (t 分布型確率的近傍埋め込み) を表します。考え方は、点の間の類似度が反映されるように高次元の点を低次元に埋め込む、というものです。高次元空間の近接点は低次元に埋め込まれた近接点に対応し、高次元空間の遠隔点は低次元に埋め込まれた遠隔点に対応します (一般に、高次元空間と低次元空間で正確に距離を一致させることは不可能です)。

関数 tsne は、高次元データから低次元の点の集合を作成します。通常は、低次元の点を可視化して、元の高次元データにおける自然なクラスターを調べます。

このアルゴリズムでは、以下の一般的なステップを使用してデータを低次元に埋め込みます。

1. 高次元の点の間のペアワイズ距離を計算する。

2. 高次元の各点の "パープレキシティ" が所定のレベルになるように、各点 i について標準偏差 σ_i を作成する。パープレキシティの定義については、距離、ガウス分散および類似度の計算を参照してください。

3. "類似度行列" を計算する。これは、式 1によって定義される X の結合確率分布です。

4. 低次元の点の初期集合を作成する。

5. 高次元空間のガウス分布と低次元空間の t 分布の間のカルバック・ライブラー ダイバージェンスが最小になるように、低次元の点を繰り返し更新する。この最適化手順は、このアルゴリズムで最も時間がかかる部分です。

van der Maaten and Hinton [1] を参照してください。

t-SNE アルゴリズム

基本的な t-SNE アルゴリズムでは、以下のステップを実行します。

• データの準備

• 距離、ガウス分散および類似度の計算

• 埋め込みと発散の初期化

• カルバック・ライブラー ダイバージェンスの勾配降下

データの準備

はじめに tsne は、NaN 値が含まれている行を入力データ X から削除します。そして、名前と値のペア Standardize が true の場合、tsne は各列の平均を減算することにより X をセンタリングし、列を標準偏差で除算することにより X をスケーリングします。

原著者の van der Maaten と Hinton [1] は、主成分分析 (PCA) を使用して元のデータ X を低次元データに縮小することを推奨しています。tsne の名前と値のペア NumPCAComponents は、50 など任意の次元数に設定できます。このステップをより細かく制御するには、関数 pca を使用してデータを前処理します。

距離、ガウス分散および類似度の計算

前処理の後で、tsne は X 内の点 x_i および x_j の各ペア間の距離 d(x_i,x_j) を計算します。名前と値のペア Distance を使用して、さまざまな距離計量を選択できます。既定では、tsne は標準のユークリッド尺度を使用します。tsne は、以後の計算で距離計量の 2 乗を使用します。

次に、tsne は X の各行 i について、行 i の "パープレキシティ" が名前と値のペア Perplexity と等しくなるように標準偏差 σ_i を計算します。パープレキシティは、モデル ガウス分布に関して次のように定義されます。van der Maaten と Hinton[1]が説明しているように、"データ点 x_i に対するデータ点 x_j の類似度は、x_i でガウス分布がセンタリングされた状態で確率密度に比例して近傍が選択された場合に x_i が x_j を近傍として選択する条件付き確率 $$p_{j|i}$$ である。近接するデータ点どうしの場合 $$p_{j|i}$$ は比較的大きく、遠く離れたデータ点どうしの場合 $$p_{j|i}$$ は (妥当な値のガウス分布の分散 σ_i に対して) ほぼ無限小になる"。

与えられた i に対する j の条件付き確率を次のように定義します。

$$\begin{array}{l}{p}_{j|i}=\frac{\exp \left(-d{\left(x_i,x_j\right)}^2/\left(2{\sigma }_i^2\right)\right)}{{\displaystyle \sum _{k\ne i}\exp \left(-d{\left(x_i,x_k\right)}^2/\left(2{\sigma }_i^2\right)\right)}}\\ p_{i|i}=0.\end{array}$$

次に、条件付き確率を対称化することにより結合確率 p_ij を定義します。

$$p_{ij}=\frac{p_{j|i}+p_{i|j}}{2N},$$

(1)

ここで、N は X の行数です。

この分布では、まだ名前と値のペア Perplexity に関して標準偏差 σ_i が定義されていません。データ点 x_i が与えられた場合の他のすべてのデータ点における条件付き確率分布を P_i で表すとします。この分布のパープレキシティは次のようになります。

$$\text{perplexity}\left(P_i\right)=2^{H\left(P_i\right)},$$

ここで、H(P_i) は P_i のシャノン エントロピーです。

$$H\left(P_i\right)=-{\displaystyle \sum _j{p}_{j|i}{\log }_2\left(p_{j|i}\right)}.$$

パープレキシティは、点 i の有効な近傍の個数の尺度です。tsne は、各点 i の複雑さを決定するため、σ_i に対する二分探索を実行します。

埋め込みと発散の初期化

X 内の点を低次元空間に埋め込むため、tsne は最適化を実行します。tsne は、X 内の点のモデル ガウス分布と低次元空間における点 Y のスチューデントの t 分布の間のカルバック・ライブラー ダイバージェンスを最小化しようとします。

最小化手順は、点 Y の初期集合で始まります。既定では、tsne はランダムなガウス分布の点として点を作成します。これらの点を作成して tsne の名前と値のペア 'InitialY' に含めることもできます。この場合、tsne は Y 内の点の各ペア間の類似度を計算します。

点 y_i と点 y_j の距離の分布の確率モデル q_ij は次のようになります。

$$\begin{array}{l}{q}_{ij}=\frac{{\left(1+{\Vert y_i-y_j\Vert }^2\right)}^{-1}}{{\displaystyle \sum _k{\displaystyle \sum _{l\ne k}{\left(1+{\Vert y_k-y_l\Vert }^2\right)}^{-1}}}}\\ q_{ii}=0.\end{array}$$

この定義と 式 1 で与えられる X 内の距離のモデルを使用すると、同時分布 P および Q の間のカルバック・ライブラー ダイバージェンスは次のようになります。

$$KL(P||Q)={\displaystyle \sum _j{\displaystyle \sum _{i\ne j}{p}_{ij}\log \frac{p_{ij}}{q_{ij}}}.}$$

この定義の結果については、有用な非線形変形を参照してください。

カルバック・ライブラー ダイバージェンスの勾配降下

カルバック・ライブラー ダイバージェンスを最小化するため、'exact' アルゴリズムでは修正された勾配降下手順を使用します。発散の Y 内の点に関する勾配は次のようになります。

$$\frac{\partial KL(P||Q)}{\partial y_i}=4{\displaystyle \sum _{j\ne i}Z\left(p_{ij}-q_{ij}\right)q_{ij}\left(y_i-y_j\right)},$$

ここで、正規化項は次のとおりです。

$$Z={\displaystyle \sum _k{\displaystyle \sum _{l\ne k}{\left(1+{\Vert y_k-y_l\Vert }^2\right)}^{-1}}}.$$

変更された勾配降下アルゴリズムでは、いくつかの調整パラメーターを使用して、適切な局所的最小値を求めようとします。

• 'Exaggeration' — 勾配降下の最初の 99 ステップで、tsne は式 1の確率 p_ij と強調値を乗算します。このステップは、出力 Y 内のクラスター間に、より多くの空間を作成する傾向があります。

• 'LearnRate' — tsne は、勾配降下反復の収束を改善するために適応学習を使用します。降下アルゴリズムには、降下の前回のステップと現在の勾配の線形結合である反復ステップがあります。'LearnRate' は、線形結合に対する現在の勾配の乗数です。詳細については、Jacobs [3] を参照してください。

t-SNE の Barnes-Hut バリエーション

t-SNE アルゴリズムを高速化しメモリ使用量を削減するため、tsne には近似最適化法があります。Barnes-Hut アルゴリズムでは、近接点をグループ化して、t-SNE 最適化ステップの複雑さとメモリ使用量を削減します。Barnes-Hut アルゴリズムは、厳密なオプティマイザーではなく近似オプティマイザーです。速度と精度のトレードオフに影響を与える非負の調整パラメーター Theta があります。'Theta' の値が大きくなると最適化が高速になりますが、結果の精度は低下します。このアルゴリズムは、範囲 (0.2,0.8) では 'Theta' の値の影響をあまり受けません。

Barnes-Hut アルゴリズムでは、低次元空間で近接点をグループ化し、これらのグループに基づいて近似勾配降下を実行します。考え方は、元々は天体物理学で使用されていたもので、近接点どうしでは勾配が似ているので計算を単純化できる、というものです。

van der Maaten [2] を参照してください。

t-SNE の特徴

• 埋め込みを使用して新しいデータを分類することはできない

• パフォーマンスがデータ サイズとアルゴリズムに依存

• 有用な非線形変形

埋め込みを使用して新しいデータを分類することはできない

多くの場合に t-SNE はデータ クラスターを十分に分離するので、t-SNE は新しいデータ点を分類できるように思われます。しかし、t-SNE は新しいデータ点を分類できません。t-SNE の埋め込みは、データに依存する非線形写像です。低次元空間で新しい点を埋め込むために前の埋め込みを写像として使用することはできません。代わりに、アルゴリズム全体を再度実行します。

パフォーマンスがデータ サイズとアルゴリズムに依存

t-SNE では、データを処理するために多くの時間がかかる可能性があります。D 次元にある N 個のデータ点を Y 次元に写像する場合、

• 厳密な t-SNE では、D*N² 回のオーダーの演算を行います。

• Barnes-Hut t-SNE では、D*Nlog(N)*exp(dimension(Y)) 回のオーダーの演算を行います。

したがって、N が 1000 を超えるような大規模なデータ セットで埋め込み次元 Y が 2 または 3 である場合、Barnes-Hut アルゴリズムは厳密なアルゴリズムより高速になる可能性があります。

有用な非線形変形

t-SNE では、変形された低次元の類似物に高次元の距離を写像します。次の図に示されているように、低次元空間におけるスチューデントの t 分布の方が裾が広いので、多くの場合 tsne は、高次元と比較して近くにある点をより近くに、遠くにある点をより遠くに移動します。この図には、密度が 0.25 および 0.025 になる点におけるガウス分布とスチューデントの t 分布の両方が示されています。ガウス密度は高次元の距離に、t 密度は低次元の距離に関連します。t 密度は、ガウス密度と比較して近くにある点がより近くに、遠くにある点がより遠くになることに相当します。

t = linspace(0,5);
y1 = normpdf(t,0,1);
y2 = tpdf(t,1);
plot(t,y1,'k',t,y2,'r')
hold on
x1 = fzero(@(x)normpdf(x,0,1)-0.25,[0,2]);
x2 = fzero(@(x)tpdf(x,1)-0.25,[0,2]);
z1 = fzero(@(x)normpdf(x,0,1)-0.025,[0,5]);
z2 = fzero(@(x)tpdf(x,1)-0.025,[0,5]);
plot([0,x1],[0.25,0.25],'k-.')
plot([0,z2],[0.025,0.025],'k-.')
plot([x1,x1],[0,0.25],'g-',[x2,x2],[0,0.25],'g-')
plot([z1,z1],[0,0.025],'g-',[z2,z2],[0,0.025],'g-')
text(1.1,.25,'Close points are closer in low-D')
text(2.4,.05,'Far points are farther in low-D')
legend('Gaussian(0,1)','Student t (df = 1)')
xlabel('x')
ylabel('Density')
title('Density of Gaussian(0,1) and Student t (df = 1)')
hold off

この変形は、当てはまる場合は有用です。ガウス分散が大きい (ガウス分布のピークが小さくなり分布が平らになる) 場合などでは、これは当てはまりません。このような場合、tsne は近くにある点を元の空間より遠くに移動する可能性があります。有用な変形を実現するには、

• 名前と値のペア 'Verbose' を 2 に設定する。

• 報告される分散の範囲が 1 より大きく離れず、平均分散が約 1 になるように、名前と値のペア 'Perplexity' を調整する。

この範囲の分散を実現できる場合、図が当てはまり、tsne の変形が有用になります。

効果的に tsne を調整する方法については、Wattenberg, Viegas and Johnson [4] を参照してください。

参照

[1] van der Maaten, Laurens, and Geoffrey Hinton. "Visualizing Data using t-SNE." J. Machine Learning Research 9, 2008, pp. 2579–2605.

[2] van der Maaten, Laurens. Barnes-Hut-SNE. arXiv:1301.3342 [cs.LG], 2013.

[3] Jacobs, Robert A. "Increased rates of convergence through learning rate adaptation." Neural Networks 1.4, 1988, pp. 295–307.

[4] Wattenberg, Martin, Fernanda Viégas, and Ian Johnson. "How to Use t-SNE Effectively." Distill, 2016. Available at How to Use t-SNE Effectively.

関連する例

• t-SNE の使用による高次元データの可視化
• t-SNE の出力関数
• tsne の設定

詳細

• 主成分分析 (PCA)
• 古典的多次元尺度構成法
• 因子分析