t-SNE を用いた次元圧縮方法のご紹介

こんにちは。データ分析部の越水です。

以前、 弊社ブログ記事
高次元データの可視化の手法をSwiss rollを例に見てみよう
にて、高次元データの可視化手法を複数ご紹介いたしました。
今回は、 Kaggle などのデータコンペで最近注目を集めている可視化手法として、
t-SNE をご紹介したいと思います。

t-SNE は、高次元データの次元を圧縮するアルゴリズムであり、特に高次元データを可視化する際に有用です。
高次元データの関係性をうまく捉えられるという特徴があり、
最近 Kaggle などのデータコンペでよく用いられるようになりました。

t-SNE はどんな仕組みなのか?

t-SNE は SNE というアルゴリズムの改良版に当たります。
これらのアルゴリズムでは、(次元圧縮したい)高次元データx_iを低次元空間上の点y_iに対応付けます。その際、 高次元空間におけるデータ同士の「近さ(類似度)」が、低次元空間におけるデータ同士の「近さ」に反映されるよう学習を行う(y_iを変化させる)のです。
「近さ」の指標としてはユークリッド距離やコサイン類似度など様々なものがありますが、 SNE の大きな特徴としてこの「近さ」を確率分布によって表現することが挙げられます。

本記事ではまずは SNE のアルゴリズムを紹介し、それから t-SNE について紹介したいと思います。
厳密さよりも分かりやすさを重視した説明なので、詳細を知りたい方は原論文をご覧ください。

SNE のアルゴリズム

SNEでは、確率を用いて「近さ」を表現します。
具体的には、点 x_i を基準としたときの点 x_j までの距離を以下のように定義します。

  1. \sigma_i を計算する(計算方法は原論文参照)
  2. 平均 x_i ,分散 \sigma_i^2 の正規分布を考え、 x_i を基準としたとき x_j が抽出される条件付き確率 p_{j|i}
    p_{j|i} = \frac{\exp(-||x_i - x_j||^2 / 2\sigma_i^2)}{\sum_{k\neq i}\exp(-||x_i - x_k||^2 / 2\sigma_i^2)}, p_{i|i} = 0

    と定義する
  3. 上記の p_{j|i} を点 x_i を基準としたときの点 x_j までの距離と定義する
    同様に低次元空間上の点 y_i を基準としたときの点 y_j までの距離 q_{j|i} も以下のように定義されます。
    q_{j|i} = \frac{\exp(-||y_i - y_j||^2)}{\sum_{k\neq i}\exp(-||y_i - y_k||^2)}, q_{i|i} = 0

学習の目的を振り返ると、高次元空間上のデータ間の「近さ」と低次元空間上のデータ間の「近さ」を出来る限り同じ様にする事でした。つまり p_{j|i} , q_{j|i} を近づけてやればよいわけです。
p_{j|i}q_{j|i} はともに確率分布ですから、これらの間の距離を測る指標として、KL(カルバック・ライブラー)情報量を利用します。
このKL情報量を損失関数 C とし、 C が最小となる様に、最急降下法によって圧縮後の点 y_i の座標を更新していきます。


C = \sum_{i}\sum_{j}p_{j|i} \log \frac{p_{j|i}}{q_{j|i}}

t-SNE のアルゴリズム

SNE のアルゴリズムを紹介したところで、改良点に触れながら t-SNE を紹介していきたいと思います。
改良点は主に2点となります。

  • 圧縮後の確率分布にt分布を利用
  • 「近さ」の対称化

まず、 t 分布の導入に関して説明します。
SNE に限らず、高次元空間にあるデータポイントを低次元空間におけるデータポイントで表現する際、データポイント間の「近さ」を完全に一致させることは難しいです。
特に、 ||x_i-x_j|| が大きいほど y_j の配置され得る範囲が広くなってしまう問題があります。
圧縮後の空間では、圧縮前の空間上で近くにあるデータポイント同士が近くにまとまり、そうでないデータポイントはまとまりに混じらないように配置される事が理想なので、この問題の影響を極力排除する工夫が必要となります。

