Nature: DeepMind の大規模モデルが 60 年前の数学的問題を突破、その解決法は人間の認識力を超える

Google DeepMind の最新の成果が再び Nature に掲載され、大規模なモデルを使用して 60 年以上にわたって数学者を悩ませてきた問題を解決しました。

著者の一人であり、Google DeepMindの研究担当副社長であるプッシュミート・コーリ氏は、次のように述べています。

この解決策はトレーニング データには存在せず、これまで人間にも知られていませんでした。

このテクノロジーは FunSearch と呼ばれ、Fun は function という単語の略語です。

大規模モデルを使用して長年の科学的問題を解決すると、以前には存在しなかった新しい検証可能な貴重な*情報が生成されます。

Nature の論文に付随するニュースで、DeepMind の責任者は「私たちは大規模なモデルを創造性のエンジンとして利用しています」と語った。

大規模なモデルに基づくシステムが数学者やコンピューター科学者の理解を超える可能性があることを実証したのはこれが初めてでした。

これは斬新なだけでなく、現在存在するものよりも効果的です。

この功績について、一部のネットユーザーは嘆いた。

もしこれが真実なら、それは火の発見以来人類が成し遂げた最も重要な発見となる。

それで、FunSearch はどのような問題を解決するのでしょうか?

NP困難な問題に対するより良い解決策を見つける

DeepMind は具体的に 2 種類の問題を実証しましたが、どちらもNP 困難な問題です。

学術界では、あらゆるケースにおいて NP 困難問題の正確な解を多項式時間で見つけることができるアルゴリズムは存在せず、おそらく今後も存在しないでしょう。

このような問題に直面した研究者は通常、近似的な解決策や特定の状況に適用できる効率的なアルゴリズムを探します。

FunSearch の場合、最初に解決する NP 困難問題は、上限集合問題の一種であるCap set problemです。これは次のように説明されます。

n 次元空間では、各次元に n 個の等間隔の点があります (合計 n^n 個の点。たとえば、3 次元は3*3*3です)。集合を形成するためにできるだけ多くの点を見つけ、集合内のどの 3 点も同一直線上にないことを条件とします。このような集合には最大でいくつの点がありますか。

理解するのが少し難しいと思われる場合は、キャップ集合問題の前身である、遺伝学者マーシャ・ファルコが 1970 年代に発明したカード ゲームについて学習するとよいかもしれません。

このカードゲームには合計 81 枚のカードがあり、各カードには 1 ～ 3 色のパターンがあり、同じカード上のパターンは色、形、色合いがまったく同じです。

このカード セットには、3 つの色、3 つの形、3 つの色合いがあります。さまざまなパターンの数を合わせると、合計 3* 3*3 *3=81 枚のカードがあります。プレーヤーはいくつかのカードをめくり、3 枚のカードの特別な組み合わせを見つける必要があります。

この「特別な組み合わせ」の具体的な方法を離散幾何学的形式で表現すると、キャップ集合問題が得られます。

キャップ集合問題も1970年代に生まれ、オックスフォード大学の数学者ロン・グラハムによって提案されましたが、最初の重要な結果は1990年代まで現れませんでした。

2007 年、テレンス・タオはブログの投稿で、これが彼のお気に入りの自由形式の数学の問題であると述べました。

FunSearch が登場する前、キャップ集合問題における最も重要なブレークスルーは、2016 年にアメリカの数学者 Jordan Ellenberg 氏とオランダの数学者 Dion Gijswijt 氏によって提案されました。

Ellenberg と Gijswijt は多項式法を使用して、n>6 の場合にこのタイプの問題の解の上限を 2.756^n に絞り込みました (最大値は n≤6 のときに正確に見つかります)。

また、n>6 の場合、下限の新しい数値は 2.218^n であり、これは 2022 年にブリストル大学の博士課程の学生である Fred Tyrrell によって提案されました。

しかし、この最小値は理論上のみ存在します。n=8 の場合、人間が構築できる最大の集合には 496 個の点しかありませんが、ティレルの結論によれば、点の数は 585.7 個以上である必要があります。

