騒動を巻き起こしたディープマインドの論文は万能ではない

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載しています。転載の際は出典元にご連絡ください。

この記事では、ニューラル ネットワークを使用して MIP (混合整数計画法) を解決する DeepMind の最近の論文について、予備的な解釈を示します。実際、この分野における最近の同様の研究と比較すると、分岐限定法やニューラルネットワークをヒューリスティックアルゴリズムに利用する試みなど、MIPソリューションの特定の側面の開発におけるDeepMindの研究は、より洗練され、高度にエンジニアリングされており、オープンソースのソルバーとの結合も著しく進んでいます。また、比較的良い進歩を遂げていますが、画期的で破壊的なアイデアはあまり見られません。

Google の DeepMind チームは最近、ニューラル ネットワークを使用して MIP を解決する方法に関する論文を発表しました。

この事件は大きな騒動を引き起こし、国内外のオペレーションズ・リサーチおよび最適化コミュニティで議論を巻き起こしました。

[[417732]]

傍観者の中にはこう言う人もいた。

これは超クールだ。

ML と組み合わせ最適化の融合がようやく実現しつつあることに興奮しています。

OR（オペレーションズ・リサーチ）が征服されるのは時間の問題です。

すでに一部の専門家はコードを要求しています。

コードはオープンソースですか? 標準的な難しい問題でテストしてみたいです。

ここでいくつかのコードを確認する必要があります。

これをテストするのは非常に興味深いでしょう。

実際、機械学習と整数計画法を組み合わせることは新しいトピックではありません。

Google のこの論文がなぜこれほど注目を集めたのでしょうか?

もちろん、Google と DeepMind チームの名声が最大の要因です。囲碁の AlphaGo から最近のタンパク質構造予測の AlphaFold2 まで、DeepMind が行ったすべての動きは注目の的となる大きな動きであり、実際にいくつかの分野で画期的な進歩をもたらしました。

しかし、この論文には「OR（オペレーションズ・リサーチ）を打ち破る」ような破壊的な研究結果が含まれているのでしょうか？

DeepMind はこのコードをオープンソース化する要請に応じなかったため、同社の成果を知る唯一の方法は論文を読むことです。

Sunshu Technology の COPT ソルバー開発チームは、この論文を詳細に研究しました。

ここでは、機械学習と最適化アルゴリズムの組み合わせをさらに探求するためのチームの分析と議論を紹介します。

MIP (混合整数計画法) は、一般的に混合整数線形計画法を指し、線形制約 Ax≤b と整数制約 x∈Z を満たすという前提の下で目的関数 f(x) = c·x の最小値を求めます。

配列 x は決定変数と呼ばれ、配列 c はこれらの決定変数のターゲット係数、行列 A は線形制約行列、Z は整数の集合です。

整数計画法は現実世界で幅広い用途に使用されています。たとえば、航空宇宙、エネルギーグリッド、製造、輸送物流、軍事、通信などの分野で、かけがえのない基本的なモデリングと解決機能を果たしています。

しかし、整数計画法も非常に難しい問題です。コンピュータの複雑性理論では、NP困難問題のカテゴリに属します。また、米国のカランが発表した数学の7つのミレニアム懸賞問題のうちの1つでもあります。この種の問題では、多項式時間で正確に解くアルゴリズムが存在するかどうかはまだ判明していません。

整数計画法を解くための主なアルゴリズム コンポーネントは、事前解決、分岐と限定、ヒューリスティック アルゴリズム、切断面、競合分析、線形計画法ソルバー モジュールです。

DeepMind の論文は主に分岐アルゴリズムとヒューリスティック アルゴリズムを扱っているため、ここではそれぞれこの 2 つの方向に焦点を当てます。

以下の記事では、まずDeepMindの基本的な結論を分析し、次にDeepMindの論文で言及されているNeural BranchingとNeural Divingという2つの成果について、混合整数計画法に関連する背景知識を紹介し、最後に論文の新しいアイデアと従来のアルゴリズムとの関係を比較分析します。

DeepMindの論文解答結果の分析