この問題に対処するため t-SNE では、圧縮後側の確率分布に正規分布ではなく自由度 1 の t 分布を想定します。
t 分布は正規分布に比べて裾が重いため、高次元空間において距離の遠いデータポイントのペアを、低次元空間でも遠くなるよう配置する事ができるのです。
t-sneのイメージ
次に、「近さ」の対称化に関して説明します。
SNE における条件付き確率の定義では、 p_{j|i}p_{i|j} が同じ値ではありませんでした。
つまり、 x_i から見た x_jx_j から見た x_i とで「近さ」の指標が違うという事です。
これによりKL情報量の最小化が難しくなってしまうという問題がありました。

t-SNE では、高次元データ上の「近さ」としては、学習時の影響を考慮して「対称化された条件付き確率」 p_{ij} を、圧縮後の低次元データ上の「近さ」としては、全ての点の組み合わせを考慮した同時確率 q_{ij} を利用します。

上記2点の改善点によって、最終的に利用される確率分布 p_{ij}q_{ij} 、 KL情報量は以下の様になります。


p_{ij} = \frac{p_{j|i}+p_{i|j}}{2N}
q_{ij} = \frac{(1+||y_i - y_j||^2)^{-1}}{\sum_{k,l,k\neq l}(1+||y_k - y_l||^2)^{-1}}, q_{ii} = 0
C = \sum_{i}\sum_{j}p_{ij} \log \frac{p_{ij}}{q_{ij}}

以上が、 t-SNE および SNE のアルゴリズムの概要です。

t-SNE を用いて、データ可視化を行う

それでは、実際に t-SNE を実行してみましょう。

t-SNE は様々なプログラミング言語に対応したパッケージが用意されています。
R などのパッケージで実装されているのは、通常の t-SNE を高速化した Barnes-Hut t-SNE と呼ばれる手法です。

この手法は、簡単に言えば、

  • 十分に離れている 2 点間の確率を 0 と近似
  • quadtree (3 次元に圧縮する場合は Octree) を用いて空間を分割し、同じセルに含まれている点はまとめて中心点で近似

という 2 つの近似により、通常の t-SNE よりも高速かつ省メモリで実行可能な手法です。

また、t-SNE のパッケージは、デフォルトで事前に PCA (主成分分析) を実行しています。
これは、事前に 30 次元ほどに落としてから t-SNE を行うことで計算時間を節約するためであり、原論文でも推奨されているテクニックです。

今回は、t-SNE と、比較のために PCA で可視化を試みます。

データセット

http://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php

今回、データセットは Coil-20 を使います。
Coil-20 は、20 種類の物体を 5 度ずつ角度を変えて撮影した画像データセットです。
画像は全て白黒であり、20 種類 × 72 = 1440 枚の画像が用意されています。
これらを 32 × 32 pixel に圧縮し、全 1024 区画のグレースケールを取得します。

この 1440 枚、 1024 次元のデータに対し、可視化を試みます。

PCA の実行結果

まず、PCA を実行した結果は下記のとおりです。

PCAの結果

散布図を見ると、各物体が混ざってしまっていて、
まったく分類できていないことがわかります。

PCA を実行する R コードは下記のとおりです。

# Coil-20 データセットの読み込み
coil20 <- read.csv("coil20_train.csv")
# PCA の実行
d_pca <- prcomp(coil20[,-ncol(coil20)], scale=TRUE)

# plot のための準備
coil20.levels <- levels(coil20$class)
coil20.levels.colors <- rainbow(length(coil20.levels))
coil20.idx <- sapply(coil20$class, function(cls){match(cls, coil20.levels)})
coil20.colors <- sapply(coil20.idx, function(idx){coil20.levels.colors[idx]})

# plot
par(mar=c(3,3,3,7))
plot(d_pca$x[,1:2], t='n', xlab='', ylab='')
text(d_pca$x[,1:2], labels=coil20.idx, col=coil20.colors)
par(xpd=T)
legend(par()$usr[2] + 0.2, par()$usr[4]
, legend=paste(as.character(seq(1,20)), coil20.levels, sep=": ")
, pch=16
, col=coil20.levels.colors
, cex=1.0)

t-SNE の実行結果

