FunSearch（関数空間における探索の略称）は、数学的・アルゴリズム的な問題を解くコンピュータプログラムを発見するためにGoogle DeepMindが開発した人工知能手法である。これは、大規模言語モデルと自動評価器、進化的探索手順を組み合わせ、候補プログラムを生成し、スコアリングし、高性能なプログラムを用いて新たな候補を生成する。このシステムは2023年に発表され、学術誌『Nature』に論文が掲載され、極値組合せ論やオンラインビンパッキングの問題に応用されている。
FunSearchは、大規模言語モデルを発見に活用する方法における転換を表している。直接答えを生成する代わりに、問題をコンピュータプログラムの探索として捉え、モデルがコードを提案し、それを厳密にテストできるようにする。このアプローチは、Generative AIで使用されるようなモデルの生成能力を活用しつつ、出力が検証可能で、研究者が解釈できることを保証する。
方法
FunSearchは、候補プログラムを反復的に生成・評価することで動作する。ユーザーは、問題の仕様、評価関数、初期プログラムの骨格を提供する。各ステップで、システムは既存のプログラムをデータベースからサンプリングし、スコアの高いものを優先し、事前学習済みの大規模言語モデルに対するプロンプトを構築する。モデルは修正されたプログラムを生成し、それが実行され、評価器によってスコアリングされる。有効なプログラムはデータベースに追加され、探索が以前の成功に基づいて構築できるようにする。
この探索は、島ベースの進化的手法を用いて候補プログラム間の多様性を維持し、局所最適解に収束するリスクを低減する。元の論文で指摘されている主な利点は、FunSearchが最終的な数値解答やオブジェクトの大きなリストを提供するだけでなく、研究者が検査・簡略化・解釈できるプログラムを出力することである。
アルゴリズム的定式化
FunSearchは、固定された骨格に埋め込まれた関数であるプログラム断片の空間上の探索として記述できる。\(\mathcal{F}\)を候補関数の空間、\(S: \mathcal{F} \to \mathbb{R}\)を、候補関数を呼び出す固定ソルバーを実行して得られる評価スコアとする。初期関数\(f_0\)が与えられると、FunSearchは評価済みの有効な関数のデータベース\(D\)を維持する。これは、\(D\)から高スコアの関数を繰り返しサンプリングし、それらを使用して大規模言語モデルに対するプロンプトを構築し、モデルに新しい候補関数\(f'\)を生成するよう求める。新しい関数は問題固有の骨格内で実行され、スコアリングされる。有効であれば、\(D\)に追加され、後のプロンプトがより強力な候補に基づいて構築できるようにする。
理想的な目的は、高い評価スコアを持つ候補関数\(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\)を見つけることであるが、実際にはFunSearchは探索中に発見された最良の有効関数を返す。元の実装では、島ベースの進化的プロセスを使用して、高スコアのプログラムを優先しつつ多様性を維持している。
応用
キャップセット問題
FunSearchは、加法的組合せ論における問題であるキャップセット問題で最初に実証された。これは、\(\mathbb{Z}_3^n\)内の3点が一直線上にない最大の部分集合に関する問題である。次元8では、FunSearchはサイズ512のキャップセットを発見し、既知の構成を改善した。論文ではまた、許容集合に関連する構成を発見することで、キャップセット容量のより良い下界を報告している。Google DeepMindは、この結果を大規模言語モデルを用いて数学における検証可能な新しい知識を生成する例として説明した。Natureのニュース記事では、このシステムがカードゲーム「セット」に関連する組合せ論問題で人間の取り組みを改善したと報告されている。
オンラインビンパッキング
FunSearchは、アイテムが到着する際にビンに割り当てる必要があるオンラインビンパッキング問題にも適用された。この設定では、FunSearchは新しいアイテムをどのビンに受け取るかを決定するプログラム的ヒューリスティックを進化させた。元の論文では、発見されたヒューリスティックが、シミュレーションデータとOR-Libraryベンチマークインスタンスにおいて、一般的なファーストフィットおよびベストフィットのベースラインを上回ったと報告されている。
ソフトウェア
Google DeepMindは、FunSearchソフトウェアを公開GitHubリポジトリでリリースし、研究者が結果を再現し、他の問題にこの手法を適用できるようにした。リリースには、進化的探索のコード、評価器インターフェース、キャップセットおよびビンパッキング問題の例が含まれている。このオープンな利用可能性は、Machine learningおよびArtificial intelligenceの分野でのさらなる実験を支援する。
意義
FunSearchは、大規模言語モデルと進化的計算の統合で注目されており、これはDeep learningの広範な分野で注目を集めている方向性である。解釈可能なプログラムを生成することで、問題を解決するだけでなく、人間が理解し構築できる洞察を提供するAIシステムへの道を提供する。この手法は、Google DeepMindの科学的発見へのAI適用における広範な取り組みの文脈で議論されており、Generative AIの他のイニシアチブと並んでいる。
FunSearchは特定の数学的・アルゴリズム的タスクで有望性を示しているが、その一般的な適用可能性は依然として活発な研究領域である。事前学習済み言語モデルへの依存と、明確に定義された評価器の必要性は、他の領域での使用を制限する可能性のある制約である。それにもかかわらず、このアプローチは、プログラム合成と最適化に言語モデルを使用するさらなる研究を刺激し、AI研究の進化する風景に貢献している。