DeepMind の論文は、チームの評判だけでなく、論文で報告された非常に印象的なパフォーマンス改善データによっても、広く注目を集めました。

論文の概要に記載されているように、テストされた 5 セットの問題のうち 3 つは、それぞれ 1.5 倍、2 倍、10,000 倍のギャップを達成しました。

実際、ここではちょっとした言葉遊びが行なわれています。

MIP ソルバー開発者として、私たちは通常、一定期間内に達成できるギャップを主な基準として使用しません。

これは多少誤解を招くからです。実現可能性問題など、目的関数を持たず、整数解の集合を見つけるだけで解決できる特殊なクラスの整数計画問題を考えてみましょう。

すると、整数解を見つける前はギャップは 100% ですが、見つけた後は 0% になります。ヒューリスティック (または切断面) アルゴリズムをオンとオフにすると、それぞれ 1 時間と 3 時間で実行可能なソリューションを見つけることができます。

2 時間を観測ポイントとして使用する場合、このアルゴリズムをオンにすることを前提とすると、達成されるギャップの改善は無限大であると言えますが、30 分または 3 時間を観測ポイントとして使用すると、ギャップは改善されません。

DeepMind はこれらのパフォーマンス指標を計算するために使用された生データを公開していないため、業界で認められている MIP の方法を使用して評価することはできません。

一般的に言えば、現在認められているテスト基準によれば、2 時間という制限内で、解決できる問題の数と平均解決時間が MIPLIB 問題セットで比較されます。

特定のテスト セットでパフォーマンスが驚くほど向上したことは驚くべきことではありません。これは、機械学習が優れている点だからです。機械学習は、同じ種類の問題の特徴的な構造を捉え、最適化の傾向を判断できます。

後述しますが、私たち自身も開発過程で同様の経験をしました。本当に注目に値するのは、MIPLIB でのパフォーマンスです。

MIPLIB 2017は、さまざまな業界からの1,000を超える例で構成されており、MIPLIB2017ベンチマークは、構造の異なる240の選択された問題で構成されています。スクリーニングプロセス中に完全に差別化されているため、電力網最適化やNN検証などのテストセットとは根本的に異なります。

これは、MIPLIB でのアルゴリズムのパフォーマンス向上が他のデータセットほど明白でない理由も説明しています。

疑いを避けるために、Google は論文の中で早い段階で、トレーニング セットには MIPLIB の完全版の 1,000 を超える質問が使用され、残りの 240 の質問の例が削除されたことも述べていました。ただし、トレーニング セットとテスト セット間の構造的な類似性を回避することは依然として困難です。

たとえば、MIPLIB 2017 のフルバージョンを収集する場合、同じソースからわずかに異なるサイズの複数の例が収集されることがよくあります。ベンチマーク セットを選択する際、ベンチマーク セットの重複を避けるために、同じソースからの例の使用を避けるようにしています。これにより、MIPLIB 2017 のフル バージョンの残りの例には、ベンチマーク セット内の構造的に非常に類似した問題が含まれることになります。

たとえば、MIPLIB 2017 ベンチマークには graph20-20-1rand 問題があり、MIPLIB 2017 コレクションには graph-20-80-1rand、graph-40-20-1rand、graph-40-40-1rand、graph-40-80-1rand という 4 つの非常に類似した問題があります。

したがって、トレーニング セットで得られた経験は、最終的なテスト セットを解く際に確実に役立ちます。しかし、これらの支援があらゆる一般的な問題セットに一般化できるかどうかは非常に疑わしい。

分岐アルゴリズムとニューラル分岐

分岐アルゴリズムは整数計画法ソルバーのコアフレームワークです。

MIP を解くには、通常、複数の LP (線形計画法) 問題を解決する必要があります。最初の LP 問題は、すべての整数制約が削除された元の問題です。

最初の LP 問題に対する最適解が整数条件を満たす場合、この解は整数計画法に対する最適解でもあります。 LP 緩和問題の解がすべて整数条件を満たさない場合は、分岐アルゴリズムを使用して整数解の検索を継続できます。

