AI がソート アルゴリズムを書き換え、70% 高速化: DeepMind AlphaDev がコンピューティング基盤を革新し、毎日何兆ものライブラリ更新を呼び出します

「スワップとコピー移動により、AlphaDev はステップをスキップし、間違っているように見える方法でアイテムを接続しますが、実際にはショートカットです。」 この前例のない直感に反する考えは、私に春を思い出させます。 2016年。

7 年前、AlphaGo は囲碁で人間の世界チャンピオンを破りました。そして今、AI は私たちにプログラミングの新たな教訓を与えてくれました。

今朝早く、Google DeepMind CEO の Hassabis 氏からの 2 つの文がコンピュータ分野に衝撃を与えました。「AlphaDev は新しくて高速なソート アルゴリズムを発見し、それをメインの C ライブラリにオープンソース化しました」開発者が使用できるようにします。これは、コード効率の向上における AI の進歩の始まりにすぎません。」

今回は、Google DeepMindの新しい強化学習システムAlphaDevは、コンピュータサイエンス分野の基本アルゴリズムである、これまでよりも高速なハッシュアルゴリズムを発見し、AIの成果はLLVM標準CライブラリAbseilに組み込まれ、オープンソース化されました。

#この結果はどの程度重要ですか? 「私たちは、AlphaDev が発見したソートとハッシュのアルゴリズムが、世界中で毎日何兆回も呼び出されていると推定しています」と、AlphaDev の主著者の 1 人で Google DeepMind の研究科学者であるダニエル J. マンコウィッツ氏は述べています。

#AI はアルゴリズム レベルから世界を高速化するようです。

これらのアルゴリズムは、LLVM libc ソート ライブラリを改善します。短いシーケンスの場合、ソート ライブラリは 70% 速くなります。250,000 要素を超えるシーケンスの場合、速度も 70% 速くなります。 . 約1.7％増加させることができます。 Google DeepMindによると、これはシーケンスライブラリのこの部分に対する10年以上ぶりの変更だという。現在、AI は人々がコードを書くのを助けるだけでなく、より良いコードを書くのにも役立つようです。 最新のブログで、新しいシステムの作成者が AlphaDev を詳しく紹介しました。

新しいアルゴリズムはコンピューティングの基盤を変える

デジタル社会により、コンピューティングとエネルギーへの需要が増大しています。過去 50 年間、デジタル時代は需要に応えるためにハードウェアの改良に依存してきました。しかし、マイクロチップが物理的な限界に近づくにつれて、マイクロチップ上で実行されるコードを改善することが重要になります。これは、毎日何兆回も実行されるコードに含まれるアルゴリズムにとって特に重要です。

Google DeepMind によるこの研究は、このことから生まれました。関連する論文は、「Nature」に掲載されました。AlphaDev は、強化学習を使用してアルゴリズムを発見し、アルゴリズムをさらに超えた AI システムです。科学者とエンジニアによる数十年にわたる研究の成果です。

#論文アドレス: https://www.nature.com/articles /s41586-023-06004-9

全体的に、AlphaDev はより高速な並べ替えアルゴリズムを発見しました。何十億人もの人々がこれらのアルゴリズムを毎日使用していますが、最適化の余地があることに誰も気づいていません。並べ替えアルゴリズムは、オンライン検索結果からソーシャル投稿の並べ替え、コンピューターや携帯電話でのさまざまなデータ処理に至るまで、幅広いアプリケーションで使用されており、これらすべては並べ替えアルゴリズムと切り離せません。 AI を使用してより優れたアルゴリズムを生成することは、人間がコンピューターをプログラムする方法を変え、デジタル化が進む社会に大きな影響を与えるでしょう。

主要な C ライブラリの新しい並べ替えアルゴリズムをオープンソース化することで、世界中の何百万もの開発者や企業がクラウド コンピューティング、オンライン ショッピング、およびサプライ チェーン管理。スマート アプリケーションで使用します。これは、ランキング ライブラリへの変更は 10 年以上ぶりであり、強化学習で設計されたアルゴリズムがライブラリに追加されたのは初めてです。これは、人工知能を使用して世界のコードを段階的に最適化する上での重要なマイルストーンであると考えてください。

ソートについて

ソート アルゴリズムは、特定のタスクを特定の順序で配置する方法です。たとえば、3 つの文字をアルファベット順に並べ替えたり、5 つの数字を最大から最小の順に並べたり、何百万ものレコードのデータベースを並べ替えたりできます。

