JavaScriptで機械学習の実装 6 t-SNEによる次元削減

ここ数ヶ月はネットワーク周りのネタ書いてたせいかあんまり頭を使ってなかった気がするので、このGW期間中は久しぶりに理論寄りのコードをけっこう書きました。今回はその一例を挙げます。

今回はt-SNE(t-Distributed Stochastic Neighbor Embedding: t分布型確率的近傍埋め込み法)による高次元データの次元削減および可視化を試してみました。t-SNEはちょっと前に流行って、今では幅広い分野で実用されている次元削減(次元圧縮)手法の一つです。古くは主成分分析(PCA)やIsomapなど多くの手法がありましたが、それらと比較して優れた可視化結果が得られます。

t-SNE: t-Distributed Stochastic Neighbor Embedding

元論文と、発案者の一人 Laurens van der Maaten 氏によるt-SNEの解説動画はこちら。元論文は図が多いとはいえ文字分量も多くて読むのがしんどいので、解説動画を見た方がずっとわかりやすいかと思います。数式も分解しながら図と併せて説明してくれてます。

Visualizing Data using t-SNE(元論文 PDF)
Visualizing Data Using t-SNE – YouTube

日本語での説明は以下のスライドの説明が要点がまとまっていて個人的にわかりやすかったです。ありがとうございます。

Visualizing Data Using t-SNE(slideshare)

(※ 上記Webページのタイトルは全部同じですが別サイトです)

元論文にある基本的なアルゴリズムは以下のようになっています。

SNEは高次元空間での各データ点間のユークリッド距離を、類似度に相当する条件付き確率に変換して低次元空間にマッピングする手法ですが、いくつか欠点があり、それらを改善したのがt-SNEです。SNEでは損失関数の最小化が難しいという問題に対して、t-SNEでは分布を対称化(symmetric SNE)する工夫をしています。低次元分布と高次元分布を平均化している set pij の箇所が該当します。対称性があると助かるというのは、例えば点Aと点Bがあったとして、Aから見たBまでの距離とBから見たAまでの距離が異なると近さをどう表現するか困るからですね。

また、低次元空間におけるデータ点間の類似度に自由度1のt分布(Student’s t-distribution)を使って分布を表現しており、これがt-SNEの名前の由来となっています。ガウス分布より裾が広くなっているので、高次元空間において距離の遠いデータ点を低次元空間でも同様に遠くに配置することができ、距離が近いデータ点群と混ざりにくくなります。分布間での距離の関係性を保ちやすくなるということですね。ここで perplexity という重要なパラメータが出てくるのですが、これについてはデモの紹介と併せて後述します。

あとはSNEと同じ様に分布間の差異をカルバック・ライブラー情報量(KLD: Kullback-Leibler Divergence)の総和を損失関数(コスト関数)に設定し、勾配法でコツコツと最小化していきます。KLDの計算自体は簡潔です。

勾配計算は、最終的にはこちらもシンプルな形になってます。(導出はここで数式をたくさん貼るのは大変なので、知りたい場合は元論文の Appendix A. Derivation of the t-SNE gradient を参照してください)

実装・検証

いつもの縛りで、t-SNEモジュール本体は外部ライブラリ無しで素朴にJavaScriptで実装しました。前述の元論文にあるアルゴリズム(Algorithm 1)通りに書いているつもりです。つまりナイーブな実装になってるので効率化はほとんど行っていない理論学習用ですが、可視化の動作確認くらいはできるようになっているかと。論文内での文言もコード内のJSDocコメント等に適宜差し込んであるので、論文とコードを交互に追いながら理論を理解することもできるかなとは思います。GitHubに置いておくので興味あれば。

imageprocessing-labs/ml/t-sne at master – wellflat

今回利用するデータはdigitsデータセットを使います。MNISTの軽量版みたいなやつですね。64次元(8×8)なので数字の判別は人の目でも難しいかも。後述しますが、局所性を保ってるか視覚的な確認もけっこう難しかったです。。

Classes: 10
Samples per class: ~180
Samples total: 1797
Dimensionality: 64
Features: integers 0-16

Classes: 10

Samples per class: ~180

Samples total: 1797

Dimensionality: 64

Features: integers 0-16

開発環境

* Node.JS 13.9.0
* Babel 7.8.4
* Vue.js 2.6.11

今回の実装では、指定回数まで一気に勾配法を進めるPromise(非同期)板と、勾配計算を1ステップ毎に一時停止するジェネレータ版の二つのインタフェースを用意しました。なのでES2017以降の環境が必要です。パラメータは perplexity/η(学習率)/α(モーメンタム) を指定できるようにしています。

