T分布型確率的近傍埋め込み法のソースを表示

{{DISPLAYTITLE:''t''分布型確率的近傍埋め込み法}}
{{machine learning bar}}
'''t分布型確率的近傍埋め込み法'''（ティーぶんぷかくりつてききんぼううめこみほう、{{lang-en|t-distributed Stochastic Neighbor Embedding}}、略称: '''t-SNE'''）は、高次元データの個々のデータ点に2次元または3次元マップ中の位置を与えることによって可視化のための統計学的手法である。サム・ロウェイス<!--Sam Roweis-->と[[ジェフリー・ヒントン]]により最初に開発された確率的近傍埋め込み法<ref name=SNE>{{cite conference|author1-last=Roweis|author1-first=Sam| author2-last=Hinton|author2-first=Geoffrey|conference=[[Neural Information Processing Systems]]|title=Stochastic neighbor embedding|date= January 2002 |url=https://cs.nyu.edu/~roweis/papers/sne_final.pdf}}</ref>を基にしており、ラウレンス・ファン・デル・マーテン<!--Laurens van der Maaten-->が[[t分布]]版を提唱した<ref name=MaatenHinton>{{cite journal|last=van der Maaten|first=L.J.P.|author2=Hinton, G.E. |title=Visualizing Data Using t-SNE|journal=Journal of Machine Learning Research |volume=9|date=Nov 2008|pages=2579–2605|url=http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf}}</ref>。高次元データの可視化のため2次元または3次元の低次元空間へ埋め込みに最適な[[非線形次元削減]]手法である。具体的には、高次元のデータ集合を2次元または3次元へ配置する際に、高い確率で類似した集合が近傍に、異なる集合が遠方となるように対応付ける。

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

t-SNEは、[[コンピュータセキュリティ]]研究<ref>{{cite journal|last=Gashi|first=I.|author2=Stankovic, V. |author3=Leita, C. |author4=Thonnard, O. |title=An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines|journal=Proceedings of the IEEE International Symposium on Network Computing and Applications|year=2009|pages=4–11}}</ref>、音楽分析<ref>{{cite journal|last=Hamel|first=P.|author2=Eck, D. |title=Learning Features from Music Audio with Deep Belief Networks|journal=Proceedings of the International Society for Music Information Retrieval Conference|year=2010|pages=339–344}}</ref>、癌研究,<ref>{{cite journal|last=Jamieson|first=A.R.|author2=Giger, M.L. |author3=Drukker, K. |author4=Lui, H. |author5=Yuan, Y. |author6=Bhooshan, N. |title=Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE|journal=Medical Physics  |issue=1|year=2010|pages=339–351|doi=10.1118/1.3267037|pmid=20175497|volume=37|pmc=2807447}}</ref>、[[バイオインフォマティクス]]<ref>{{cite journal|last=Wallach|first=I.|author2=Liliean, R. |title=The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding|journal=Bioinformatics |year=2009|pages=615–620|doi=10.1093/bioinformatics/btp035|volume=25|issue=5|pmid=19153135}}</ref>、および生物医学信号処理<ref>{{Cite book|last=Birjandtalab|first=J.|last2=Pouyan|first2=M. B.|last3=Nourani|first3=M.|date=2016-02-01|title=Nonlinear dimension reduction for EEG-based epileptic seizure detection|url=http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7455968|journal=2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI)|pages=595–598|doi=10.1109/BHI.2016.7455968|isbn=978-1-5090-2455-1}}</ref>を含む、幅広い応用の可視化に利用されている。[[人工ニューラルネットワーク]]によって学習された高レベルの表現の可視化にもよく使用される<ref>[https://colah.github.io/posts/2015-01-Visualizing-Representations/ ''Visualizing Representations: Deep Learning and Human Beings'' Christopher Olah's blog, 2015]</ref>。

多くの場合、t-SNEで表示された図ではクラスターが見えるが、可視化されたクラスターは選択したパラメータにより強く影響される可能性があるため、t-SNEのパラメータをよく理解することが必要である。そのような「クラスター」は、非クラスターのデータにも現れることがあり<ref>{{Cite web|url=https://stats.stackexchange.com/a/264647|title=K-means clustering on the output of t-SNE|last=|first=|date=|website=Cross Validated|archive-url=|archive-date=|dead-url=|access-date=2019-04-06}}</ref>、したがって誤った発見かもしれない。したがって、パラメータを選択して結果を検証を繰り返す探索が必要となる可能性がある<ref>{{Cite journal|last=Pezzotti|first=Nicola|last2=Lelieveldt|first2=Boudewijn P. F.|last3=Maaten|first3=Laurens van der|last4=Hollt|first4=Thomas|last5=Eisemann|first5=Elmar|last6=Vilanova|first6=Anna|date=2017-07-01|title=Approximated and User Steerable tSNE for Progressive Visual Analytics|url=http://ieeexplore.ieee.org/document/7473883/|journal=IEEE Transactions on Visualization and Computer Graphics|language=en-US|volume=23|issue=7|pages=1739–1752|doi=10.1109/tvcg.2016.2570755|pmid=28113434|issn=1077-2626}}</ref><ref>{{cite web|url=https://distill.pub/2016/misread-tsne/|title=How to Use t-SNE Effectively|last=Wattenberg|first=Martin|last2=Viégas|first2=Fernanda|date=2016-10-13|publisher=Distill|language=English|accessdate=2019-04-06|last3=Johnson|first3=Ian}}</ref>。t-SNEはよく分離されたクラスターを復元できることが多く、特別なパラメーターを選択により単純な形の{{仮リンク|スペクトタルクラスタリング|en|Spectral clustering|label=スペクトルクラスター}}形状を近似することが実証されている。<ref>{{cite arxiv|last=Linderman|first=George C.|last2=Steinerberger|first2=Stefan|date=2017-06-08|title=Clustering with t-SNE, provably|eprint=1706.02582|class=cs.LG}}</ref>

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

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

最初に高次元のデータ集合について各対の類似度を計算する。ファン・デル・マーテンとヒントンは「データ点<math>x_i</math>に対してデータ点<math>x_j</math>が<math>x_i</math>を中心とする[[ガウス分布]]の確率密度分布に比例して選ばれるならば、<math>x_j</math>と<math>x_i</math>の類似度は条件付き確率<math>p_{j|i}</math>と表される」<ref name=MaatenHinton/>と説明した。
: <math>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)},</math>
ただし同じ点の対に対しては<math>p_{i\mid i}=0</math>となる。

<math>\sigma_i</math>はガウス分布の偏差で、次のパープレキシティの関係式を満たす偏差<math>\sigma_i</math>を[[二分法]]により求める。

: <math>Perp(P_i) =2^{H(P_i)}</math>
: <math>H(P_i)=-\sum_j p_{j\mid i} \log_{2} p_{j\mid i} </math>

ここで<math>H(P_i)</math> は[[シャノンエントロピー]]である。密集していてデータ集合空間が小さければ<math>\sigma_i</math>は小さい値となる。

次に同時確率<math>p_{ij}</math>を次の式で求める。
: <math>p_{ij} = \frac{p_{j\mid i} + p_{i\mid j}}{2N}</math>
ただし<math> i = j </math> の場合は0となる。  <math>p_{ii} = 0 </math>

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

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

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

自由度1の[[t分布]]（[[コーシー分布]]）を利用した同時確率。
: <math>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}}</math>

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

