技術要約：局所探索MCMCレイヤーを用いた学習

問題提起

ニューラルネットワークに組合せ最適化レイヤーを統合すること（決定フォーカス学習）は、複雑な制約を満たす構造化された離散的な決定をモデルに可能にするため、大きな注目を集めています。標準的な定式化では、パラメータ $\theta$ を最適な解 $y \in \mathcal{Y}$ へと写像するレイヤー $\theta \mapsto \arg\max_{y \in \mathcal{Y}} \langle \theta, y \rangle + \phi(y)$ を含みます。

主な課題は、エンドツーエンドの学習にあります。これらのレイヤーは区分的に定数である関数であり、意味のある勾配を持ちません。様々な緩和手法や摂動ベースの手法（例：Differentiable DP、Perturbed Optimizers）が存在しますが、それらの理論的保証は通常、厳密なソルバー（最大事後確率オラクル）が利用可能であることを前提としています。しかし、多くのオペレーションズ・リサーチの問題（例：ルーティング、スケジューリング、ナップサック問題）はNP困難であり、厳密なソルバーの使用は非現実的です。その結果、実務家は不正確なソルバー、具体的には局所探索ヒューリスティック（例：焼きなまし法、変数近傍探索）に頼ることになります。既存の微分可能なフレームワークは、これらの不正確なソルバーに適用された場合、理論的な裏付けを欠くか、あるいは機能しないことがよくあります。

手法

著者らは、局所探索ヒューリスティックとマルコフ連鎖モンテカルロ（MCMC）法の間の架け橋となることで、局所探索ヒューリスティックをニューラルネットワークに統合するための、原理に基づいたフレームワークを提案しています。

1. 局所探索からMCMCへ

局所探索ヒューリスティック（焼きなまし法など）は、メトロポリス・ヘイスティングス（MH）アルゴリズムの観点から捉えることができます。

• 近傍システム: 局所探索は、解 $y$ に対する近傍システム $\mathcal{N}(y)$ を定義します。著者らは、近傍の生成を提案分布 $q(y, \cdot)$ として扱います。
• MCMC定式化: MH受理規則を採用することで、局所探索プロセスは、温度パラメータ $t$ を持つギブス分布 $\pi_{\theta,t}(y) \propto \exp((\langle \theta, y \rangle + \phi(y))/t)$ をターゲットとする離散MCMCサンプラーとなります。
• レイヤー: 組合せレイヤーはこの分布の期待値として定義されます：$\hat{y}_t(\theta) := \mathbb{E}_{\pi_{\theta,t}}[Y]$。この期待値は、MCMC鎖の反復を平均化することによって推定されます。

2. 複数の近傍システムの取り扱い

複雑なヒューリスティックは、解空間を効果的に探索するために、異なる移動タイプ（近傍システム）の混合を利用することがよくあります。

• 課題: 複数の近傍を混合する標準的なMHアプローチでは、すべての可能な移動を合計する補正比を計算する必要がありますが、これは計算量的に実行不可能です。
• 解決策: 著者らは、各ステップで特定の近傍システム $s$ をサンプリングし、移動固有の補正比 $\alpha_s$ を適用するアルゴリズム2を提案しています。これにより、集約された近傍グラフが連結である限り、正しい定常分布を維持しつつ、すべての移動を合計する必要性を回避できます。

3. 損失関数と勾配推定

本フレームワークは、MCMCレイヤーによって解かれる正則化された最適化問題に関連するFenchel-Young損失を利用します。

• 理論的保証: 著者らは、単一のMCMC反復（$K=1$）かつ不正確なソルバーを使用する場合でも、特定のターゲット依存型Fencales-Young損失の勾配が不偏であることを証明しています。これにより、連鎖が定常状態に達することを待たずに、原理に基づいた学習が可能になります。
• 初期化: 条件付き設定では、コントラスティブ・ダイバージェンス（CD）学習と同様に、連鎖はグラウンドトゥルースの解（$y^{(0)} = y_i$）で初期化されます。無条件の設定では、永続的またはデータに基づく初期化が使用されます。

主な貢献