import tSNE from './tsne';
import { digits } from './digits_data';  // digitsデータセット本体もモジュール化

const params = { perplexity: 30, eta: 100, alpha: 0.5 };  // パラメータ
const tsne = new tSNE(digits.data, params);
const maxIter = 1000;  // 反復回数

// Promise 非同期版
tsne.compute(maxIter).then(result => {
    console.log(result);  // result: Float64Array[], 二次元座標の配列
});
// async/await
const result = await tsne.compute(maxIter);

// ジェネレータ版
const it = tsne.iterator(maxIter);
let step = it.next();  // 1ステップずつ結果を返す
while(!step.done) {
    console.log(step.value);
    step = it.next();
}

import tSNE from './tsne';

import { digits } from './digits_data'; // digitsデータセット本体もモジュール化

const params = { perplexity: 30, eta: 100, alpha: 0.5 }; // パラメータ

const tsne = new tSNE(digits.data, params);

const maxIter = 1000; // 反復回数

// Promise 非同期版

tsne.compute(maxIter).then(result => {

console.log(result); // result: Float64Array[], 二次元座標の配列

});

// async/await

const result = await tsne.compute(maxIter);

// ジェネレータ版

const it = tsne.iterator(maxIter);

let step = it.next(); // 1ステップずつ結果を返す

while(!step.done) {

console.log(step.value);

step = it.next();

}

t-SNE自体は外部ライブラリ無しで書いていますが、デモツール作成用にはVue.js + Chart.jsを使いました。ここ数ヶ月は副業でVue.jsを触っているのでツール作るのも少し慣れてきました。まぁ今回は書き捨てツールなのでまともにコンポーネント設計はしてませんが、。

t-SNE demo tool

最初は高次元分布の構築処理が走るため、少し時間と負荷がかかりますので注意してください。端末のスペックが低いとブラウザによって処理が停止させられるかも(?しれません。

t-SNEの重要なパラメータであるperplexityの扱いは難しく、実際に何度もテストして変化を確かめてました。perplexityはデータの局所的な特性と大域的な特性のどちらをより考慮するかのバランスを決めるパラメータですが、値によって最終的なクラスタの形が大きく変わってきます。元論文では5~50の間が適切とされているようです。今回作ったデモツールでもperplexityを変更できるようにしてあるので興味あればいろいろ試してみてください。

似ているように見える数字、例えば7と9のクラスタはperplexityをいい感じに設定すると期待通りに近くに配置されやすいですが、digitsデータセットは低解像度なので、そもそも似ているかどうか人間でも判別しにくかったりするので解釈が難しいです。分類されたクラスタは「局所性を保っているような”気がする”」という印象でした。やはりMNISTくらいの解像度は必要なのでしょう。

また、t-SNEの効率化方法として、Early exaggeration や Early compression と呼ばれる方法があります。Early exaggeration の方は実装が簡単だったので一応試してみましたが、digitsデータセット程度の規模ではいまいちよくわかりませんでした。GitHubに上げているコード内での該当箇所はコメントアウトして残してあるので、別のデータセットで試すときにもうちょっと効果を調べてみたいと思います。

おわりに

次元削減とデータ可視化に関連する話は久しぶりに書いたような気がします。t-SNEは前述の通りパラメータと結果の解釈が難しいですが、従来の手法よりも優れた可視化結果が得られます。局所性については今回試したデータだと上手く説明できませんでしたが、少なくとも綺麗にクラスタが分かれてくれることは確認できました。別のデータセットでも試してみる必要がありそうです。

また、2018年にUMAP(Uniform Manifold Approximation and Projection)という手法が提案されており、t-SNEより処理効率が良いとされているようです。SciPy2018でのUMAPの解説動画はこちら。UMAPも是非JavaScriptで実装してt-SNEと比較してみたいですね。

UMAP Uniform Manifold Approximation and Projection for Dimension Reduction | SciPy 2018

今回作成したコード(t-SNEモジュール、vue-chartjsによる可視化サンプルコード、デモツール)

参考

Visualizing Data using t-SNE (元論文 PDF)
Visualizing Data Using t-SNE – YouTube (Laurens van der Maaten氏によるt-SNEの解説動画)
Visualizing Data Using t-SNE (slideshare)
How to Use t-SNE Effectively
scRNAseq論文の図のtSNEて何？ – PUBLISH AND PERISH 日本の科学と技術PUBLISH AND PERISH 日本の科学と技術
t-SNEで遊ぶ – Negative/Positive Thinking

JavaScriptで機械学習の実装 6 t-SNEによる次元削減

t-SNE: t-Distributed Stochastic Neighbor Embedding

実装・検証

開発環境

おわりに

参考

あわせて読む:

コメントを残す