🤖 machine learning

Regularized Large Neighborhood Search

本論文は、正則化によってLNSヒューリスティックを効率的なMCMCサンプラーへと変貌させ、計算量的に困難なグローバルソルバーを必要とせずに組合せ最適化レイヤーのエンドツーエンド学習を可能にする、新たなフレームワークであるRegularized Large Neighborhood Search (RLNS) を導入するものである。

原著者： Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

公開日 2026-06-02

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、非常に巨大で、信じられないほど複雑なパズルを解こうとしているところだと想像してください。そこには何千ものピースがあり、それらは厳格なルールを満たすように完璧に組み合わさる必要があります。数学やコンピュータサイエンスの世界では、これは組合せ最適化問題と呼ばれます。

数十年にわたり、専門家（オペレーションズ・リサーチャー）は、このパズルを解くための巧妙なトリックである**大規模近傍探索（Large Neighborhood Search: LNS）**を使用してきました。LNSを、小説の熟練した編集者だと考えてみてください。物語全体を一度に書き直そうとするのではなく（それは不可能です）、編集者は物語の90%を凍結させ、一度に一つの小さな章だけを書き換えます。彼らはその章のベストなバージョンを見つけ出し、それを固定し、次の章へと進みます。そしてこれを繰り返します。これは高速でスケーラブルですが、「ヒューリスティック」、つまり完璧なグローバル解を保証するのではなく、非常に優れた解を見つけるための「最善の推測」に基づく手法です。

部屋の反対側では、機械学習の研究者たちが、事例を見ることでコンピュータにこれらのパズルを解く方法を教えようとしています。彼らは「ニューラルネットワーク」（AIの一種）を構築し、パズルのルールを学習して解を出力させたいと考えています。しかし、AIを訓練するためには、コンピュータが答えをより良くするための「つまみ」（勾配）をどのように調整すべきかを知る必要があります。これには通常、厳密なグローバルソルバー（常に完璧な解を見つける手法）が必要です。

問題点：
巨大な現実世界のパズル（配送トラックのスケジューリングやタスクの割り当てなど）の場合、完璧なグローバル解を見つけることは計算量的に不可能です。それには宇宙の年齢よりも長い時間がかかるでしょう。したがって、AIの訓練に使用される「完璧な」ソルバーは、オペレーションズ・リサーチャーが日々使用しているような大規模な問題には機能しないのです。

解決策：正則化LNS（Regularized LNS: RLNS）
この論文の著者たちは、この溝を埋める方法を提示しています。彼らは**正則化大規模近傍探索（Regularized Large Neighborhood Search: RLNS）**と呼ばれる新しい手法を開発しました。

以下に、いくつかの比喩を用いて、彼らがどのようにこれを行ったかを説明します。

1. 「滑らかな」編集者

標準的なLNSは硬直的です。パズルの小さな部分を選び、それを修正する唯一の「最善の方法」を見つけ出します。
RLNSは、このプロセスに「温度」または「ノイズ」を加えます。編集者が単に「最善の一文」を探すだけでなく、確率に基づいて、いくつかの異なる「十分に良い」文章を試すことが許されていると想像してください。

魔法の効果: このランダム性（正則化）を加えることで、編集者は単に「推測」するのをやめ、統計的サンプラーとして振る舞い始めます。彼らはもはや単に局所的なピークを探しているのではなく、時間の経過とともに、あらゆる可能な「良い解」の統計的分布を完璧に模倣するように、景観を探索しているのです。

2. 「ブロック・ギブス」のダンス

論文では、特定の種類の「ノイズ」（正則化と呼ばれる）を使用すると、RLNSが**ブロック・ギブス・サンプラー（Block Gibbs Sampler）**になることを証明しています。

比喩: 数千人の人々（可能な解）がいるダンスフロアを想像してください。あなたは群衆がどこにいる可能性が最も高いかを知りたいと考えています。
- 古い方法: フロアにいる全員を一度に数えようとします（グローバルソルバー）。これは巨大な群衆に対しては不可能です。
- RLNSの方法: ダンサーの90%をその場に固定します。そして残りの10%に対し、他の人々が立っている場所を考慮した上で、彼らにとってのベストな場所を見つけるように動いてもらいます。次に、別の90%を固定し、新しい10%にシャッフルさせます。
- 結果: 論文は、もしこの「シャッフルして固定する」ダンスを繰り返せば、群衆はあたかも全員を完璧に数え上げたときと同じパターンに最終的に落ち着くことを証明しています。あなたは、不可能なグローバルカウントを必要とせずに、統計的な真実を得ることができるのです。

3. 「完璧な」ソルバーなしでの学習

これがAIの学習にどのように役立つかという点が、最大の画期的な進歩です。

