Spectral partitioning for $k$-block averaging kernels of finite Markov chains

技術要約：有限マルコフ連鎖のkブロック平均カーネルのためのスペクトル分割

問題提起
本論文は、有限かつエルゴード的で可逆なマルコフ連鎖に対して、「平均化カーネル」を定義するための最適な状態空間分割 $\mathcal{O} = \{O_1, \dots, O_k\}$ を選択するという計算上のボトルネックに対処している。ベースラインとなるカーネル $P$ に、ギブスカーネル $G_\mathcal{O}$（ブロック内で定常条件付き分布から再サンプリングするもの）または加法混合 $A_\mathcal{O} = (P + G_\mathcal{O})/2$ を補完することで収束を加速できるが、この加速を最大化する分割を見つけることは組合せ爆発的な困難を伴う。著者らは、全探索を行うことなく $\mathcal{O}$ を選択するためのスペクトルアルゴリズムを求めており、具体的には「厄介なモード」を抑制し、混合を高速化することを目指している。

手法
核となるアプローチは、分割選択をスペクトル・ラウンディング問題として定式化することである。著者らは、$\pi$ 重み付きの定常分布へのフロベニウス二乗距離に基づく目的関数を定義し、それらの連続緩和をマルコフ作用素の固有関数を用いて導出している。

1. 目的関数と緩和:

   • 1ステップ・フロベニウス目的関数 ($F$): $F(\mathcal{O}) = \|G_\mathcal{O}P - \Pi\|_{F,\pi}^2$ と定義される。著者らは、これが $\text{Tr}((G_\mathcal{O} - \Pi)P^2)$ に等しいことを示している。この $F$ の連続緩和は、$P^2$ の下位の非定数固有関数（最小の固有値）によって支配される。$F$ を最小化することは、$P^2$ という2ステップ連鎖のマルチウェイ正規化カット（multiway normalized cut）を最大化することと同等である。
   • 加法混合目的関数 ($H$): $H(\mathcal{O}) = \|A_\mathcal{O} - \Pi\|_{F,\pi}^2$ と定義される。この目的関数の緩和は、$P$ の代数的に最小の固有関数（$P^2$ とは異なり、符号を保持するもの）に依存する。
   • マルチホライゾン目的関数: このフレームワークは、ラグ付き（lagged）および割引無限ホライゾン目的関数 $F^\infty_\gamma$（時間の経過に伴う情報を集約するもの）へと拡張される。これらは $P^2$ のスペクトルフィルタを使用するが、固有値の順序が保存されている限り、1ステップの目的関数と同じ下位スペクトル部分空間を保持する。

2. 情報理論的解釈:
   本論文は、$F(\mathcal{O})$ が初期のブロックラベル $Z$ と、1回の遷移後の状態 $X_1$ の間のピアソン $\chi^2$ 相互情報量 $I_{\chi^2}(Z; X_1)$ に正確に一致することを確立している。したがって、$F$ を最小化することは、1ステップにおけるブロックラベル情報の損失を最大化すること、すなわち、ブロック間の正規化されたフロー（normalized cross-block flow）が大きい分割を選択することに対応する。

3. スペクトル・ラウンディング・アルゴリズム:

   • 埋め込み（Embedding）: 状態を、関連する作用素（$F$ の場合は $P^2$、$H$ の場合は $P$）の下位 $k-1$ 個の固有関数を用いて $\mathbb{R}^{k-1}$ に埋め込む。
   • ラウンディング（Rounding）: この埋め込みを、重み付き $k$-means（重み $\pi(x)$ を使用）を用いて $k$ ブロック分割へと丸める。ラウンディング誤差 $\delta(\mathcal{O})$ は、緩和されたスペクトル部分空間とブロック定数関数の部分空間との間の弦距離（chordal distance）の二乗として示される。
   • 再スコアリング（Rescoring）: 幾何学的なサロゲート（代理指標）である $\delta(\mathcal{O})$ が必ずしも元の目的関数を最小化するわけではないため、アルゴリズムは $k$-means を通じて候補となる分割を生成し、その後、厳密な目的関数（$F, H, F^\infty_\gamma$）を評価することで最終的な分割を選択する。
   • 2ブロックの場合: $k=2$ の場合、この問題は1次元の重み付き2-means問題に帰着し、これは下位固有関数の閾値スイープ（threshold sweep）によって厳密に解かれる。

