DeepMindは行列の乗算を一人用ゲームに変え、50年来の記録を破った

Ars Technicaは2022年10月、DeepMindが行列を乗算するより効率的な方法を見つけ、50年来の記録を破ったと報じた。1969年、Volker Strassenは、学校で習う方法の64回ではなく49回の乗算で2つの4x4行列を乗算するアルゴリズムを見つけた。AlphaTensorと呼ばれるニューラルネットワークを用いて、DeepMindはそれを47回で行う方法を見つけ、Natureに発表した。

DeepMindはこの問題を一人用ゲームとして設定した。「盤面」は現在のアルゴリズムが正解からどれだけ離れているかを表す三次元テンソルであり、許される手はアルゴリズムの命令に対応し、プレイヤーはテンソルの要素をゼロにしようとする。そうすることで、任意の行列の組に対して証明可能な正しいアルゴリズムが得られ、効率はステップ数で表される。AlphaGoと同様に強化学習で訓練されたAlphaTensorは、まずStrassenの業績や他の数学者の業績を再発見し、その後それらを上回ったとDeepMindは述べている。

5x5行列については、AlphaTensorは従来の98ステップに対して96ステップの方法を見つけた。1週間後、Johannes Kepler University LinzのManuel KauersとJakob Moosbauerは95ステップを報告し、彼らの解はDeepMindの方式から1回の乗算を排除する一連の変換によって得られたと書いた。Arsは、行列乗算が音声認識や画像認識、グラフィックスの基盤にあり、そのような計算が毎日GPU上で何兆回も実行されているため、小さな節約でも積み重なる可能性があると指摘している。

より高速な行列アルゴリズムの探索をテンソル上の一人用ゲームとして再構成し、ゲームをプレイするAIが証明可能な正しいアルゴリズムを発見できるようにした。

正しいアルゴリズムはゼロに還元されたテンソルであるため、正しさはゲームのルールに組み込まれている。

使用されるステップ数は明確なスコアであるため、AIはどの手がより短いアルゴリズムにつながるかを学習できる。

行列乗算は非常に広く使われているため、49ステップから47ステップへの短縮でもGPUの規模では重要になる。

発見された方式を公開したことで、人間の研究者が1週間以内にそれを発展させることができた。

研究課題を明確なスコアを持つゲームとして枠組み化できれば、ゲームをプレイするAIがそれを探索でき、その結果がさらなる人間による改善の種になり得る。

DeepMindの発表から1週間後、オーストリアの2人の研究者は、DeepMindの成果に基づいて5x5行列の95回乗算方式を主張した。Arsは、AIが今や新しいアルゴリズムを探索しているため、他の長年の数学記録もまもなく破られる可能性があると推測した。