DeepMind は衝撃的な並べ替えアルゴリズムを開始し、C++ ライブラリは更新に追われています。

#クリックして 51CTO Web サイトのコンテンツに関するアンケートにご参加ください

コンパイル | Wang Ruiping、Yan Zheng

AlphaGo にもう 1 人の「弟」が加わりました!

Google DeepMind は、Alpha シリーズを並べ替えアルゴリズムに「組み込んで」、AlphaDev を開始しました。

これはいわば「開発秘法」のようなもので、強化学習AIを用いてソートアルゴリズムやハッシュアルゴリズムを発見することで、人間のプログラマーが設計したアルゴリズムを強制的にそれぞれ約70％、約30％高速化するというものです。

研究結果が発表されると、すぐにソフトウェア サークルに火がつきました。突然、世界中の何百万ものソフトウェアの実行速度が急上昇し、数十年間の科学者やエンジニアの成果を直接上回り、10年間更新されていなかったLLVM標準Cライブラリが更新されました。

(出典: Nature)

これも、Google の 2 つの AI 部門の合併後に発売された破壊的テクノロジーです。この論文は、「深層強化学習を使用して発見された高速ソートアルゴリズム」というタイトルでNatureに掲載されました。この論文の筆頭著者は、DeepMind のコンピュータ科学者である Daniel Mankowitz です。

1. 進化: ソート アルゴリズムの起源

ソートは、多くの項目を特定の順序 (たとえば、アルファベット順に 3 文字、大きいものから小さいものへ) で整理する方法です。数値を入力したり、数百万のレコードを含むデータベースを並べ替えたりできます。

注文方法は 2 世紀から 3 世紀まで遡ることができ、現在も進化しています。当初、学者たちはアレクサンドリア図書館の本棚にある数千冊の本をアルファベット順に手作業で並べ替えていました。

産業革命後、1890 年の米国国勢調査の結果を収集するために、パンチカードに情報を保存する集計機である自己分類機が発明されました。

1950 年代に商用コンピューターが台頭し始め、すぐに並べ替えアルゴリズムが作成されました。ソートされていない数値をソート アルゴリズムに入力すると、ソートされた一連の数値が生成されます。

現在、大量のデータを処理するために、さまざまな並べ替え手法やアルゴリズムがあらゆるコード ベースで依然として使用されています。

#数十年にわたる研究開発の後、これらの並べ替えアルゴリズムの効率は向上し続け、コンピューター科学者やプログラマーによって認められました。しかし、さらなる改善には大きな課題が残されています。

2. ハイライト: AlphaDev を使用して新しい並べ替えアルゴリズムを生成する方法?

研究者たちは当初、特定のタスクを効率的に完了することを目的として、AlphaDev を使用して新しいアルゴリズムを生成しました。

AlphaDev はまったく新しいアルゴリズムを構築しており、以前のアルゴリズムに基づいて開発されたものではないため、オリジナルとみなすことができます。その過程で、アセンブリコードの中間言語が適用されます。 AlphaDev を使用すると、言語がコンピューターのバイナリ命令に近いため、効率的なアルゴリズムの作成が容易になります。

具体的には、AlphaDev は毎回命令を生成し、その出力が正しいかどうかをテストし、最短のアルゴリズムを生成するための要件をモデルに設定します。

並べ替えアルゴリズムの再設計を求められたとき、AlphaDev は、既存のアルゴリズムより 70% 高速で、同時に 5 つのデータを並べ替えることができる新しい並べ替えアルゴリズムをランダムに生成しました。また、250,000 データを並べ替える場合、最良のアルゴリズムよりも 1.7% 高速でした。

並べ替えアルゴリズムはさまざまな一般的なソフトウェアで広く使用されているため、この革新は世界的なアルゴリズムに大きな影響を与えるでしょう。 DeepMind はそれらをオープンソース化し、Libc 標準ライブラリに統合しました。

DeepMind の研究者によると、「命令の組み合わせが多数あるため、一見単純な研究プロセスは非常に困難です。」

