当時のAlphaGoの魔法のタッチを再現！ DeepMindの新AIが70%高速化したソートアルゴリズムを発見、10年間更新されていなかったC++ライブラリが更新

DeepMind が再び Nature に登場し、大ヒットを記録しました!

今回、彼らは再び学習 AI を強化し、コンピューター分野で最も基本的な 2 つのアルゴリズムで新たなブレークスルーを達成しました。

1 つはソート アルゴリズムで、最も高速な改善が見出されています 70 % 新しい実装;

もう 1 つはハッシュ アルゴリズムで、これも速度を 30% 向上させる新しい方法を発見しました。

それだけではなく、AIが使用した手法は「AlphaGoのマジックタッチを再現する」というもので、違法と思われますが、その時は人間のマスター、イ・セドルとの対戦でした。

このニュースが出るやいなや、学界はたちまち爆発し、一部のネチズンは次のように叫びました:

このような古くからある基本的なアルゴリズムがさらに発展するとは予想していませんでした改善されました。

今回の成果があったからこそ、10年間も更新されていなかったLLVM標準Cライブラリが、更新されれば、何十億人もの人々が恩恵を受けることになります。

なぜなら、ソートであろうとハッシュであろうと、そのアプリケーション シナリオはオンライン ショッピング、クラウド コンピューティングからサプライ チェーン管理などに至るまで、さまざまなシナリオで使用でき、毎日何億回も呼び出されるからです。

ただし、DeepMind が述べているように、

あまり興奮しないでください。AI の力は、コード効率を向上させるために利用され始めたばかりです。

Alpha ファミリーの「成り上がり」が、より高速な並べ替えアルゴリズムを発見しました

この AI は AlphaDev と呼ばれ、 Alpha ファミリーの「成り上がり」であり、AlphaZero (2017 年に世界チャンピオンを破ったチェス AI) に基づいて構築されています。

その発見は既存のアルゴリズムに基づいておらず、最下位レベルのアセンブリ命令から始まります。

DeepMind の研究者は、そのためにシングルプレイヤーの「アセンブリ」ゲームを設計しました。

適切な命令 (下図のプロセス A) を検索して選択できる限り、それはデータを整理することで報酬を得ることができます（下図の処理B）。

しかし、このゲームの課題は、探索空間のサイズだけではありません (組み合わせ可能な命令の数は、その数に相当します)宇宙の粒子の数）だけでなく、1 つの間違った命令がアルゴリズム全体の失敗を引き起こす可能性があるため、報酬関数の性質にも依存します。

AlphaDev には、学習アルゴリズムと表現関数という 2 つのコア コンポーネントがあります。

その中で、学習アルゴリズムは主に強力な AlphaZero を基に拡張されており、DRL とランダム検索最適化アルゴリズムを組み合わせて大量の命令検索を実行でき、主な表現機能は Transformer に基づいており、アセンブリ プログラムの基礎となる構造であり、特別なシーケンスとして表現されます。

AlphaDev がモンスターとの戦いとアップグレードを続けるにつれて、研究者は実行できるステップ数と並べ替えられるシーケンスの長さも制限する予定です。

最終的に、AlphaDev は新しい並べ替えアルゴリズムを発見しました:

シーケンスが短い場合、人間のベースライン並べ替えアルゴリズムと比較して速度を 70% 向上させることができます。シーケンスの長さが 25,000 要素を超えると、増加率は 1.7% になります。

短いシーケンスの並べ替えは、特に大規模な並べ替え関数の重要なコンポーネントとして実際に広く使用されており、何度も呼び出されます。短いシーケンスが改善される限り、すべてのシーケンスのソート速度を向上させることができます。 )

具体的には、このアルゴリズムの革新性は主に 2 つの命令シーケンスにあります。

(1) AlphaDev Swap Move (交換移動)
(2) AlphaDev Copy Move (コピー移動) )

下の図に示すように、左側は min(A,B,C) を使用した元の sort3 実装であり、右側は min のみを必要とする「AlphaDev Swap Move」の実装です。 (A、B)。命令の 1 ステップを省略でき、A と B の最小値のみを計算する必要があることがわかります。

著者は、この斬新な手法は、伝説の囲碁棋士イ・セドルを直接破り、聴衆に衝撃を与えた直感に反する手、AlphaGoの「手37」を彷彿とさせると述べた。

同様に、AlphaDev は動きを交換してコピーすることでステップをスキップし、間違っているように見えても実際には近道となる方法で目標を達成します。

下図に示すように、8 要素をソートするアルゴリズムでは、AlphaDev も「AlphaDev Copy Move」を使用して、元の実装の変更を max (B, min (A, C)) に置き換えます。は複雑な max (B, min (A, C, D)) 命令であり、アルゴリズム全体の命令の総数も 1 ステップ削減されます。

作者は、より高速な並べ替えアルゴリズムを発見した後、その汎用性を証明するために、AlphaDev でハッシュ アルゴリズムも試しました。

結果は期待を裏切りませんでした。AlphaDev は、9 ～ 16 バイトの長さの範囲で 30% の速度向上も達成しました。

並べ替えアルゴリズムと同様に、彼らは新しいメソッドを Abseil ライブラリに統合し、現在世界中の何百万もの開発者が利用できるようにしています。

最後に、著者は、2 つの新しいアルゴリズムの実装は、AlphaDev が独自のソリューションを発見する強力な能力を持っていることを示しており、コンピューター分野の基本的なアルゴリズムを改善する方法についてさらに考えさせるだろうと述べました。

ただし、この研究で使用されているアセンブリ言語には制限があるため、彼らは次に、高級言語 (C など) でアルゴリズムを最適化する AlphaDev の機能を試す予定です。

ネチズン: 新しい並べ替えアルゴリズムの発見は考慮に入れません

多くの人がこの成果について大きな興奮を表明しました。

このネチズンは次のように述べています:

AlphaGo が世界を驚かせた後、強化学習で他に何ができるでしょうか?実用的に重要なことは何かできるでしょうか？これが答えです。

しかし今回、DeepMindがタイトルを誇張している疑いがあると多くの人が指摘した。

従来の意味での時間計算量ではなく、アルゴリズムの遅延を計算します。実際に時間計算量を計算すると、データの見た目が良くなくなる可能性があります。

その改善はソート アルゴリズムそのものではなく、最新の CPU 向けの新しいソート最適化 (特に短いシーケンス) にあります。この手法は実は非常に一般的で、例えばFFTWやATLASなどのライブラリでもこの手法が採用されています。

同意します。彼らは特定の CPU に対するより高速なマシンの最適化を発見しただけであり、新しい並べ替えアルゴリズムや方法自体ではありませんでした。素晴らしいですが、まだ画期的な研究ではありません。 ＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃どう思いますか？

論文アドレス:

https://www.php.cn/link/a3fefe83288ecb0e40ebe40b2bde29fe

公式ブログ:

https://www.php.cn/link/f5b2aa928f940f3f09a0d14f45a27875

参考リンク:

[1]https://www.php.cn/link/5383c7318a3158b9bc261d0b6996f7c2
[2]https:// www.php.cn/link/ecf9902e0f61677c8de25ae60b654669

[3]

https://www.php.cn/link/0383314bf626052313b8275638fcccce

以上が当時のAlphaGoの魔法のタッチを再現！ DeepMindの新AIが70%高速化したソートアルゴリズムを発見、10年間更新されていなかったC++ライブラリが更新の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。