分岐アルゴリズムは、値が整数ではない変数 x=x を選択して分岐し、2 つの制約 x≤floor(x) (つまり、値が x より大きくない最大の整数の下限) と x≥ceil(x) (つまり、値が x より小さくない最小の整数の上限)* を追加して、元の問題を 2 つのサブ問題に分解します。

元の整数計画問題に対する最適解は、これら 2 つの分岐のいずれかにある必要があります。

次に、最適な整数解が見つかるまで、または整数解が存在しないことが証明されるまで、これら 2 つの新しい問題を解き続けます。

分岐アルゴリズムの本質が列挙であることは容易に理解できます。n 個の 0-1 変数を持つ混合整数計画問題では、最悪のケースは 2 の n 乗の分岐ノードをすべて走査することです。

また、混合整数計画問題は NP 困難問題であるため、現在の正確な解を求めるアルゴリズムは基本的に分岐アルゴリズムのフレームワークに基づいています。最悪の場合、複雑さは指数時間レベルになり、時間消費が非常に長くなる可能性があります。

実際には、整数計画を解くのに必要なのは、通常、すべてのノードを列挙するよりもはるかに少ない量です。

これは、分岐アルゴリズムが分岐する変数をよりスマートに選択できるためです。多くの分岐アルゴリズムの中で最も効果的なのは、完全強力分岐アルゴリズム (Full Strong Branching、略して FSB) です。

このアルゴリズムの原理は非常に単純で、値が整数ではない現在の LP (線形計画) 問題の各変数を分岐し、分岐後のすべての LP 問題を解き、LP の目的関数値を通じてどの分岐が MIP ソリューションを最も速く完了できるかを判断します。

実際には、FSB に必要な計算量は非常に大きいため、すべての LP ノードに使用するのは現実的ではありません。 MIP ソリューション プロセス中、各変数分岐の最適な推定値を取得するために、限られた数のサイクルによる強力な分岐が随時実行されます。

Google が提案するニューラル分岐の本質は、まずニューラル ネットワークを通じてオフラインで FSB の実際の計算結果を学習し、次に実際のアプリケーションで FSB 計算をシミュレートして、計算時間を節約しながら FSB 効果を追求することです。

実際、このテーマについては過去数年間に同様の論文が数多く発表されています。

Google の論文では、関連研究における他の 8 つの関連研究論文も言及されており、そのほとんどは基本的な考え方が似ています。したがって、Google の論文に書かれているように、現時点での論文の革新性には一定の限界があります。

これは、GPU と ADMM を使用して元の問題の FSB 近似を大量に計算し、大量の機械学習データを生成することで実現されます。

しかし、これは別の観点から見ると、FSB に必要な計算量も反映しています。オフライン学習用のデータを生成する場合でも、計算を高速化する方法を見つける必要があります。

従来の分岐アルゴリズムと比較すると、ニューラル分岐やこの分野の他の研究は、（オフライン）機械学習と最適化アルゴリズムの興味深い組み合わせです。

しかし、古典的な分岐アルゴリズムも履歴データに基づく将来の分岐の予測に基づいており、その本質はオンライン機械学習のメカニズムでもあることを指摘する価値があります。

例えば、SugShu ソルバーでは、強い分岐を使用するのは項目の 1 つにすぎません。さらに、疑似コスト、信頼性、推論など、公開されている判断基準と非公開の判断基準があります。

これらのアルゴリズムはすべて、解決プロセス中に情報を蓄積し、それを使用して新しい分岐変数を判断および選択します。

ヒューリスティックアルゴリズムとニューラルダイビング

ヒューリスティック アルゴリズムは、メインの分岐限定アルゴリズムの外側で整数解を見つけるアルゴリズムの総称です。

ヒューリスティックアルゴリズムはMIP研究のホットな話題であり、関連する論文は無数にあります。現在、SCIPだけで57ものヒューリスティックアルゴリズムが実装されています。

これらのヒューリスティック アルゴリズムは、大まかに 4 つのカテゴリ (丸め、分割、サブ MIP、および上記 3 つのカテゴリ以外のアルゴリズム) に分類できます。

