Download as PDF, PPTX
More Related Content
Rでisomap（多様体学習のはなし）
- 1. Tokyo.R #14 Rでisomap （多様体学習のはなし） 2011年5月28日 Tokyo.R #14 Kohta Ishikawa (@_kohta) 1
- 2. Tokyo.R #14 アウトライン l 多様体学習って？ l 線形と非線形 l isomap l 実装してみた l 実務的な難しさ 2
- 3. Tokyo.R #14 多様体学習(manifold learning)？ l 非線形な多様体(manifold)上に分布するような データの構造を学習する一連の手法 l 例えば、高次元空間に埋め込まれた実質的に低次 元な多様体を学習することで、非線形データの低次 元表現が可能になる l データの分布構造が線形なら… l 主成分分析 （線形変換によって低次元でデータをよ く説明しようと試みる） l 因子分析 l etc… 3
- 4. Tokyo.R #14 多様体？ l 定義 松本幸夫「多様体の基礎」 (東京大学出版会)より 位相空間Mが次の条件(1),(2)をみたすとき、Mをm次元位相多様体 (topological manifold)という。 (1) Mはハウスドルフ空間である (2) Mの任意の点pについて、pを含むm次元座標近傍(U,φ)が 存在する。 座標近傍： 位相空間Xの開集合Uから、m次元数空間Rmのある開集合U’への 同相写像 Φ: U → U’ があるとき、Uとφの対(U,φ)をm次元座標近傍といい、φをU上の 局所座標系という。 4
- 5.
- 6. Tokyo.R #14 なんということはない l 一見高次元に見えるデータが、実はもっと低次元の 構造しか持っていない場合がある l そういうデータを適切に学習したい（多様体学習） Sam T. Roweis and Lawrence K. Saul “Nonlinear Dimensionality Reduction by Locally Linear Embedding” SCIENCE (2000) スイスロール → 3次元とみせかけて2次元 （ただし曲面上に分布している） 曲面の構造 ∈ 多様体 6
- 7. Tokyo.R #14 線形な次元削減 東京大学大学院 情報理工学研究科 l 主成分分析 数理情報学専攻 中川研 公開資料より図表抜粋 l 次元削減と言えばこれ http://bit.ly/hhSlyB l 非線形データに対してはうまくいかない 主成分分析 どうやって(線形な)座標変換をしても 低次元で上手くデータを説明できない 7
- 8. Tokyo.R #14 非線形な次元削減 l Isomap l LaplacianEigenmap l Kernel PCA etc… うまい座標変換を施して、低次元でデータを説明したい 8
- 9. Tokyo.R #14 isomap l 非線形次元削減手法のひとつ l K近傍グラフを用いて多様体上の測地線距離を(近 似的に)求め、多次元尺度構成法を用いて近似的に ユークリッドな低次元空間に射影する 9
- 10. Tokyo.R #14 測地線？ l 定義 Wikipediaより リーマン多様体上の微分可能な曲線x(τ)が を満たすとき、x(τ)を測地線という。 ここで はアフィン接続である。 10
- 11.
- 12. Tokyo.R #14 難しいのは単語だけ 測地線距離が欲しいので、各点について近場の点だけは 2点間のユークリッド距離は ユークリッド距離でつなぐことにする。 データの構造(本当の「遠さ」) そうしてできたグラフ（ネットワーク）を辿って最短距離を見出せば を反映していない 測地線距離に近いものが計算できると期待する。 グラフの2次元表現 2点間の本当の「遠さ」を表しているのは 各点の近場のk点を直線距離でつないだグラフ データが分布する面(多様体！)に沿った 距離 測地線距離 K近傍グラフ 12
- 13. Tokyo.R #14 ようするに いやがる多様体を わざわざユークリッド空間に埋め込む 13
- 14. Tokyo.R #14 他に何が必要？ 点データ K近傍グラフの作成 測地線距離行列の作成 点間の距離データから 適切な座標値を計算！ 多次元尺度構成法 点データの低次元マップ表現 14
- 15. Tokyo.R #14 多次元尺度構成法 l 点間の距離データのみが与えられた場合に、点を 上手く座標空間に表示する（座標値を求める）方法 l Tokyo.R #09 l http://www.slideshare.net/yokkuns/tokyor09 l 私のブログ l http://d.hatena.ne.jp/koh_ta/20110514 15
- 16. Tokyo.R #14 多次元尺度構成法 距離行列(の成分2乗) ダブル・センタリング変換 Dij=dij2 K = -1/2 HDH Hij = δij – (1/n)1ij ・Kの固有値が正（正定値）でなければならない ・距離がユークリッドでないときは一般に負の固有値が現れる ・isomapでは負の固有値は無視して固有値の大きい順に いくつか(2,3次元)を採用する ⇒ 低次元表現！ ・測地線距離のユークリッド性が弱いときは近似が悪くなる 16
- 17. Tokyo.R #14 Rにisomapがない l たぶんない l Pure Rで実装すると重くてむり l データ1000個 → 20分くらい… 17
- 18. Tokyo.R #14 あらためて探したらあった l veganパッケージ l 植生関連の人向けのパッケージ dist(d) : dist形式(ユークリッド距離)データ ndim : 出力する次元 k : k近傍グラフの近傍数 18
- 19. Tokyo.R #14 C++で書くかRcppとかあるし とか言って大体書いたあとに見つけた l Rcpp l RとC++の連携を便利にしたRパッケージ l 先人達のとてもすばらしい資料群 l @sfchaos l http://www.slideshare.net/sfchaos/tokyor7rcc l @mickey24 l http://www.slideshare.net/mickey24/extend-r-with- rcpp l Pure Rに比べてだいたい10～100倍くらいは速い 19
- 20. Tokyo.R #14 書いた l CPPLapackというすばらしいLapackのクラスラッ パーがある l LapackはFortran臭がきつい l CPPLapackは行列クラスも定義しているので、和 や積などの行列演算も簡単 l ただしLapackのフル機能が使えるとは限らない… l 実際Rのcmdscale関数(Fortran実装)が使ってい る_dsysvxルーチンは使えないっぽい 20
- 21. Tokyo.R #14 Rcppの返り値形式 書いた SEXPはRのデータ形式 最後にC++オブジェクトをラップしてRに返す 21
- 22. Tokyo.R #14 実行結果 l まだ微妙にバグがあります… l でもほぼあってます 元データ 2次元マップ 22
- 23. Tokyo.R #14 で、実際使えるの？ l 実務的に使える手法の条件（例） l 手法が理解しやすいこと l 結果の解釈が容易であること l 直感と外れない結果が出ること l etc 23
- 24. Tokyo.R #14 非線形の(実務的)むずかしさ l 手法が複雑になりがち l 結果の解釈が難しくなりがち l なんでそういう結果が出たのか？ l 次元削減に使った非線形変換の性質を元の座標系 （＝実務的に意味がある量）で説明できるのか？ l 主成分分析等は簡単（性質＝主成分寄与率、因子付加量 など） l 結果を直感で解釈できるかどうかは問題による l 構造に興味を持たない範囲（単純な分類など）では 使えるんじゃないか 24
- 25. Tokyo.R #14 Isomapの実用的むずかしさ l K近傍グラフのKをいくつにするべきか？ l Kが小さすぎると全体が正しく連結されない l Kが大きすぎると多様体の構造が正しく反映されない l 多分色々研究があると思いますがぶっちゃけあまり調べて ないです… l マッピングルールの解釈が不可能 l 元の点⇒測地線距離⇒多次元尺度法 25
- 26. Tokyo.R #14 kの値による変化 l 少なすぎても多すぎてもだめ l 具体的なkの値はバグもあるので「だいたい」と思ってください k=4(少なすぎ) k=8(丁度良い) k=20(多すぎ) 多分バグがとれるとk=5,6 あたりで丁度良くなります 26
- 27. Tokyo.R #14 kの値による変化 l kが少ないとグラフが分断してしまう l kが多いと多様体の構造を無視して繋がってしまう k=4 k=8 k=20 snaパッケージのgplot関数を利用 27
- 28. Tokyo.R #14 今後 l Isomapはあったから他の多様体学習を実装して 差別化したい… (with @sfchaos) l パッケージ周りの細かいことを色々調べないと… l winとlinuxの動的ライブラリの違いとか 28
- 29.