t分布型確率的近傍埋め込み法

t分布型確率的近傍埋め込み法（ティーぶんぷかくりつてききんぼううめこみほう、英語: t-distributed Stochastic Neighbor Embedding、略称: t-SNE）は、高次元データの個々のデータ点に2次元または3次元マップ中の位置を与えることによって可視化のための統計学的手法である。サム・ロウェイスとジェフリー・ヒントンにより最初に開発された確率的近傍埋め込み法^[1]を基にしており、ラウレンス・ファン・デル・マーテンがt分布版を提唱した^[2]。高次元データの可視化のため2次元または3次元の低次元空間へ埋め込みに最適な非線形次元削減手法である。具体的には、高次元のデータ集合を2次元または3次元へ配置する際に、高い確率で類似した集合が近傍に、異なる集合が遠方となるように対応付ける。

t-SNEのアルゴリズムは主に2つの段階で構成される。第一に、高次元データの各対について類似する集合が選択される可能性が高く、一方で異なる集合が選択される可能性が極めて小さくなるように確率分布を構築する。第二に、低次元マップ上の集合について同様な確率分布を定義し、2つの分布間のカルバック・ライブラー情報量を最小化する低次元マップ内の点の位置を求める。元のアルゴリズムは二点の類似度の指標にユークリッド距離を使用しているが、これは必要に応じ適切に変更する必要がある。

t-SNEは、コンピュータセキュリティ研究^[3]、音楽分析^[4]、癌研究,^[5]、バイオインフォマティクス^[6]、および生物医学信号処理^[7]を含む、幅広い応用の可視化に利用されている。人工ニューラルネットワークによって学習された高レベルの表現の可視化にもよく使用される^[8]。

多くの場合、t-SNEで表示された図ではクラスターが見えるが、可視化されたクラスターは選択したパラメータにより強く影響される可能性があるため、t-SNEのパラメータをよく理解することが必要である。そのような「クラスター」は、非クラスターのデータにも現れることがあり^[9]、したがって誤った発見かもしれない。したがって、パラメータを選択して結果を検証を繰り返す探索が必要となる可能性がある^[10]^[11]。t-SNEはよく分離されたクラスターを復元できることが多く、特別なパラメーターを選択により単純な形のスペクトルクラスター（英語版）形状を近似することが実証されている。^[12]

詳細

高次元の $N$ 個のデータ集合 $\mathbf {x} _{1},\dots ,\mathbf {x} _{N}$ 与えられているとする。高次元データ集合の類似度の特徴を反映した低次元上に表現された $N$ 個のデータ集合 $Y$ ( $\mathbf {y} _{1},\dots ,\mathbf {y} _{N}$ ) を求めるのが目的である。

t-SNEのパラメータとしてコスト関数のパラメータのパープレキシティ (perplexity) と最適化のパラメーターの反復計算回数 $T$ 、学習率 $\eta$ 、モーメンタム $\alpha (t)$ をそれぞれ与える。ファン・デル・マーテンによればt-SNEの性能は異なるパープレキシティの設定に対してはかなり頑健で、最適なパープレキシティは使用するデータにより異なるが典型的には5から50までの間の値が用いられる。

最初に高次元のデータ集合について各対の類似度を計算する。ファン・デル・マーテンとヒントンは「データ点 $x_{i}$ に対してデータ点 $x_{j}$ が $x_{i}$ を中心とするガウス分布の確率密度分布に比例して選ばれるならば、 $x_{j}$ と $x_{i}$ の類似度は条件付き確率 $p_{j|i}$ と表される」^[2]と説明した。

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})}},

ただし同じ点の対に対しては $p_{i\mid i}=0$ となる。

$\sigma _{i}$ はガウス分布の偏差で、次のパープレキシティの関係式を満たす偏差 $\sigma _{i}$ を二分法により求める。

Perp(P_{i})=2^{H(P_{i})}

H(P_{i})=-\sum _{j}p_{j\mid i}\log _{2}p_{j\mid i}

ここで $H(P_{i})$ はシャノンエントロピーである。密集していてデータ集合空間が小さければ $\sigma _{i}$ は小さい値となる。

次に同時確率 $p_{ij}$ を次の式で求める。

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

ただし $i=j$ の場合は0となる。 $p_{ii}=0$

平均0のガウス分布の無作為標本を初期解 $Y^{(0)}$ とする。

最後にt=1からt=Tまで以下の手順をT回の繰り返しにより解 $Y^{(T)}$ を求める。

t-1番目の解 $Y^{(t-1)}$ に対する低次元上の類似度を計算する。

自由度1のt分布（コーシー分布）を利用した同時確率。

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

ただし同じ点の対に対しては0とする。 $q_{ii}=0$

$p_{ij}$ の分布Pと $q_{ij}$ の分布Qについてのカルバック・ライブラー情報量を目的関数とし、最小となる解 $Y^{(t)}$ 求める。

KL(P||Q)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}

各iについて目的関数の勾配を計算する。

{\frac {\delta C}{\delta y_{i}}}=4\sum _{j}(p_{ij}-q_{ij})(y_{i}-y_{j})(1+\lVert y_{i}-y_{j}\rVert ^{2})^{-1}

目的関数の勾配と以前の解よりt番目の解 $Y^{(t)}$ を計算する。

Y^{(t)}=Y^{(t-1)}+\eta {\frac {\delta C}{\delta Y}}+\alpha (t)\left(Y^{(t-1)}-Y^{(t-2)}\right)

解 $Y^{(T)}$ を図示することで高次元のデータ集合のクラスターを把握できる。

