応用数学：強化学習による、より高速な行列乗算アルゴリズムの発見
Nature 610, 7930 doi: 10.1038/s41586-022-05172-4
基本的な計算のアルゴリズムの効率は、大規模計算全体の速度に影響を及ぼし得るので、その改善の影響は広範囲に及ぶ可能性がある。行列乗算は、そうした基本的タスクの1つであり、ニューラルネットワークから科学計算ルーチンまで、多くの系で見られる。機械学習を用いたアルゴリズムの自動発見によって、人間の直感を超え、人間が設計した現在最良のアルゴリズムを凌駕する見通しが得られる。しかし、アルゴリズムの発見手順の自動化は、アルゴリズムが存在し得る空間が巨大であるため難解である。今回我々は、効率がよく、正しさを証明できる任意の行列の乗算アルゴリズムを発見するための、AlphaZeroに基づく深層強化学習法について報告する。今回のエージェントAlphaTensorは、有限の因子空間内でテンソル分解を見つけることを目的としたシングルプレイヤーゲームを行うように訓練されている。AlphaTensorは、多くの行列サイズについて、最先端の複雑さを凌駕するアルゴリズムを発見した。中でも特に重要なのは、有限体における4 × 4行列の場合で、AlphaTensorのアルゴリズムはこの行列において、50年前に発見されたStrassenの2レベルアルゴリズムに、我々の知る限りでは発見以来初めて改良を加えた。さらに我々は、AlphaTensorの柔軟性を、構造化行列乗算のための最先端の複雑さを持つアルゴリズムや、特定のハードウエアにおける実行時間について行列乗算を最適化することによる実用的効率の改善などのさまざまな適用事例を通して示す。今回の結果は、さまざまな問題に対してアルゴリズム発見過程を加速し、さまざま基準で最適化する、AlphaTensorの能力を浮き彫りにしている。
