最強将棋AIが新境地へ、DeepMindのAI「AlphaTensor」が50年以上停滞していた行列乗算アルゴリズムの改良に成功

囲碁世界チャンピオンを打ち負かしたDeepMind製のAI「AlphaGo」は度重なる機能強化によってチェスや将棋などあらゆるボードゲームへの対応を果たしました。新たに、AlphaGoの系譜を受け継ぐAI「AlphaTensor」が「行列の積を計算する最適な方法を求めるゲーム」に挑み、行列の積を計算する未発見のアルゴリズムを導き出すことに成功しました。

Discovering faster matrix multiplication algorithms with reinforcement learning | Nature
https://doi.org/10.1038/s41586-022-05172-4

Discovering novel algorithms with AlphaTensor
https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor

今回AlphaTensorが取り組んだ「行列の積を計算するアルゴリズム」は画像処理やゲームのグラフィック処理、天気予報、データの圧縮など日常生活にかかわる多様な分野で用いられています。行列計算を高速化するために多くの企業が計算用ハードウェアの開発や増強に取り組んでいますが、アルゴリズムそのものが効率化されれば行列計算の速度が飛躍的に向上する可能性があります。

行列の積を高速に計算するアルゴリズムとしては、1969年に発表された「シュトラッセンのアルゴリズム」が広く知られています。しかし、シュトラッセンのアルゴリズムが発表されて以降50年以上にわたって大幅な効率化は実現していませんでした。そこで、DeepMindは「行列の積を算出する最適な方法を求めるゲーム」を設計してAlphaTensorにプレイさせました。

プレイ開始時のAlphaTensorは「行列の積を計算する方法」を一切学習していませんでしたが、プレイを繰り返すうちに効率的な計算方法を身に付け始めました。例えば、「4×5の行列」と「5×5の行列」の積を求める際は、愚直に計算すると100回乗算が必要ですが、既知のアルゴリズムを用いれば乗算回数を80回に減らせます。それに対して、AlphaTensorが導き出したアルゴリズムでは76回の乗算で積を求めることが可能です。

プレイを重ねた結果、AlphaTensorはシュトラッセンのアルゴリズムに似たアルゴリズムを自力で導きだし、さらに、既存のアルゴリズムより効率的に計算可能なアルゴリズムを導き出すことに成功しました。DeepMindによると、AlphaTensorが発見したアルゴリズムは数千行という膨大な大きさの行列にも対応可能とのこと。また、「NVIDIA V100」や「Google TPU v2」といった特定のハードウェアで行列計算速度を10％～20％高速化するアルゴリズムも導き出されました。

DeepMindは、AlphaTensorが発見したアルゴリズムがコンピューターグラフィックスや通信処理、ニューラルネットワークのトレーニングなどの計算を大幅に効率化する可能性があると述べています。また、DeepMindはAlphaTensorによるアルゴリズム探求を行列以外の計算分野にも役立てられる可能性を指摘しています。

なお、AlphaTensorが発見した行列乗算アルゴリズムは、以下のGitHubリポジトリで公開されています。

GitHub - deepmind/alphatensor
https://github.com/deepmind/alphatensor