t分布ぶんぷ型がた確かく率りつ的てき近傍きんぼう埋うめ込こみ法ほう

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

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

t-SNEは、コンピュータセキュリティ研究けんきゅう、音楽おんがく分析ぶんせき、癌がん研究けんきゅう,、バイオインフォマティクス、および生物せいぶつ医学いがく信号しんごう処理しょりを含ふくむ、幅広はばひろい応用おうようの可視かし化かに利用りようされている。人工じんこうニューラルネットワークによって学習がくしゅうされた高こうレベルの表現ひょうげんの可視かし化かにもよく使用しようされる。

多おおくの場合ばあい、t-SNEで表示ひょうじされた図ずではクラスターが見みえるが、可視かし化かされたクラスターは選択せんたくしたパラメータにより強つよく影響えいきょうされる可能かのう性せいがあるため、t-SNEのパラメータをよく理解りかいすることが必要ひつようである。そのような「クラスター」は、非ひクラスターのデータにも現あらわれることがあり、したがって誤あやまった発見はっけんかもしれない。したがって、パラメータを選択せんたくして結果けっかを検証けんしょうを繰くり返かえす探索たんさくが必要ひつようとなる可能かのう性せいがある。t-SNEはよく分離ぶんりされたクラスターを復元ふくげんできることが多おおく、特別とくべつなパラメーターを選択せんたくにより単純たんじゅんな形かたちのスペクトルクラスター形状けいじょうを近似きんじすることが実証じっしょうされている。

詳細しょうさい

高こう次元じげんの$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}$と表あらわされる」と説明せつめいした。

$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}$はほとんど同おなじ値ちとなる（高こう次元じげんで定数ていすうに漸近ぜんきんする）。これを軽減けいげんするために、各かく点てんの固有こゆうの次元じげんに基もとづいて、冪べき乗じょう変換へんかんにより距離きょりを調節ちょうせつする手法しゅほうが提案ていあんされている。
• t目的もくてき関数かんすうの大域たいいき的てき最小さいしょう値ちへの収束しゅうそくが保証ほしょうされていない。
  • 同おなじアルゴリズムパラメータでも得えられる解かいが異ことなることがある。

外部がいぶリンク

• https://lvdmaaten.github.io/tsne/ ラウレンス・ファン・デル・マーテンによるt分布ぶんぷ型がた確かく率りつ的てき近傍きんぼう埋うめ込こみ法ほうの解説かいせつ
• Visualizing Data Using t-SNE, t-SNEに関かんするGoogle Tech Talk