t分布確率近傍埋め込み

t分布確率的近傍埋め込み（t-SNE）は、各データポイントに2次元または3次元マップ内の位置を与えることで高次元データを視覚化する統計的手法です。これは、もともとGeoffrey HintonとSam Roweisによって開発された確率的近傍埋め込みに基づいています^[1] 。Laurens van der MaatenとHintonは、t分布の変形を提案しました^[2]。これは、 2次元または3次元の低次元空間に視覚化するために高次元データを埋め込む非線形次元削減手法です。具体的には、各高次元オブジェクトを2次元または3次元のポイントでモデル化し、類似オブジェクトは近くのポイントでモデル化され、類似しないオブジェクトは離れたポイントでモデル化される可能性が高くなります。

t-SNE アルゴリズムは、2 つの主な段階から構成されます。まず、t-SNE は、類似するオブジェクトには高い確率が割り当てられ、類似しないポイントには低い確率が割り当てられるような方法で、高次元オブジェクトのペアに確率分布を構築します。次に、t-SNE は低次元マップのポイントに同様の確率分布を定義し、マップのポイントの位置に関して 2 つの分布間のKullback–Leibler ダイバージェンス(KL ダイバージェンス) を最小化します。元のアルゴリズムでは、類似性メトリックのベースとしてオブジェクト間のユークリッド距離を使用しますが、これは必要に応じて変更できます。リーマン変種はUMAPです。

t-SNEは、ゲノミクス、コンピュータセキュリティ研究、^[3] 自然言語処理、音楽分析、^[4] 癌研究、^[5] バイオインフォマティクス、^[6]地質学的領域解釈、^{[7] [8] [9]}および生物医学信号処理^{[10]など、幅広いアプリケーションでの可視化に使用されています。}

n要素のデータセットの場合、t-SNEはO( n2 )時間で実行され、^O ( n2 )の^空間を必要とする。^[11]

高次元オブジェクトのセットが与えられると、t-SNE はまず、オブジェクトとの類似度に比例する確率を次のように計算します。 ${\displaystyle N}$${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{N}}$${\displaystyle p_{ij}}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle \mathbf {x} _{j}}$

について、定義する ${\displaystyle i\neq j}$

${\displaystyle p_{j\mid i}={\frac {\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{j}\rVert ^{2}/2\sigma _{i}^{2})}{\sum _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2}/2\sigma _{i}^{2})}}$

と設定します。上記の分母はすべての に対してを保証することに注意してください。 ${\displaystyle p_{i\mid i}=0}$${\displaystyle \sum _{j}p_{j\mid i}=1}$${\displaystyle i}$

ファンデルマーテンとヒントンは次のように説明しています。「データポイント間の類似性は、を中心とするガウス分布の下での確率密度に比例して近傍点が選択される場合に、 が近傍点として選択する条件付き確率 です。」^[2]${\displaystyle x_{j}}$${\displaystyle x_{i}}$${\displaystyle p_{j|i}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}}$

定義する

${\displaystyle p_{ij}={\frac {p_{j\mid i}+p_{i\mid j}}{2N}}}$

これは 、N 個のサンプルからのおよび が 1/N として推定されるため、条件付き確率は および と 記述できるためです 。 であるため、前の式を取得できます。 ${\displaystyle p_{i}}$${\displaystyle p_{j}}$${\displaystyle p_{i\mid j}=Np_{ij}}$${\displaystyle p_{j\mid i}=Np_{ji}}$${\displaystyle p_{ij}=p_{ji}}$

また、および にも注意してください 。 ${\displaystyle p_{ii}=0}$${\displaystyle -\sum _{i,j}p_{ij}=1}$

ガウスカーネル の帯域幅は、条件付き分布のエントロピーが二分法を使用して事前に定義されたエントロピーに等しくなるように設定されます。その結果、帯域幅はデータの密度に適応されます。つまり、データ空間の密度が高い部分では、より小さな値が使用されます。エントロピーはこの分布の複雑さとともに増加します。この関係は次のように表されます。 ${\displaystyle \sigma_{i}}$${\displaystyle \sigma_{i}}$${\displaystyle P_{i}}$

${\displaystyle Perp(P_{i})=2^{H(P_{i})}}$

