拡散マップ

拡散マップは、 Coifmanと Lafon ^{[1] [2] [3] [4]}によって導入された次元削減または特徴抽出アルゴリズムであり、データ セットのユークリッド空間 (多くの場合、低次元) への埋め込み のファミリーを計算します。この座標は、データに対する拡散演算子の固有ベクトルと固有値から計算できます。埋め込み空間内のポイント間のユークリッド距離は、それらのポイントを中心とする確率分布間の「拡散距離」に等しくなります。主成分分析(PCA) などの線形次元削減方法とは異なり、拡散マップは、データがサンプリングされた基礎となる多様体を発見することに重点を置く非線形次元削減方法のファミリーの一部です。異なるスケールでのローカルな類似性を統合することにより、拡散マップはデータ セットのグローバルな説明を提供します。他の方法と比較して、拡散マップ アルゴリズムはノイズ摂動に対して堅牢であり、計算コストも低くなります。

^[3]と^[5]に従って、拡散マップは4つのステップで定義できます。

拡散マップは、熱拡散とランダムウォーク マルコフ連鎖の関係を利用します。基本的な観察結果は、データ上でランダムウォークを実行すると、近くのデータポイントに歩く可能性が遠くにある別のデータポイントに歩く可能性よりも高いということです。を測度空間とし、 をデータセット、上の点の分布を表します。 ${\displaystyle (X,{\mathcal {A}},\mu )}$${\displaystyle X}$${\displaystyle \mu}$${\displaystyle X}$

これに基づいて、2 つのデータ ポイント間の接続性、およびは、ランダム ウォークの 1 ステップで からまでを歩く確率として定義できます。通常、この確率は 2 つのポイントのカーネル関数で指定されます。たとえば、一般的なガウス カーネルは次のようになります。 ${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle k:X\times X\rightarrow \mathbb {R} }$

${\displaystyle k(x,y)=\exp \left(-{\frac {||xy||^{2}}{\epsilon }}\right)}$

より一般的には、カーネル関数は以下の特性を持つ。

${\displaystyle k(x,y)=k(y,x)}$

（対称です） ${\displaystyle k}$

${\displaystyle k(x,y)\geq 0\,\,\forall x,y}$

（正値保存です）。 ${\displaystyle k}$

カーネルは、データセットのローカルジオメトリの事前定義を構成します。特定のカーネルはデータセットの特定の特徴を捉えるため、その選択は想定しているアプリケーションに基づいて行う必要があります。これは、すべてのデータポイント間の相関関係を一度に考慮する 主成分分析などの方法との大きな違いです。

が与えられた場合、 上に可逆な離散時間マルコフ連鎖を構築することができます（正規化グラフラプラシアン構築と呼ばれるプロセス）。 ${\displaystyle (X,k)}$${\displaystyle X}$

${\displaystyle d(x)=\int _{X}k(x,y)d\mu (y)}$

そして定義します:

${\displaystyle p(x,y)={\frac {k(x,y)}{d(x)}}}$

新しい正規化カーネルは対称性プロパティを継承しませんが、正値保存プロパティを継承し、保存プロパティを獲得します。

${\displaystyle \int _{X}p(x,y)d\mu (y)=1}$

から、上のマルコフ連鎖 ( )の遷移行列を構築できます。言い換えると、は から への 1 ステップ遷移確率を表し、 はt ステップ遷移行列を与えます。 ${\displaystyle p(x,y)}$${\displaystyle M}$${\displaystyle X}$${\displaystyle p(x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle M^{t}}$

拡散行列を定義する（これはグラフラプラシアン行列の一種でもある） ${\displaystyle L}$

${\displaystyle L_{i,j}=k(x_{i},x_{j})\,}$

次に新しいカーネルを定義します

${\displaystyle L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,}$

または同等に、

${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }\,}$

ここでDは対角行列であり、${\displaystyle D_{i,i}=\sum _{j}L_{i,j}.}$

この新しいカーネルにグラフラプラシアン正規化を適用します。

${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )},\,}$