弱点

一般的な次元削減課題をどのように実行するかが不明確である。
比較的局所的な性質によりデータの固有次元の呪いに敏感になる。
- ガウス関数はユークリッド距離 $\lVert x_{i}-x_{j}\rVert$ を使用しているため、次元の呪いの影響を受け、高次元でデータを距離により区別する能力が失われる。 $p_{ij}$ はほとんど同じ値となる（高次元で定数に漸近する）。これを軽減するために、各点の固有の次元に基づいて、冪乗変換により距離を調節する手法が提案されている。^[13]
t目的関数の大域的最小値への収束が保証されていない。
- 同じアルゴリズムパラメータでも得られる解が異なることがある。

脚注

^ Roweis, Sam; Hinton, Geoffrey (January 2002). Stochastic neighbor embedding (PDF). Neural Information Processing Systems.
^ ^a ^b van der Maaten, L.J.P.; Hinton, G.E. (Nov 2008). “Visualizing Data Using t-SNE”. Journal of Machine Learning Research 9: 2579–2605.
^ Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. (2009). “An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines”. Proceedings of the IEEE International Symposium on Network Computing and Applications: 4–11.
^ Hamel, P.; Eck, D. (2010). “Learning Features from Music Audio with Deep Belief Networks”. Proceedings of the International Society for Music Information Retrieval Conference: 339–344.
^ Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N. (2010). “Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE”. Medical Physics 37 (1): 339–351. doi:10.1118/1.3267037. PMC 2807447. PMID 20175497.
^ Wallach, I.; Liliean, R. (2009). “The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding”. Bioinformatics 25 (5): 615–620. doi:10.1093/bioinformatics/btp035. PMID 19153135.
^ Birjandtalab, J.; Pouyan, M. B.; Nourani, M. (2016-02-01). Nonlinear dimension reduction for EEG-based epileptic seizure detection. 595–598. doi:10.1109/BHI.2016.7455968. ISBN 978-1-5090-2455-1
^ Visualizing Representations: Deep Learning and Human Beings Christopher Olah's blog, 2015
^ “K-means clustering on the output of t-SNE”. Cross Validated. 2019年4月6日閲覧。
^ Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna (2017-07-01). “Approximated and User Steerable tSNE for Progressive Visual Analytics” (英語). IEEE Transactions on Visualization and Computer Graphics 23 (7): 1739–1752. doi:10.1109/tvcg.2016.2570755. ISSN 1077-2626. PMID 28113434.
^ Wattenberg, Martin (2016年10月13日). “How to Use t-SNE Effectively” (English). Distill. 2019年4月6日閲覧。
^ Linderman, George C.; Steinerberger, Stefan (8 June 2017). "Clustering with t-SNE, provably". arXiv:1706.02582 [cs.LG]。
^ Schubert, Erich; Gertz, Michael (4 October 2017). Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection. SISAP 2017 – 10th International Conference on Similarity Search and Applications. pp. 188–203. doi:10.1007/978-3-319-68474-1_13。

外部リンク

https://lvdmaaten.github.io/tsne/ ラウレンス・ファン・デル・マーテンによるt分布型確率的近傍埋め込み法の解説
Visualizing Data Using t-SNE, t-SNEに関するGoogle Tech Talk

[SNE-1] Roweis, Sam; Hinton, Geoffrey (January 2002). Stochastic neighbor embedding (PDF). Neural Information Processing Systems.

[MaatenHinton-2] van der Maaten, L.J.P.; Hinton, G.E. (Nov 2008). “Visualizing Data Using t-SNE”. Journal of Machine Learning Research 9: 2579–2605.

[3] Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. (2009). “An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines”. Proceedings of the IEEE International Symposium on Network Computing and Applications: 4–11.

[4] Hamel, P.; Eck, D. (2010). “Learning Features from Music Audio with Deep Belief Networks”. Proceedings of the International Society for Music Information Retrieval Conference: 339–344.

[5] Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N. (2010). “Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE”. Medical Physics 37 (1): 339–351. doi:10.1118/1.3267037. PMC 2807447. PMID 20175497.

[6] Wallach, I.; Liliean, R. (2009). “The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding”. Bioinformatics 25 (5): 615–620. doi:10.1093/bioinformatics/btp035. PMID 19153135.

[7] Birjandtalab, J.; Pouyan, M. B.; Nourani, M. (2016-02-01). Nonlinear dimension reduction for EEG-based epileptic seizure detection. 595–598. doi:10.1109/BHI.2016.7455968. ISBN 978-1-5090-2455-1

[8] Visualizing Representations: Deep Learning and Human Beings Christopher Olah's blog, 2015

[9] “K-means clustering on the output of t-SNE”. Cross Validated. 2019年4月6日閲覧。

[10] Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna (2017-07-01). “Approximated and User Steerable tSNE for Progressive Visual Analytics” (英語). IEEE Transactions on Visualization and Computer Graphics 23 (7): 1739–1752. doi:10.1109/tvcg.2016.2570755. ISSN 1077-2626. PMID 28113434.

[11] Wattenberg, Martin (2016年10月13日). “How to Use t-SNE Effectively” (English). Distill. 2019年4月6日閲覧。

[12] Linderman, George C.; Steinerberger, Stefan (8 June 2017). "Clustering with t-SNE, provably". arXiv:1706.02582 [cs.LG]。

[13] Schubert, Erich; Gertz, Michael (4 October 2017). Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection. SISAP 2017 – 10th International Conference on Similarity Search and Applications. pp. 188–203. doi:10.1007/978-3-319-68474-1_13。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]