強化学習で行列乗算アルゴリズムを発見、DeepMind が Nature の表紙を飾り、AlphaTensor を発売

アルゴリズムは、何千年もの間、数学者が基本的な演算を実行するのに役立ってきました。昔、古代エジプト人は九九を使わずに 2 つの数値を乗算するアルゴリズムを発明しました。ギリシャの数学者ユークリッドは、今日でも使用されている最大公約数を計算するアルゴリズムを説明しました。イスラム黄金時代、ペルシアの数学者ムハンマド・イブン・ムーサ・アル・フワリズミは、その後の研究に大きな影響を与える一次方程式および二次方程式を解くための新しいアルゴリズムを考案しました。

実際、アルゴリズムという言葉の出現についての格言があります。ペルシャの数学者ムハンマド・イブン・ムーサ・アル・フワリズミの名前にあるアル・フワリズミという言葉は、ラテン語に訳すと次のようになります。 Algoritmi という意味は、アルゴリズムという言葉につながります。しかし、今日私たちはアルゴリズムをよく知っていますが、教室で学ぶことができ、科学研究の分野でも頻繁にアルゴリズムに遭遇します。社会全体がアルゴリズムを使用しているように見えますが、新しいアルゴリズムを発見するプロセスは非常に困難です。 。

現在、DeepMind は AI を使用して新しいアルゴリズムを発見しています。

Nature の表紙論文の最新号「強化学習によるより高速な行列乗算アルゴリズムの発見」で、DeepMind は AlphaTensor を提案し、これが次のような基本的な関数に使用できる最初のアルゴリズムであると述べました。行列の乗算として、新しい、効率的で正しいと証明できるアルゴリズムを発見することを使命とする人工知能システム。簡単に言えば、AlphaTensor を使用すると、新しいアルゴリズムを発見できます。この研究は、2 つの行列を乗算する最速の方法を見つけるという、数学における 50 年来の未解決の問題に光を当てます。

• 紙のアドレス ： https://www.nature.com/articles/s41586-022-05172-4
• GitHub アドレス: https://github.com/deepmind / alphatensor

AlphaTensor は、チェスの AlphaZero に基づいて構築されており、エージェントに勝つことができます。囲碁や将棋などのボードゲームの人間。この作品は、AlphaZero がゲームでの使用から未解決の数学的問題を解決するために初めて使用されるまでの移行を示しています。

行列の乗算

行列の乗算は、代数学の最も単純な演算の 1 つであり、通常は高校の数学の授業で教えられます。しかし、教室の外では、この地味な数学的演算が現代のデジタル世界に多大な影響を与え、現代のコンピューティングのいたるところに浸透しています。

#2 つの 3x3 行列を乗算する例。

行列の乗算は、スマートフォンの画像処理や音声コマンドの認識など、私たちの生活のあらゆるところに隠されていることに気づいていないかもしれません。コンピューター ゲームのグラフィックスの生成など、舞台裏での計算。世界中の企業は、行列の乗算を効率的に解くためのコンピューティング ハードウェアの開発に膨大な時間と資金を費やすことに積極的です。したがって、行列の乗算効率の小さな改善でも、広範囲に影響を与える可能性があります。

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

標準アルゴリズムと Strassen アルゴリズムを比較すると、後者の方が実行する乗算演算が 1 つ少なく、7 です。前者では 8 回必要となり、全体の効率が大幅に向上します。

ストラッセンは、非常に小さな行列 (サイズ 2x2) を研究することで、行列の項を組み合わせてより大きな高速アルゴリズムを生成する賢い方法を発見しました。 。その後数十年間、研究者たちはより大きな行列を研究してきましたが、3x3 行列を乗算する効率的な方法さえまだ解決されていません。

DeepMind による新しい研究では、最新の AI テクノロジーが新しい行列乗算アルゴリズムの自動検出をどのように推進しているかを調査しています。人間の直観の進歩に基づいて、AlphaTensor によって発見されたアルゴリズムは、より大きな行列に対して多くの SOTA メソッドよりも効率的です。この研究は、AI によって設計されたアルゴリズムが人間によって設計されたアルゴリズムよりも優れていることを示しており、アルゴリズム発見の分野において重要な前進となります。

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

まず、行列乗算の効率的なアルゴリズムを発見するという問題をシングルプレイヤー ゲームに変換します。このうち、board は、現在のアルゴリズムがどの程度正しいかを把握するために使用される 3 次元テンソル (数値の配列) です。アルゴリズムの命令に対応する一連の許可された動きを通じて、プレイヤーはテンソルを変更し、そのエントリをゼロに戻そうとします。

