DeepMindがNatureで発表した「Mathematical discoveries from program search with large language models」を読んだ際のメモです。
概要
対象問題
「キャップ セット問題」や「オンラインビンパッキング問題」のような組み合わせ問題の解を生成するプログラムを生成する。
対象とする問題は、解を評価関数でスコアリングできる必要がある。
独立して進化させる部分にスケルトンプログラムを提供できる必要がある。
アルゴリズム
構成
ProgramDB、Sampler、Evaluatorから構成される。
ProgramDBは、生成されたプログラムを管理する。
Samplerは、ProgramDBから改善するプログラムをサンプリングする。
Evaluatorは、生成されたプログラムが出力する解を評価する。
進化的アルゴリズム
島モデルを使用して、それぞれの島でプログラムを進化的アルゴリズムで改善する。
定期的に、下位半分の島のプログラムを削除し、上位の島のプログラムをコピーする。
島モデルにより多様性が確保され局所解に陥るのを避けることができ、島間で情報が流れることで効率的に改善される。
プログラムを改善するプロンプト
プログラムを改善するプロンプトは、複数のプログラムをサンプリングし、スコア順にプログラムを並べて、後のプログラムのコメントに「一つ前の改善したバージョン」であることを記述する。
最後に、プログラムのヘッダーと「一つ前の改善したバージョン」であるコメントを加える。
このプロンプトを使用してLLMで、改善したプログラムを生成する。
このプロンプトを「ベストショット プロンプト」と呼ぶ。
LLM
LLMには、APIで使用できるPaLM 2ベースのCodeyとオープン ソースの StarCoderを使用した（StarCoder は Codey と比較してパフォーマンスがわずかに悪い）。
事前学習済みモデルを使用して、ファインチューニングは行っていない。
結果
キャップ セット問題
次元 n = 8 では、FunSearch は以前に知られていたものよりも大きなキャップ セットを発見した。
オンラインビンパッキング問題
良く知られているヒューリスティックである「ファースト フィット」と「ベスト フィット」よりも優れたパフォーマンスを発揮した。
発見されたプログラムは人間に解釈可能で、アイテムを最小容量のビン (最適フィットなど) に詰め込むのではなく、アイテムを配置した後のフィット感が非常に厳しい場合にのみ、アイテムを最小容量のビンに割り当てる戦略が使用されていた。
