FunSearch：LLMを活用した数学・科学分野の新たな発見

 (deepmind.google)
1 ポイント 投稿者 GN⁺ 2023-12-15 | 1件のコメント | WhatsAppで共有
  • Google DeepMindのFunSearchは、事前学習済みLLMと自動評価器を組み合わせ、数学・コンピューターサイエンスの問題で検証可能な新しい解法をコードの形で探索する
  • LLMが新しいプログラムを作り、自動評価器がスコアを付けた後、高スコアのプログラムを再びプールに入れる進化的反復によって解法を改善する
  • cap set problemでは、一部の設定でこれまでに見つかった最大のcap setを発見し、既存の最先端計算ソルバーでは扱いにくい規模でも性能を示した
  • 同じアプローチはonline bin packingにも適用され、データ特性に合わせて調整されたプログラムが、既存のヒューリスティックよりも同じ数のアイテムを少ないbinに収めた
  • 出力が人間に読める短いプログラムであるため、研究者は解法の構造を検討し、問題設定を改善する人間とAIの協働に活用できる

FunSearchの基本アイデア

  • FunSearchは、数学とコンピューターサイエンスで新しい解法を見つけるため、コンピューターコードで書かれた関数を探索する
  • 名前は関数（function）を探索するという点に由来する
  • LLMは事実と異なる情報を作り出すことがあるため、FunSearchは創造的な提案を出すLLMを自動**評価器（evaluator）**と組み合わせ、誤ったアイデアをふるい落とす
  • 難しい科学・数学の未解決公開問題において、LLMで新発見を生み出した初の事例にあたる

進化的反復構造

  • ユーザーはまず問題記述をコードの形で書く
    • プログラムを評価する手順が含まれる
    • プログラムプールを初期化するシードプログラムも用意する
  • 各反復では、現在のプログラムプールの一部がLLMに入力される
    • LLMは既存のプログラムをもとに新しいプログラムを生成する
    • 新しいプログラムは自動実行と評価を受ける
    • スコアの高いプログラムは再びプログラムデータベースに追加される
  • ユーザーはいつでも、それまでに見つかった最高スコアのプログラムを取り出せる
  • FunSearchはGoogle PaLM 2を使用したが、コードで学習された他のLLMとも互換性がある
  • 難しい組合せ問題に対応するため、探索構造も強化された
    • 問題に関する一般知識から始め、新発見に必要な核心的アイデアに集中する
    • アイデアの多様性を高めて停滞を避ける
    • 進化プロセスを並列実行して効率を高める

Cap set problemでの結果

  • 最初の適用対象は、数十年にわたり複数の研究分野の数学者を悩ませてきたcap set problemである
  • この問題は、高次元格子で3点が同一直線上に並ばない点集合、すなわちcap setの最大サイズを見つける課題である
  • 極値組合せ論（extremal combinatorics）の他の問題のモデルとしても機能する
  • 可能な場合の数が急速に宇宙の原子数を上回るため、総当たり計算は機能しない
  • FunSearchはプログラム形式の解法を生成し、一部の設定でこれまでに見つかった最大のcap setを発見した
  • この結果は、過去20年間でcap setのサイズにおける最大の増加に相当し、問題規模が既存の最先端計算ソルバーの現在の能力を超える領域でも、より良い性能を示した
  • 直感を作りにくい組合せ問題で既存結果を超えられることを示し、今後、類似の組合せ論の理論問題や通信理論のような分野につながる可能性がある

人間が解釈できる短いプログラム

  • FunSearchは解答リストだけを出すブラックボックスではなく、解法がどのように構成されたかを示すプログラムを生成する
  • 新しい発見や現象を生成過程として説明する、科学における一般的な方法とも重なる
  • FunSearchは、低いKolmogorov complexityを持つ圧縮的なプログラムとして表現された解法を好む
    • Kolmogorov complexityは、解法を出力する最短のコンピュータープログラムの長さである
    • 短いプログラムは非常に大きな対象を説明できるため、針を探すような大規模問題への拡張に役立つ
    • プログラム出力は研究者にとって理解しやすい
  • 一部の高スコア出力コードでは興味深い対称性が観察され、それをもとに問題設定を洗練して、より良い解法を得た
  • Jordan Ellenbergは、FunSearchが「攻撃戦略を開発するまったく新しいメカニズム」を提供し、生成された解法は数値のリストより概念的にはるかに豊かだと述べている

