Deep Mind AlphaTensor は新しいアルゴリズムを発見します

Deep Mind は AlphaZero を数学に拡張し、研究アルゴリズムの新しい可能性を解き放ちました。

AlphaTensor は、チェス、囲碁、将棋などのボード ゲームで超人的なパフォーマンスを発揮したエージェントである AlphaZero を基に構築されています。この作品は、AlphaZero がゲームをプレイすることから未解決の数学的問題に初めて取り組むまでの旅を示しています。

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

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

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

ゼロからトレーニングされた AlphaTensor は、人間やコンピューターが設計した既存のアルゴリズムよりも効率的な行列乗算アルゴリズムを発見します。 既知のアルゴリズムよりも改善されているにもかかわらず、AlphaTensor の制限は、一連の潜在的な因子エントリ F を事前に定義する必要があることであり、これにより検索空間が離散化されますが、効率的なアルゴリズムを見逃す可能性があることに注意してください。 将来の研究の興味深い方向性は、AlphaTensor を F の検索に適応させることです。AlphaTensor の重要な強みの XNUMX つは、アルゴリズムを見つけることに加えて、複雑な確率的および微分不可能な報酬 (テンソル ランクから特定のハードウェアでの実用的な効率まで) をサポートする柔軟性です。さまざまな空間 (有限フィールドなど) でのカスタム操作用。 彼らは、数値安定性やエネルギー使用量など、ここでは考慮しなかったメトリクスを最適化するアルゴリズムの設計に向けて、AlphaTensor のアプリケーションが促進されると考えています。

行列乗算アルゴリズムの発見は、行列の逆変換、行列式の計算、線形システムの解決など、多くの計算タスクの中核に位置するため、広範囲に及ぶ意味を持ちます。

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

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

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

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

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

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

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

Nature – 強化学習によるより高速な行列乗算アルゴリズムの発見

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