3. 起源: ゲームをプレイしながら最適なアルゴリズムを見つける

さらに、AlphaDev は、AlphaZero の構造に基づいて設計された、より高度なモデルです。 AlphaZero は、以前は DeepMind の強化学習モデルであり、囲碁、チェス、その他のチェス ゲームで世界チャンピオンを破りました。

この実験を通じて、新しいモデル AlphaDev は、ゲームのプレイから科学的問題の解決へ、そして実験シミュレーションから現実世界のアプリケーションへの移行において、独自の利点を発揮します。

研究者らは、AlphaDev が新しいアルゴリズムを発見できるように訓練するために、シングルプレイヤーの「組み立てゲーム」として並べ替えをシミュレートしました。ゲームの各ターン中、AlphaDev は生成されたアルゴリズムと CPU に含まれる情報を観察し、各手を実行するためにアルゴリズムに追加する命令を選択します。

論文では、AlphaDev がソート可能なアルゴリズムを取得するために、考えられる多数の命令の組み合わせを効率的に検索できなければならないため、アセンブリ ゲームが非常に難しいと述べています。

命令の組み合わせの数は、宇宙内の粒子の数、またはチェス (10120 ゲーム) や囲碁 (10700 ゲーム) で考えられる手の組み合わせの数に似ています。間違った手ごとに、アルゴリズム全体が無効になります。

モデルはアルゴリズムを出力し、それを予想される出力と比較し、アルゴリズムの正確さと待ち時間に基づいてエージェントに報酬を与えます。

アルゴリズムを構築するとき、命令が入力されるたびに、AlphaDev は出力アルゴリズムと期待される結果を比較して正確さをチェックします (並べ替えアルゴリズムの場合、これは、順序付けされていない数値を入力した後、正しく並べ替えられて出力できることを意味します)数字）。

モデルは、数値の正しい順序と効率に対して AlphaDev に報酬を与えます。最終的に、より正確で高速なプログラムを発見した AlphaDev が競争に勝ちました。

4. アルゴリズムの革新: スワップ移動およびコピー移動命令シーケンス

AlphaDev は、より高速なアルゴリズムを生成するだけでなく、2 つの命令シーケンスも革新します。

具体的には、生成されるソート アルゴリズムには、スワップ移動とコピー移動という 2 つの新しい命令シーケンスが含まれており、使用されるたびに 1 つの命令が保存されます。研究者らはこれを「AlphaDevのスワップ移動とコピー移動」と呼んでいる。

この斬新なアプローチは、見物人に衝撃を与え、チェスの伝説を生み出した「直感に反する」チェスのプレイである AlphaGo の「手 37」を彷彿とさせます。

移動命令シーケンスとコピー移動命令シーケンスを交換することにより、AlphaDev はステップをスキップし、間違いのように見えても実際には近道である方法で目標を完了します。これは、AlphaDev には初期の解決策を発見し、コンピューター サイエンス アルゴリズムの改善を試みる能力があることを意味します。

5. テスト: ハッシュ アルゴリズムの推進と改善

研究者は、より高速な並べ替えアルゴリズムを発見した後、それを別のコンピューター サイエンス アルゴリズムであるハッシュ アルゴリズムに適用しようとしました。

ハッシュ アルゴリズムはコンピューティングの基本アルゴリズムであり、データの取得、保存、圧縮に使用されます。図書館員が分類システムを使用して特定の本を見つけるのと同じように、ハッシュ アルゴリズムは、ユーザーが探しているものとその場所を知るのに役立ちます。

これらのアルゴリズムは、特定のキー (ユーザー名「Jane Doe」など) のデータを取得してハッシュし、生データを一意の文字列 (1234ghty など) に変換できます。

コンピュータは、すべてのデータを検索するのではなく、このハッシュを使用して、キーに関連するデータを迅速に取得します。

研究者たちは、より高速なアルゴリズムを発見するために、データ構造で最も一般的に使用されるハッシュ アルゴリズムの 1 つに AlphaDev を適用しました。ハッシュ関数の 9 ～ 16 バイト範囲に適用すると、AlphaDev は 30% 高速なアルゴリズムを生成しました。