Online bin packingへの適用

  • FunSearchは、実用的なコンピューターサイエンスの問題であるbin packingにも適用された
  • bin packingは、異なるサイズのアイテムをできるだけ少ない数のbinに収める問題である
  • 実際の適用例には、コンテナ積載、データセンターでコストを下げるためのコンピュート作業の割り当てなどが含まれる
  • online bin packingは通常、人間の経験に基づくヒューリスティックで扱われる
    • サイズ、タイミング、容量が異なる特定の状況ごとにルールセットを見つけるのは難しい場合がある
  • FunSearchはcap set problemとは大きく異なる問題にもかかわらず容易に設定でき、データ特性に合わせて自動調整されたプログラムを作成した
  • 生成されたプログラムは、既存のヒューリスティックよりも同じ数のアイテムを少ないbinに収めた
  • ニューラルネットワークや強化学習のような他のAIアプローチも難しい組合せ問題に効果的であり得るが、デプロイには相当なリソースが必要になる場合がある
  • FunSearchは検査しやすくデプロイしやすいコードを出力するため、さまざまな実産業システムに組み込める形の解法を作れる

2024年のアップデートと拡張

  • 2024年12月に公開されたarXivレポートは、FunSearch方式が組合せ的な競技プログラミングで人間の能力を増幅するために使えることを示した
  • Codeforcesのような従来のコーディングコンテストは、時間・メモリ制約の中で古典的アルゴリズム問題の完全な解法を求める
  • 組合せ的なコンテストは、1つの正解ではなく、可能な限り良い近似解法を探す複雑な問題を扱う
  • この方式は、上位パーセンタイルの参加者が見つけた解法よりも良い解法を作れる
  • 人間のプログラマーが解法コードのbackboneを書き、LLMがそれを操る関数を創造的に進化させる協働構造を使う
  • 一般的なLLMの改善によりコード特化モデルが不要になり、Gemini 1.5 Flashをベースとして使用できる
  • 競技プログラミング以外にも、FunSearchはBayesian optimizationフレームワークで関数をより良く最適化する方法を見つけるために使われた

LLMベースの発見の方向性

  • FunSearchは、LLMの幻覚を防ぐ仕組みを置けば、LLMを新しい数学的発見だけでなく、重要な現実問題の潜在的解法の生成にも活用できることを示している
  • 科学と産業における長年の問題や新しい問題で、LLMベースの方式により効果的でカスタマイズされたアルゴリズムを生成することが一般化する可能性がある
  • FunSearchはLLM全般の発展に伴って改善される可能性があり、さまざまな科学・工学問題へ能力を広げる方向で拡張される予定である

関連記事