古い問題: AIを訓練するには、通常、エラーを計算するために「完璧な」答えを知る必要があります。完璧な答えが見つからない場合、AIを訓練することはできません。
RLNSによる解決策: 著者たちは、これらの「局所的なシャッフル」だけでAIを訓練できることを示しています。
- もし1回のシャッフル（K=1）を行う場合、AIは「疑似尤度（pseudolikelihood）」（局所的な近似）に基づいて学習します。これは高速で安価です。
- もし多くのシャッフル（K=100）を行う場合、AIは「正確な最大尤度（exact maximum likelihood）」（グローバルの真実）に近い形で学習します。
- メリット: あなたは、速度と精度の間でトレードオフを行うための「つまみ」を回すことができます。もうグローバルソルバーは必要ありません。必要なのは、オペレーションズ・リサーチャーがすでに使用している局所的な「編集者」（LNS）だけです。

4. 実世界でのテスト

著者たちは、3種類のパズルでこのRLNSをテストしました。

アイテムのサブセット選択: 1,000個の中からちょうど500個のアイテムを選ぶようなケース。
一般割当問題（Generalized Assignment）: 5台のトラックの限られたスペースに50個の荷物を割り当てるようなケース。
車両スケジューリング（Vehicle Scheduling）: 不確実な交通遅延がある都市内での配送トラックのルート作成のようなケース。

これらすべてのケースにおいて、RLNSは機能しました。RLNSは、「ブラックボックス」的な近似を使用したり、不可能なグローバル計算を必要としたりする方法よりも、高速かつ効率的に、良い解を予測することを学習しました。

まとめ

この論文は、通常の「局所探索」ヒューリスティック（通常は単に「一つの良い答え」を見つけるだけのもの）を、AIモデルを訓練するために使用できる厳密な統計ツールへと変える手法であるRLNSを紹介しています。

これは、機械学習モデルが、巨大で複雑な現実世界のパズル（物流やスケジューリングなど）を解く方法を、まずそのパズルの「完璧な」バージョンを解くことなく学習することを可能にします。これは実質的にこう言っています。「森全体を見る必要はない。目の前にある木々をどのように進むべきかを知り、それを十分に頻繁に行えばよいのだ。」

技術要約：正則化大規模近傍探索 (Regularized Large Neighborhood Search: RLNS)

問題提起

組合せ最適化レイヤーをニューラルネットワークに統合することは、構造化予測のための強力なパラダイムとして台頭しており、モデルが複雑な制約を満たす離散的な決定を出力することを可能にしている。標準的な定式化では、 $\mathcal{Y}$ を有限だが組合せ爆発的な実行可能解の集合としたとき、 $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$ と定義されるレイヤーが含まれる。

この設定における根本的な課題は、微分可能性である。 $\arg \max$ 演算子はほとんどの領域でゼロ勾配を与えるため、既存のアプローチは通常、連続的で微分可能な緩和を実現するために正則化に依存している。しかし、既存の多くの手法（Fenchel-Young損失や摂動付き最適化器など）は、グローバルな厳密なソルバー（グローバルMAPオラクル）へのアクセス、またはギブス分布の期待値を計算するための周辺オラクルへのアクセスを本質的に仮定している。オペレーションズ・リサーチで一般的なNP困難な最適化問題において、学習ステップごとにグローバルオラクルを呼び出すことは計算量的に実行不可能である。その結果、実務家は、変数の部分集合を固定して残りを再最適化することで反復的に解を洗練する、大規模近傍探索（Large Neighborhood Search: LNS）のようなスケーラブルなヒューリスティックに頼らざるを得ない。LNSを微分可能な組合せレイヤーとして用いるための原理的な枠組みの欠如は、依然として重大なボトルネックとなっている。

手法：正則化LNS (RLNS)

著者らは、スケーラブルなヒューリスティックと微分可能な最適化レイヤーの間の溝を埋める、LNSの確率版である**正則化大規模近傍探索（Regularized Large Neighborhood Search: RLNS）**を導入する。核心となるアイデアは、LNSフレームワーク内の局所的なサブ問題を正則化または摂動させることで、ヒューリスティックを組合せ集合上の効率的なマルコフ連鎖モンテカルロ（MCMC）サンプラーへと変容させることである。

1. フレームワークと局所的正則化

RLNSは、グローバルな正則化関数 $\Omega$ から導出される局所的正則化関数の族を定義する。解の部分集合 $\mathcal{Z} \subseteq \mathcal{Y}$ に対して、局所的正則化関数 $\Omega_{\mathcal{Z}}$ は包含写像を介して定義される。グローバルな正則化問題を解く代わりに、RLNSは、座標の集合 $S^{(k)}$ を固定することによって定義される局所的な近傍 $\mathcal{Y}(k)$ に対し、局所的に正則化された分布 $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$ から反復的にサンプリングを行う。

2. エントロピー正則化とブロックギブスサンプリング

