Variational Free Energy Pivot Selection for Pivoted Cholesky

技術要約：ピボット付きコレスキー分解のための変分自由エネルギー・ピボット選択

問題提起
対称正定値（SPD）行列の低ランク近似は、数値線形代数、特にガウス過程（GP）回帰において、カーネル行列 $K$ をランク $r$ の分解 $\tilde{K} = LL^\top$ で近似する際に極めて重要である。貪欲法やランダム・ピボット・コレスキー（RPCholesky）などの古典的な手法は、残差の代数的なトレースノルム誤差（$\text{tr}(K - \tilde{K})$）を最小化するように逐次的にピボットを選択する。しかし、多くのアプリケーションにおいて、行列 $K$ は単独で評価されるのではなく、非線形な行列関数の中で評価される。具体的には、GP回帰において、近似の質は変分自由エネルギー（VFE）$L(\tilde{K})$ によって決定され、これは対数周辺尤度の下界として機能する。

VFE汎関数は、3つの異なる項（複雑さを示す対数行列式項、二次的なデータ適合項、およびトレース・ペナルティ項）を組み合わせたものである。既存のピボット選択規則は、残差の対角成分の大きさにのみ依存しており、トレースノルム誤差を標的としている。その結果、これらは対数行列式およびデータ適合の成分を無視しており、特定の推論目的において系統的に劣った近似をもたらす可能性がある。本論文は、以下の問いに取り組んでいる：行列の近似誤差そのものではなく、行列汎関数を最適化することが目的である場合、どのようにピボット選択を行うべきか？

手法
著者らは、$\Delta$-VFE ピボット付きコレスキーと呼ばれる新しいピボット選択規則を提案している。これは、コレスキー整合的なランク1更新の下で、VFE 汎関数の正確な一ステップの変化を直接最大化するものである。

1. 利得式の導出:
   著者らは、ランク1更新 $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$ によって誘発される VFE $L(\tilde{K})$ の正確な変化 $\Delta L$ に関する閉形式の式を導出した。行列行列式補題（Matrix Determinant Lemma）とシャーマン・モリソン公式（Sherman-Morrison formula）を用いることで、彼らは利得を以下の3つの加法的な成分に分解した：
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   ここで：

   • $a = u^\top \Sigma_i^{-1} u$ は、複雑さの寄与（対数行列式項）であり、正則化された逆行列メトリックとの相互作用を測定する。
   • $b = u^\top \Sigma_i^{-1} y$ は、データ適合の寄与であり、更新方向と現在の予測残差との間の整合性を測定する。
   • $\|u\|^2_2$ は、トレースの寄与（残差分散の減少）であり、古典的な手法で使用される対角成分のプロキシではなく、正確な一ステップのトレース減少に対応する。

2. コレスキー整合的な更新:
   近似が有効なコレスキー分解であり続けることを保証するために、更新ベクトル $u$ は $u_p = t_p / \sqrt{(T_i)_{p,p}}$ という形式に制限される。ここで $t_p$ は残差行列 $T_i$ の第 $p$ 列である。この制限により、残差が半正定値であり、選択されたピボットの対角成分がゼロになることが保証される。

3. アルゴリズムの実装:
   すべての $n$ 個の候補に対して $\Delta L$ を評価することは計算量的に困難である（$O(n^2r^2)$）。効率を維持するため、本手法はバッチサンプリング戦略を採用している：

   • 各反復において、$s$ 個の候補ピボットが未使用のインデックス集合からサンプリングされる。
   • サンプリング確率は、RPCholesky で使用される分布と同様に、残差の対角成分に比例する。
   • 正則化された逆行列 $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$ は、ウッドベリーの公式（Woodbury matrix identity）と補助行列 $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$ への逐次的な更新を用いて、効率的に適用される。
   • このアプローチにより、バッチ因子 $s$ を除いて RPCholesoles と同等の漸近計算量 $O(snr^2)$ で、$s$ 個の候補に対する利得の評価が可能となる。

主な貢献

• 目的関数を考慮したピボット規則: 本論文は、トレースノルム誤差ではなく、VFE の一ステップあたりの利得を明示的に最大化する最初のピボット選択基準を導出した。
• 理論的保証: 著者らは、コレスキー整合的なランク1更新の任意の系列が、VFE 値の単調非減少な系列をもたらすことを証明している。提案された規則は、各ステップでこの保証された利得を最大化するピボットを選択する。
• 計算効率: ウッドベリーによる逐次更新とバッチ候補評価を活用することで、ランダム化ピボット・コレスキー（$O(snr^2)$）と同じ漸近計算量を達成している。
• 階層的解釈: 本研究は、ピボット規則の3段階の階層を確立している：
  1. レベル1: 古典的な貪欲法/RPCholesky（トレース減少のための対角プロキシを使用）。
  2. レベル2: 正確なトレース減少最大化器（フル残差列を使用し、データ/複雑さを無視）。
  3. レベル3: $\Delta$-VFE（フル残差列、データベクトル、および正則化逆行列を使用し、完全なVFEを最適化）。

結果
Abalone および QM7 データセットを用いた数値実験により、以下のことが示された：

• VFE 最適化: $\Delta$-VFE は、低・中程度のランク（$r \le 1024$）において、貪欲法および RPCholesky の両方と比較して、対数周辺尤度のよりタイトな下界（より小さい相対 VFE ギャップ）を一貫して達成する。
• 近似の質: 本手法は、RPCholesky と同等のトレースノルム近似精度を維持している。VFE の改善を得るために、標準的なカーネル近似の精度を犠牲にすることはない。
• 予測性能: GP 回帰タスクにおいて、改善された VFE は、低・中程度のランクにおける予測誤差（RMSE および MAE）の減少につながる。
• バッチサイズへの感度: バッチサイズ $s$ を大きくすると、性能の向上には収穫逓減が見られるものの、VFE ギャップと予測精度は一貫して向上する。小さなバッチサイズ（例：$s=8$ または $s=16$）であっても、RPCholesky に対して大幅な改善が得られる。

意義
本論文は、提案手法が代数的な行列近似と、タスク固有の推論目的との間の溝を埋めるものであると主張している。VFE の正確な閉形式の利得を導出することにより、著者らは、ガウス過程の確率的推論の目的と明示的に一致した、貪欲なピボット規則を提供している。結果は、行列汎関数にデータ適合項や複雑さの項が含まれる場合、トレースノルム誤差のみを最適化することは不十分であり、目的関数を考慮した選択が、大きな計算オーバーヘッドなしに優れた実用的性能をもたらすことを示唆している。本手法は、追加の情報を組み込んだ RPCholesky の直接的な一般化として提示されている。