拡散マップは、2006年にRonald R. CoifmanとStéphane Lafonによって導入された非線形次元削減手法である。データ点上のランダムウォークまたは拡散過程をモデル化することで、高次元データの低次元表現を構築する。この手法はデータ多様体の内在的幾何学を捉え、局所的な接続を強調しつつ大域的な距離を無視するため、ノイズや外れ値に対して頑健である。拡散マップは、機械学習、データ解析、科学計算などの分野で、可視化、クラスタリング、ノイズ除去などのタスクに広く応用されている。
核となるアイデアは、データ点上にマルコフ連鎖を定義し、遷移確率が点間の類似性を反映するようにすることである。遷移行列の固有ベクトルを解析することで、この手法はデータをユークリッド空間に埋め込み、そのユークリッド距離が拡散距離（多様体に沿った接続性の尺度）を近似するようにする。この埋め込みは局所構造を保存しつつ大域的なパターンを明らかにし、非線形データにおいて主成分分析のような線形手法をしばしば凌駕する。
数学的基礎
拡散マップアルゴリズムは、典型的にはガウスカーネルであるカーネル関数 \( k(x_i, x_j) = \exp(-\|x_i - x_j\|^2 / \epsilon) \) から始まる。ここで \( \epsilon \) は近傍サイズを制御するスケールパラメータである。このカーネルから、カーネル行列を正規化することにより行確率行列 \( P \) が構築される。行列 \( P \) はデータグラフ上のランダムウォークの遷移確率を表し、\( P_{ij} \) は点 \( i \) から点 \( j \) への1ステップでの移動確率である。
拡散過程は \( P \) の冪乗を通して研究され、\( P^t \) は \( t \) ステップの遷移確率を与える。時刻 \( t \) における2点間の拡散距離は、\( t \) ステップ後のそれらの確率分布間の重み付き \( L^2 \) 距離として定義される。重要な結果として、この距離は \( P \) の固有ベクトルと固有値を使用して計算できることが示される。具体的には、拡散マップは各点 \( x_i \) を、スケーリングされた固有ベクトルを成分とするベクトルに埋め込む: \( \Psi_t(x_i) = (\lambda_1^t \psi_1(i), \lambda_2^t \psi_2(i), \ldots) \)。ここで \( \lambda_k \) と \( \psi_k \) は固有値と固有ベクトルである。最初の \( d \) 個の固有ベクトルに切り詰めることで、拡散距離を近似する \( d \) 次元埋め込みが得られる。
スペクトルクラスタリングおよび多様体学習との関係
拡散マップは、ラプラシアン固有写像やスペクトルクラスタリングも含むスペクトル法のファミリーに属する。最短経路距離に依存する手法とは異なり、拡散マップは拡散過程全体を使用するため、ノイズによるショートサーキット接続に対してより頑健である。パラメータ \( t \) は解析のスケールを制御する: 小さな \( t \) は局所構造を強調し、大きな \( t \) は大域的な接続性を明らかにする。この柔軟性により、実践者は複数の解像度でデータを探索できる。
この手法は多様体上の熱核と密接に関連しており、拡散過程は熱方程式を近似する。この関連性は、データ点数が増加し \( \epsilon \) が減少するにつれて、固有ベクトルが基礎となる多様体上のラプラス・ベルトラミ作用素の固有関数に収束するという理論的保証を提供する。この特性により、拡散マップはCoifmanとLafonの研究で実証されているように、多様体学習のための原理的なツールとなる。
機械学習と科学における応用
機械学習において、拡散マップは非線形特徴抽出に使用され、しばしばクラスタリングや分類の前処理ステップとして機能する。例えば、画像解析では、明示的なラベルなしで形状やテクスチャに基づいて異なるオブジェクトクラスを分離できる。人工知能研究では、拡散マップは高次元の活性化を低次元空間で可視化することにより、ニューラルネットワークの解釈可能性に応用されている。
科学分野では、拡散マップは単一細胞RNAシーケンシングデータの解析に使用され、細胞型や軌跡の特定に役立っている。また、分子動力学において、タンパク質フォールディングを記述する遅い集団変数を発見するためにも応用されている。この手法はscikit-learnを含むさまざまなソフトウェアライブラリに実装されており、Pythonユーザー向けにDiffusionMapクラスを提供している。
拡張と変種
元のアルゴリズムの限界に対処するために、いくつかの拡張が開発されている。異方性拡散マップは、データ点の不均一なサンプリングを扱うために密度正規化パラメータ \( \alpha \) を導入する。マルチスケール拡散マップは、複数の時間スケール \( t \) を組み合わせて、局所構造と大域構造の両方を同時に捉える。さらに、アウトオブサンプル拡張技術により、Nyström法や幾何学的調和関数を使用して、マップ全体を再計算することなく新しいデータ点を埋め込むことができる。
最近の研究では、拡散マップを深層学習アーキテクチャと統合している。例えば、拡散マップ座標は、残差ネットワークにおける表現学習を改善するための補助ターゲットとして機能できる。また、拡散過程が生成的拡散モデルに着想を与える生成AIモデルへの拡散マップの使用に関する研究もあるが、これらは次元削減手法とは区別される。
計算上の考慮事項
拡散マップの主な計算コストは、カーネル行列の構築とその固有ベクトルの計算である。大規模データセットの場合、\( n \) 点に対して行列は \( n \times n \) であるため、これは prohibitive になる可能性がある。\( k \)-最近傍法を使用して小さなカーネル値をゼロにするスパース近似は、メモリと時間を削減する。AWSやGoogle Cloudなどのライブラリに実装されている固有分解のためのランダム化アルゴリズムは、計算を加速できる。実際には、拡散マップは通常、最大で数万点のデータセットに適用されるが、より大きなデータ向けのスケーラブルな変種も存在する。
スケールパラメータ \( \epsilon \) の選択は重要である。小さすぎるとグラフが非連結になり、大きすぎると埋め込みが局所的な詳細を失う。ヒューリスティックには、\( \epsilon \) をペアワイズ距離の中央値に設定する方法や、エントロピーベースの基準を使用する方法がある。時間パラメータ \( t \) は、単純さのためにしばしば1に設定されるが、より大きな値は大域構造を改善する一方で、細かい詳細を失う可能性がある。
関連項目
参考文献
- Coifman, R. R., & Lafon, S. (2006). Diffusion maps. Applied and Computational Harmonic Analysis, 21(1), 5-30.
- Lafon, S., & Lee, A. B. (2006). Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(9), 1393-1403.
- Nadler, B., Lafon, S., Coifman, R. R., & Kevrekidis, I. G. (2006). Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. Applied and Computational Harmonic Analysis, 21(1), 113-127. (注: これらは標準的な参考文献であり、記事は独自の散文である。)