概要
数学者は優れたパズルが大好きです。 乗算行列 (数値の 18 次元の表) のような抽象的なものでさえ、最も効率的な方法を見つけようとするとゲームのように感じることがあります。 これは、ルービック キューブをできるだけ少ない手数で解こうとするようなもので、やりがいがありますが魅力的です。 ただし、ルービック キューブの場合、各ステップで可能な移動の数は 10 です。 行列の乗算では、比較的単純な場合でも、すべてのステップで XNUMX を超える値が表示されることがあります。12 オプション。
過去 50 年間、研究者はこの問題にさまざまな方法でアプローチしてきましたが、そのすべてが人間の直感に助けられたコンピューター検索に基づいています。 先月、人工知能企業 DeepMind のチームは、この問題に新しい方向から取り組む方法を示し、レポートで報告しました。 紙 in 自然 ニューラル ネットワークのトレーニングに成功し、行列乗算の新しい高速アルゴリズムを発見しました。 それはあたかも AI が途方もなく複雑なルービック キューブを解くための未知の戦略を発見したかのようでした。
「それは非常に素晴らしい結果です」と彼は言いました ジョシュアルマン、コロンビア大学のコンピューター科学者。 しかし、彼と他の行列乗算の専門家は、そのような AI 支援は、少なくとも近い将来、既存の方法を置き換えるのではなく、補完するものになるだろうと強調しました。 「これは、ブレークスルーになる可能性のある何かの概念実証のようなものです」と Alman 氏は言います。 その結果は、研究者の探求に役立つだけです。
それを証明するかのように、そのXNUMX日後、 自然 論文が発表されたとき、オーストリアの研究者のペアが、新しい方法と古い方法が互いに補完し合う方法を示しました。 彼らは、従来のコンピューター支援検索を使用して、 さらに改善する ニューラル ネットワークが発見したアルゴリズムの XNUMX つです。
結果は、ルービック キューブを解くプロセスのように、より良いアルゴリズムへの道は紆余曲折に満ちていることを示唆しています。
行列の乗算
行列の掛け算は、すべての数学で最も基本的で普遍的な操作の XNUMX つです。 のペアを乗算するには nバイn 行列、それぞれ n2 これらの要素を特定の組み合わせで乗算および加算して、製品を生成します。 nバイn マトリックス。 XNUMX を乗算するための標準的なレシピ nバイn 行列が必要 n3 たとえば、2 行 2 列の行列では XNUMX 回の乗算が必要です。
何千もの行と列を持つ大規模な行列の場合、このプロセスはすぐに面倒になります。 しかし1969年、数学者フォルカー・シュトラッセンは 手順を発見 2 ではなく 2 つの乗算ステップを使用して XNUMX 行 XNUMX 列の行列のペアを乗算しますが、より多くの加算ステップが導入されます。
Strassen のアルゴリズムは、2 行 2 列の行列のペアを乗算するだけの場合、不必要に複雑になります。 しかし、彼は、それがより大きなマトリックスでも機能することに気付きました。 これは、行列の要素自体が行列になる可能性があるためです。 たとえば、20,000 行と 20,000 列の行列は、2 つの要素がそれぞれ 2 行 10,000 行列である 10,000 行 5,000 列の行列として再考できます。 これらの各行列は、5,000 つの 2 行 2 列のブロックに分割できます。 Strassen は、彼の方法を適用して、この入れ子になった階層の各レベルで XNUMX 行 XNUMX 列の行列を乗算することができました。 行列のサイズが大きくなるにつれて、少ない乗算による節約が大きくなります。
Strassen の発見は、行列乗算の効率的なアルゴリズムの検索につながり、それ以来、XNUMX つの異なるサブフィールドに影響を与えてきました。 XNUMX つは原理の問題に焦点を当てています。 nバイn 行列とみましょう n 無限に向かって実行すると、可能な限り高速なアルゴリズムの乗算ステップの数はどのようにスケーリングされますか n？ ザ・ 現在の記録 最適なスケーリングのために、 n2.3728596、アルマンに属し、 バージニアヴァシレフスカウィリアムズ、マサチューセッツ工科大学のコンピューター科学者。 (最近の未発表 プレプリント しかし、これらのアルゴリズムは純粋に理論的な関心事であり、途方もなく大きな行列に対してのみ Strassen のような方法に勝っています。
XNUMX 番目のサブフィールドは、より小さなスケールで考えます。 Strassen の研究の直後、イスラエル系アメリカ人のコンピューター科学者 Shmuel Winograd 示されました Strassen が理論上の限界に達したこと: 2 行 2 列の行列を XNUMX 未満の乗算ステップで乗算することはできません。 しかし、他のすべての行列サイズでは、必要な乗算の最小数は未解決のままです。 また、小さな行列の高速アルゴリズムは、大きな影響を与える可能性があります。そのようなアルゴリズムを繰り返し反復すると、合理的なサイズの行列が乗算されているときに Strassen のアルゴリズムに勝る可能性があるからです。
残念ながら、可能性の数は膨大です。 3 行 3 列の行列の場合でも、「可能なアルゴリズムの数は、宇宙の原子の数を超えています」と、 アルフセイン・フォージ、DeepMind の研究者であり、新しい研究のリーダーの XNUMX 人です。
この目のくらむようなオプションのメニューに直面して、研究者は、行列の乗算をまったく異なる数学の問題のように見えるもの、つまりコンピューターが処理しやすいものに変換することで進歩を遂げました。 1 つの行列を乗算するという抽象的なタスクを、特定の種類の数学的オブジェクト (テンソルと呼ばれる数値の XNUMX 次元配列) として表すことができます。 研究者は、このテンソルを「ランク XNUMX」テンソルと呼ばれる基本コンポーネントの合計に分割できます。 これらはそれぞれ、対応する行列乗算アルゴリズムの異なるステップを表します。 つまり、効率的な乗算アルゴリズムを見つけることは、テンソル分解の項の数を最小限に抑えることになります。項が少ないほど、必要なステップが少なくなります。
このようにして、研究者は新しい発見をしました アルゴリズム 増殖する nバイn 標準よりも少ない行列を使用 n3 多くの小さな行列サイズの乗算ステップ。 しかし、標準だけでなく、小さな行列に対する Strassen のアルゴリズムよりも優れたアルゴリズムは、今まで到達できていませんでした。
ゲームオン
DeepMind チームは、テンソル分解をシングルプレイヤー ゲームに変えることで、この問題に取り組みました。 彼らは、2016 年に別の DeepMind AI である AlphaGo から派生した深層学習アルゴリズムから始めました。 ボードゲーム囲碁を学ぶ 人間のトッププレイヤーを打ち負かすのに十分です。
すべての深層学習アルゴリズムは、ニューラル ネットワークを中心に構築されています。これは、各ニューロンが次の層のニューロンにどの程度影響を与えるかを表す強さの異なる接続を持つ、層に分類された人工ニューロンのウェブです。 これらの接続の強さは、トレーニング手順を何度も繰り返して微調整されます。その間、ニューラル ネットワークは、受け取った各入力を、アルゴリズムが全体的な目標を達成するのに役立つ出力に変換することを学習します。
AlphaTensor と呼ばれる DeepMind の新しいアルゴリズムでは、入力は有効な行列乗算スキームへの道に沿ったステップを表します。 ニューラル ネットワークへの最初の入力は、元の行列乗算テンソルであり、その出力は、AlphaTensor が最初の移動に選択したランク 1 テンソルです。 アルゴリズムは、このランク 1 テンソルを初期入力から減算し、新しい入力としてネットワークにフィードバックされる更新されたテンソルを生成します。 このプロセスは、最終的に開始テンソルのすべての要素がゼロになるまで繰り返されます。つまり、取り出すランク 1 テンソルがなくなります。
その時点で、ニューラル ネットワークは有効なテンソル分解を発見しました。これは、すべてのランク 1 テンソルの合計が最初のテンソルと正確に等しいことが数学的に保証されているためです。 そして、そこにたどり着くまでにかかったステップは、対応する行列乗算アルゴリズムのステップに戻すことができます。
これがゲームです: AlphaTensor は、テンソルを一連のランク 1 コンポーネントに繰り返し分解します。 毎回、ステップ数を減らす方法を見つけた場合、AlphaTensor は報われます。 しかし、勝利への近道はまったく直感的ではありません。すべてを解決する前に、ルービック キューブで完全に並べられた面をスクランブルしなければならない場合があるのと同じです。
チームは、理論的には問題を解決できるアルゴリズムを手に入れました。 彼らは最初にそれを訓練しなければなりませんでした。
新しいパス
すべてのニューラル ネットワークと同様に、AlphaTensor はトレーニングに大量のデータを必要としますが、テンソル分解は非常に難しい問題です。 研究者がネットワークに供給できる効率的な分解の例はほとんどありませんでした。 代わりに、彼らは、ランダムに生成されたランク 1 テンソルの束を追加するという、はるかに簡単な逆問題でアルゴリズムをトレーニングすることによって、アルゴリズムの開始を支援しました。
「彼らは難しい問題のためにより多くのデータを生成するために簡単な問題を使用しています。」 マイケル・リットマン、ブラウン大学のコンピューター科学者。 この後方トレーニング手順を強化学習と組み合わせることで、AlphaTensor が効率的な分解を探し回って失敗したときに独自のトレーニング データを生成することで、いずれかのトレーニング方法単独よりもはるかにうまく機能しました。
DeepMind チームは、12 行 12 列までの行列の乗算を表すテンソルを分解するように AlphaTensor をトレーニングしました。 通常の実数の行列を乗算するための高速なアルゴリズムと、モジュロ 2 演算として知られるより制約のある設定に固有のアルゴリズムを求めました。 (これは 0 つの数のみに基づく数学であるため、行列の要素は 1 または 1 のみであり、1 + 0 = XNUMX になります。) 研究者は、ここで発見されたアルゴリズムを適用できることを期待して、このより制限された、しかしまだ広大な空間から始めることがよくあります。実数の行列を扱います。
トレーニング後、AlphaTensor は Strassen のアルゴリズムを数分以内に再発見しました。 次に、行列サイズごとに数千もの新しい高速アルゴリズムを発見しました。 これらは最もよく知られているアルゴリズムとは異なりますが、乗算ステップの数は同じでした。
いくつかのケースでは、AlphaTensor が既存の記録を打ち破ることさえありました。 その最も驚くべき発見は、2 を法とする演算で発生しました。ここでは、4 の乗算ステップで 4 行 47 列の行列を乗算する新しいアルゴリズムを発見しました。これは、Strassen のアルゴリズムの 49 回の反復に必要な 5 ステップよりも改善されています。 また、5 行 2 列の 98 を法とする行列の最もよく知られたアルゴリズムよりも優れており、必要な乗算の数を以前の記録である 96 から 91 に減らしています。 5 行 5 列の行列を使用する Strassen のアルゴリズム)。
新しい注目を集める結果は、多くの興奮を引き起こしました。 一部の研究者 AIによる現状の改善に絶賛の声が寄せられています。 しかし、行列乗算コミュニティの全員がそれほど感銘を受けたわけではありません。 「少し誇大宣伝されているように感じました」と Vassilevska Williams は言いました。 「それは別のツールです。 『ああ、コンピューターが人間を打ち負かした』というようなものではありませんよね？」
研究者はまた、記録破りの 4 行 4 列のアルゴリズムの即時の適用は限られていることを強調しました。これはモジュロ 2 演算でのみ有効であるだけでなく、実際には速度以外にも重要な考慮事項があります。
Fawzi 氏も、これはほんの始まりにすぎないことに同意しました。 「改善と研究の余地はたくさんあります。それは良いことです」と彼は言いました。
最後のひねり
十分に確立されたコンピューター検索方法に対する AlphaTensor の最大の強みは、その最大の弱点でもあります。優れたアルゴリズムがどのように見えるかについて人間の直感に制約されないため、その選択を説明できません。 そのため、研究者はその成果から学ぶことが難しくなっています。
しかし、これは見た目ほど大きな欠点ではないかもしれません。 AlphaTensor の結果の数日後、数学者は マヌエル・カウアーズ と彼の大学院生 ヤコブ・モスバウアー、オーストリアのヨハネス・ケプラー大学リンツの両方が、別の一歩前進を報告しました.
概要
DeepMind の論文が発表されたとき、Kauers と Moosbauer は、従来のコンピューター支援検索を使用して新しい乗算アルゴリズムを検索していました。 しかし、新しい指針で新たに始めるそのような検索のほとんどとは異なり、彼らの方法は、既存のアルゴリズムを繰り返し微調整して、そこからより多くの乗算の節約を絞り出すことを期待して機能します。 5 行 5 列のモジュロ 2 行列に対する AlphaTensor のアルゴリズムを出発点として採用したところ、わずか数秒の計算で乗算ステップの数が 96 から 95 に減少したことがわかり、彼らは驚きました。
AlphaTensor は、別の改善を間接的に行うのにも役立ちました。 以前、Kauers と Moosbauer は、Strassen のアルゴリズムの 4 回の反復を打ち負かすことはできないと考えて、わざわざ 4 行 47 列の行列の空間を探索することはありませんでした。 AlphaTensor の結果は彼らに再考を促し、ゼロから計算を始めて 4 週間の計算時間の後、彼らの方法は、AlphaTensor が発見したものとは無関係の別の 4 ステップのアルゴリズムを見つけました。 「誰かが XNUMX x XNUMX について何か発見すべきことがあると言っていたなら、もっと早くそれを実現できたはずです」と Kauers 氏は述べています。 「でもまあ、まあ、それが機能する方法です。」
Littman は、このような状況を、ランナーが初めて XNUMX マイルを XNUMX 分未満で完走したときのようなものだと例え、これまで不可能と考えられていた偉業を予想しています。 「人々は『待て、これならできる』と思っていましたが、今では多くの人ができるようになりました」と彼は言いました。
今後、Fawzi は、AlphaTensor を一般化して、より広範な数学的および計算タスクに取り組むことを望んでいます。これは、その祖先の AlphaGo が最終的に他のゲームに分岐したようにです。
Kauers 氏は、これを、機械学習を新しいアルゴリズムの発見に適用するための真のリトマス試験紙と見なしています。 彼は、高速な行列乗算アルゴリズムの探求は、人間の支援の有無にかかわらず、コンピューター検索が適している組み合わせ問題であると指摘しています。 しかし、すべての数学の問題を簡単に特定できるわけではありません。 機械学習が質的に新しいアルゴリズムのアイデアを発見できれば、「これはゲームチェンジャーになるでしょう」と彼は言いました。
