AlphaTensorを使用して新しいアルゴリズムを発見する

Discover new algorithms using AlphaTensor.

数学へのAlphaZeroの初の拡張は、研究の新たな可能性を開く

アルゴリズムは、何千年もの間、数学者が基本的な操作を行うのを助けてきました。古代エジプト人は、乗算表を必要とせずに2つの数を掛け算するアルゴリズムを作り出し、ギリシャの数学者ユークリッドは最大公約数を計算するアルゴリズムを記述しました。このアルゴリズムは今日でも使われています。

イスラム黄金時代には、ペルシャの数学者ムハンマド・イブン・ムーサ・アル＝ハワーリズミーが線形方程式や二次方程式を解くための新しいアルゴリズムを設計しました。実際、アル＝ハワーリズミーの名前はラテン語でAlgoritmiと翻訳され、アルゴリズムという用語の由来となりました。しかし、アルゴリズムは今日、教室の代数から最先端の科学研究まで社会全体で広く使われているにもかかわらず、新しいアルゴリズムを発見するプロセスは非常に困難であり、人間の驚異的な推論能力の一例です。

本日Natureに掲載された私たちの論文では、AlphaTensorという初の人工知能（AI）システムを紹介しています。このシステムは、行列の乗算などの基本的なタスクに対して、新しい効率的で証明可能なアルゴリズムを発見するためのものです。これにより、行列の最速の乗算方法を求める数学上の50年前からの未解決問題に光を当てています。

この論文は、AIを使って科学を進歩させ、最も基本的な問題を解決するためのDeepMindの使命の一環です。私たちのシステムであるAlphaTensorは、将棋を含むボードゲームで超人的なパフォーマンスを示したエージェントであるAlphaZeroを基にしており、この研究はAlphaZeroがゲームをプレイすることから初めて未解決の数学問題に取り組むまでの道のりを示しています。

• AIモデルの知覚を測定する
• ビデオゲームの世界でインタラクティブなエージェントを構築する
• DeepMindの最新研究（NeurIPS 2022）

行列の乗算

行列の乗算は代数学の中でも最も単純な操作の一つであり、高校の数学の授業でよく教えられています。しかし、教室の外では、このささやかな数学の操作が現代のデジタル世界に大きな影響を与え、現代のコンピューティングで広く使われています。

この操作は、スマートフォンでの画像処理、音声コマンドの認識、コンピュータゲームのグラフィック生成、天気予報のためのシミュレーション、インターネットでのデータや動画の圧縮など、現代のコンピューティングにおいて普遍的に使用されています。世界中の企業は、効率的な行列の乗算のために多くの時間と資金を費やしてコンピューティングハードウェアを開発しています。そのため、行列の乗算の効率性をわずかに改善するだけでも広範な影響を与えることができます。

数世紀にわたり、数学者たちは、標準的な行列の乗算アルゴリズムが効率の面で最善であると信じていました。しかし、1969年、ドイツの数学者フォルカー・シュトラッセンがより良いアルゴリズムが存在することを示し、数学コミュニティを驚かせました。

彼は非常に小さな行列（2×2のサイズ）を研究することで、行列のエントリーを組み合わせる巧妙な方法を見つけ出し、より速いアルゴリズムを生み出しました。シュトラッセンの大発見以降、数十年にわたる研究にもかかわらず、この問題のより大きなバージョンは未解決のままです。実際、3×3のサイズの行列をどれだけ効率よく乗算できるかは分かっていません。

私たちの論文では、現代のAI技術が新しい行列の乗算アルゴリズムの自動的な発見をどのように進めるかを探求しました。AlphaTensorは、人間の直感の進展に基づいて、多くの行列サイズにおいて最先端のアルゴリズムよりも効率的なアルゴリズムを発見しました。私たちが開発したAIによるアルゴリズムは、人間による設計のアルゴリズムを上回り、アルゴリズムの発見の分野における重要な進歩です。

アルゴリズムの自動化のプロセスと進歩

まず、行列の乗算の効率的なアルゴリズムを見つける問題を、一人用のゲームに変換しました。このゲームでは、現在のアルゴリズムの正確さからどれだけ離れているかを捉えた3次元テンソル（数の配列）がボードとなります。アルゴリズムの指示に対応する一連の許可された動きを通じて、プレイヤーはテンソルを変更し、そのエントリーをゼロにすることを試みます。プレイヤーが成功すると、これにより任意の行列の乗算に対して証明された正しいアルゴリズムが得られ、その効率性はテンソルをゼロにするためにかかったステップの数で表されます。