FunSearch はコレクション サイズを 512 ポイントに拡大しました。理論値とはまだ差がありますが、この問題における 20 年間で最も重要なブレークスルーと見なされています。

同時に、キャップセットサイズの最小値も FunSearch によって 2.2202^n に改善されました。

2番目のカテゴリはオンラインパッキング問題です。

容量が C の標準コンテナのセットがあり、n 個のアイテムのシーケンス (アイテムのサイズは C を超えない) が特定の順序で到着するとします。

「オンライン」とは、オペレーターがすべての品目を事前に確認することはできず、品物が到着したらどのコンテナに積み込むかをすぐに決定する必要があることを意味します。

最終的な目標は、使用するコンテナをできるだけ少なくすることです。

オンラインパッキング問題は 1970 年代から広く研究されており、1831 年にガウスが研究したレイアウト問題にまで遡ることができます。

200年近く研究が続けられていますが、いまだに成熟した理論や効果的な数値計算方法は存在しません。

従来、一般的に使用されている貪欲アルゴリズムには、First Fit と Best Fit が含まれます。

• ファースト フィットとは、各アイテムを、それが収まる最初のボックスに入れることを意味します。
• ベストフィットとは、各アイテムを、そのアイテムが収まる大きさで、ボックス内の残りスペースが最も少ないボックスに入れることです。

FunSearch は、OR と Weibull テスト データ セットの両方で使用されるコンテナーの数を大幅に削減する新しいアルゴリズムを提案しました。

特に、テスト セット内のアイテム数が 100,000 に達すると、FunSearch によって見つかったソリューションは、理論上の下限よりもわずか 0.03% 多くのコンテナーを消費します。

（下の表のデータは理論上の下限との差を表しており、数値が小さいほどパフォーマンスが優れていることを意味します）

それで、FunSearch はどのように機能するのでしょうか?

「回答」ではなく「手順」を検索してください

全体的に、FunSearch のワークフローは反復的なプロセスであり、その中心は問題自体の答えではなく、問題を解決できるプログラムを検索することです。

探索は、DeepMind が AlphaGo 以来探求してきた道です。

共同創設者のシェーン・レッグはかつてインタビューでこう語った。

AlphaGoがイ・セドルに勝利することを可能にした鍵となる「37手目」はどこから来たのか？それは人間のゲームデータからではなく、確率空間の探索から得られます。

現在の大規模モデルは、さまざまなトレーニング データを単純に模倣して混合するだけです。真の創造性を生み出し、現在のアーキテクチャを超えるには、検索と組み合わせる必要があります。

最新の成果である FunSearch に戻ると、システムにはプログラム ライブラリがあります。各反復で、システムはそこから初期プログラムを検索し、大規模なモデルを入力します (実験では PaLM2 が使用され、他のサポート コードも互換性があります)。

ビッグモデルはこれを基に新しいプログラムを構築し、自動評価システムに提出します。最高スコアを獲得したプログラムはプログラムライブラリに追加され、自己循環サイクルが実現します。

評価システムは、ユーザーの質問に基づいてテストケースを生成し、候補プログラムの出力が正しいかどうかを判断します。

正確性を判断する方法としては、複雑さに応じて、出力値を直接確認したり、関連する関数を呼び出したりする方法があります。

同時に、評価システムにはフォールト トレラント ロジックも装備されており、タイムアウトやその他の問題がプロセス全体に影響するのを防ぎます。

最終的に、システムはこれらのテスト ケースでの候補プログラムの動作に基づいて全体的なスコアを付与し、結果の生成とその後のプログラム ライブラリの更新の基礎を提供します。

論文の共著者であるウィスコンシン大学マディソン校のジョーダン・エレンバーグ氏は、FunSearchの重要な特徴は、人々がAIによって生成された成功した解決策を見てそこから学ぶことができる点であり、これは従来のAIのブラックボックスモデルとはまったく異なるものだと考えている。

私にとって最もエキサイティングなのは、人間と機械のコラボレーションの新しいモデルを構築することです。私は、それを人間の数学者の代わりとしてではなく、むしろ力の倍増器として使うことを期待しています。

論文アドレス: https://www.nature.com/articles/s41586-023-06924-6