主な貢献

• スペクトルの方向性: 本論文は、古典的な正規化スペクトル・クラスタリングとは「逆」のスペクトル・クラスタリング・アプローチを導入している。古典的な手法は、低周波成分である上位の非定数モードを用いて、通信が遅いクラスター（境界が小さい領域）を見つけるが、本手法は下位モード（ラプラシアン $I-P^2$ に関する高周波成分）を用いて、正規化されたクロスブロック・フローが大きい分割を見つける。
• 厳密なトレースおよびカット表現: 著者らは、フロベニウス目的関数を $P^2$ の正規化カットおよびピアソン $\chi^2$ 相互情報量に結びつける厳密な恒等式を導出した。
• 理論的保証: 論文は、ラウンディング誤差 $\delta(\mathcal{O})$ と目的関数 $F(\mathcal{O})$ を関連付ける「スペクトル・サンドイッチ」境界を提供している。これらの境界は、固有値ギャップ（eigengap）とスペクトル幅に依存しており、スペクトル・スイープの最適分割に対する劣最適性に関する保証を与える。
• 加法混合およびマルチホライゾンへの拡張: フレームワークは加法混合（$P^2$ ではなく $P$ を使用）および有限または割引無限ホライゾン上の目的関数へと一般化されており、異なる時間スケールがいかに異なる分割を選択するかを示している。

結果
著者らは、以下の3つの異なる実験によって手法を検証している：

1. 制御されたスペクトルを持つグラフ: 正負の固有値を調整可能な重み付きダンベルグラフ。実験により、負の固有値が顕著な場合に、加法混合目的関数（$H$）がフロベニウス目的関数（$F$）とは異なる分割を選択することが示され、符号を保持することの重要性が確認された。マルチホライゾン目的関数は、1ステップの目的関数とは異なる分割を選択し、より長い時間スケールにおいて性能を向上させることが示された。
2. 平均場イジングモデル: キュリー・ワイス・モデルにおける、厳密な有限状態実験（$d=8$）。スペクトル・スイープは、決定論的なベースライン（磁化ビン、座標ブロック）やランダムな分割を大幅に上回り、目的関数の値を減少させた。得られた分割は、標準的なメタステーブル（準安定）クラスターに似ているのではなく、持続的なスペクトルモードを抑制するように設計されたブロックであった。
3. ベイズ変数選択: 4096の状態を持つベンチマーク。この研究では、制約のないスペクトル・ラウンディングがしばしば極端に不均衡なブロック（質量が1つのブロックに崩壊する）を生じさせることが、実用的な解決策というよりも、オラクル的な診断ツールとして機能することを浮き彫りにした。ブロック質量制約を課すことで、ベースラインのメトロポリス・カーネルと比較して、統計的推定誤差（事後包含確率、モデルサイズ分布、予測精度）を大幅に改善するバランスの取れた分割が得られた。

意義および主張
本論文は、MCMCの収束を加速させるための平均化カーネルを構築するための、原理に基づいた計算可能な手法を提供すると主張している。これは、単にグループ作用をチューニングするだけでなく、分割選択のための具体的なスペクトルアルゴリズムを提供する点で、既存のグループ平均化MCMCの研究と一線を画している。著者らは、自らの手法が固有関数を単なる収束の診断用としてではなく、より速く混合することを意図した、シミュレーション可能な新しいカーネルを構築するために使用している点を強調している。

その意義は、スペクトル・クラスタリングのパラダイムの逆転にある。持続的なクラスターを見つけるのではなく、ブロック情報の「損失」を最大化する分割を見つけ、それによって遅いモードを打破する。論文では、スペクトルによる候補生成は効果的であるが、変数選択の実験における主な改善要因は、制御されたブロック質量を持つ非退化な条件付き平均化ステップの導入であったことが控えめに述べられており、これはスペクトル法が、離散的な分割問題に対するグローバルな最適解を保証するものではなく、高品質な候補を生成する堅牢なジェネレーターとして機能していることを示唆している。