名前が示すように、丸めヒューリスティック アルゴリズムは、LP 緩和ソリューションが整数制約を満たさない場合、整数ソリューションを取得するために満たされていない変数を丸めます。

ダイビング ヒューリスティック アルゴリズムの本質は深さ優先探索です。LP 緩和ソリューションが整数制約を満たさない場合、現在のノードから開始し、整数ソリューションが見つかるか、サブ問題が実行不可能であることが証明されるまで、深さ優先探索に最適なブランチを継続的に選択します。

これら 2 種類のアルゴリズムの原理は単純ですが、実装のバリエーションも多数あり、ここでは説明しません。

サブ混合整数計画問題 (Sub-MIP) のヒューリスティック アルゴリズムは、サブ MIP 問題を構築して解決し、高品質の整数ソリューションを見つける大規模なアルゴリズムのクラスです。

サブ問題を構築する場合、変数を固定または強化したり、制約を追加したり、目的関数の値を変更したりするなど、さまざまな構築方法があります。

その中で、固定変数型アルゴリズムはより有名であり、例えば緩和誘導近傍探索 (RINS) は、LP 緩和解の整数変数の値が現在の最良整数解の値と一致する場合、変数はこの整数値に固定されるという原理に基づいて動作します。

多数の変数を固定できる場合、固定変数の後のサブ問題は、高品質の整数解を見つけることを目的とした完全に新しい MIP として解決できます。

多数の変数が固定されるため、サブ問題の検索空間が小さくなり、事前解決によって問題のサイズをさらに縮小できるため、サブ問題の解決が比較的容易になります。

DeepMind が提案する Neural Diving アルゴリズムは、機械学習とニューラル ネットワークを使用して、問題構造が与えられた場合にいくつかの整数変数の値をどのように固定するかを予測し、サブ MIP を解きます。

したがって、「ダイビング」という単語が使用されていますが、サブ問題を解決するためのヒューリスティック アルゴリズムとして分類できると考えています。このアルゴリズムは、変数が異なる方法で固定されている点を除けば、原理的には前述の RINS と多くの類似点があることがわかります。

アイデアは多くの既存のヒューリスティック アルゴリズムに似ていますが、Neural Diving には独自の機能があります。 Neural Diving の最大の利点の 1 つは、元の問題を正式に解決する前に、差別化された部分変数値の複数のセットを生成し、ヒューリスティック アルゴリズムを開始できることです。

これにより、一方では、高品質の整数解を見つけるアルゴリズムの成功率が向上し、他方では、整数解を見つける時間も短縮されるため、より小さなギャップをより早く得ることができます。私たちは、これが DeepMind の論文の中で最も価値のある部分であると考えています。

人工知能とMIPを組み合わせた実用化

Shanshu ソルバーは開発中に機械学習ツールをフル活用しました。本質的にオンライン学習である上記の分岐アルゴリズムに加えて、私たちは他のさまざまな方向でも機械学習ツールを使用しています。

たとえば、サブ MIP を解決するためのヒューリスティック アルゴリズムは効果的ですが、非常に時間のかかるアルゴリズムです。

開発プロセスでは、多数のサブ問題を解決し、サブ問題の特徴（再事前解決の効果、変数の種類など）を抽出し、機械学習を使用して、サブ問題の解決に時間を費やす価値があるかどうかを判断し、時間のかかる非効率的な方法を回避して、解決速度を向上させます。

さらに、当社の線形計画 LP ソルバー開発も機械学習の恩恵を受けています。

たとえば、機械学習を使用して、特殊な構造を持ついくつかの LP に対して、変数が最適解の基本解の一部であるかどうかを予測し、この予測結果を目的関数の小さな摂動を通じて LP 問題に適用して、高速なソリューションを実現します。

ソルバーに組み込まれた上記の機械学習の成果に加えて、過去数年間、Shanshu はソルバーを使用して複数の業界の困難な問題を解決する際に、機械学習、ディープラーニング、強化学習からも大きな恩恵を受けています。

一例として、State Grid の Security Constrained Unit Commitment (SCUC) 問題が挙げられます。

