Main Content

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 から削除します。そして、名前と値のペア Standardizetrue の場合、tsne は各列の平均を減算することにより X をセンタリングし、列を標準偏差で除算することにより X をスケーリングします。

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

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

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

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

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

pj|i=exp(d(xi,xj)2/(2σi2))kiexp(d(xi,xk)2/(2σi2))pi|i=0.

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

pij=pj|i+pi|j2N,(1)

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

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

perplexity(Pi)=2H(Pi),

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

H(Pi)=jpj|ilog2(pj|i).

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

埋め込みと発散の初期化

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

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

yi と点 yj の距離の分布の確率モデル qij は次のようになります。

qij=(1+yiyj2)1klk(1+ykyl2)1qii=0.

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

KL(P||Q)=jijpijlogpijqij.

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

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

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

KL(P||Q)yi=4jiZ(pijqij)qij(yiyj),

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

Z=klk(1+ykyl2)1.

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

  • 'Exaggeration' — 勾配降下の最初の 99 ステップで、tsne式 1の確率 pij と強調値を乗算します。このステップは、出力 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*N2 回のオーダーの演算を行います。

  • 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

Figure contains an axes object. The axes object with title Density of Gaussian(0,1) and Student t (df = 1), xlabel x, ylabel Density contains 10 objects of type line, text. These objects represent Gaussian(0,1), Student t (df = 1).

この変形は、当てはまる場合は有用です。ガウス分散が大きい (ガウス分布のピークが小さくなり分布が平らになる) 場合などでは、これは当てはまりません。このような場合、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.

関連する例

詳細