Google は AI を使用して 10 年間にわたるランキング アルゴリズムの封印を破りました。このアルゴリズムは毎日何兆回も実行されていますが、ネチズンはこれが最も非現実的な研究だと主張していますか?

アレンジメント | ヌカ・コーラ、チュー・シンジュアン

基本的なコンピューター サイエンスのコースを受講した友人は、ソート アルゴリズムを個人的に設計したはずです。つまり、コードを使用して、順序なしリスト内の項目を昇順または降順に並べ替えます。これは興味深い挑戦であり、実現する方法はたくさんあります。並べ替えタスクをより効率的に実行する方法を見つけるために、多くの時間が費やされてきました。

基本的な操作として、ほとんどのプログラミング言語には標準ライブラリに並べ替えアルゴリズムが組み込まれています。オンラインで大量のデータを整理するために、世界中のコードベースでさまざまなソート手法やアルゴリズムが使用されていますが、少なくとも LLVM コンパイラで使用される C ライブラリに関する限り、ソート コードは 10 年以上変わっていません。 。

最近、Google の DeepMind AI チームは、人間のコード例による事前トレーニングを必要とせずに、極めて最適化されたアルゴリズムを開発できる強化学習ツール AlphaDev を開発しました。現在、これらのアルゴリズムは LLVM 標準 C 並べ替えライブラリに統合されており、並べ替えライブラリのこの部分が変更されたのは 10 年以上で初めてであり、強化学習を使用して設計されたアルゴリズムがライブラリに追加されたのは初めてです。 。

プログラミングプロセスを「ゲーム」として考えてみましょう

DeepMind システムは、人間のゲーム戦略に事前に触れる必要がないため、人間が思いつかなかった問題の解決策を発見できることがよくあります。 DeepMind は経験から学習する際に完全に自己対決に依存しているため、人間によって悪用される可能性のある盲点が存在することがあります。

この方法は実際にはプログラミングに非常に似ています。大規模な言語モデルは、人間のコードの例を数多く見てきたため、効率的なコードを書くことができます。しかしこのため、言語モデルが人間がこれまでにやったことのないものを生み出すことは困難です。ユビキタスな既存のアルゴリズム (ソート関数など) をさらに最適化したい場合、既存の人間のコードに依存し続けることによって、固有のアイデアの制約を突破することは困難になります。では、AI はどのようにして真に新しい方向性を見つけることができるのでしょうか?

DeepMind の研究者は、チェスや囲碁に似た方法を使用してコード タスクを最適化し、コード タスクをシングル プレイヤーの「ジグソーパズル」に変えました。 AlphaDev Systems は、コードの実行遅延をスコアとして扱い、コードがスムーズに実行できるようにしながらスコアを最小限に抑えるよう努める x86 アセンブリ アルゴリズムを開発しました。 AlphaDev は、強化学習の応用により、効率的で簡潔なコードを書く技術を徐々に習得してきました。

AlphaDev は AlphaZero に基づいています。 DeepMindは、ゲームのルールを自ら学習できるAIソフトウェアの開発で有名です。この考え方は非常に効果的であることが証明されており、チェス、囲碁、「スタークラフト」などの多くのゲームの問題を解決することに成功しています。詳細はプレイするゲームによって異なりますが、DeepMind のソフトウェアは繰り返しプレイすることで学習し、スコアを最大化する方法を継続的に模索します。

AlphaDev の 2 つのコア コンポーネントは、学習アルゴリズムと表現関数です。

DRL とランダム検索最適化アルゴリズムを組み合わせてゲームを組み立てるのは、AlphaDev 学習アルゴリズムの 1 つの方法です。 AlphaDev の主な学習アルゴリズムは、ゲーム全体の検索をガイドするためにニューラル ネットワークがトレーニングされるよく知られた DRL アルゴリズムである AlphaZero 33 の拡張です。