グローバルな正則化がシャノンの負のエントロピー（ $\Omega = -\gamma H_s$ ）である場合、著者らはRLNSが厳密なブロックギブスサンプリングを実行することを証明している。具体的には、局所的に正則化された分布は、固定された変数における条件付きのグローバル正則化ギブス分布と一致する：
$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)](y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$
既約な変数選択スキームの下で、RLNSの反復の定常分布は、グローバルに正則化されたギブス分布に正確に収束する。この結果はエントロピー正則化に特有のものである。命題2は、シャノンのエントロピーが、この厳密性を保証する唯一の可分な正則化関数であることを特徴付けている。

3. 摂動ベースの正則化

局所的な周辺オラクル（エントロピーサンプリングに必要）は困難であるが、局所的なMAPオラクルが利用可能なシナリオにおいて、著者らは摂動ベースの正則化を使用することを提案している。局所的なスコアにノイズ $\epsilon Z$ を加え、摂動付きの局所最大化問題を解くことで、RLNSは局所的に正則化された分布からサンプリングできる。このアプローチは、メトロポリス・ヘイスティングスに基づく局所探索とは異なり、サンプル拒絶メカニズムを必要とせずに、標準的なLNSオラクル（例：ナップサック問題に対する動的計画法）を活用できる。

4. 学習と補間

本論文は、RLNSの反復回数（ $K$ ）と学習目的関数の間の関係を確立している：

$K=1$ (局所Fenchel-Young損失): RLNSの単一ステップは、局所Fenchel-Young損失の不偏推定量を提供する。エントロピーの設定において、これは擬似尤度（複合尤度）目的関数を回収し、他の変数で条件付けられた変数部分集合の尤度を最大化する。
$K \to \infty$ (グローバルFenchel-Young損失): 反復回数が増えるにつれ、推定器はグローバルFenchel-Young損失の勾配に収束し、厳密な最大尤度推定を近似する。
これにより、実務家は $K$ を調整することで、擬似尤度と厳密な最大尤度推定の間を補間することができ、グローバルソルバーなしでのエンドツーエンドの学習を可能にする。

主な貢献

RLNSフレームワーク: 局所的正則化をLNSサブ問題に統合し、微分可能な組合せレイヤーを作成する、正則化された確率的LNSの導入。
理論的等価性: エントロピー正則化の下で、RLNSが、その定常分布がグローバルに正則化されたギブス分布と一致する厳密なブロックギブスサンプラーを実装することを証明。
摂動による実行可能性: 摂動ベースの正則化により、RLNSが標準的な局所MAPオラクルを利用できることを示し、標準的なLNSが実行可能であれば常に実行可能であることを保証。
学習パラダイムの補間: RLNSの反復回数によって、擬似尤度と厳密な最大尤度推定の間を補間できるという理論的および経験的な実証。
経験的検証: 以下の3つの異なる問題による評価：
- $\kappa$ -hot ベクトル: 真の分布に対する収束性を検証する制御された推定タスク。
- 割当問題 (Generalized Assignment Problem: GAP): 局所サブ問題が0/1ナップサック問題となる割当の予測学習。
- 確率的車両スケジューリング: 実世界のベンチマークであり、RLNS-1がブラックボックス微分およびバイナリクロスエントロピーのベースラインを上回り、かつグローバルソルバーよりも大幅に少ない計算量を必要とする。

結果

収束性: $\kappa$ -hot ベクトルの実験において、RLNSはローカルサーチMCMCよりも速く収束し、特に多くの変数が自由な状態のとき、同じサンプル数に対してモンテカルロ推定よりも低い平均絶対誤差（MAE）を達成した。
スケーラビリティ: GAPの実験において、RLNSが使用する局所MAPオラクルは、特に問題の規模が大きくなるにつれて、グローバルな混合整数線形計画法（MILP）ソルバーよりも数桁高速であった。
パフォーマンス: 確率的車両スケジューリングにおいて、RLNS-1（単一反復を使用）は、遅延コストの面でグローバルな摂動付きFenchel-Young（PFY）学習の性能にほぼ匹敵しつつ、ソルバーが処理するサブ問題を元のサイズの約3分の1に抑えている。また、ブラックボックス微分（DBB）およびバイナリクロスエントロピー（BCE）のベースラインを大幅に上回った。
バイアス分析: 理論的な境界は、近似誤差が固定された変数と自由な変数の間の共有制約（カット制約）の数に比例することを示しており、これらの方策（例：最小カット選択）による変数選択スキームの重要性を裏付けている。

意義と主張

本論文は、高度にスケーラブルなヒューリスティック（LNS）をニューラルネットワークの微分可能なレイヤーとして使用することを可能にし、計算量的に実行不可能なグローバルソルバーへの依存を取り除くことで、既存の文献における重要なギャップを埋めるものであると主張している。LNSとギブスサンプリングの間の厳密な関係を確立することにより、本研究は、局所オラクルのみを使用して微分可能な組合せ最適化レイヤーを微分するための原理的な枠組みを提供している。著者らは、RLNSを、反復回数 $K$ によって計算コストと統計的精度のトレードオフを調整できる、NP困難な制約を含む構造化予測タスクのための実用的なソリューションとして位置づけている。