LLM支援型アルゴリズム発見のための対照的概念ツリー探索

TL;DR（結論）

大規模言語モデル（LLM）を用いたアルゴリズム発見は、プログラム空間における反復的な最適化プロセスであるが、プログラム空間自体の構造が脆弱であるため、効率的な探索が困難であった。本研究では、生成されたプログラムから階層的な意味的概念を抽出し、高性能な解と低性能な解を対照的にモデル化することで親プログラムの選択を導く「対照的概念ツリー探索（CCTS）」を提案した。実験の結果、CCTSは組合せ数学の問題において従来手法を上回る探索効率を示し、特に「どの概念を避けるべきか」を学習することが性能向上に大きく寄与していることを明らかにした。

なぜこの問題か

大規模言語モデル（LLM）の急速な進展により、プログラム合成を反復的なブラックボックス最適化ループに組み込んだ新しいアルゴリズム発見システムが登場している。この手法では、LLMが候補となるプログラムを提案し、外部の評価関数がその性能を測定し、数ラウンドにわたって洗練させていく。このようなプロセスは、プログラム空間における進化プロセスとして捉えられ、LLMは変異オペレーター、プログラムの性能は適合度関数の役割を果たす。最近では、エルデシュ型の組合せ数学問題の解を改善したり、人間の設計に匹敵するヒューリスティックを生成したりすることに成功している。 しかし、現在のLLM支援型アルゴリズム発見システムには重大な限界が存在する。既存のシステムの多くは、適合度駆動型の進化的な更新に依存しており、親プログラムはターゲットタスクにおけるスコアのみに基づいて選択される。この戦略はプログラム空間内で直接動作するが、プログラム空間自体は構造が非常に脆弱である。LLMによって制約されている場合でも、生成されるアルゴリズムには明確な局所性や滑らかな変化、あるいは探索に活用できる構成的構造が欠けている。…

核心：何を提案したのか

本研究では、アルゴリズム空間の潜在的な構造を明示化するために、アルゴリズムを階層的に組織化された意味的な概念空間の観点から記述できるという仮説を立てた。この階層構造において、各ノードは概念を表し、エッジは洗練または特殊化の関係をエンコードする。各概念はタスクの性能に対して正または負に寄与し、強力なアルゴリズムは有用な概念を組み合わせ、有害な概念を避けることで生まれると考える。このようなツリー構造の組織化は、科学的発見において自然なものである。 この仮説に基づき、本研究では「対照的概念ツリー探索（Contrastive Concept-Tree Search, CCTS）」を導入した。CCTSは、探索中にどの意味的概念を優先すべきかを学習する概念誘導型のアルゴリズム発見フレームワークである。…

続きはログイン/プランで閲覧できます。