<math>p_{ij}</math>の分布Pと<math>q_{ij}</math>の分布Qについてのカルバック・ライブラー情報量を目的関数とし、最小となる解<math>Y^{(t)}</math>求める。
: <math>KL(P||Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}</math>

各iについて目的関数の勾配を計算する。
: <math>\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} </math>

目的関数の勾配と以前の解よりt番目の解<math>Y^{(t)}</math>を計算する。
: <math>Y^{(t)}=Y^{(t-1)}+\eta \frac{\delta C}{\delta Y} + \alpha (t) \left( Y^{(t-1)} - Y^{(t-2)}  \right) </math>

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

== 弱点 ==
* 一般的な次元削減課題をどのように実行するかが不明確である。
* 比較的局所的な性質によりデータの固有次元の呪いに敏感になる。
** ガウス関数はユークリッド距離 <math>\lVert x_i-x_j \rVert</math>を使用しているため、[[次元の呪い]]の影響を受け、高次元でデータを距離により区別する能力が失われる。<math>p_{ij}</math>はほとんど同じ値となる（高次元で定数に漸近する）。これを軽減するために、各点の固有の次元に基づいて、冪乗変換により距離を調節する手法が提案されている。<ref>{{Cite conference|last=Schubert|first=Erich|last2=Gertz|first2=Michael|date=2017-10-04|title=Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection|conference=SISAP 2017 – 10th International Conference on Similarity Search and Applications|pages=188–203|doi=10.1007/978-3-319-68474-1_13}}</ref>
* t目的関数の大域的最小値への収束が保証されていない。
** 同じアルゴリズムパラメータでも得られる解が異なることがある。

== 脚注 ==
{{reflist}}

== 外部リンク ==
*  https://lvdmaaten.github.io/tsne/ ラウレンス・ファン・デル・マーテンによるt分布型確率的近傍埋め込み法の解説
* [https://www.youtube.com/watch?v=RJVL80Gg3lA Visualizing Data Using t-SNE], t-SNEに関するGoogle Tech Talk

{{DEFAULTSORT:ていいふんふかたかくりつてききんほううめこみほう}}

[[Category:次元削減]]
[[Category:機械学習]]
[[Category:データ分析]]
[[Category:数学に関する記事]]