Google傘下の人工知能研究部門 DeepMind が、「新規で効率的かつ証明可能に正しいアルゴリズムを発見するための最初の人工知能システム」と同社が表現する、「AlphaTensor」を発表した。この研究は、2つの行列を乗算する最速の方法を見つけるという、数学における50年来の未解決問題に「光を当てる」と、同社は述べている。

1969年にシュトラッセンのアルゴリズムが発表されて以来、コンピューターサイエンスは、2つの行列の掛け算の速度を上げることを追求してきた。行列の乗算は、高校の数学で習う代数学の最も単純な操作の1つである一方、最も基本的な計算タスクの1つでもあり、今日のニューラルネットワークの中核となる数学的操作であることが分かっている。

スマートフォンの画像処理、音声コマンドの理解、コンピュータゲームのCG生成、データ圧縮などに、多くの処理に行列乗算が使われている。現在、世界中の企業は、行列を効率的に乗算するためのコンピューティング ハードウェアの開発に多大な時間と費用を費やしているため、これを少しでも高速化できれば、コスト削減と省エネルギー化に繋がるという点で画期的なことなのだ。

行列の概念が生み出されてから数世紀、数学者は標準的な行列の乗算アルゴリズムが、効率という点で最高のものであると信じていた。だが1969年、ドイツの数学者Volker Strassenが、より優れたアルゴリズムが存在することを示し、数学界に衝撃を与えた。2×2という非常に小さな行列を研究し、行列のエントリーを組み合わせることでより高速なアルゴリズムが得られるという独創的な方法を発見したのである。されてから数世紀、数学者は標準的な行列の乗算アルゴリズムが、効率という点で最高のものであると信じていた。だが1969年、ドイツの数学者Volker Strassenの発見以来、数十年にわたる研究が行われたが、この問題の大規模版は未解決のままであり、3×3という小さな2つの行列をどれだけ効率的に掛け合わせることができるかは不明である。

今回のDeepMindの研究は、最新のAIが、この行列乗算について人間を超える効率の良い方法を発見出来るかどうかを探ったものだ。その結果、人間の直感の進歩に基づき、AlphaTensorは多くの行列サイズについて、現状よりも効率的なアルゴリズムを発見した。AlphaTensorが設計したアルゴリズムは、人間が設計したアルゴリズムを凌駕しており、これはアルゴリズム発見の分野での大きな前進となる。

DeepMindはAIを利用してコンピュータサイエンスを改善する

「AIを使って基本的な計算タスクの新しいアルゴリズムを見つけることができれば、現在使われているアルゴリズムを超えることができるかもしれないので、これは非常に大きな可能性を秘めた研究です。そしてそれは、効率の向上につながるかもしれません」と、DeepMindの科学向けAI責任者のPushmeet Kohli氏はプレスリリースで述べている。

特に、新しいアルゴリズムを発見するプロセスは非常に難しく、AIを用いたアルゴリズム発見の自動化には、アルゴリズム問題に関する直感の形成から、実際に新しいアルゴリズムを書き、特定のインスタンスについてそのアルゴリズムが正しいことを証明するという、長く困難な推論プロセスが必要なのだ。

AlphaTensorは、問題についての知識なしで始まり、その後、徐々に何が起こっているかを学び、時間をかけて改善していくプロセスをとっている。

