novelty日記

データサイエンスやプログラムなど

論文アイデアメモ: diffusion map

論文

diffusion mapという少し前に出て有名な論文を読む。

アブストとイントロだけ理解する。

アブスト

データの幾何学的な特徴を発見するためにdiffusionプロセスというものを提案する。

マルコフ行列(遷移確率行列)の固有ベクトルを元にしてデータの幾何構造を良く表す座標系への写像(diffusion map)を構築する事が可能である。

マルコフ行列による遷移を繰り返す過程(マルコフ過程)において、その固有ベクトルにより複数スケールの幾何構造が定義され、それはデータのパラメータ化、次元削減に応用可能である。

結局これはマルコフ過程とスペクトル学習を繋げる意味合いを持ち合わせている事になる。

イントロ

巨大で冗長なデータを本質的な低次元モデルで表すのは大事である。

本論ではグラフ理論をベースにして手法を提案する。

グラフは例えば、データサンプル間の局所的な類似性や関係の強さの幾何構造を示すのに使える。

これらは特に非線形モデルにも適用可能である。

スペクトル学習では、そんなグラフ構造を元にしたマルコフ行列(遷移確率)を用いてマルコフ過程が構築し、その固有ベクトルによって構造的に密な部分とそうでない部分を見つけてくる事を可能にする(スペクトルクラスタリング、グラフカット)。

またPageRankといったランキング系アルゴにおいても、文書間の関係の強さをランキングするためにマルコフ行列の固有ベクトルを用いる。

一方、多様体学習においては、データ間距離に基づいた類似性評価によりデータをグラフ表現しておく事で、データのユークリッド的な多様体構造を表現する事が可能で、その固有ベクトルはその多様体が拡がっていく方向を良く示す軸として考えられる。

そのため固有値の高い少数の固有ベクトルで張る空間はデータの多様体構造上を張る空間として捉えられる。

この空間では、局所的なデータ間の関係性を保ったまま、低次元空間を学習する事が出来ている。

本手法てはこうした多様体学習の手法は拡散プロセスの特別な場合である事を示す。

遷移確率行列を用いたランダム・ウォークにより描かれるパスは拡散プロセスとして考えられるため、対応する固有ベクトルは主要な拡散方向を表していると解釈出来る。

すなわち、各固有ベクトルはスペクトル的な意味、いくつかのスケールにおける拡散方向を示している事になる。

その他

多様体学習はグラフラプラシアンとかのイメージだが、拡散マップはそれを任意の類似性尺度に拡張したという事か?