では、t-SNE を実行してみましょう。
下記のような実行結果が得られました。

t-SNEの実行結果

20 種の写真が、おおむね綺麗に分類できていることが分かります。

Coil-20 の画像データは、ひとつの物体を5度ずつ角度を変えて撮影したものです。
正面から撮った写真と、 360 度近くの回転をして撮った写真は、当然似た写真になります。
t-SNE では、そういった構造をループ状に表しており、
多次元空間での構造を低次元空間に表すことができていると考えられます。
なかなか面白い結果ですよね。

よく見ると、右上あたりに、いくつかの線状に連なっているものがありますね。。。
これらは、3 種のミニカーの写真のようです。

minicars

実際に写真を見ればわかりますが、
同じ車種で異なる角度のミニカーより、異なる車種でも同じ角度のミニカーのほうが、
類似した写真であるため、t-SNE では近い空間に配置されているというわけです。

t-SNE を実行する R コードは下記のとおりです。
上述の通り、t-SNE は様々なプログラミング言語に対応したパッケージが用意されており、
今回は {Rtsne} パッケージを使用しました。

実行は非常に簡単です。
{Rtsne} パッケージを読み込み、 Rtsne() 関数の引数にデータセットとオプションを指定するだけで実行できます。

# Rtsne パッケージの読み込み
# install.packeges("Rtsne") # インストール
library(Rtsne)

# t-SNE の実行
d_tsne.coil20 <- Rtsne(coil20[,-ncol(coil20)])

# plot
par(mar=c(3,3,3,7))
plot(d_tsne.coil20$Y, t='n', xlab='', ylab='')
text(d_tsne.coil20$Y, labels=coil20.idx, col=coil20.colors)
par(xpd=T)
legend(par()$usr[2] + 0.2, par()$usr[4]
, legend=paste(as.character(seq(1,20)), coil20.levels, sep=": ")
, pch=16
, col=coil20.levels.colors
, cex=1.0)

他の手法と比較するとどうなのか

原論文では、 Coil-20 データセットに対して Isomap や LLE など他の次元削減手法を適用した結果が掲載されています。
その結果を見ると、 t-SNE 以外はうまく可視化できていないことがわかります。

Isomap や LLE などの手法は、Swissroll のようなデータがつながっている構造を捉えるのは得意ですが、Coil-20 のようないくつかの部分に分かれているデータには不向きのようです。
t-SNE ではデータが分かれている構造をしていても有効なので、複数のクラスタがあるデータを可視化したいときには便利な手法であるといえるでしょう。

原論文の Supplemental Material には、
さらに他の手法と比較した結果も掲載されているので、興味のある方は是非ご覧ください。

おわりに

以上、t-SNE の紹介および実行結果でした。
高次元データの関係性をうまく捉えることができる手法であることをご理解いただけたと思います。

注意点として、t-SNE で圧縮する次元は、 2・3 次元が推奨されています。
4 次元や 5 次元でも計算できないことはないのですが、計算コストがかなり高くなってしまうので実用的ではありません。
そのため、 2・3 次元以外の次元に圧縮したい場合は別のアルゴリズムを用いるべきです。
しかし、t-SNE の主な用途は可視化であるので、特に大きな問題ではないかと思われます。

高次元データを可視化する際には、多様体学習に加え、 t-SNE を是非お試しください。

また、多様体学習と t-SNE の得意領域はデータのつながり度合いの構造によって決まりそうですが、高次元データにおいてその構造はどのように解明できるのでしょうか?
このような高次元データの構造を解明する方法の一つとして、「トポロジカルデータアナリシス(TDA)」という分野を用いる方法があります。
こちらについても、後日 弊社ブログにてご紹介させていただく予定ですので、お楽しみに!

ALBERTでは、データサイエンティストを積極募集しています。
ぜひ採用ページをご覧ください。

参考文献

  • L.J.P. van der Maaten and G.E. Hinton. Visualizing High-Dimensional Data Using t-SNE. Journal of Machine
    Learning Research
    , 9(Nov):2431–2456, 2008.
  • L.J.P. van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research 15(Oct):3221-3245, 2014.