Dimensionality reduction with t-SNE(Rtsne) and UMAP(uwot) using R packages.
- 1. Dimensionality Reduction with t-SNE and UMAP tSNE とUMAPを使ったデータの次元削減と可視化 第２回 R勉強会＠仙台（#Sendai.R）
- 3. 次元削減 高次元のデータをヒトがわかる形で把握?理解したい ? 高次元上におけるデータ点 X={x1, x2, ..., xn}を、 ? 低次元空間上のマップ点 Y={y1, y2, ..., yn}に、変換する データ点のもつ構造をなるべく保ったまま変換できるとうれしい。 http://web.mit.edu/cocosci/isomap/datasets.html
- 4. Rを使った最近の次元削減手法 1. t-SNE ? 概要 ? Rで使ってみる ? パラメータの調整 ? perplexityの自動調整 2. UMAP ? 概要 ? Rで使ってみる ? 教師あり?半教師あり学習 と 距離学習 ? パラメータの調整 URL Today’s Topic
- 5. ALL the Sample Codes On github: ? https://github.com/katokohaku/tSNE_and_UMAP_using_R_pac kages ? UMAP関連のコードは、後日追加予定
- 6. 1. 概要 2. Rで使ってみる 3. パラメータの調整 4. perplexityの自動調整 １．t-SNE
- 7. 概要：SNE → t-SNE → Barnes-Hut-SNE ? SNE（確率的近傍埋め込み法; Stochastic Neighbor Embedding） ? Hinton and Roweis, 2002 ? データ点とマップ点の距離を正規分布で定義した確率分布モデルで表現し、 両者がなるべく近づくようなマップ点を探索する ? t-SNE（t分布型SNE; t-distributed SNE） ? van der Maaten and Hinton, 2008 ? SNEにおける、コスト関数の最適化が困難?Crowding problemといった 問題点に対応 ＋学習効率を上げるためのトリックの追加 ? Barnes-Hut-SNE ? van der Maaten and Hinton, 2013 ? 計算量とメモリ容量の問題点に対応した、 t-SNEの近似法
- 8. 概要：SNE ① データ点とマップ点の距離をそれぞれ確率分布モデルで表現し、 両者がなるべく近づくようなマップ点を探索する １．データ点 xi から xj までの類似度を、条件付き確率分布pj|iと考える ? pj|iは、平均 xi ，分散 σi 2 の正規分布で定義される ? ただし、pi|i＝０ 分散 σi 2は、与えられたperplexityを満たすように 二分探索する。 ? perplexityは、データ点xの周りの有効な近傍の数 ? データ点xiの周りの密度が高 → 分散が小 ? データ点xiの周りの密度が低 → 分散が大 xi から 近い xi から 遠い
- 9. 概要：SNE ② データ点とマップ点の距離をそれぞれ確率分布モデルで表現し、 両者がなるべく近づくようなマップ点を探索する ２．マップ点 yi から yj までの類似度を、条件付き確率分布qj|iと考える ? qj|iは平均 yi ，分散 σ=1/√2の正規分布で定義される ? ただし、qi|i＝０ ３．pj|i と qj|i とが近づくように、yi を探索する ? pj|i と qj|iとの距離は、KL情報量（Kullback–Leibler divergence）で表現 ? すべてのデータ点に対するKL情報量の和を損失関数 とし、勾配法で最小化 ●問題点 ? コスト関数の最適化が困難 ? Crowding problem
- 10. 概要：t-SNE ① SNEにおける、コスト関数の最適化が困難?Crowding problemといった 問題点に対応 ＋学習効率を上げるためのトリックの追加 １．コスト関数の最適化を改善 ? 損失関数を同時確率分布pji と qji とのKL情報量の最小化に置き換える （Symmetric SNE） ? 外れ値による悪影響を防ぐため、データ点の類似度の形を変更 pji ＝ pij 、qji ＝ qij がそれぞれ対象になるため、 コスト関数の勾配がシンプルになる
- 11. 概要：t-SNE ② SNEにおける、コスト関数の最適化が困難?Crowding problemといった 問題点に対応 ＋学習効率を上げるためのトリックの追加 ２．Crowding problemの軽減 ? 低次元上のマップ点同士の類似度を、自由度１のｔ分布と考える ｔ分布はガウス分布よりもheavy tailなので、 高次元上で近い点は低次元でも近く、 高次元上で遠い点は低次元ではより遠くに 配置される 近くの点は近くに配置 遠い点はより遠くに配置
- 12. 概要：t-SNE ③ SNEにおける、コスト関数の最適化が困難?Crowding problemといった 問題点に対応 ＋学習効率を上げるためのトリックの追加 ３．学習効率を上げるためのトリック ? Early Compression ? 最適化開始時にマップ上の点を密集するようにする ? Early exaggeration ? 最適化の前半と後半で、重みをシフトさせる ? クラスタリングがより緊密になり、マップ点のクラスター間の距離が大きくなる ? Rtsneではこちらを採用（初期点が指定されていると無効） ? データ点 X を主成分分析 (PCA) で次元削減する前処理ステップを推奨 ●問題点 ? 計算量とメモリ容量は依然として大きい
- 13. 概要：Barnes-Hut-SNE 二つの近似法の組み合わせにより、t-SNEの計算量をO(N2)→O(N logN)に高 速化＋省メモリ化 １．xiから十分に遠くにあるxjでは、pij=0とする ? 非ゼロとなるデータ点はnearest neighboursで探索 ２．近傍点をグループ化 ? quadtreeで空間分割されたセル内のデータ点を、 中心点で代表化することでデータのサイズを削減
- 14. Rで使ってみる： Rtsne::Rtsne() mapping.tsne <- Rtsne::Rtsne(train.matrix, verbose = TRUE) #> Performing PCA #> Read the 10000 x 50 data matrix successfully! #> OpenMP is working. 1 threads. #> Using no_dims = 2, perplexity = 30.000000, and theta = 0.500000 #> Computing input similarities... #> Building tree... #> - point 10000 of 10000 #> Done in 7.74 seconds (sparsity = 0.012240)! #> Learning embedding... #> Iteration 50: error is 97.591196 (50 iterations in 1.70 seconds) #> （中略） #> Iteration 1000: error is 1.924562 (50 iterations in 1.43 seconds) #> Fitting performed in 33.09 seconds. ①PCAで次元削減（前処理） データフレーム、距離(‘dist’)オブジェクトでもOK ②近似法による高速化 ③KL情報量の最小化(勾配法)
- 15. 今回のデータ：MNIST ? Mixed National Institute of Standards and Technology database ? 28×28ピクセルの手書きの数字のデータセット ? http://yann.lecun.com/exdb/mnist/ ? 今回は、CSVファイルをダウンロードして、10000件にサンプリング ? https://github.com/pjreddie/mnist-csv-png ? テストセット（＝ 10000件）をそのまま使えばよかったことに後から気づいた。
- 20. 並列化 mapping.tsne <- Rtsne::Rtsne(train.matrix, verbose = TRUE, n_threads = 4) #> Performing PCA #> Read the 10000 x 50 data matrix successfully! #> OpenMP is working. 4 threads. #> Using no_dims = 2, perplexity = 30.000000, and theta = 0.500000 #> Computing input similarities... #> Building tree... #> - point 10000 of 10000 #> Done in 2.56 seconds (sparsity = 0.012240)! #> Learning embedding... #> Iteration 50: error is 97.591199 (50 iterations in 0.75 seconds) #> （中略） #> Iteration 1000: error is 1.918716 (50 iterations in 0.65 seconds) #> Fitting performed in 13.58 seconds. ? n_threads で、スレッド数(>1)を指定する ? パフォーマンスに直接影響する デフォルトでは 並列化しない設定(=1)なので、 たいていの場合、かなり省時間化される
- 21. パラメータ：perplexity ? 最重要 ? 高次元上の各データ点の確率分布モデルを決定するパラメータ ? 元の論文では、５～５０を推奨（データサイズ/３が上限） Perp = 5 Perp = 15 Perp = 30 Perp = 50
- 22. （参考）perplexityの自動調整① Automatic Selection of t-SNE Perplexity ? Cao and Wang 2017 ? よさそうなperplexityを探すのは計算時間が掛かる＋目視での評 価になるため、選択基準を与えて自動探索したい ? KL(P||Q) にperplexityによる罰則項を加えた指標を提案 ? この指標が有効なら、S(perp)の最小点を二分探索（＝自動 化）できる ? 探索範囲は、 ５ ～ データサイズ/３のあいだ
- 23. 概要：SNE ② データ点とマップ点の距離をそれぞれ確率分布モデルで表現し、 両者がなるべく近づくようなマップ点を探索する ２．マップ点 yi から yj までの類似度を、条件付き確率分布qj|iと考える ? qj|iは平均 yi ，分散 σ=1/√2の正規分布で定義される ? ただし、qi|i＝０ ３．pj|i と qj|i とが近づくように、yi を探索する ? pj|i と qj|iとの距離は、KL情報量（Kullback–Leibler divergence）で表現 ? すべてのデータ点に対するKL情報量の和を損失関数 とし、勾配法で最小化 ●問題点 ? コスト関数の最適化が困難 ? Crowding problem
- 24. （参考）perplexityの自動調整① Automatic Selection of t-SNE Perplexity ? Cao and Wang 2017 ? よさそうなperplexityを探すのは計算時間が掛かる＋目視での評 価になるため、選択基準を与えて自動探索したい ? KL(P||Q) にperplexityによる罰則項を加えた指標を提案 ? この指標が有効なら、S(perp)の最小点を二分探索（＝自動 化）できる ? 探索範囲は、 ５ ～ データサイズ/３のあいだ KL(P||Q)が得られれば S(perp)は計算できる
- 25. （参考）perplexityの自動調整② Automatic Selection of t-SNE Perplexity ? Rtsne() は、KL(P||Q) を返してくれるので計算できる itercosts： ? The total costs (KL-divergence) for all objects in every 50th + the last iteration pen.KLdist = last(mapping.tsne$itercosts) + log(mapping.tsne$N) * perplexity/ mapping.tsne$N)
- 26. （参考）perplexityの自動調整③ Automatic Selection of t-SNE Perplexity ? 計算してみた ? S(perp)が最小となるPerplexityが50よりも大きくなった ? データに依存するかどうか、別のデータで検証が必要
- 27. パラメータ：max_iter ? 勾配法のイテレーションサイズ ? 少なすぎると収束しないが、大きくすると時間が掛かる ? 前回の結果にイテレーションを追加したければ、Y_init に前回の結 果を初期配置として指定する ? デフォルト（max_iter=1000）で足りないと思ったら追加。
- 28. パラメータ：theta ? Barnes-Hut-SNEにおけるSpeed/accuracy trade-offを コントロールするパラメータ ? theta=0で、近似をやめてexactモード（きわめて遅い） ? 0.2～0.8はロバストとされているので、デフォルト(=0.5)でよさそう
- 29. 1. 概要 2. Rで使ってみる 3. 教師あり?半教師あり学習 と 距離学習 4. パラメータの調整 ２．UMAP
- 30. 概要？ ：UMAP ? The details for the underlying mathematics can be found in: ? McInnes, L, Healy, J, UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, ArXiv e-prints 1802.03426, 2018 ? https://arxiv.org/abs/1802.03426 ? The important thing is that： ? you don't need to worry about that ? you can use UMAP right now for dimension reduction and visualisation as easily as a drop in replacement for scikit- learn's t-SNE. ※ ただし「拡張とか考えるなら、きちんと理解しておけ」みたいなことは書いてある https://github.com/lmcinnes/umap
- 32. Rで使ってみる：uwot::umap() uwot::umap(train.matrix , verbose = TRUE) data.frame, matrix, dist オブジェクト sparseMatrixでもOK (距離行列とみなされる)
- 33. クラスタリング ? umap-learnの公式ドキュメントでは、hDBSCANを推奨。 ? https://umap-learn.readthedocs.io/en/latest/clustering.html ? 今回はhclustを使う。 やり方はt-SNEの時と同じ。
- 34. 並列化 ? n_threads>1 を指定する ? デフォルトでは環境設定を利用するため、意識しなくてもマルチスレッドになって いることが多い
- 35. PCAによる前処理 ? t-SNEと同様に、前処理としてPCAで次元削減できる ? pca = 50 のように、正の整数を指定する ? デフォルトでは「しない」設定
- 36. metricの指定 ① ? metric = “method”で、距離指標を指定できる ? デフォルトで指定できるmetricは、"euclidean" (the default), "cosine", "manhattan", "hamming", "categorical" metric = “cosine” に変更
- 37. metricの指定② ? 列ごとに違う種類の距離指標で評価できる ? 列名、または列番号で指定する ? Factor型の列を指定可能 ? デフォルトでは数値型以外の列は自動的に削除する （マニュアルから）
- 38. Supervised Embedding ? Y={ラベル列、または数値列} を指定すると教師あり学習モード ? デフォルトは教師なし学習 ? カテゴリ型のラベル列に欠損がある場合、半教師あり学習モード ? 数値列の場合は、欠損NG
- 39. Supervised Embedding uwot::umap(train.matrix , verbose = TRUE, y = train.label) 学習にラベルが反映される
- 41. Metric Learning ? 距離学習による、新しく追加されたデータの埋め込み 学習したモデルの取得は、 ret_model = TRUE を指定する： ml.umap <- uwot::umap(train.matrix , verbose = TRUE, y = train.label, ret_model = TRUE) ※ umapが返すオブジェクトが listになるので注意 学習したモデルで、新しく追加されたデータを埋め込むには： embed.test <- umap_transform(test.matrix, model = ml.umap)
- 42. パラメータの調整 ? n_neighbors ? 多様体近似の際に使用する各点近傍のサンプルデータ点の数。 2~100が推奨レンジ ? 値が大きいほどより遠くの点までサンプリングする。値が小さいほど局所的な構造を保存する ? n_components ? 埋め込み先の空間の次元サイズ（デフォルト＝２） ? 可視化目的なら2~3。 前処理目的なら、~100くらいまでが推奨 ? spread ? 埋め込み先の空間のeffective scale。 min_dist とのバランスをとりながら調整する ? 埋め込み先の各点のクラスター性?凝集性を調整する ? min_dist ? 埋め込み先の各点間の最小距離。 ? 値が小さいほど互いに近い点が凝集する。 値が大きいほど各点の分布が均一になる
- 43. n_neighbors vs min_dist n_neighbors = 5 min_dist = 0.0125 0.05 0.2 5 spread = 1で固定 = 20 = 80 = 320
- 44. まとめ まずはUMAPで検討してから、必要ならt-SNEを検討、でよいかも ? 収束が早い（＝短時間でいろいろ試せる） ? 良さそうなクラスタリングになることが多い ? 教師あり学習／半教師あり学習からも、よいクラスタリングが期待できる ? 距離学習ができるので、新規データの追加埋め込みできる ? UMAPは、t-SNEと比較しても調整すべきポイントとパラメータが多い ? 今回紹介をしなかったパラメータがまだまだある。 ? わりと最近の提案手法なので、SNEのように理論?実用の両面から体系的に 拡張されていってほしい。 https://github.com/jlmelville/uwot
- 45. t-SNE Original Paper ? Stochastic Neighbor Embedding ? http://papers.nips.cc/paper/2276-stochastic-neighbor-embedding.pdf ? Visualizing Data using t-SNE ? http://www.jmlr.org/papers/v9/vandermaaten08a.html ? Barnes-Hut-SNE ? https://arxiv.org/abs/1301.3342 R Package ? Rtsne ? https://github.com/jkrijthe/Rtsne 解説記事?スライド（日本語） ? 八木貴之 さんの狠狠撸Share（超オススメ） ? /TakayukiYagi1/tsne ? MATLABのドキュメント ? https://jp.mathworks.com/help/stats/t-sne.html References
- 46. UMAP Original Paper ? Uniform Manifold Approximation and Projection for Dimension Reduction ? https://arxiv.org/abs/1802.03426 Packages and related documents ? uwot ? https://github.com/jlmelville/uwot ? umap-learn (python) ? https://github.com/lmcinnes/umap ? https://umap-learn.readthedocs.io/ 解説記事?スライド（日本語） ? UMAP 論文を読む ? https://qiita.com/cympfh/items/e8c2669c646a73205ea9 References