多様体学習と非線形次元縮約

多様体学習と非線形次元縮約

Manifold Learning and Nonlinear Dimension Reduction

西森 康則

∗

産業技術総合研究所 脳神経情報研究部門

Neuroscience Research Institute, National Institute of Advanced Industrial Science and

Technology (AIST)

Abstract: We review algorithms and theory of manifold learning in machine learning.

1

はじめに

データの次元縮約は、パターン認識における特徴抽 出などの前処理として、また、機械学習における教師 無き学習や、データマイニングにおける可視化などと 関連して様々な領域で用いられている操作である。し かしながら、通常よく使われる主成分分析などの線形 の次元縮約手法は自ずから適用限界があり1_{、近年、高} 次元のユークリッド空間の中で低次元多様体の周囲に 集中して散布しているとみなせるデータに対して、そ の多様体構造を利用した非線形次元縮約法が、多様体 学習 (manifold learning) という名の下に研究されてい る。粗く述べると、機械学習における多様体学習とは、 Rn_{内の d 次元部分多様体 M からサンプルされた N} 個のデータ Ω = (x1, x2, . . . , xN), xi ∈ Rnが与えられ た時、それらの点を M 内の隣接関係をできるだけ保 存するように低次元空間Rd(d≪ n) に写像することを 指す。 xi7→ yi= (f1(xi), . . . , fd(xi))⊤ ∈ Rd より狭義には、M が、スイスロールに代表されるよう なRd_{の凸部分集合 Θ から等長的にR}n_{に埋め込まれ} た (ψ : Θ → M) 部分多様体 [25]、あるいは Rd_の開 連結部分集合 Θ から局所等長的にRnに埋め込まれた 部分多様体 [9] のように、Θ でパラメータ表示された 多様体の時、サンプル xi(i = 1, . . . , N )のパラメータ ψ−1(xi)を、Rdの等長変換分の不定性を除いて求める ことである。(3 節で触れる) 90年代にも局所 PCA や画像多様体などの、多様体学習 に関連した研究は単発的に発表されていたが、機械学習 ∗_{連絡先：産業技術総合研究所 脳神経情報研究部門}       〒 305-8568 茨城県つくば市梅園 1-1-1 つくば中央第 2        E-mail: [email protected] 1_{ただし、多様体の次元が入れ物の次元に比べて充分低次元で、曲} がり具合も穏やかな場合は、線形写像（ランダム射影）でも、充分 測地的距離を保存した次元縮約が高確率でできる、という結果があ る。[1] の分野でこの問題が活発に研究されるようになったの は、2000 年にサイエンス誌で 2 つの論文が掲載されて からだと思われる。そこで発表された手法 (Isomap と LLE(局所線形埋め込み)) が脚光を浴びたのは、解法が (一般化）固有値問題に還元されるため、局所最適解に 陥ることを回避できるという点や、カーネル PCA の一 種として理解できるため機械学習のトレンドにうまく 適合したことがあげられるだろう。本稿では、Isomap や LLE を含む、固有ベクトルを用いた埋め込み型の多 様体学習のアルゴリズム (それらは [5] でスペクトル埋 め込みと呼ばれている) についてレビューを行う。その 他の手法、例えば隠れ変数を用いた確率モデルを使う 手法については触れない。以下、第 2 節で代表的な埋 め込み型の多様体学習のアルゴリズムを簡潔に紹介す る。第 3 節でアルゴリズムが実際に元の多様体の座標 を復元しているか、に関わる理論研究を紹介する。第 4節で応用例を示す。第 5 節で今後の問題について述 べる。

2

スペクトル埋め込み型の多様体学

習のアルゴリズム

スペクトル埋め込みのクラスに属する多様体学習の アルゴリズムには、Isomap, LLE, ラプラシアン固有 マップ [2]、ヘシアン固有マップ [9]、スペクトルクラス タリング、拡散マップ (diffusion maps)[8] 等がある。以 下で Isomap, LLE, ラプラシアン固有マップ、拡散マッ プの各アルゴリズムを簡潔にまとめる。いずれも固有 値問題を解いて、固有ベクトルを並べたデータをもと に写像を作るのが特徴である。これらのアルゴリズム は、まず前処理として、データの多様体に関する情報 を近傍グラフに変換する。データの各点がグラフの頂 点に対応し、各頂点は近傍に含まれる頂点とのみ辺で 結ばれる。多くは ϵ 近傍や、k 最近傍を選ぶ。その後に 以下の手続きによって非線形次元縮約を行う。 人工知能学会研究会資料 SIG-DMSM-A903-18 (03/30) 115

1. Isomap • M 上の任意の 2 点 xi, xjの測地的距離の近 似値として、近傍グラフ上の xi, xjの最短 経路長 dijをダイクストラ法などによって求 める。 • dijを用いて多次元尺度構成法 (MDS) によ り、xiを yiにマップする。 2. LLE • xi∈ Rnを xiの近傍 Uiに含まれる点の線形 結合で “近似的”に表したい。xi≈ ∑N j=1Wijxj ここで j /∈ Uiなら Wij = 0とする。Wij を ∑j_∈UiWij = 1という制約化で||xi − ∑ j∈UiWijxj|| 2_{を最小化する事によって求} める。 • 上で得られた各近傍 Ui内の線形の隣接関係 を、次元縮約後もできるだけ保ちたい。そ こで、∑N_i=1||yi− ∑ j∈UiWijyj|| 2_を最小化 する。この解は (I− W )⊤(I− W ) の固有ベ クトルを固有値の２番目に小さいもの v1か ら (d + 1) 番目 vdまで抽出することで得ら れる。(最小固有値に対応する固有ベクトル は定ベクトルなので省く）V = (v1, . . . , vd) • xiを yi = Vi⊤ ∈ Rdにマップする。ここに Viは V の第 i 行ベクトル。 3. ラプラシアン固有マップ • 近傍グラフの各辺 xixjに重み Wij = 1、あ るいは exp(−||xi− xj||2/σ)を割り当てる。 • 多様体のラプラス作用素のグラフにおける 類似物であるグラフラプラシアン L = D− W (Dii = ∑n j=1Wij, Dij = 0(i ̸= j)) を導 入し、グラフラプラシアンの固有ベクトル (正確には Lv = λDv の解) を、固有値の２ 番目に小さいもの v1から (d + 1) 番目 vdま で抽出する。(最小固有値に対応する固有ベ クトルは定ベクトルなので省く）以下 LLE と同様。 4. 拡散マップ • 近傍グラフの各辺 xixjに重み Wij ≥ 0, Wij = Wjiを割り当てる。これを正規化して N×N の推移確率行列 P を作る。 Pij = p1(xi, xj) = Wij/Dii pt(xi, xj)は P で表現されるグラフ上のラン ダムウォークによって xiを出発して t ステッ プ後に xjに到達する確率を表すとする。推 移行列の性質から pt(xi, xj)は t→ ∞ で定 常分布 ϕ0(xj)に収束する。この時、点 xi, xj の拡散距離を Dt(xi, xj)2= ∑N k=1(pt(xi, xk)− pt(xj, xk))2/ϕ0(xk)で定義する。 • P の固有値及び固有ベクトルを P ψi = λiψi, 1 =|λ0| ≥ |λ1| ≥ . . . ≥ |λN₋₁| ≥ 0 とする。 この時 D2 t(xi, xj) = ∑N k=1λ 2t k(ψk(xi)− ψk(xj))2 が成り立つ。|λi| ≤ 1 であるから、N より 小さい適当な次元 d(t) までの固有ベクトル をとって yi= Ψt(xi) = (λt1ψ1(xi), . . . , λt_d(t)ψd(t)(xi))⊤ と次元縮約する。この時 ||yi− yj||2≈ Dt2(xi, xj)が成り立つ。 Isomap、LLE、ラプラシアン固有マップ、スペクトル クラスタリング等はデータに依存したカーネルを使っ たカーネル PCA と解釈できることが、[5, 12] で示さ れている。[5] では、さらにナイストレム (Nystr¨om)拡 張を援用することによって、未知サンプルを再学習す ることなく埋め込む方法についても論じている。

3

理論解析

統計的学習理論の汎化性能の解析と同様に、多様体 学習の有効性が理論的に正当化されるには、サンプル 数を十分大きくした極限で、背景にある多様体の情報 が復元されるという議論がなされるべきである。“多様 体”、“学習”という名前が付いているものの、実際に多 様体学習のアルゴリズムでこのことを示している論文 はまだあまりない。 Isomapでは多様体 M 上の 2 点 x, y 間の測地的距離 dM(x, y)の近似として、近傍グラフ G 上の最短経路長 dG(x, y)が使われたが、M がRd内の凸集合からRn に等長的に埋め込まれた部分多様体 (ψ : Θ→ M) で、 M からある条件を満たす確率分布に従ってデータが サンプルされた時、漸近的に dG(x, y)が dM(x, y)に 収束することが Bernstein 等により示されている。[7] 従って、Isomap は漸近的には xi(i = 1, . . . , N )の座標 ψ−1(xi)(i = 1, . . . , N )を、Rdの等長変換分の不定性 を除いて復元しているといってよい。 一方 Donoho 等 [9] は、Rd の開連結部分集合 Θ から局 所等長的にRnに埋め込まれた部分多様体の時、M 上の 汎関数H =∫_M||Hf(m)||2Fdxの零空間が、M の局所座 標 ψ−1(xi)(i = 1, . . . , N )を、Rdの等長変換分の不定性 を除いて与えることを示した。(Hf(m)は f : M → R のヘシアン) この汎関数をサンプル値を使って近似的に 求め、その零空間を求めることによりサンプル点の次 元縮約を与える方法がヘシアン固有マップである。し かしながら、Bernstein 等の結果のような、サンプル数 116

を大きくしていった時に、ヘシアンの推定値が M のヘ シアンに収束するか、といった議論はなされていない ようである。 最後にラプラシアン固有マップに関連してであるが、 ユークリッド空間内のリーマン部分多様体とその上の 確率測度が与えられた時、サンプル点が無限に増えて いく極限で、サンプルから作った近傍グラフのグラフラ プラシアンの固有ベクトルが、元の多様体のラプラシ アン (ラプラス作用素) の固有関数へ収束するか？とい う問題が幾つかのグループで論じられている。[4, 8, 13] ここで、機械学習の研究者にはほとんど知られていな いが、リーマン多様体のラプラシアンに関する定理と して B`erard等 [6] による以下のものがあることに注意 する。 n次元の閉リーマン多様体 M と M のラプラシアンの 固有関数の正規基底が一つ{φj(x)}_j≥1与えられたと き、次で定まる写像は任意の t≥ 0 に対して M から l2 への埋め込みを与える。 ψt: M→ l2(t≥ 0) (1) x→√2 (4π)n/4t(n+2)/4 { e−λjt/2_φ j(x) } j_≥1 (2) さらに l2_{の標準計量を can と書くと、t が 0 に近づく} 極限で (ψt)∗canは漸近的に M のリーマン計量 g に収

束する。(ψt)∗can= g + t/3(1/2Scalg·g −Ricg) + O(t2)

ここに Scalg, Ricg は各々M のスカラー曲率、リッチ・ テンソル。 Jones等 [14] はこの定理を精緻化して、閉多様体 M のラプラシアンの固有関数（の定数倍）を、(最小固有 値の 0 を除いて) 小さい固有値に対応するものから n 個 並べることによって、M の任意の点の近傍で局所座標 を構成できることを示した。従って、グラフラプラシ アンの固有ベクトルが、多様体のラプラシアンの固有 関数に (ある条件の下で) 収束することを示す Belkin[4] 等の結果と併せると、ラプラシアン固有マップが、漸 近的には元の多様体の局所座標を構成することがほぼ 示せる。(しかし厳密な証明はまだ与えられていないと 思われる）

4

応用

多様体学習は機械学習の中ではカーネル法、距離学 習、クラスタリング、半教師あり学習 [3]、転移学習と 密接に関連している。他分野への応用としては、コン ピュータ・ビジョンの分野で最も多く使われている印 象を受ける。例えば同一人物の顔が受ける変化は低次 元の自由度を持つと考えられるから、それらはまとめ て一つの多様体（articulation manifold)[10] をなして いると考えられる。モーション・キャプチャー・データ なども同様なものとみなせるだろう。[11] 同様に、背 後にある少数自由度のものに制御されて生成される運 動やスピーチなどのデータには多様体学習が使える可 能性がある。[16, 21] また、多様体学習はグラフの埋め込みにも使うことが できるが、多様体学習とグラフ埋め込みの動機は微妙 に異なるので、可視化などに適したグラフに特化した 埋め込み方法が色々研究されている。[22] その他に非 線形独立成分分析 [23]、マルコフ決定過程 [18]、ニュー ロンのスパイクデータ解析 [24]、分子構造の解析等に も多様体学習は使われている。無論、多様体学習の応 用例は既に莫大にあり、これらの例は全く網羅的なも のではない。

5

今後の課題

グラフラプラシアンの収束性の議論は多分に技術的 であるが、他に理論的に解決すべき問題としては例え ば多様体の次元の推定があるだろう。[17] さらに、一 つのチャートでは覆えない多様体の複数のチャートを 求める問題や、多様体のトポロジーをサンプルから学 習する問題 [19] はまだ充分研究されていない。これら は今後の課題であろう。また、単独の多様体だけでな く、複数の多様体を扱う問題、特に交差した、次元の 異なる複数の多様体からサンプルされたデータの学習 (多様体クラスタリング) も重要な問題だと思われる。 本稿では触れなかったが、もちろん確率モデルを用い る方法も強力であり、問題によって埋め込み型の方法 と相補的に用いられるべきであろう。

参考文献

[1] R G. Baraniuk, and M B. Wakin: Random Pro-jections of Smooth Manifolds, Foundations of

Computational Mathematics, Volume. 9, No. 1,

pp.51-77  (2009)

[2] M. Belkin, and P. Niyogi: Laplacian Eigenmaps for Dimensionality Reduction and Data Repre-sentation, Neural Computation, Vol. 15, No.6, pp. 1373–1396 (2003)

[3] M. Belkin, and P. Niyogi: Semi-Supervised Learning on Riemannian Manifolds, Machine

Learning, Vol. 56, No. 1, pp. 209–239 (2004年) [4] M. Belkin, and P. Niyogi: Convergence of

Lapla-cian Eigenmaps, preprint, (2008)

[5] Y. Bengio, O. Delalleau, N. Le Roux, J-F. Paiement, P. Vincent, M. Ouimet: Learn-ing Eigenfunctions Links Spectral EmbeddLearn-ing and Kernel PCA, Neural Computation, Vol. 16, No. 10, pp. 2197–2219 (2004)

[6] B. B`erard, G. Besson and S. Gallot: Embedding Riemannian manifolds by their heat kernel,

Ge-ometric And Functional Analysis, Vol. 4, No. 4,

pp. 374–398 (1994)

[7] M. Bernstein, V de Silva, JC. Langford, and JB. Tenenbaum: Graph approximations to geodesics on embedded manifolds, preprint

[8] R. Coifman, and S. Lafon: Diffusion maps

Ap-plied and Computational Harmonic Analysis ,

Vol. 21, pp. 5–30 (2006)

[9] D L. Donoho, and C Grimes: Hessian eigen-maps: Locally linear embedding techniques for high-dimensional data, Proceedings of National

Academy of Science, Vol. 100, No. 10, pp.

5591-5596 (2009)

[10] D L. Donoho, and C Grimes: Image Manifolds which are Isometric to Euclidean Space,

Jour-nal of Mathematical Imaging and Vision, Vol. 23,

No. 1, pp. 5–24 (2009)

[11] A. Elgammal, and C-S Lee: Inferring 3D Body Pose from Silhouettes Using Activity Manifold Learning, Proc. of CVPR’04, Vol. 2, pp. 681-688 (2004)

[12] J. Ham, D D. Lee, S. Mika, and B. Scholkopf: A kernel view of the dimensionality reduction of manifolds, Proceedings of International

Confer-ence on Machine Learning pp. 47–54 (2004)

[13] M. Hein, J.-Y Audibert, and U. von Luxburg: From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians,

Lec-ture Notes in Computer Science, Vol. 3559,

pp. 1611–3349 (2005)

[14] P. Jones, M. Maggioni, and R. Schul: Universal local parametrizations via heat kernels and eigen-functions of the Laplacian, arXiv:0709.1975.

[15] ND. Lawrence: Gaussian Process Latent Vari-able Models for. Visualisation of High Dimen-sional Data, Advances in NIPS 16, pp. 329–336 (2004)

[16] J. Lee, and S-Y. Lee: Learning the Dynamical System Behind Sensory Data, to appear in

Neu-ral Computation

[17] E. Levina, and PJ. Bickel: Maximum Likelihood Estimation of Intrinsic Dimension, Advances in

NIPS 17, pp. 777–784 (2005)

[18] S Mahadevan, and M. Maggioni: Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes, The Journal of Machine Learning

Re-search, Vol. 8, pp. 2169–2231 (2007)

[19] P. Niyogi, S. Smale, and S. Weinberger: Find-ing the Homology of Submanifolds with High Confidence from Random Samples, Discrete and

Computational Geometry, Vol. 39, No.,pp. 1–23

(2009)

[20] S. Roweis and S. Saul: Nonlinear Dimensional-ity Reduction by Locally Linear Embedding,

Sci-ence, Vol. 290, No. 5500, pp. 2323–2326 (2000)

[21] A. Safonova, J K. Hodgins, Synthesizing Physically Realistic Human Motion in Low-dimensional, Behavior-specific spaces, ACM Transactions on Graphics, Vol. 23, No. 3 (2004)

[22] B. Shaw, and T. Jebara: Structure Preserving Embedding, Proc. of ICML (2009)

[23] A. Singer,and R R. Coifman: Non-linear inde-pendent component analysis with diffusion maps, Applied and Computational Harmonic Analy-sis,Vol. 25, No. 2, pp. 226–239 (2008)

[24] M. Stopfer, V. Jayaraman1, and G. Laurent: In-tensity versus Identity Coding in an Olfactory System, Neuron, Vol. 39, No. 6, pp. 991-1004 (2003)

[25] J. Tenenbaum, V. de Silva, and L. Langford:

Sci-ence, Vol. 290, No. 5500, pp. 2319–2323 (2000)