多様体学習紹介 中川研機械学習勉強会 2008/6/19 吉田 稔（中川研） ※数学的な部分はいい加減なのでご注意下さい 参考文献 • “Algorithms for manifold learning”, Lawrence Cayton, UCSD tech report CS2008-0923 • “Robust Euclidean Embedding”, Lawrence Cayton, Sanjoy Dasgupta, ICML 2006 “Algorithms for manifold learning”, L. Cayton, UCSD tech report CS2008-0923 多様体とは？（感覚的説明） • 見かけは違うが、実質的にはd次元ユーク リッド空間で表現できるような図形 • 「局所的に地図が書けるような図形」とも言え る（例：地球表面） 3次元中に埋め込まれた、1次元多様体 同じく、2次元多様体（「スイスロール」） 多様体とは？（定義） • Mがd次元多様体である⇔ • Mの各要素xと、その近傍Nxについて、ユーク リッド空間Rd（の部分空間）への同相写像が 存在する。 – f: X→Yが同相写像⇔ • fが全単射かつ連続写像、さらにf-1も連続写像 モチベーション：次元圧縮 • データの次元をうまく減らす – 学習に不必要or有害なfeatureを削除 – Visualizationに使える – 有用なfeatureを取り出す⇔featureに対するデー タマイニング 問題設定 • 入力： x1,x2,...,xn （D次元ベクトル） – X ： i行目がxiであるような行列 • 出力： y1,y2,...,yn （d次元ベクトル） – Y ： yiを並べた行列 • N(i): 点xiの、k-nearest neighbors • (νi, λi): (固有ベクトル,固有値)の列、 λ1≧λ2≧...≧λn 主成分分析(PCA) • 次元削減といえばまずこれ • D次元をd次元に削減する場合： – 各データポイントを、d次元空間に射影し、その分 散（射影後の全データポイントの分散）を考える – 分散が最大になるような射影を求める 主成分分析 • 式 Rayleigh商： この最大値は、XTXの 最大固有値・固有ベクトル によって与えられる。 Why not PCA? • PCAは、線形部分空間への射影しか扱えない • PCAを、多様体を扱えるように拡張したい。 主要な４つのアルゴリズム • • • • Isomap Locally Linear Embedding (LLE) Laplacian Eigenmaps Semidefinite Embedding (SDE) Isomap • Isometric feature mapping (等尺素性写像？) • 最も有名なアルゴリズム • MDS(Multidimensional Scaling)の拡張 – MDS: ユークリッド空間への埋め込み （embedding）を行うポピュラーなアルゴリズム • 埋め込み：点の集合と、その「2点間の距離」が与えら れた時、点をユークリッド空間上に配置する Multidimensional Scaling • アルゴリズム Multidimensional Scaling - Theorem 1 • 距離行列とGram matrix (内積行列)との関係 • （余弦定理?）を 使うことにより、両者を関連付けることができ る Isomap -- Algorithm • STEP-1: 与えられた点どうしの測地距離を計算 – 測地距離：多様体の形に沿って測られた距離 • 実際には、 – 近傍：ユークリッド距離で近似 – それ以外：xiと近傍の距離をもとに、最短パス探索によって計算 • STEP-2: 測地距離をもとに、MDSを使い、低次元 のユークリッド空間へ点を配置 – このとき、「測地距離=埋め込み先でのユークリッド距 離」となるようなfの存在を仮定 Isomap -- Algorithm • 最終的には、以下のアルゴリズムになる。 Isomap – 結果例 • 左の多様体を、右のパラメータ空間で表現 主要な４つのアルゴリズム • • • • Isomap Locally Linear Embedding (LLE) Laplacian Eigenmaps Semidefinite Embedding (SDE) Locally Linear Embedding (LLE) • Isomapとほぼ同時期に提案 • 「多様体（さらに、そこからの写像）が、局所的 に見れば線形」という直感に基づくアルゴリズ ム Locally Linear Embedding (LLE) • STEP-1: 各xiを、その近傍の点の線形結合で 表す – 具体的には、以下を最小化するWを求める – Wへの制約： • 各行で、要素の和は1 • 近傍でない点どうしの要素は0 • STEP-2: 各yiを、同じWのもとで配置する – 具体的には、以下を最小化するYを求める Locally Linear Embedding (LLE) • STEP-1: 各xiを、その近傍の点の線形結合で 表す – 具体的には、以下を最小化するWを求める – これは、以下で与えることができる Locally Linear Embedding (LLE) • STEP-2: 各yiを、同じ制約のもとで配置する – 具体的には、以下を最小化するYを求める – これは、以下の形に書き直せる（Yのi列目がyi） – ただし、 Locally Linear Embedding (LLE) • STEP-2: 各yiを、同じ制約のもとで配置する – 以下を最小化 – これは、Rayleigh’s quotientと呼ばれる形 • Rayleigh’s quotientの最小値は、最小の固有値と、そ の固有ベクトルで与えられる。 LLE - Algorithm 主要な４つのアルゴリズム • • • • Isomap Locally Linear Embedding (LLE) Laplacian Eigenmaps Semidefinite Embedding (SDE) Laplacian Eigenmaps • スペクトルグラフ理論（?）的アプローチ • グラフラプラシアンを利用 • Wの選び方は2通り – k-nearest neighborsなら1、それ以外は0 – Gaussian heat kernel: Laplacian Eigenmaps • 以下のコスト関数を最小化する(Yのi行目がyi) • ただし、スケール変換の影響を避けるため、以 下の制約を置く。 • ラグランジュ乗数法により、解が • で得られることがわかる。 Laplacian Eigenmaps - Algorithm LLEとの関係 • Laplacian Eigenmapsは、（提唱者らによれ ば、）LLEにスペクトルグラフ理論的解釈を与 えることができる。 • いくつかの仮定のもとで、LLEは、「1/2L^2（た だし、LはLaplace-Beltrami作用素）の固有関 数」を求めていると見なせる（そうです） 主要な４つのアルゴリズム • • • • Isomap Locally Linear Embedding (LLE) Laplacian Eigenmaps Semidefinite Embedding (SDE) Semidefinite Embedding (SDE) • 物理的なイメージに基づくアルゴリズム – 「各点とその近傍を、棒でつなぐ」 – ⇒「なるべく広くなるよう引っ張る」 • ＝近傍でない点どうしの距離を最大化する Semidefinite Embedding (SDE) • 物理的なイメージに基づくアルゴリズム – 「各点とその近傍を、棒でつなぐ」 – ⇒「なるべく広くなるよう引っ張る」 • ＝近傍でない点どうしの距離を最大化する • すなわち・・・ – の元で、以下の最大化を行う（ただし ） Semidefinite Embedding (SDE) • アルゴリズム 半正定値計画問題 ⇒解くための パッケージが 多数存在 Robust Euclidian Embedding L. Cayton and S. Dasgupta ICML 2006 Classical MDS (cMDS) • 再掲 Classical MDS (cMDS) • 再掲 Dがユークリッド空間上での点距離で なかった場合、ここで近似処理を していることになる。 Classical MDS (cMDS) • 再掲 Dがユークリッド空間上での点距離で なかった場合、ここで近似処理を していることになる。 どんな近似？⇒ cMDSの問題点 • cMDSの近似では、以下を解いている – すなわち、直接Dを近似せず、対応するGram matrixを近似している – HDHとDの関係は – であるため、Dの1つの要素(k,j)での誤差が、以下 のようにHDH全体に伝搬する cMDSの問題点 • cMDSの近似の問題点： – 直接Dを近似せず、対応するGram matrix(HDH)を 近似している – 2-ノルムを使っているため、外れ値に弱い • それに対する解決策： – 直接Dを近似し、そのさいに1-ノルムを使う Robust Euclidean Embedding • 以下を最小化する • ⇔以下の半正定値計画問題を解く Robust Euclidean Embedding • アルゴリズム ノイズ耐性に関する比較実験 • cMDSの結果に比べ、REEはノイズ耐性が強い おまけ PCAとの比較 • Laplacian Eigenmaps使用 元データ Laplacian Eigenmaps PCA PCAとの比較 • Laplacian Eigenmaps使用 元データ Laplacian Eigenmaps PCA 自然言語への適用例 • Laplacian Eigenmaps使用 自然言語への適用例 • Laplacian Eigenmaps使用
© Copyright 2024 ExpyDoc