このアルゴリズムは長い間存在しており、よく進化してきました。順序付けの最も初期の例の 1 つは、紀元 2 世紀から 3 世紀に遡り、学者たちがアレクサンドリア図書館の棚にある数千冊の本を手作業でアルファベット順に並べていました。産業革命の到来により、人々の分類を支援する機械が登場し、1890 年の米国国勢調査の結果を収集するために使用されたパンチカードを使用して情報を保存する集計機械が登場しました。

1950 年代の商用コンピューターの台頭により、ソートのための最も初期のコンピューター サイエンス アルゴリズムが開発され始めました。現在、大量のオンライン データを処理するために、世界中のコード ベースでさまざまな並べ替え手法やアルゴリズムが使用されています。

#並べ替えられていない一連の数値をアルゴリズムに入力し、並べ替えられた数値を出力します。

コンピューター科学者やプログラマーによる数十年の研究の後、現在の並べ替えアルゴリズムはすでに非常に効率的であるため、これ以上の改善を達成するのは困難です。電力を節約したり、数学の効率を高めたりするための新しい方法であり、これらのアルゴリズムはコンピューター サイエンスの基礎です。

新しいアルゴリズムの探索: アセンブリ命令

AlphaDev は、既存のアルゴリズムに基づくのではなく、より高速なアルゴリズムを最初から探索します。さらに、AlphaDev を使用することもできます。ほとんどの人は、コンピューターの組み立て説明書には参加しません。

アセンブリ命令を使用して、コンピューターが実行するバイナリ コードを作成できます。開発者は C などの高級言語でコードを作成しますが、それをコンピュータが理解できる「低レベル」アセンブリ命令に変換する必要があります。

Google DeepMind は、このレベルには改善の余地が多く、高レベルのプログラミング言語では検出するのが難しいと考えています。このレベルでは、コンピューターのストレージと操作がより柔軟になります。これは、速度とエネルギー使用に大きな影響を与える可能性のある改善の可能性がより高いことを意味します。

# コードは通常、C などの高級プログラミング言語で記述されます。次に、コンパイラはこれをアセンブリ命令と呼ばれる低レベルの CPU 命令に変換します。アセンブラは、コンピュータが実行できるように、アセンブリ命令を実行可能なマシンコードに変換します。

#図 A: 最大 2 つの要素をソートできる C アルゴリズムの例; 図 B : 対応するアセンブリ表現。

AlphaGo のメソッドを使用して最適なアルゴリズムを見つける

AlphaDev は、囲碁、チェス、チェスなどのゲームに勝つという、Google DeepMind の以前の成果に基づいています。世界チャンピオンの強化学習モデル AlphaZero。そして、AlphaDev は、このモデルがゲームから科学的課題に、そしてシミュレーションから現実世界のアプリケーションにどのように移行するかを示します。

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

AlphaDev は、考えられる多数の命令の組み合わせを効率的に検索して、ソート可能で現在最適なアルゴリズムより高速なアルゴリズムを見つける必要があるため、アセンブリ ゲームは非常に困難です。命令の可能な組み合わせの数は、宇宙の粒子の数、またはチェス (10^120 ゲーム) や囲碁 (10^700 ゲーム) で可能な手の組み合わせの数に似ており、1 つの間違った手を間違えるとダウンしてしまう可能性があります。アルゴリズム全体。

# 図 A: 組み立てゲーム。プレーヤー AlphaDev は、システム st の状態を入力として受け取り、現在生成されているアルゴリズムに追加するアセンブリ命令を選択することによってチェスをプレイします。図B: 報酬の計算。各移動の後、結果のアルゴリズムにテスト入力シーケンスが供給されます。sort3 の場合、これは 3 つの要素シーケンスのすべての組み合わせに対応します。次に、アルゴリズムは、ソート状況に応じてソートされたシーケンスの予想される出力と比較される出力を生成します。エージェントは、アルゴリズムの正確さと待ち時間に基づいて報酬を受け取ります。

#アルゴリズムを構築するとき、一度に 1 命令ずつ、AlphaDev はアルゴリズムの出力を期待される結果と比較することによって、その出力が正しいかどうかをチェックします。並べ替えアルゴリズムの場合、これは、順序付けされていない数値が入力され、正しく並べ替えられた数値が出力されることを意味します。チームは、数字を正しく並べ替えることと、並べ替えの速度と効率に対して AlphaDev に報酬を与え、AlphaDev が正しくより高速なプログラムを発見してゲームに勝ちます。

より高速な並べ替えアルゴリズムを発見しました

AlphaDev は、LLVM libc 並べ替えライブラリを改善する新しい並べ替えアルゴリズムを発見しました: シーケンス ライブラリは 70短いシーケンスでは % 高速になり、250,000 要素を超えるシーケンスでは約 1.7% 高速になります。

