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 ]など、幅広いアプリケーションで可視化に使用され}ています。

データセットの場合${\displaystyle n}$要素、t-SNEは${\displaystyle O(n^{2})}$時間と${\displaystyle O(n^{2})}$空間。^{[ 11 ]}

与えられたセット${\displaystyle N}$高次元オブジェクト$\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{N}}$t-SNEはまず確率を計算します${\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}$。

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

定義

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

これは次のような動機によるものです。 ${\displaystyle p_{i}}$そして ${\displaystyle p_{j}}$ N個のサンプルから1/Nと推定されるため、条件付き確率は次のように表すことができます。 ${\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 ]}

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

t-SNEは、${\displaystyle d}$次元マップ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N}}$（と$\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d}}$そして${\displaystyle d}$通常は2つまたは3つに選ばれる）類似性を反映している ${\displaystyle p_{ij}}$可能な限り。この目的のために、類似性を測定します。$q_{ij}}$地図上の2点間${\displaystyle \mathbf {y} _{i}}$そして${\displaystyle \mathbf {y} _{j}}$非常に似たアプローチを使用しています。具体的には、${\displaystyle i\neq j}$、 定義する$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}}}}$

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

ポイントの位置${\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}}}}$

点に関するカルバック・ライブラー情報量の最小化${\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は、t-SNEを厳密解とBarnes-Hut近似の両方で実装しています。
• 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 を使用したデータ可視化、Google Tech Talk による t-SNE について
• 様々な言語におけるt-SNEの実装、Laurens van der Maaten氏が管理するリンク集