数学への AlphaZero の最初の拡張により、研究の新しい可能性が開かれます

アルゴリズムは、何千年もの間、数学者が基本的な演算を実行するのに役立ってきました。 古代エジプト人は、乗算表を必要とせずに XNUMX つの数を乗算するアルゴリズムを作成し、ギリシャの数学者ユークリッドは、今日でも使用されている最大公約数を計算するアルゴリズムを記述しました。 

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

紙、本日 Nature に掲載されました, 紹介します アルファテンソル、行列乗算などの基本的なタスクのための斬新で効率的で証明可能なアルゴリズムを発見するための最初の人工知能 (AI) システムです。 これは、50 つの行列を乗算する最速の方法を見つけることについて、数学で XNUMX 年前に未解決の問題が発生したことに光を当てます。

この論文は、科学を進歩させ、AI を使用して最も基本的な問題を解き明かすという DeepMind の使命の足がかりです。 私たちのシステム、AlphaTensor は、AlphaZero に基づいて構築されています。 チェス、囲碁、将棋などのボードゲームで超人的なパフォーマンスを見せた、そしてこの作品は、ゲームをプレイすることから未解決の数学的問題に初めて取り組むまでのAlphaZeroの旅を示しています. 

行列乗算

行列の掛け算は代数の中で最も単純な演算の XNUMX つで、高校の数学の授業でよく教えられます。 しかし、教室の外では、この控えめな数学的操作は現代のデジタル世界に多大な影響を与え、現代のコンピューティングではどこにでもあります。 

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

何世紀にもわたって、数学者は標準的な行列乗算アルゴリズムが効率の面で達成できる最高のものであると信じていました。 しかし1969年、ドイツの数学者フォルケン・シュトラッセンは 数学界に衝撃を与えた より優れたアルゴリズムが存在することを示すことによって。

非常に小さな行列 (サイズ 2×2) を研究することで、彼は行列のエントリを組み合わせてより高速なアルゴリズムを生成する独創的な方法を発見しました。 Strassen の突破口に続く何十年にもわたる研究にもかかわらず、この問題のより大きなバージョンは未解決のままであり、3×3 ほどの小さい XNUMX つの行列をどれだけ効率的に乗算できるかはわかっていません。 

私たちの論文では、最新の AI 技術が新しい行列乗算アルゴリズムの自動発見をどのように進めることができるかを探りました。 人間の直感の進歩に基づいて、AlphaTensor は多くの行列サイズに対して最先端のアルゴリズムよりも効率的なアルゴリズムを発見しました。 当社の AI 設計アルゴリズムは、人間が設計したアルゴリズムよりも優れています。これは、アルゴリズム発見の分野における大きな前進です。 

アルゴリズム発見の自動化のプロセスと進捗状況

まず、行列乗算の効率的なアルゴリズムを見つける問題をシングルプレイヤー ゲームに変換しました。 このゲームでは、ボードは XNUMX 次元のテンソル (数値の配列) であり、現在のアルゴリズムがどれだけ正しくないかを捉えています。 プレイヤーは、アルゴリズムの命令に対応する一連の許可された動きを通じて、テンソルを変更し、そのエントリをゼロにしようとします。 プレーヤーがそうすることができた場合、これにより、行列の任意のペアに対して証明可能な正しい行列乗算アルゴリズムが得られ、その効率はテンソルをゼロにするために実行されるステップの数によってキャプチャされます。

このゲームは非常にやりがいがあります。考慮すべきアルゴリズムの数は、行列の乗算の小さなケースであっても、宇宙の原子の数よりもはるかに多くなります。 残っていた囲碁と比べて 何十年にもわたる AI の課題、ゲームの各ステップで可能な移動の数は、30 桁も大きくなります (10 を超える)³³ 検討する設定の XNUMX つ)。

基本的に、このゲームを上手にプレイするには、膨大な数の可能性の干し草の山の中から、最も小さな針を特定する必要があります。 従来のゲームとは大きく異なるこの領域の課題に取り組むために、問題固有の帰納的バイアスを組み込んだ新しいニューラル ネットワーク アーキテクチャ、有用な合成データを生成する手順、対称性を活用するレシピなど、複数の重要なコンポーネントを開発しました。問題。

次に、強化学習を使用して AlphaTensor エージェントをトレーニングし、既存の行列乗算アルゴリズムに関する知識なしでゲームをプレイしました。 学習を通じて、AlphaTensor は時間の経過とともに徐々に改善され、Strassen のような歴史的な高速行列乗算アルゴリズムを再発見し、最終的には人間の直感の領域を超え、以前に知られていたよりも速くアルゴリズムを発見します。

たとえば、学校で教えられている従来のアルゴリズムが 4×5 × 5×5 の行列を 100 回の乗算を使用して乗算し、この数が人間の創意工夫によって 80 回に削減された場合、AlphaTensor は、わずか 76 回の乗算を使用して同じ演算を行うアルゴリズムを発見しました。 

この例を超えて、AlphaTensor のアルゴリズムは、50 年前の発見以来初めて、有限体での Strassen の XNUMX レベル アルゴリズムを改善しています。 小さな行列を乗算するためのこれらのアルゴリズムは、任意のサイズのはるかに大きな行列を乗算するためのプリミティブとして使用できます。 

さらに、AlphaTensor は、最先端の複雑さを備えた多様なアルゴリズムのセット (サイズごとに最大数千の行列乗算アルゴリズム) も発見しており、行列乗算アルゴリズムの空間がこれまで考えられていたよりも豊富であることを示しています。 

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

今後の研究や応用への影響を探る

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

行列の乗算は、コンピューター グラフィックス、デジタル通信、ニューラル ネットワークのトレーニング、および科学計算にまたがる多くの計算タスクのコア コンポーネントであるため、AlphaTensor が発見したアルゴリズムは、これらの分野での計算を大幅に効率化する可能性があります。 あらゆる種類の目的を考慮できる AlphaTensor の柔軟性は、エネルギー使用量や数値安定性などのメトリックを最適化するアルゴリズムを設計するための新しいアプリケーションに拍車をかけ、アルゴリズムが機能するときに小さな丸め誤差が雪だるま式に増えるのを防ぐのに役立ちます。

ここでは行列乗算の特定の問題に焦点を当てましたが、私たちの論文が他の基本的な計算タスクのアルゴリズムの発見を導くために AI を使用することに他の人を刺激することを願っています。 私たちの調査では、AlphaZero が は、数学の未解決の問題を解決するのに役立つ、従来のゲームの領域をはるかに超えて拡張できる強力なアルゴリズムです。 私たちの研究に基づいて、私たちはより多くの仕事に拍車をかけることを望んでいます.AIを適用して、社会が数学や科学全体の最も重要な課題のいくつかを解決するのを支援します.