# その中で、Google DeepMind チームは、3 ～ 5 要素の短いシーケンスの並べ替えアルゴリズムの改善に重点を置いています。これらのアルゴリズムは、大規模な並べ替え機能の一部として複数回呼び出されることが多く、これらのアルゴリズムを改善すると、任意の数の項目を並べ替える全体的な速度を向上させることができるため、最も広く使用されています。

#新しい並べ替えアルゴリズムを人々にとってより便利なものにするために、チームはアルゴリズムをリバース エンジニアリングし、最も一般的に使用される C に変換しました。開発者向け. 人気のあるプログラミング言語の 1 つ。

現在、これらのアルゴリズムは LLVM libc 標準並べ替えライブラリ (https://reviews.llvm.org/D118029) で提供されており、何百万ものユーザーによって使用されています。世界中の開発者や企業によって使用されています。

「行動を交換してコピー」神の手が再び現れる？

実際、AlphaDev はより高速なアルゴリズムを発見しただけでなく、新しいメソッドも発見しました。そのソート アルゴリズムは、適用されるたびに命令を保存する新しい命令シーケンスで構成されています。これらのアルゴリズムは毎日何兆回も使用されるため、これは明らかに大きな影響を与えます。彼らはこれらを「AlphaDev スワップおよびコピー アクション」と呼んでいます。

この斬新な手法は、AlphaGo の「ステップ 37」を彷彿とさせます。当時、この直感に反する手法は見物人を驚かせ、伝説のイ・セドル棋士の敗北につながりました。 AlphaDev はアクションを交換してコピーすることでステップをスキップし、間違いのように見えても実際にはショートカットとなる方法で項目を接続します。これは、独自のソリューションを発見し、コンピューター サイエンスのアルゴリズムを改善する方法について人間の考え方に挑戦する AlphaDev の能力を示しています。

#左の図: min (A,B,C) のオリジナルの sort3 実装、右の図: AlphaDev スワッピング動き - AlphaDev は min (A,B) だけが必要であることを発見しました。

#

左: 8 つの要素をソートするためのより大きなソート アルゴリズムで max(B,min(A,C,D)) を使用した元の実装; 右: AlphaDev Discovery のコピー アクションを使用する場合、max のみ(B, min(A, C)) は必須です。

スケーリング能力テスト:「ソート」から「ハッシュ」まで

より高速なソート アルゴリズムを発見した後、チームは AlphaDev がアルゴリズムを一般化して改善できるかどうかをテストしました。さまざまなコンピューター サイエンス アルゴリズム: ハッシュ。

ハッシュは、コンピューティングでデータの取得、保存、圧縮に使用される基本的なアルゴリズムです。図書館員が分類システムを使用して特定の本を見つけるのと同じように、ハッシュ アルゴリズムは、ユーザーが探しているものとその場所を知るのに役立ちます。これらのアルゴリズムは、特定のキー (例: ユーザー名「Jane Doe」) のデータを取得してハッシュします。これは、生データを一意の文字列 (例: 1234ghfty) に変換するプロセスです。コンピューターはこのハッシュを使用して、すべてのデータを検索するのではなく、キーに関連するデータを迅速に取得します。

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

今年、AlphaDev の新しいハッシュ アルゴリズムがオープン ソースの Abseil ライブラリにリリースされ、世界中の何百万もの開発者が利用できるようになりました。おそらく毎日、何兆回も使用されています。

オープンソース アドレス: https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

結論

Google DeepMind AlphaDev は、世界中の開発者が使用できるように改良されたソートおよびハッシュ アルゴリズムを最適化してリリースすることにより、現実世界に影響を与える新しいアルゴリズムを一般化して発見する能力を実証しています。 AlphaDev は、コンピューティング エコシステム全体を最適化し、社会の利益のためにその他の問題を解決できる汎用 AI ツールの開発に向けた一歩とみなすことができます。

低レベルのアセンブリ命令空間での最適化は非常に強力ですが、AlphaDev にはアルゴリズムが成長するにつれて依然として制限があり、チームは現在、高レベルでの直接最適化を検討しています。 C などの言語。開発者にとってより便利なアルゴリズムを最適化する機能。

AlphaDev の発見 (スワップ アクションやコピー アクションなど) は、アルゴリズムを改善できるだけでなく、新しい解決策も見つけられることを示しています。これらの発見は、研究者や開発者に、基礎となるアルゴリズムをさらに最適化して、より堅牢で持続可能なコンピューティング エコシステムを構築できるテクノロジと方法を作成するよう促す可能性があります。

以上がAI がソート アルゴリズムを書き換え、70% 高速化: DeepMind AlphaDev がコンピューティング基盤を革新し、毎日何兆ものライブラリ更新を呼び出しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。