ここで対角行列であり、${\displaystyle D^{(\alpha )}}$${\displaystyle {D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.}$

${\displaystyle p(x_{j},t|x_{i})=M_{i,j}^{t}\,}$

拡散フレームワークの主なアイデアの 1 つは、連鎖を時間的に前進させると ( の累乗を大きくしていくと)、 の幾何学的構造がより大きなスケールで明らかになる (拡散プロセス) というものです。具体的には、データセット内のクラスターの概念は、この領域から抜け出す確率が低い領域 (特定の時間 t 内) として定量化されます。したがって、 t は時間パラメータとして機能するだけでなく、スケールパラメータという 2 つの役割も果たします。 ${\displaystyle M}$${\displaystyle X}$

行列 の固有値分解により、${\displaystyle M^{t}}$

${\displaystyle M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,}$

ここで、はの固有値のシーケンスであり、 はそれぞれ双直交左固有ベクトルと双直交右固有ベクトルです。 固有値のスペクトル減衰により、この合計で所定の相対精度を達成するには、いくつかの項のみが必要です。 ${\displaystyle \{\lambda _{l}\}}$${\displaystyle M}$${\displaystyle \{\psi _{l}\}}$${\displaystyle \{\phi _{l}\}}$

を伴う正規化ステップを導入する理由は、データ ポイント密度が拡散の微小遷移に与える影響を調整するためです。一部のアプリケーションでは、データのサンプリングは、記述する多様体の幾何学とは一般に関係ありません。この場合、 を設定でき、拡散演算子はラプラス–ベルトラミ演算子を近似します。次に、ポイントの分布に関係なく、データ セットのリーマン幾何学を復元します。確率微分方程式系のポイント分布の長期的な動作を記述するには、 を使用できます。結果として得られるマルコフ連鎖は、フォッカー–プランク拡散 を近似します。 を使用すると、古典的なグラフ ラプラシアン正規化に簡約されます。 ${\displaystyle \alpha }$${\displaystyle \alpha =1}$${\displaystyle \alpha =0.5}$${\displaystyle \alpha =0}$

2点間の拡散距離は、観測空間における2点の類似性とそれらの間の接続性として測定できます。これは次のように表されます。 ${\displaystyle t}$

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}}$

ここで、はマルコフ連鎖の定常分布であり、 の最初の左固有ベクトルによって与えられます。明示的には、 ${\displaystyle \phi _{0}(y)}$${\displaystyle M}$

${\displaystyle \phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}}$

直感的に、と を接続する短い経路が多数ある場合、 は小さくなります。 以前の議論に基づいて、拡散距離に関連する興味深い特徴がいくつかあります。これはスケールパラメータとしても機能します。 ${\displaystyle D_{t}(x_{i},x_{j})}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle t}$

1. グラフ内でポイントが高度に接続されている場合、ポイントは特定のスケール（ で指定）でより近くなり、クラスターの概念が強調されます。${\displaystyle D_{t}(x_{i},x_{j})}$
2. 2 点間の距離は、点間の長さの可能なすべての経路に依存するため、この距離はノイズに対して堅牢です。${\displaystyle t}$
3. 機械学習の観点から見ると、距離はにリンクするすべての証拠を考慮に入れており、この距離は優勢性の多数に基づく推論アルゴリズムの設計に適していると結論付けることができます。^[3]${\displaystyle x_{i}}$${\displaystyle x_{j}}$

拡散距離は、固有ベクトルを用いて次のように計算できる。

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,}$

したがって、固有ベクトルはデータの新しい座標セットとして使用できます。拡散マップは次のように定義されます。

${\displaystyle \Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))}$

スペクトルの減衰のため、最初のk 個の固有ベクトルと固有値のみを使用すれば十分です。このようにして、元のデータから元の空間に埋め込まれたk次元空間への拡散マップが得られます。

^[6]では、

${\displaystyle D_{t}(x_{i},x_{j})^{2}\approx ||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,}$

したがって、拡散座標におけるユークリッド距離は拡散距離に近似します。

拡散マップの基本的なアルゴリズムフレームワークは次のとおりです。

ステップ1.類似度行列Lが与えられます。

ステップ 2. パラメーターに従って行列を正規化します 。${\displaystyle \alpha }$${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }}$

ステップ3. 正規化された行列を作成します。 ${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )}}$

ステップ 4.のk 個の最大固有値と対応する固有ベクトルを計算します。 ${\displaystyle M^{t}}$

ステップ 5. 拡散マップを使用して埋め込みを取得します。 ${\displaystyle \Psi _{t}}$

論文^{[6]でNadlerらは、}フォッカー・プランク方程式によって引き起こされる拡散を再現するカーネルの設計方法を示しました。彼らはまた、データが多様体を近似する場合、ラプラス・ベルトラミ演算子の近似を計算することによってこの多様体の形状を回復できることを説明しました。この計算は点の分布にまったく影響されないため、統計とデータの形状を分離できます。拡散マップはデータセットのグローバルな記述を与えるため、データが埋め込まれている多様体内のサンプル点のペア間の距離を測定できます。拡散マップに基づくアプリケーションには、顔認識、^[7] スペクトルクラスタリング、画像の低次元表現、画像セグメンテーション、^[8] 3Dモデルセグメンテーション、^[9]話者検証^[10]および識別、^[11]多様体上のサンプリング、異常検出、^{[12] [13]}画像修復、^[14]脳の安静時ネットワーク組織の解明^[15] などがあります。

さらに、拡散マップの枠組みは複雑ネットワークに効果的に拡張され、^[16]純粋に位相的または構造的なものとは異なるネットワークの機能的構成を明らかにした。

• 非線形次元削減
• スペクトルクラスタリング