この関数は、コード開発中の全体的なパフォーマンスを監視するために使用され、アルゴリズムの一般的な構造と x86 レジスタおよびメモリの使用をカバーします。システムには、ゲーム システムから借用したモンテカルロ ツリー検索方法を使用して選択を行うときに独立して追加されるアセンブリ命令が徐々に導入されます。ツリー構造により、システムは多数の潜在的な命令を含む限られた領域に検索を迅速に絞り込むことができますが、モンテカルロ法ではこの分岐領域からある程度のランダム性で特定の命令を選択します。ここでいう「命令」とは、有効で完全なアセンブリを作成するための特定のレジスタの選択などの操作であることに注意してください。 )

その後、システムはアセンブリ コードの待ち時間と有効性ステータスを評価し、スコアを与え、以前のスコアと比較します。強化学習を通じて、システムは特定のプログラム状態のツリー構造内のさまざまなブランチの作業情報を記録できます。時間が経つにつれて、システムは最高のスコア (最小の遅延を表す) でゲームに勝つ (ソートの成功) 方法に慣れてきます。 AlphaDev の主な表現機能はトランスフォーマーに基づいています。

AlphaDev をトレーニングして新しいアルゴリズムを発見するために、AlphaDev は各ラウンドで生成するアルゴリズムと中央処理装置 (CPU) に含まれる情報を観察し、アルゴリズムに追加する命令を選択してゲームを完了します。 AlphaDev は、多数の考えられる命令の組み合わせを効率的に検索して、順序付けが可能で、現在最適なアルゴリズムよりも高速なアルゴリズムを見つける必要があります。一方、エージェント モデルには、アルゴリズムの正確さと遅延に基づいて報酬を与えることができます。

写真A:組み立てゲーム、写真B:報酬計算

最後に、AlphaDev は、LLVM libc ソート ライブラリを改善できる新しいソート アルゴリズムを発見しました。短いシーケンスでは、ソート ライブラリは 70% 高速になり、250,000 要素を超えるシーケンスでは、速度が約 1.7% 向上しました。

具体的には、このアルゴリズムの革新性は主に、AlphaDev Swap Move (スワップ移動) と AlphaDev Copy Move (コピー移動) の 2 つの命令シーケンスにあり、これら 2 つの命令により、AlphaDev はステップをスキップしてアイテムを接続する方法を実行します。それは間違っているように思えるかもしれませんが、実際には近道です。

左: min(A,B,C) を使用した元の sort3 実装。 ‍

右の図: AlphaDev Swap Move - AlphaDev は、min(A,B) のみが必要であることを発見します。

左: 8 つの要素を並べ替える大規模な並べ替えアルゴリズム用の max (B, min (A, C)) の元の実装。

‍右: AlphaDev は、コピー移動を使用する場合、最大 (B, 最小 (A, C)) のみが必要であることを発見しました。

このシステムの主な利点は、トレーニング プロセスにコード サンプルが必要ないことです。代わりに、システムはコード例を自律的に生成し、それらを評価します。その過程で、命令の組み合わせの効果的な順序付けに関する情報を徐々に習得します。

ソートからハッシュ化へ

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

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

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

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

実際に使えるコード

複雑なプログラムの並べ替えメカニズムは、任意のエントリの大規模なコレクションを処理できます。ただし、標準ライブラリ レベルでは、この機能は高度に制限された一連の特定の関数から提供されます。これらの各関数は、1 つまたは少数の状況のみを処理できます。たとえば、一部の個別のアルゴリズムでは、3、4、または 5 つのエントリしか並べ替えることができません。一連の関数を使用して任意の数のエントリを並べ替えることができますが、関数呼び出しごとに並べ替えできるエントリは最大 4 つまでです。

AlphaDevはDeepMindにより各機能が実装されていますが、実際の動作方法は大きく異なります。特定の数のエントリを処理する関数を処理する、つまり変数の状態に応じて異なるコードを実行する、分岐ステートメントを使用しないコードを作成することが可能です。したがって、コードのパフォーマンスは、関係する命令の数に反比例する傾向があります。

