t-SNE

t-SNEとは

t-SNE(t-Distributed Stochastic Neighbor Embedding)は、高次元のデータを2次元や3次元の地図(map)に置き直し、人が目で見て構造をつかめるようにする次元削減の手法です。ファン・デル・マーテン(Laurens van der Maaten)とヒントン(Geoffrey Hinton)が、2008年の論文「Visualizing Data using t-SNE」(Journal of Machine Learning Research 第9巻)で提案しました。名前のtは、後で述べるスチューデントのt分布を指しています。

土台になったSNEの考え方

t-SNEの出発点はSNE(Stochastic Neighbor Embedding)です。SNEは、データ点どうしの高次元でのユークリッド距離をそのまま使うのではなく、類似度を表す条件付き確率に変換するところから始まります。データ点xjがxiにどれだけ似ているかは、xiがxjを自分の近傍として選ぶ確率p(j|i)として表します。距離の近い点ほど、この確率は大きくなります。

SNEから変えた2つの点

論文は、t-SNEのコスト関数がSNEと2つの点で異なると説明しています。

1つ目は、確率を対称化した(symmetrized)版を使うことです。xiから見たxjの近さと、xjから見たxiの近さを分けて扱うのではなく、点の組ごとの同時確率として扱います。

2つ目は、低次元空間で2点の類似度を計算するときに、ガウス分布ではなくスチューデントのt分布を使うことです。論文の言葉では、t-SNEは低次元空間における2点間の類似度の計算に、ガウス分布ではなくt分布を使う手法です。

2つの確率分布を近づける

t-SNEは、高次元空間での点の組の同時確率分布Pと、低次元の地図での同時確率分布Qを用意します。そのうえで、PとQの間のカルバック・ライブラー(Kullback-Leibler)ダイバージェンス、略してKLダイバージェンスが最小になるように、地図上の点の位置を求めます。KLダイバージェンスは2つの確率分布の食い違いを測る量です。これを小さくすることは、低次元の地図の上でも高次元での近さの関係をできるだけ再現しようとすることにあたります。

クラウディング問題とt分布

高次元のデータで、ある点のまわりの自然なクラスタに属する点を2次元のような低次元の地図に置くことを考えます。このとき、その点までの距離をすべて忠実に再現しようとすると、地図の中に十分な空間がありません。論文はこれをクラウディング問題(crowding problem)と呼んでいます。

t分布は、ガウス分布に比べて中心から離れたところでも確率が小さくなりにくい、裾の重い(heavy-tailed)分布です。t-SNEは低次元側にこの裾の重い分布を使うことで、クラウディング問題を緩和します。論文は、この変更がクラウディング問題と、SNEが抱えていた最適化上の問題の両方を和らげるとしています。