1. 微分可能な確率的レイヤー: 局所探索ヒューリスティックを、近傍システムを離散MCMCの提案分布へと変換することで、微分可能な確率的レイヤーへと変換する手法を導入しました。
2. 統一された混合フレームワーク: 多様な近傍システムの混合を扱うためのフレームットワーク（アルゴリズム2）を拡張し、計算上の過度なオーバーヘッドなしに、強力で複雑なソルバーを統一されたMCMCサンプラーとして使用することを可能にしました。
3. 理論的収束: 提案された学習アルゴリズムが、有限のMCMCステップによるバイアスのある推定値を用いても収束することを、収束分析を通じて示しました。$K=1$ の場合、推定値は特定のFenchel-Young損失の勾配に対応することを実証しています。
4. 計算効率: 厳密なソルバーを局所探索MCMCに置き換えることで、フォワードパスの計算上のボトルネックを大幅に軽減し、より大規模な問題インスタンスでの学習を可能にしました。

実験結果

本手法は、3つの異なるタスクで評価されています。

1. 動的車両配送問題（DVRPTW）:

   • コンテキスト: リクエストが動的に到着する大規模なチャレンジ（EURO Meets NeurIPS 2022）。
   • セットアップ: モデルはクライアントへのサービスに対する「賞金」を予測し、それが賞金収集型VRPTWソルバーに投入されます。
   • 知見: MCMC連鎖をグラウンドトゥルースの解（またはヒューリスティックによる精緻化）で初期化することは、ランダム初期化よりも大幅に優れた性能を示しました。提案手法は、摂動ベースのベースライン（PFY）と比較して競争力のあるテスト相対コストを達成しつつ、計算予算（オラクル呼び出し回数）を劇的に削減しており、学習においてより効率的です。

2. バイナリベクトル予測:

   • コンテキスト: ハイパーキューブ出力空間における合成的な無条件学習タスク。
   • 知見: 実験により、永続的およびデータに基づく初期化が収束に極めて重要であり、ランダムな再起動を大幅に上回ることが確認されました。さらに、近傍システムの混合（異なるハミング距離）を使用することで、単一の提案タイプと比較して収束が改善されることが示されました。

3. 多次元ナップサック問題（MKP）:

   • コンテキスト: 特徴量からアイテムの価値が予測される決定フォーカス学習問題。
   • 知見: 提案されたLocal Search-MCMC (LS-MCMC) レイヤーは、最新のベースライン（SPO+, PFY, NID, NCE）と比較して競争力のあるテスト相対レグレットを達成しながら、バッチあたりの平均時間を大幅に短縮しました。LS-MCMCの勾配分散は他の手法よりも一貫して低く、より安定した学習信号を示しています。

意義と主張

本論文は、不正確な組合せソルバーを用いた学習のための原理に基づいたアプローチを提供すると主張しており、厳密なオラクルを前提とする現在の決定フォーカス学習における重要な限界に対処しています。

• 理論的厳密性: 不正確なソルバーを保証のないブラックボックスとして扱う従来のメソッドとは異なり、本研究はメトロポリス・ヘイスティングスの接続を利用して、特定の条件下での理論的収束と不偏勾配推定を実現することで、ヒューリスティックという「ブラックボックス」を開いています。
• スケーラビリティ: 最適化レイヤーの計算負荷を軽減することで、厳密なソルバーのコストにより以前は困難であった、より大規模で複雑なオペレーションズ・リサーチ問題へのニューラルネットワークの学習を可能にします。
• 実用性: 本アプローチにより、オペレーションズ・リサーチの文献における確立された高性能なメタヒューリスティクスを、ニューラルネットワークに直接統合することが可能になり、古典的な最適化と現代的なディープラーニングの架け橋となります。

著者らは、本フレームワークが摂動ベースの手法よりも「ブラックボックス」性が低いこと（内部の移動構造へのアクセスが必要であること）、および現在は単一軌跡の局所探索に限定されており、集団ベースのメタヒューリスティクスよりもグローバルな探索能力が低い可能性があることを認めています。しかし、彼らは、不正確なソルバーを使用する際に理論的保証を得るためには、このトレードオフが必要であると主張しています。