今年初め、AlphaDev によって生成された新しいハッシュ アルゴリズムがオープン ソースの Abseil ライブラリにリリースされ、世界中の何百万人もの開発者が利用できるようになりました。現在では毎日数万人が使用していると推定されています. 億回。

6. 勢いを増す: AGI 開発の第一歩を踏み出す

「ソートおよびハッシュ アルゴリズム」を最適化することで、AlphaDev は、さまざまな実用的な新しいアルゴリズムを生成できることを実証しました。

これは、AlphaDev による汎用人工知能 (AGI) ツールの開発に向けた最初のステップでもあり、同様の AI ツールは、コンピューティング エコシステム全体の最適化や、社会に利益をもたらす他の問題の解決にも役立ちます。

低レベルアセンブリ命令空間の最適化アルゴリズムは非常に強力ですが、制限もあります。現在、チームは、開発者にとってより有益となる、高級言語 (C など) でアルゴリズムを最適化する AlphaDev の機能を研究しています。

つまり、これらの新しい発見が、開発者に新しいテクノロジと手法を作成し、基本的なアルゴリズムをさらに最適化し、より強力で持続可能なコンピューティング エコシステムを構築するよう促すことが期待されています。

7. オープンソース: AI 最適化コードにおける画期的な画期的な進歩

以前は、並べ替えアルゴリズムは毎日何兆回も使用されていました。コンピューティングのニーズの増大に伴い、アルゴリズムに対するパフォーマンスの要求もますます高くなっています。人間のエンジニアはさまざまな並べ替えアルゴリズムを発見しましたが、数十年にわたる最適化の後、画期的な進歩を遂げることは難しく、増大する需要に応えることができません。

今回、AlphaDev は、データを並べ替えるためのより高速な並べ替えアルゴリズムを発見しました。

新しいランキング アルゴリズムは、オンライン検索結果やソーシャル投稿をランク付けしたり、コンピューターや携帯電話上のデータを処理したりするために使用できます。

新しい並べ替えアルゴリズムがメインの C ライブラリでオープンソース化されたことは祝う価値があります。現在、世界中の何百万もの開発者や企業がクラウド コンピューティング、オンライン ショッピング、サプライ チェーン管理などに使用しています。

つまり、人工知能ツールを使用してアルゴリズムを最適化すると、従来のプログラミング方法が完全に変わります。並べ替えライブラリが変更されるのは 10 年以上ぶりであり、強化学習モデルによって設計されたアルゴリズムが並べ替えライブラリに追加されるのは初めてであり、人工知能を使用して並べ替えを行う上で画期的な画期的な出来事となりました。コードを最適化します。

8. ユーザー: おそらくこれは単なるからくりだろう

ユーザーは研究結果についてさまざまな意見を持っており、Twitter では賞賛の声がほとんどです。 # 基本を学ぶ タスクの順序付けはプログラマーが早い段階で習得するスキルの 1 つであり、このスキルにより速度が 70% 向上します。 AI を活用して、私たち全員が依存しているアルゴリズムやライブラリが大幅に高速化されるのを見るのはとても興味深いことです。"

"もうすぐ、普通の人でも高度なプログラマーになれるようになるでしょう。"

" 興味深い手法です。 、アセンブリ レベルから最適化を開始してください!

しかし、一部のプログラマはこれが単なるギミックであると考えており、DeepMind はアルゴリズムの機能を誇張しています。

まず、効率の観点から、実際に時間計算量を変更するのではなく、アルゴリズムの遅延のみをカウントします。

さらに、他のさまざまなコード ライブラリで一般的な並べ替えも実際には変更しません。 :

1.https://www.nature.com/articles/s41586-023-06004-9

2.https://www.deepmind.com/blog/alphadev - Discovers-faster-sorting-algorithms

3.https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalized-ai-tools

4 。 https://twitter.com/demishassabis

以上がDeepMind は衝撃的な並べ替えアルゴリズムを開始し、C++ ライブラリは更新に追われています。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。