ファンサーチ

FunSearch （関数空間検索の略）は、数学的およびアルゴリズム的問題を解決するコンピュータプログラムを発見するためにGoogle DeepMindによって開発された人工知能手法です。大規模な言語モデルと自動評価器、進化的探索手順を組み合わせ、候補プログラムを生成し、スコアを付け、高性能なプログラムを使用して新しい候補を生成します。^{[ 1 ]}

Google DeepMindは2023年にFunSearchを発表し、関連論文はNatureに掲載された。^{[ 2 ]}このシステムは極値組み合わせ論のキャップセット問題とオンラインビンパッキング問題に適用され、新しい数学的構成と新しいパッキングヒューリスティックを発見した。^{[ 3 ] [ 4 ]}

FunSearch は、問題を個々のソリューションを直接検索するのではなく、コンピュータ プログラムの検索として捉えます。ユーザーは、問題仕様、評価関数、および初期プログラムまたはプログラムスケルトンを提供します。各イテレーションで、FunSearch はデータベースから既存のプログラムをサンプリングし、スコアの高いプログラムを優先し、事前学習済みの大規模言語モデルへのプロンプトを作成し、モデルに修正プログラムを生成するように要求します。生成されたプログラムは、評価者によって実行され、スコアが付けられます。^{[ 1 ]}

探索プロセスでは、多様な候補プログラム群を維持し、局所最適解に陥るリスクを軽減することを目的とした、島ベースの進化的手法が用いられています。原論文によると、この手法の利点の1つは、FunSearchが最終的な数値解やオブジェクトの大きなリストだけを出力するのではなく、研究者が検査、簡略化、解釈できるプログラムを出力する点です。^{[ 1 ]}

FunSearchは、通常は固定されたプログラム骨格に埋め込まれた関数であるプログラム断片の空間に対する検索として説明できます。$\displaystyle {\mathcal {F}}}$候補関数の空間にして${\displaystyle S:{\mathcal {F}}\to \mathbb {R} }$候補関数を呼び出す固定ソルバーを実行することによって得られる評価スコアとする。初期関数が与えられた場合${\displaystyle f_{0}}$FunSearchはデータベースを維持しています${\displaystyle D}$評価済みで有効な関数から、高得点の関数を繰り返しサンプリングします。${\displaystyle D}$それらを使用して大規模な言語モデルのプロンプトを構築し、モデルに新しい候補関数を生成するように要求します。${\displaystyle f'}$新しい関数は問題固有のプログラムスケルトン内で実行され、評価者によって採点されます。生成された関数が有効な場合、それは再び追加されます。${\displaystyle D}$これにより、後のプロンプトがより強力な以前の候補に基づいて構築されるようになる。^{[ 1 ]}

簡略化すると、検索ループは次のように記述できます。

$${\displaystyle D\leftarrow \{(f_{0},S(f_{0}))\}}$$

$${\displaystyle f'\sim \operatorname {LLM} (\operatorname {prompt} (f_{1},\ldots ,f_{k})),\quad (f_{i},S(f_{i}))\in D}$$

$${\displaystyle {\text{f'{\text{が有効な場合}、D\leftarrow D\cup \{(f',S(f'))\}。}$$

理想的な目標は、評価スコアの高い候補関数を見つけることです。

$${\displaystyle f^{*}\in \operatorname {*} {arg\,max}_{f\in {\mathcal {F}}}S(f),}$$

ただし、実際には FunSearch は検索中に発見された最良の有効な関数を返します。元の実装では、候補関数の多様性を維持しながらスコアの高いプログラムを優先するために、アイランドベースの進化プロセスを使用しています。^{[ 1 ] [ 4 ]}

Google DeepMind はFunSearch 論文に付随する公開GitHubリポジトリで FunSearch ソフトウェアを公開しました。リポジトリには、キャップ セット、許容セット、オンラインビン パッキング、サイクル グラフの強い積における独立セット、コーナーフリー セット、および関連する実験の例とデータが含まれています。また、 FunSearchパイプラインのシングル スレッド実装も含まれていますが、リポジトリには、元の実験で使用された言語モデル、実行サンドボックス、または分散インフラストラクチャは含まれていないと記載されています。リポジトリには、ソフトウェアはApache License 2.0でライセンスされており、その他の資料はCreative Commons Attribution 4.0 International Licenseでライセンスされていると記載されています。^{[ 6 ]}

Nature News & Views の記事で、ジャン＝バティスト・ムーレは FunSearch を遺伝的プログラミングと大規模言語モデルを結びつけるものとして説明し、この研究は言語モデルがコンピュータ プログラムの進化にどのように役立つかを示していると述べている。この記事では、このシステムを AI 支援による数学的発見の概念実証として特徴づけている。^{[ 3 ]}

• アルファデヴ
• アルファエボルブ
• アルファジオメトリ
• アルファテンソル
• 自動定理証明
• 進化アルゴリズム
• 人工知能アルゴリズム一覧
• 数学における未解決問題一覧
• プログラム合成

• 公式サイト
• funsearch （GitHub）