SCUC 問題は規模が小さいという特徴がありますが、迅速な解決が必要です。私たちが実際に遭遇した問題には数千個の整数変数しかなく、それを 15 分ごとに解く必要があり、15 分以内にできるだけ早く解く必要がありました。

ディープニューラルネットワークなどの機械学習手法を使用して、MIPモデルの最適解において各決定変数が1を取る確率を予測し、最も信頼度の高い変数を固定し、中程度の信頼度を持つ変数に多変量分岐切断面を追加することで、最終的な問題が実行可能である確率が最も高くなります。

この方法は、分枝限定木の検索スケールを効果的に縮小し、一方では迅速な収束を達成し、他方では高品質の初期ソリューションを迅速に見つけることができます。

最終実験では、この方法により、同じ品質のソリューション (Gap=0.01%) に到達する速度が約 5 ～ 10 倍向上することが示されました。

本来の問題は 3 分では解決できないが、機械学習アルゴリズムを使用することでわずか 10 秒で解決できる場合があります。この速度の向上は、15 分ごとに迅速な決定の計算を必要とする SCUC 問題にとって非常に重要です。

電力網の最適化も、DeepMind がインテリジェント MIP が注力できる領域であると指摘している分野です。

ただし、電力網のもう 1 つの特徴として、安全性と堅牢性に対する厳しい要件があることを強調しておく価値があります。

しかし、戦争や自然または人的要因によって発電所や送電線に大きな変化が生じるなど、新たな問題のデータ構造が突然変化し、過去のデータが将来を予測できなくなると、機械学習の役割は大幅に弱まるでしょう。

現時点では、データから独立しており、古典的なアルゴリズムである MIP ソルバー自体の 6 つのモジュールの実装機能に依存することがよくあります。

もう 1 つの例は、中国郵政のルーティング ネットワーク計画問題です。

実際に遭遇するこのような問題では、通常、出発スケジュールを決定するために数十万の整数変数を持つ MIP を解く必要があります。これをソルバーに直接投入すると、最初の整数解が見つかるまでに 1 ～ 2 時間かかることがよくあります (ギャップは約 30% か、さらに悪化します)。

観察を通じて、出発の手配をすべて予測することは不可能だが、いくつかの確率の高い車両の手配を予測できることがわかった。次に、機械学習の履歴データを使用して、線形制約に基づいて何千もの出発スケジュールの部分的な初期ソリューションを生成する方法を開発しました。

これを基に、これらの決定変数を一時的に固定してサブ MIP 問題を構築し、ソルバーを使用してサブ問題の解を迅速に計算して完成させます。このサブ問題のいくつかの重要な変数が決定されているため、事前解決モジュールによって問題の規模が大幅に縮小され、迅速な解決が容易になります。

このサブ問題に対する最適解は元の問題に対する最適解ではありませんが、実際には、この解 (10% 以内) は、計算に 1 ～ 2 時間かかる最初の実行可能な解よりも大幅に優れています。

予測からサブ問題の解決まで、通常は 1 分もかかりません。したがって、機械学習は同等の品質（実際はより優れた品質）の整数解を 50 倍速く見つけるのに役立つと言えます。

より広い意義を持つもう一つの例は、最近の科学研究論文や、インテリジェントな意思決定に取り組んでいると主張する複数の企業の主張の中に、車両配車やルート計画などの交通関連の問題が見られることです。これらの問題はイベント頻度が高く、データ構造が比較的安定しているため、分岐戦略、固定された初期ソリューション、さらには切断面の生成など、すべて機械学習技術を通じて取得でき、MIPモデルによる問題の解決を加速できます。

そして実際、多くの学者がこの件に関して比較的大きな進歩を遂げています。

そのため、交通分野は近年、機械学習やインテリジェントな意思決定などの技術が注目されている分野でもあります。

実際のところ、それは単なるルート計画以上のものです。