このゲームは非常に挑戦的です – 行列の乗算の小さなケースでも考慮すべき可能なアルゴリズムの数は、宇宙の原子の数よりもはるかに大きいです。AIにとっての困難であった囲碁と比較すると、私たちのゲームでは各ステップで考慮する可能な手の数は30の桁以上大きいです（私たちが考慮する設定の1つでは10の33乗を超えます）。

基本的には、このゲームをうまくプレイするためには、可能性の巨大なハヤスタックの中で最も微細な針を見つける必要があります。この伝統的なゲームから大きく逸脱しているこの領域の課題に取り組むために、私たちは問題特有の帰納的バイアスを組み込んだ新しいニューラルネットワークアーキテクチャや、有用な合成データを生成する手順、問題の対称性を活用するレシピなど、複数の重要なコンポーネントを開発しました。

その後、強化学習を用いてAlphaTensorエージェントを訓練し、既存の行列乗算アルゴリズムについての知識を全く持たない状態からゲームをプレイさせました。学習により、AlphaTensorは徐々に向上し、ストラッセンのような歴史的に高速な行列乗算アルゴリズムを再発見し、以前に知られていたものよりも高速なアルゴリズムを発見し、人間の直感を超える領域に達しました。

例えば、学校で教えられる伝統的なアルゴリズムでは、4×5行列と5×5行列を100回の乗算で掛け算するとします。この数値を人間の創造力により80まで削減した場合、AlphaTensorは同じ操作をわずか76回の乗算で行うアルゴリズムを見つけました。

この例に加えて、AlphaTensorのアルゴリズムは、有限体でのStrassenの2階層アルゴリズムを50年ぶりに改善しています。これらの小行列の乗算のアルゴリズムは、任意のサイズのより大きな行列の乗算に基本的な要素として使用することができます。

さらに、AlphaTensorは最先端の複雑さを持つ多数の行列乗算アルゴリズムを発見します – 各サイズに対して数千のアルゴリズムがあり、行列乗算アルゴリズムの空間が以前に考えられていたよりも豊かであることを示しています。

この豊かな空間のアルゴリズムには、異なる数学的および実用的な特性があります。この多様性を活用して、AlphaTensorをNvidia V100 GPUやGoogle TPU v2などの特定のハードウェア上で高速なアルゴリズムを見つけるように適応させました。これらのアルゴリズムは、同じハードウェア上で一般的に使用されるアルゴリズムよりも10〜20％高速に大規模な行列の乗算を行います。これはAlphaTensorの柔軟性を示しています。

将来の研究と応用への影響の探索

数学的な観点からは、私たちの結果は計算問題の最速アルゴリズムを決定することを目指す複雑性理論のさらなる研究を導くことができます。従来の手法よりも効果的な方法で可能なアルゴリズムの空間を探索することにより、AlphaTensorは行列乗算アルゴリズムの豊かさに関する理解を進めるのに役立ちます。この空間の理解は、コンピュータサイエンスで最も基本的なオープンな問題の1つである行列乗算の漸近的複雑さを決定するための新しい結果を見つけることを可能にするかもしれません。

行列の乗算は、コンピュータグラフィックス、デジタル通信、ニューラルネットワークのトレーニング、科学計算など、多くの計算タスクで中核的な要素です。AlphaTensorによって発見されたアルゴリズムは、これらのフィールドでの計算を大幅に効率化することができます。AlphaTensorの柔軟性により、エネルギー使用量や数値の安定性などのメトリックを最適化するアルゴリズムの設計においても、新しい応用が生まれる可能性があります。これにより、アルゴリズムが動作する過程での小さな丸め誤差が蓄積するのを防ぐのに役立ちます。

ここでは特に行列の乗算の問題に焦点を当てましたが、私たちの論文が他の基本的な計算タスクにおいてもAIを使用してアルゴリズムの発見を導くことに他の人々を刺激することを望んでいます。また、私たちの研究は、AlphaZeroが伝統的なゲームの範囲を超えて拡張可能な強力なアルゴリズムであり、数学の未解決の問題を解決するのにも役立つことを示しています。私たちの研究を基に、数学や科学全般においてAIを活用して社会が直面する重要な課題の解決に貢献したいと考えています。

詳細は、AlphaTensorのGitHubリポジトリで確認することができます。

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!