大規模言語モデルを利用して数学の未解決問題で新たな解を発見――実用的な課題でもその性能を実証

Google DeepMindは、大規模言語モデル（LLM）を利用した新手法「FunSearch」を用いて、数理科学において長年の未解決問題である「cap set（キャップ集合）問題」の新しい解を発見した。さらに、現実世界で多様な応用が可能な「ビンパッキング（箱詰め）問題」の、より効果的なアルゴリズムも見つけた。この研究は2023年12月14日付で『Nature』に掲載され、科学や数学の未解決問題に対して、LLMを使って新しい発見をした初めての研究例になるという。

LLMは概念を組み合わせることに優れており、読み書きやコーディングができて、問題解決を支援する便利なアシスタントだ。しかし、LLMはまるで「幻覚」を見たかのように、事実とは異なる情報をもっともらしく生成して出力することがあるという点が明らかになっており、LLMを使用して立証可能な正しい発見をすることは困難だ。

そこで研究者らは、創造的な解決策をコンピューターコードの形で提供するよう事前に訓練されたLLMと、「幻覚」や誤ったアイデアを防ぐように自動化された「評価装置」をペアにして機能するFunSearchを考案した。このシステムは、コンピューターコードに書かれた「関数（function）」を「検索（search）」することから「FunSearch」と名付けられた。

FunSearchは、LLMと評価装置との間で繰り返される反復処理を行う。生成済みプログラムの中からいくつか選択してLLMに送ると、LLMはそれらを元にして独創的に新たなプログラムを生成する。LLMが生成した新プログラムは自動的に評価され、最も優れたプログラムはデータベースに追加されて、次のサイクルで選択される。こうして自己改善ループが形成される。

FunSearchで最初に取り組んだキャップ集合問題は、何十年も数学者たちを悩ませてきた未解決問題だ。高次元格子において3つの点が直線上には存在しない点の集合で最大のものを求めるというものだが、しらみつぶしに演算して解こうとすると、考えるべき可能性の数がすぐに宇宙に存在する原子の数より多くなってしまうためうまくいかない。

この問題について重要なブレークスルーを明らかにした、米ウィスコンシン大学マディソン校数学部のJordan Ellenberg教授と共同で研究した結果、FunSearchはプログラムの形で解決策を生成し、いくつかの設定においてはこれまでに発見された中で最大のキャップ集合を発見した。また、FunSearchは単に問題の解を生成するだけでなく、その解がどのようにして導き出されたかを説明するプログラムを、研究者が理解しやすい形で生成するといった利点もある。そのおかげで、研究者は実用的な洞察を得られ、さらに優れた解決策を導き出すのに役立ったという。

次に取り組んだビンパッキング問題は、異なるサイズの物品すべてを詰め込むために必要な一定容量のビン（箱）の数を最小にするような方法を求めるというものだ。オンラインのビンパッキング問題は、通常、人間の経験に基づくアルゴリズム的経験則（ヒューリスティックス）を用いて対処される。しかし、サイズ、タイミング、容量が異なるそれぞれの状況ごとのルールを見つけることは困難だ。

キャップ集合問題とはまったく異なる問題にもかかわらず、FunSearchは簡単な設定をするだけで、データ仕様に適応し、自動的にそれぞれの目的に合ったプログラムを生成した。このプログラムは、定評のあるヒューリスティックスを上回り、同じ数の物品を詰めるために必要なビンの数は少なくなった。FunSearchは導入しやすいコードを出力するので、さまざまな産業システムで迅速に利益をもたらす可能性がある

FunSearchは、LLMの「幻覚」を防げば、その能力を数学的な新発見だけでなく、現実世界の重要な問題に対して、影響力の強い解決策を明らかにすることにも活用できることを実証したといえる。

研究チームは、科学や産業における多くの問題に対して、LLM駆動型アプローチを用いて、効果的で目的に合ったアルゴリズムを生成することが一般的な方法になると予想しているという。

大規模言語モデルを利用して数学の未解決問題で新たな解を発見――実用的な課題でもその性能を実証