AlphaDev は、sort-3、sort-5、sort-8 で命令数を 1 つずつ減らすことに成功し、sort-6 と sort-7 ではさらに多くの命令数を減らすことに成功しました。既存のコードを改善する方法は、sort-4 でのみ見つかりました。実際のシステムでテストを繰り返すと、命令数を減らすとパフォーマンスが向上することがわかりました。

可変数のエントリを並べ替えるには、コードに分岐ステートメントを含める必要があります。プロセッサごとに、これらの分岐の処理専用のコンポーネントの数も異なります。

研究者らは、このシナリオを評価する際に 100 台の異なるコンピューティング デバイスを使用しました。 AlphaDev は、そのようなシナリオでパフォーマンスをさらに絞り込む方法も見つけました。例として、一度に最大 4 つのアイテムを並べ替える関数を取り上げて、その動作を見てみましょう。

C ライブラリの現在の実装では、コードは一連のテストを実行して並べ替える必要があるエントリの数を確認し、エントリの数に基づいて対応する並べ替え関数を呼び出す必要があります。

AlphaDev の修正されたコードは、より「魔法の」アイデアを採用しています。まず、エントリが 2 つあるかどうかをテストし、エントリが 2 つある場合は、対応する関数を呼び出してすぐにソートします。数値が 2 より大きい場合、コードは最初の 3 つのエントリを最初に並べ替えます。このようにして、実際にエントリが 3 つしかない場合、並べ替えられた結果が返されます。実際には並べ替える項目が 4 つあるため、AlphaDev は特殊なコードを実行して、非常に効率的に並べ替えられた最初の 3 つの項目の適切な位置に 4 番目の項目を挿入します。

このアプローチは少し奇妙に聞こえますが、そのパフォーマンスは常に既存のコードよりも優れていることがわかります。

AlphaDev はより効率的なコードを生成するため、研究チームはこれらの結果を LLVM 標準 C ライブラリに再マージする予定です。しかし問題は、コードが C ではなくアセンブリ形式であることです。したがって、同じアセンブリを生成する C コードを見つけるには、逆方向に作業する必要があります。

この文のリライト版: コードのこの部分は LLVM ツールチェーンに統合され、ほぼ 10 年ぶりに更新されました。研究者らは、AlphaDev によって生成された新しいコードが毎日何兆回も実行されると推定しています。

＃＃＃結論＃＃＃ ＃＃＃これは素晴らしい！私たちプログラマーは、この基本的な並べ替えタスクをずっと前に学びましたが、今では 70% 速くなりました。大幅な高速化を実現するために私たち全員が依存しているアルゴリズムとライブラリにおける AI には、非常に興味深い点があります。 「一部の開発者は、Google DeepMind の結果に興奮を表明しました。

しかし、一部の開発者はこれを購入しませんでした。「かなり残念です...1.7% の改善ですか? 5 つの要素のシーケンスの 70% ですか? おそらく最も不人気で最も非現実的な応用研究でしょう...」と開発者もいます。 : 「新しいアルゴリズムが発見されたと言うのは、少し誤解を招きませんか? アルゴリズムの最適化に近いように思えます。とにかく、それでもクールです。」

参考リンク:

https://arstechnica.com/science/2023/06/googles-deepmind-develops-a-system-that-writes-efficient-algorithms/

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

深さ: なぜ中国のデータベース分野では Snowflake のような巨人が現れなかったのでしょうか?

17年間で最も奇妙な崩壊！ OpenAI と Google が無料でデータを取得するのを阻止するために、Reddit は巨額の API 料金を請求し、開発者を中傷し、コミュニティで大規模な抗議活動を引き起こしました

会社を設立するためのコードを「盗み」、学歴を偽り、6 日間で 1 億ドルを稼いだのに賃金を支払わなかったこの AI ユニコーン CEO は、繰り返し質問された後、個人的に回答しました

以上がGoogle は AI を使用して 10 年間にわたるランキング アルゴリズムの封印を破りました。このアルゴリズムは毎日何兆回も実行されていますが、ネチズンはこれが最も非現実的な研究だと主張していますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。