1件のコメント

 
GN⁺ 2023-12-15
Hacker Newsの意見

  • ここで LLMがどれほど必要なのか が気になる
    見たところ、与えられた型シグネチャに従うもっともらしい Python 関数を生成するのが LLM の役割のように思える
    しかし LLM がなくても、与えられた型シグネチャを満たすランダムで正しい Python 関数は作れるはずにも思える。[1] のような演習だが、はるかに複雑な言語を対象にしているだけで、制限された言語のほうが書きやすいかもしれない。PushGP [2] のような方式も可能ではないかと思う
    問いは、(1) ここでの LLM の付加価値は何か、収束に必要な評価回数を大幅に減らすのか、減らすならどうやってか、(2) 同じ問題で他の遺伝的プログラミング手法は競争力が低く、適合度の低い解を出すのか、(3) より伝統的な遺伝的プログラミングが似た適合度に到達できるなら、LLM の学習コストまで含めた計算コストに差があるのか、ということ
    [1] http://www.davidmontana.net/papers/stgp.pdf
    [2] https://faculty.hampshire.edu/lspector/push.html

    • 実行可能なプログラムの状態空間は、有用なプログラムよりはるかに大きい
      猿とタイプライターだけでは足りず、ここで PaLM2 を使う理由は、候補がランダムではなくもっともらしくある必要があるからだ。意味不明なプログラムに時間を浪費したくない
      さらに、ランダムなプログラム生成ベースの遺伝アルゴリズムは コールドスタート 問題が非常に大きい。すべての候補の適合度が 0 なら、序盤で、そしておそらく最後まで進展がない可能性が高い
    • 発見された関数はここにある: https://github.com/google-deepmind/funsearch/blob/main/cap_s...
      遺伝アルゴリズムにはそこまで詳しくないが、この程度なら遺伝アルゴリズムで見つけられないとは思わない。ただ、実際にたくさん試した人がいるなら驚く
      一方で、論文付録 A.2 にあるように、LLM なしの遺伝的アプローチは LLM アプローチより 手作業の設計 が多く必要になりそうだ
    • 遺伝アルゴリズムは制約を入れても無意味なプログラムを大量に作りがちだ。十分に努力すれば文法的には大半を正しくできるだろうが、それだけだ
      ここで LLM が生み出す違いは、可能な変異空間をおおむね 意味的にもっともらしいプログラム に制限する点にある
      3番については、学習済み LLM は非常に多くの目的に有用なので、最初からの学習コストも償却すれば大きくない。FunSearch フレームワークに合わせた追加の微調整コストはあるかもしれないが、微調整コストはかなり小さい。このフレームワークでは、遺伝的プログラミングだけを使うより有利である可能性が高い
    • 帰納的プログラム合成 は探索空間が大きすぎて、数十年にわたり事実上停滞していた。ごく些細なプログラムを超えるのが難しかったからだ
      LLM は探索空間を大幅に縮小してくれる。もちろん間違った縮小をすることも多いが、その後に帰納的プログラム合成を適用して微調整し、テストできる。LLM なしでは、このようなやり方は現在の知る限り不可能だ。些細なケースであっても、まったく意味をなさないプログラムを何十億個もテストすることになるからだ
    • 確率的勾配降下法と LLM は 遺伝的プログラミング よりはるかに速く収束すると考えていた。ランダム探索よりは確かにずっと速い

  • 重要な文脈として、この発見は組合せ論のある数が、昨年知られていた 2.218~2.756 の範囲ではなく、現在は 2.2202~2.756 の間にあることを示したという点がある
    改善は論理中心の数学的証明というより、特別な性質を持つ特定の数列を見つけることで達成された。だからといって厳密でないという意味ではない
    興味深く、おそらく有用な例生成の方法であり、実質的には LLMを組み合わせた遺伝アルゴリズム に近い

  • Subbarao の「自己対局」関連のコメント: https://twitter.com/rao2z/status/1728121216479949048
    投稿によれば、FunSearch は LLM によって駆動される進化的手法を使い、高スコアのアイデアを促進・発展させる。これらのアイデアはコンピュータプログラムの形を取るため、自動実行・評価が可能だ
    ユーザーは問題の説明をコードの形で記述する。この説明には、プログラムを評価する手順と、プログラムプールを初期化するシードプログラムが含まれる
    各反復で FunSearch は現在のプールから一部のプログラムを選択し、LLM がそれを創造的に拡張して新しいプログラムを作り、新しいプログラムは自動評価される。最良のものが既存のプールに再び追加され、自己改善ループ を作る
    Web 検索では、評価者の役割として pplx.ai や phind.com を似たように使っている。質問を投げて、どんな参考資料や Web リンクを持ってくるかを見てから、質問を磨いたり後続の質問を投げたりして、より深い、あるいは別の資料を引き出す。reddit や Google を漁るより、隠れた逸材を見つけるのにうまく機能する
    Tech Twitter にも優れたコンテンツは多いので、Grok が一般公開された今、研究に使ってみることを期待している

  • https://twitter.com/gfodor/status/1735348301812383906
    「DeepMindがニューラルネットワークが本当に新しい知識を生成できることを決定的に証明したのだとすれば、火の発見以来もっとも重要な発見だ」という意見がある
    もし本当にそうなら、なぜみんながこの話をしていないのか不思議だ。PaLM 2で実現したという点も印象的で、GPT-4やGeminiよりも進んでいないモデルで成し遂げたことになる。今後数世代のモデルがこうした手法を活用すれば、何ができるようになるのか途方もない

    • ここで大変な仕事をしているのは進化アルゴリズムだ
      LLMはランダムな変異演算子を置き換えて、「この20行のPythonに妥当な修正を提案してくれ」と頼まれている程度だ。知識生成の功績をニューラルネットワークに帰するのは、少し甘い評価に感じる
      また、「作るのは難しく、評価は容易」という構造が必要なだけでなく、問題の性質にも大きく依存する。進化させたい部分が、ごく短いPython関数ひとつに分解できる必要がある
    • 思わず「うわっ!」と声が出た
      LLMが20年間進展のなかった高次元幾何学の新しい解法を発見できるなんて、学習データの盗用された断片をもっともらしくつなぎ合わせるだけのレベルをはるかに超えている
      正しくプロンプトし、正しく評価する方法さえ見つければ、LLM能力にはまだ隠れた深みがあることを示唆している
      期待を大きく裏切る結果だ。次のプロンプトやランダムシードの先に、どんな発見が潜んでいるのかわからない
    • ニューラルネットワークはずっと以前から「新しい知識」を生成できていた
      LLMも同様だ: https://www.nature.com/articles/s41587-022-01618-2
    • 論文によれば、FunSearchは現在、次の特性を持つ問題で最もうまく機能する
      a) 効率的な評価器がある、b) 改善の度合いを定量化する豊富なスコアフィードバックがある、つまり二値信号ではない、c) 進化させる孤立した部分を含む骨格を与えられる
      たとえば定理証明生成の問題はこの範囲外だ。十分に豊かなスコア信号をどう与えるかが明確でないためだ
    • この例は、新しいアルゴリズムや関数を見つける用途としては比較的限定的に感じる
      素晴らしい仕事ではあるが、火の発見や、その間にある数多くのもの、たとえば電気と比べると同列には見えない

  • 要するに、プログラムのテンプレート/骨格と適応度関数が与えられたとき、LLMでプログラム集団を生成し、別のk個のバージョンから新しいプログラムを作るプロンプトを使い、k=2が良いことを見つけた。やや生物学的だ。その後、入力に対してプログラムを実行し、適応度関数で採点し、進化には島モデルを使う
    プロンプトは原理的にはこんな感じだろう
    def foo_v1(a, b): ...
    def foo_v2(a, b): ...
    # foo_v1とfoo_v2を使って新しい関数を作ってください。{{ THIS }}のように二重中括弧の中だけ変更できます
    def foo(a, b): return a + {{}}
    新しい結果を得るのにLLM呼び出しが約1e6回しか要らなかったのなら、かなり印象的に少ない数だ。評価/採点には数分かかるとも書かれている
    ここでは深さと幅のトレードオフを考える価値がある。個々のプログラムと集団を採点するときのレイテンシとスループットに結びつく。すべてのプログラムに対してメモ化を行うのはどうだろうか。損失関数を多次元のまま保ち、入力または入力バケットごとに1次元ずつ持たせれば、まず異なる領域で強いプログラム集団を見つけて、後で結合するようにできるかもしれない
    cap setがどれほど希少かについて事前知識があったのかも気になる。以前にも計算的な試みがあって成果がなかったのか気になるが、とにかくすごい

  • Twitter / Xの投稿を言い換えるなら、これからは良くなる一方だということだ
    つまりAIの能力は単調増加しており、何十年もそうであり、このケースではその能力が再帰的に自己改善している。すでにAIオートコンプリート、AIベースのリファクタリング、コメント内でAIが自動生成したコードレビューdiffによって、自分のコーディング生産性が体感で約20〜30%向上している
    AIは90年代のIntelのような時代に入った感じがする。コードを2倍速くしたければ、Intel CPUの次の改訂を待てばよかった。今はAIモデルがその役割を担う。コーディング、顧客サポート、バグ分類のような業務フローの一部をLLMシステムにつないでおけば、システムの「改善」はモデル名を差し替える程度で済む
    初期統合の後は、最小限の労力で今後数年間「すべてが魔法のように少しずつ良くなっていく」状況を期待できる

    • 私が見る限り、ブログ記事にもリンク先の論文にもそのような話はどこにも書かれていない
      特に、LLMを使った結果と使わなかった結果の比較はしていない。私の理解では、この論文は与えられた型シグネチャにおそらく従うPythonカーネル関数をLLMで生成する遺伝的プログラミングの結果を示したものだ。この作業にLLMが必須というわけではない
      したがって、ここで特にLLMが何か特別なことをしているのかは、依然として未解決の問いだ

  • 取り組んだ問題のひとつはcap set問題だった
    https://en.m.wikipedia.org/wiki/Cap_set
    この問題は、高次元格子で3点が一直線上に並ばない最大の点集合、すなわちcap setを見つけることだ。極値組合せ論の他の問題のモデルとして機能するため重要である。極値組合せ論は、数、グラフ、その他の対象の集まりがどれほど大きく、あるいは小さくなりうるかを研究する。この問題には総当たり計算は通用しない。考慮すべき可能性の数が、すぐに宇宙の原子数を超えてしまうからだ
    FunSearchはプログラムの形の解を生成し、いくつかの設定ではこれまでに見つかった中で最大のcap setを発見した。これは過去20年間でcap setの大きさにおける最大の伸びだ。また、この問題は現在の最先端の計算ソルバーの能力をはるかに超える規模まで大きくなるため、FunSearchはそれらのソルバーを上回った

  • 記号推論をLLMとどう統合するのか、あるいはそもそも可能なのか気になる

    • 私たちがやっているのはまさにそれだ。可能なだけでなく、試行錯誤型の生成を超えるアプリケーションには必要だと考えている
    • ASUのLab V2が探っているニューラル・シンボリックのアイデアとも、ある程度は並行しているように見える
    • LEAN

  • 最近のDeepMindのFunSearch論文は、コード改善を生成するために事前学習済み大規模言語モデルを使用したことを強調していた。
    興味深いことに、主なLLMはPaLM2モデル系に基づくCodeyだったが、補足資料ではオープンソースLLMであるStarCoderにも言及している。
    しかし、FunSearchのGitHubリポジトリにはこのようなLLM実装が含まれていない。たとえばsampler.pyには次のようなコードがある。

    class LLM:  
"""Language model that predicts continuation of provided source code."""

def __init__(self, samples_per_prompt: int) -> None:  
self._samples_per_prompt = samples_per_prompt

def _draw_sample(self, prompt: str) -> str:  
"""Returns a predicted continuation of `prompt`."""  
raise NotImplementedError('Must provide a language model.')

    このコードは、外部のLLM実装が必要であることを示している。StarCoderを成功裏に使用していたのであれば、それ、あるいは類似のオープンソースLLMに関する統合ガイドや基本実装がないのは意外だ。そうした内容があれば、研究の再現性とアクセシビリティは大きく向上したはずだ。

  • これが検証可能な新しい知識であるかどうかとは別に、モデル規模やその他の規制手段によってAIへのアクセスを制限する問題を考えると、興味深いケーススタディでもある。
    そのような制限は、新しい知識や自然法則を発見しても共有せずに収益化できる企業に、不公平な優位性を与える