プレイヤーがこれを行うことができれば、任意の行列のペアに対して証明可能で正しい行列乗算アルゴリズムが生成され、その効率はテンソルをゼロにするために必要なステップ数によって測定されます。 。

このゲームは非常に挑戦的で、考慮すべきアルゴリズムの数は、行列の乗算のような小さな場合であっても、宇宙の原子の数よりもはるかに多くなります。何十年にもわたって AI の課題であった囲碁と比較すると、このゲームには 1 手あたり 30 桁も多くの可能な手があります (DeepMind が検討した設定の 1 つは 10^33+ でした)

#従来のゲームとは大きく異なるこの領域の課題に対処するために、DeepMind は、問題固有の帰納的バイアスを組み込んだ新しいニューラル ネットワーク アーキテクチャ、有用な合成データを生成するプログラム、および問題の対称性を利用します。

次に、DeepMind は、既存の行列乗算アルゴリズムの知識がない状態から、ゲームをプレイできるように強化学習エージェント AlphaTensor をトレーニングしました。 AlphaTensor は学習によって時間の経過とともに徐々に改善され、歴史的に高速な行列アルゴリズム (ストラッセンのアルゴリズムなど) を再発見したり、以前に知られていたよりも高速なアルゴリズムを発見したりします。

AlphaTensor 正しい行列乗算アルゴリズムを見つけることが目的のシングル プレイヤー ゲームです。ゲームの状態は、実行すべき残りの作業を表す数値の立方体配列 (灰色は 0、青色は 1、緑色は - 1 を表します) です。

たとえば、学校で教えられる従来のアルゴリズムが、人間の知恵を通じて 4x5 と 5x5 の行列の乗算を 100 回の乗算で完了できるとします。その数を 80 分の 1 に減らすことができます。比較すると、AlphaTensor によって発見されたアルゴリズムは、次の図に示すように、わずか 76 回の乗算を使用して同じ演算を実行します。

上記の例に加えて、AlphaTensor によって発見されたアルゴリズムは、有限体における Strassen の 2 次アルゴリズムも改良しています。初めてのアルゴリズム。小さな行列を乗算するためのこれらのアルゴリズムは、任意のサイズのより大きな行列を乗算するためのプリミティブとして使用できます。

AlphaTensor は、各サイズの行列乗算アルゴリズムが数千個ある、SOTA の複雑さを備えた多様なアルゴリズムのセットも発見し、行列乗算アルゴリズムの空間がこれまで考えられていたよりも大きいことを示しています。

この豊かな空間のアルゴリズムには、さまざまな数学的および実用的な特性があります。この多様性を利用して、DeepMind は、特定のハードウェア (Nvidia V100 GPU、Google TPU v2 など) で高速に実行されるアルゴリズムを特に検出するように AlphaTensor を調整しました。これらのアルゴリズムは、同じハードウェア上で一般的に使用されるアルゴリズムよりも 10 ～ 20% 高速に大規模な行列乗算を実行し、任意の目的を最適化する際の AlphaTensor の柔軟性を示しています。

#AlphaTensor には、アルゴリズム ランタイムに対応するターゲットがあります。正しい行列乗算アルゴリズムが見つかると、指定されたハードウェアでベンチマークが実行され、指定されたハードウェアでより効率的なアルゴリズムを学習するために AlphaTensor にフィードバックされます。

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

数学的観点から見ると、DeepMind の結果は、計算問題を解決するための最速のアルゴリズムを特定することを目的とした複雑性理論の指針となる可能性があります。 AlphaTensor は、可能なアルゴリズムの空間を以前の方法よりも効率的に探索することで、行列乗算アルゴリズムの豊富さについての理解を深めるのに役立ちます。

さらに、行列乗算はコンピューター グラフィックス、デジタル通信、ニューラル ネットワーク トレーニング、科学計算などの多くのコンピューティング タスクの中核コンポーネントであるため、AlphaTensor によって発見されたアルゴリズムはこれらのタスクを大幅に改善できます。フィールド、計算効率。

この記事では行列の乗算という特定の問題のみに焦点を当てていますが、DeepMind は、より多くの人々に AI を使用して他の基本的なコンピューティング タスクのアルゴリズム発見をガイドするよう促したいと考えています。さらに、DeepMind の研究は、AlphaZero の強力なアルゴリズムが従来のゲームの領域をはるかに超えており、数学分野の未解決の問題の解決に役立つことも示しています。

DeepMind は、研究に基づいて、将来的には人工知能をさらに活用して、社会が数学と科学における最も重要な課題のいくつかを解決できるようにしたいと考えています。

以上が強化学習で行列乗算アルゴリズムを発見、DeepMind が Nature の表紙を飾り、AlphaTensor を発売の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。