シャノンエントロピーは どこにありますか${\displaystyle H(P_{i})}$${\displaystyle H(P_{i})=-\sum _{j}p_{j|i}\log _{2}p_{j|i}.}$

パープレキシティはt-SNEの手動で選択されたパラメータであり、著者らは「パープレキシティは、有効な近傍数の滑らかな尺度として解釈できます。SNEのパフォーマンスはパープレキシティの変化に対してかなり堅牢であり、典型的な値は5〜50です。」と述べています^[2]。

ガウスカーネルはユークリッド距離を使用するため、次元の呪いの影響を受け、高次元データでは距離が識別能力を失うと、非常に類似したものになります（漸近的には定数に収束します）。これを緩和するために、各ポイントの固有次元に基づいて、べき乗変換で距離を調整することが提案されています。^[12]${\displaystyle \lVert x_{i}-x_{j}\rVert }$${\displaystyle p_{ij}}$

t-SNEは、類似性を 可能な限り反映する次元マップ（ と は通常2または3に選択される）を学習することを目指しています。この目的のために、マップ内の2つの点と の間の類似性を、非常によく似たアプローチを使用して測定します。具体的には、 について、次のように 定義します。${\displaystyle d}$${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N}}$${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d}}$${\displaystyle d}$${\displaystyle p_{ij}}$${\displaystyle q_{ij}}$${\displaystyle \mathbf {y} _{i}}$${\displaystyle \mathbf {y} _{j}}$${\displaystyle i\neq j}$${\displaystyle q_{ij}}$

${\displaystyle q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1}}{\sum _{k}\sum _{l\neq k}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1}}}}$

そして と設定します。ここでは、低次元の点間の類似性を測定するために、裾の重いスチューデントのt分布（自由度は1で、コーシー分布と同じ）が使用され、異なるオブジェクトをマップ内で離れた場所にモデル化できるようになります。 ${\displaystyle q_{ii}=0}$

マップ上の点の位置は、分布 と分布の（非対称の）カルバック・ライブラー分布を最小化することによって決定されます。つまり、 ${\displaystyle \mathbf {y} _{i}}$${\displaystyle P}$${\displaystyle Q}$

${\displaystyle \mathrm {KL} \left(P\parallel Q\right)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}}$

点に関する Kullback–Leibler 情報量の最小化は、勾配降下法を使用して実行されます。この最適化の結果は、高次元の入力間の類似性を反映するマップです。 ${\displaystyle \mathbf {y} _{i}}$

t-SNE プロットはクラスターを表示することが多いように見えますが、視覚的なクラスターは選択されたパラメータ化 (特にパープレキシティ) によって大きく左右される可能性があるため、t-SNE のパラメータをよく理解する必要があります。このような「クラスター」は、明確なクラスタリングのない構造化データにも現れることがあり、^[13]誤った結果である可能性があります。同様に、t-SNE によって生成されるクラスターのサイズは有益ではなく、クラスター間の距離も同様です。^[14]したがって、パラメータを選択して結果を検証するには、対話型の探索が必要になる場合があります。^{[15] [16]} t-SNE は、十分に分離されたクラスターを回復できることが示されており、特別なパラメータを選択すると、単純な形式のスペクトル クラスタリングに近似します。^[17]

• Barnes-Hut の C++ 実装は、元の著者の 1 人の github アカウントで入手できます。
• R パッケージ Rtsne は、Rで t-SNE を実装します。
• ELKIにはtSNEが含まれており、Barnes-Hut近似も含まれています。
• Python の人気のある機械学習ライブラリであるscikit-learn は、正確な解と Barnes-Hut 近似の両方を使用して t-SNE を実装します。
• TensorFlowに関連する可視化キットである Tensorboardも t-SNE (オンライン版) を実装しています。
• JuliaパッケージTSneはt-SNEを実装している

• Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (2016-10-13). 「t-SNE を効果的に使用する方法」. Distill . 1 (10): e2. doi : 10.23915/distill.00002 . ISSN  2476-0757.インタラクティブなデモンストレーションとチュートリアル。
• t-SNE を使用したデータの視覚化、t-SNE に関する Google Tech Talk
• t-SNE のさまざまな言語での実装、Laurens van der Maaten が管理するリンク集