このゲームは、囲碁で人間を凌駕したAlphaGoを元にしたAlphaTensorにとっても挑戦しがいのあるもので、膨大な手数があると言われた囲碁に比べても、その手数は30桁も多いとのことだ。(検討している設定の 1 つは 10 ³³を超えている）

学習を通じて、AlphaTensor は時間の経過とともに徐々に改善され、シュトラッセンが成し遂げたようなな歴史的な高速行列乗算アルゴリズムを再発見し、最終的には人間の直感の領域を超え、以前に知られていたものよりも速いアルゴリズムを発見したのだ。

Kohli氏は、この論文が、他の競技の基本的なタスクにAIを使用してアルゴリズム的発見を導く上で、他の人たちを刺激することを期待していると述べている。「これは、アルゴリズムの発見にAIを本当に利用するための大きな一歩だと考えています。」

DeepMindのスタッフリサーチエンジニアであるThomas Hubert氏によると、AlphaTensorの中身は、実際にAlphaZeroが一部で動いているとのことだ。チェスや囲碁で学習し、活躍したアルゴリズムを、行列乗算に挑戦することにしたのだ。そこで、DeepMindは「行列の積を算出する最適な方法を求めるゲーム」を設計してAlphaTensorにプレイさせた。

実際、DeepMindによると、このゲームは非常に難易度が高く、行列の乗算という小さなケースでも、考慮すべき可能なアルゴリズムの数は宇宙の原子の数よりはるかに多いとのことだ。数十年にわたりAIの課題であった囲碁と比較すると、可能な手の数は30桁も多いという（検討している設定の 1 つは 10 ³³を超えているという）

“このゲームは、基本的にテンソルをゼロにすることであり、実際にはいくつかのアルゴリズム演算を表すいくつかの許容された動きがあります “と彼は説明しました。「これは、2つの非常に重要な結果をもたらします。1つは、テンソルを完全にゼロ分解できれば、証明可能な正しいアルゴリズムが保証されるということです。2つ目は、このテンソルを分解するのにかかるステップ数が、実はアルゴリズムの複雑さを示していることです。だから、とてもとてもきれいなんです」。

DeepMindの論文では、AlphaTensorが、これまで考えられていたよりも豊富な行列乗算アルゴリズムの空間(各サイズで最大数千)を発見していることも指摘されている。

また、ブログ記事によると、著者らは、NVIDIA V100 GPUやGoogle TPU v2といった所定のハードウェア上で高速なアルゴリズムを見つけるためにAlphaTensorを特に適応させたと述べている。 これらのアルゴリズムは、同じハードウェア上で一般的に使用されているアルゴリズムよりも10～20％速く大きな行列を乗算し、これは、任意の目的を最適化するAlphaTensorの柔軟性を示している。

オーストリア・リンツにあるヨハネス・ケプラー大学のコンピュータ科学者、Martina Seidl氏は、「非常に素晴らしいことです。この作品は、難しい数学の問題を解決するために機械学習を使うことの可能性を示しています。」と述べている。

7月に研究者たちは、DeepMindのAlphaFoldツールが、地球上のほぼすべての既知のタンパク質をカバーする、約100万種の生物種から2億以上のタンパク質の構造を予測できることを示した。AlphaTensorは、AIが科学だけでなく数学においても大きな役割を果たす可能性を示している。

論文

• Nature: Discovering faster matrix multiplication algorithms with reinforcement learning

参考文献

• DeepMind: Discovering novel algorithms with AlphaTensor
• Nature: DeepMind AI invents faster algorithms to solve tough maths puzzles

研究の要旨

基本的な計算を行うアルゴリズムの効率化は、大量の計算の全体速度に影響を与えるため、広範囲に影響を及ぼす可能性がある。行列の乗算もその一つで、ニューラルネットワークから科学計算ルーチンに至るまで、多くのシステムで発生する原始的な作業だ。機械学習を用いたアルゴリズムの自動探索は、人間の直感を超え、人間が設計した現在の最良のアルゴリズムを凌駕する可能性がある。しかし、アルゴリズム探索の自動化は、アルゴリズムが存在する空間が膨大であるため、複雑な作業である。本稿では、AlphaZero に基づく深層強化学習により、任意の行列の乗算に関する効率的かつ証明可能な正解のアルゴリズムを発見する手法を報告する。我々のエージェントであるAlphaTensorは、有限因子空間内でテンソル分解を見つけることを目的としたシングルプレイヤーゲームをプレイするように訓練される。AlphaTensorは、多くの行列サイズに対して、最先端の複雑さを凌駕するアルゴリズムを発見した。特に、有限体における4×4行列の場合、AlphaTensorのアルゴリズムは、50年前のStrassenの発見以来、我々の知る限り初めて2レベルアルゴリズムを改善することができた。さらに、さまざまなユースケースを通して、AlphaTensorの柔軟性を紹介します。構造化行列乗算のための最先端の複雑性を持つアルゴリズムや、特定のハードウェア上での実行のために行列乗算を最適化することによる実用的な効率の向上などです。我々の結果は、AlphaTensorが様々な問題に対してアルゴリズムの発見プロセスを加速し、異なる基準で最適化する能力を持つことを強調している。