5年前、山樹は国内最大級の旅行プラットフォームと提携し、運転手と乗客のインテリジェントな動的マッチングシステムを検討しました。問題は、マッチング係数を計算し、ヒューリスティックアルゴリズムの割り当てを行う単純な機械学習から始まり、都市全体の時間スライスネットワークフローマッチング、ピークシェービングとバレーフィリングとスマートトラベルの概念の統合、システム全体の動的計画モデルの構築、強化学習フレームワークを使用して将来の傾向と決定に対する近似法の実行、そして最終的に時間と空間の両方でグローバル最適化に近いソリューションを獲得しました。

データがより完全になり、コンピューティングパワーが利用可能になるにつれて、システム全体は両者が共同で確立した強化学習フレームワークの下で進化し続けます。単純な線形関数近似からニューラルネットワーク近似まで、ますますインテリジェントで正確になります。2017年までに、広く使用され、大きな経済的および社会的利益を生み出しました。

結論

最後に、「機械学習の父」マイケル・ジョーダンが指摘したように、将来の人工知能における最も重要なブレークスルーは、最適化アルゴリズムと密接に統合される必要があることを強調したいと思います。そして、これがオペレーションズ・リサーチの中核となる基盤です。

今日議論した例では、簡単に言えば、ニューラル ネットワークと機械学習テクノロジの進歩は、MIP が開発した 6 つのモジュールのうち 2 つで検討された兵器庫に、高価 (コンピューティング リソース要件) だが強力な武器を追加し、これらのモジュールの加速機能を強化するようなものですが、OR を破壊するにはほど遠いものです。これらの技術によって実証された可能性は称賛に値しますが、現実に MIP 問題を解決するには、極めて高度な数学的スキルとエンジニアリング経験が必要です。

従来の MIP 解決ツールには、数十年にわたる理論的実証と理論的分析の基盤があります。比較すると、MIP 解決における機械学習ツールは、モデル構造の複雑さのために理論的な実証結果が少なくなります。

関連する機械学習の研究の多くは、その有効性を検証するために 1 つまたは複数の種類のデータ セットの数値実験結果に依存しています。したがって、現実の一般的な問題を解決する上での機械学習手法の信頼性については、さらなる実証が必要です。

一方、ほとんどの機械学習アルゴリズムの設計では、モデルを従来の整数、線形、凸、または非凸の数理計画モデルに変換してから分析する必要があります。

MIP に戻ると、機械学習を使用して特定の時点でブレークスルーを達成するだけでは十分ではないと言えます。一般的な整数計画法や NP 困難な問題の大部分は、真に破壊的な技術的進歩 (量子コンピュータの真の実用化など) が起こるまで、今後何年もの間、人間の知能の限界の 1 つになると予想されています。

注：本稿の執筆にあたり、香港中文大学（深圳）の王子卓氏、スタンフォード大学の葉銀宇氏、ニューヨーク大学の陳曦氏、ジョンズ・ホプキンス大学の江紅毅氏をはじめ、多くの学者の方々からご指導とご示唆を頂きました。この場を借りて感謝申し上げます。

著者について

Sunshu Technology の副社長であるHuangfu Qi氏は、エディンバラ大学で最適化アルゴリズムの博士号を取得しています。

彼は長年 XPRESS ソルバーに取り組んでおり、数理計画法ソルバー開発の分野では上級専門家です。国際的に有名な最適化ジャーナル Mathematical Programming Computation の年間最優秀論文賞 (2018 年) や Computational Optimization and Applications の年間最優秀論文賞 (2015 年) を受賞しています。

Sunshu Technologyの共同創設者兼最高科学責任者であり、上海財経大学学際科学研究所の学部長兼教授であるGe Dongdong氏。

彼はスタンフォード大学でオペレーションズリサーチの博士号を取得しています。オープンソース ソルバー プロジェクト LEAVES と商用ソルバー プロジェクト COPT のリーダー。彼は、NeurIPS、ICML、FOCS、SODA、オペレーションズ・リサーチ、数理計画法など、人工知能、理論計算機科学、オペレーションズ・リサーチに関するジャーナルや会議で多数の論文を発表しています。

論文の宛先:

出典：http://arxiv.org/abs/2012.13349