分類方法は人類の歴史を通じて進化してきました。最古の例は 2 世紀から 3 世紀に遡り、学者たちがアレクサンドリア図書館の書架に数千冊の本を手作業でアルファベット順に並べていました。
産業革命の後、私たちは分類に役立つ機械を発明しました。パンチカードに情報を保存する集計機は、1890 年の米国国勢調査の結果を収集するために使用されました。
1950 年代の商用コンピューターの台頭により、最も初期のコンピューター サイエンスの並べ替えアルゴリズムが登場しました。
現在、オンラインで大量のデータを整理するために、世界中のコード ベースでさまざまな並べ替え手法とアルゴリズムが使用されています。
# 並べ替えアルゴリズム、つまり、並べ替えられていない一連の数値を入力し、並べ替えられた数値を出力します
#これらのアルゴリズムは、コンピューター サイエンスの基礎となっています。
今日のアルゴリズムでは、コンピューター科学者やプログラマーが数十年にわたる研究開発に投資する必要があります。
これは、既存のアルゴリズムが非常に効率的であるため、前進するたびに大きな課題となるためです。
この難易度は、電気エネルギーを節約する新しい方法を見つけるか、より効率的な数学的手法を見つけるようなものです。 新しいアルゴリズムを探しています
AlphaDev の革新的な重要性は、既存のアルゴリズムを改良するのではなく、より高速なアルゴリズムを完全にゼロから発見することです。
さらに、それは実際には、ほとんどの人間が思いつかないところ、つまりコンピューターの組み立て説明書から始まりました。
アセンブリ命令は、バイナリ コードを作成するために使用されます。開発者はコードを記述するときに C などの高級言語を使用しますが、コンピューターが理解できるようにするには、これらの高級言語を「低レベル」アセンブリ命令に変換する必要があります。
通常、C などの高級プログラミング言語を使用してコードを記述し、コンパイラーがそれを翻訳します。低レベルの CPU 命令、アセンブリ命令にも組み込まれます。次に、アセンブラはアセンブリ命令を実行可能なマシン コードに変換します。
Google DeepMind の研究者は、この下位レベルには改善の余地がたくさんあると考えており、これらの改善は可能性があります。高レベルのプログラミング言語では見つけるのが困難です。
この下位レベルでは、コンピューターはストレージと操作の両方においてより柔軟であるため、さらにいくつかの潜在的な改善が速度とエネルギーに大きな影響を与える可能性があります。
#図 A: 最大 2 つの要素をソートするための C アルゴリズム
図 B: コードに対応するアセンブリAlphaDev: AlphaZero のアセンブリ バージョン
ご存知のとおり、DeepMind の強化学習モデルは、囲碁、国際 チェスや将棋などのゲームで世界チャンピオンを繰り返し破ってきた。
そして、今回の主人公である AlphaDev は、AlphaZero をベースにしています。
AlphaDev は、コンピューターの推論と直観を組み合わせてボード ゲームの各手を選択する、その前身である AlphaZero と同様に機能します。
ただし、AlphaDev は次にどのように移動するかを選択するのではなく、どの命令を追加するかを選択します。
AlphaDev をトレーニングして新しいアルゴリズムを発見するために、DeepMind は並べ替え問題を「組み立てゲーム」に変換しました。
各ラウンドで、AlphaDev は、生成したアルゴリズムと中央処理装置 (CPU) に含まれる情報を観察し、アルゴリズムに命令を追加して行動を起こす必要があります。
そして、このアセンブリ ゲームは非常に困難です。AlphaDev は、考えられる多数の命令の組み合わせを効率的に検索して、ソート可能で現在最適なアルゴリズムよりも高速なアルゴリズムを見つける必要があるからです。
「可能なコマンドの組み合わせ」は、宇宙内の粒子の数や、チェス (10^120 ゲーム) と囲碁 (10^700 ゲーム) の可能な組み合わせと直接比較することもできます。ゲーム)、動きの組み合わせ。
さらに、間違った動きをするとアルゴリズム全体が無効になる可能性があります。
最終的に、DeepMind は、数値を正しく並べ替える能力と、その並べ替えをいかに迅速かつ効率的に完了するかに基づいて AlphaDev に報酬を与えます。AlphaDev は、正確かつ高速な方法を発見してゲームに勝つ必要があります。プログラム。
# 図 A: 組み立てゲーム。プレーヤー AlphaDev は、システム状態 st を入力として受け取り、すでに生成されたアルゴリズムに追加するアセンブリ命令を選択することによって動きます。
図 B: 報酬の計算。各移動の後、結果として得られたアルゴリズムがテストされ、その正確さと応答時間に基づいてエージェントに報酬が与えられます。
具体的には、AlphaZero は、詳細な思考 (熟議) を行う際に、各決定点で次に考えられるアクションと、次に考えられる次のステップを検討します。樹形図のように、段階的に逆算して、どのアクションが成功する可能性が最も高いかを判断します。
しかし問題は、状況の考えられるすべての分岐を考慮すると、必要な時間は宇宙の年齢よりも長くなる可能性があるということです。そこで研究者は直感のようなものを使ってそれを絞り込みます。
各ステップで、プログラムは現在の状態をニューラル ネットワーク (複雑で調整可能な数学関数) に入力し、最も適切な動作を見つけます。同時に、トレーニング プロセス中、ニューラル ネットワークは結果に基づいて更新され続けます。場合によっては、最高評価の行動が積極的な探索の対象として意図的に選択されないことがあります。
AlphaDev が実行できるアクションは 4 つあります。これには、異なる値の比較、値の別の場所への移動、プログラムの別の部分へのジャンプなどが含まれます。
各ステップの後、一連のリストを並べ替えてみて、正しく並べ替えられたリスト内の値の数に基づいて報酬を受け取ります。
以下同様に、リスト全体がソートされるか、プログラムの長さの制限に達し、新しいプログラムが最初から開始されるまで続きます。
C 実行速度が 70% 向上します
AlphaDev は新しい並べ替えアルゴリズムを発見し、LLVM libc 並べ替えライブラリに大幅な改善をもたらしました。
短いシーケンスの場合、スピードアップは 70% ですが、250,000 要素を超えるシーケンスの場合、スピードアップはわずか約 1.7% です。
研究者は、より短い 3 ～ 5 個の要素を使用した配列ソート アルゴリズムの改善に重点を置いています。
これらのアルゴリズムは、大規模な並べ替え関数の一部として複数回呼び出されることが多いため、最も広く使用されています。
これらのアルゴリズムを改善すると、任意の数の項目を並べ替える全体的な速度が向上します。
新しい並べ替えアルゴリズムを誰でも利用できるようにするために、研究者らはまた、このアルゴリズムをリバース エンジニアリングし、「プログラマー」が最も一般的に使用するコーディング言語である C に翻訳しました。
現在、これらのアルゴリズムは LLVM libc 標準並べ替えライブラリで利用できるようになりました。
ハッシュ関数の効率が 30% 向上
より高速な並べ替えアルゴリズムを発見した後、DeepMind は、AlphaDev がさまざまなコンピューター サイエンス アルゴリズムを一般化して改善できるかどうかをテストしました。 - ハッシュ。
ハッシュはコンピューティングの基本的なアルゴリズムであり、データの取得、保存、圧縮に使用されます。図書館員が特定の本を見つけるために分類システムを使用するのと同じように、ハッシュ アルゴリズムは、ユーザーが探しているものと正確な場所を知るのに役立ちます。
これらのアルゴリズムは、特定のキー (ユーザー名「Jane Doe」など) をハッシュします。つまり、元のデータを一意の文字列 (1234ghfty など) に変換します。その後、コンピューターはこのハッシュ値を使用して、すべてのデータを検索するのではなく、キーに関連付けられたデータを迅速に取得します。
結果は、AlphaDev によって発見されたアルゴリズムが、ハッシュ関数の 9 ～ 16 バイト範囲に適用された場合、従来のアルゴリズムよりも 30% 高速であることを示しています。
DeepMind は、新しいハッシュ アルゴリズムをオープン ソースの Abseil ライブラリにリリースしました。このアルゴリズムは毎日何兆回も使用されることが予想されることがわかります。
2 つの新しい戦略: 「スワップ移動」と「コピー移動」
AlphaDev は、より高速なアルゴリズムを発見しただけでなく、新しいメソッドも発見しました。
その並べ替えアルゴリズムは新しい一連の命令で構成されており、適用されるたびにそのうちの 1 つが保存されます。これらのアルゴリズムは毎日何兆回も使用されるため、これは大きな影響を与える可能性があります。
研究者らはこれを「AlphaDev スワップ移動」および「AlphaDev コピー移動」と呼んでいます。
最新の手法は、AlphaGo の衝撃的な「ステップ 37」を彷彿とさせます。
2016 年のマンマシン戦争で、AlphaGo は人間の直感に反する単純なショルダーチャージという手を打ち、伝説の囲碁棋士イ・セドルを破りました。
どちらの戦略でも、AlphaDev はステップをスキップし、間違っているように見えても実際には近道となる方法でプロジェクトを接続します。
これは、独自のソリューションを発見する AlphaDev の能力を実証し、コンピューター サイエンス アルゴリズムを改善する方法についての私たちの考え方に挑戦します。
下の図に示すように、元の sort3 実装には min(A, B, C) が含まれていますが、AlphaDev Swap Move を使用すると、AlphaDev は min(A, B) のみが必要であることがわかりました。 。
別の例として、元の実装では、max(B, min(A,C, D)) のより大きな並べ替えアルゴリズムを使用して 8 を並べ替えます。要素を並べ替えます。
AlphaDev は、「スワップとコピーの移動」を使用する際に必要なのは max(B, min(A, C)) だけであることを発見しました。
世界中のコードを一度に 1 つのアルゴリズムで最適化する
最適化して使用できるように展開することによってAlphaDev は、改良されたソートおよびハッシュ アルゴリズムにより、世界クラスの新しいアルゴリズムを一般化して発見する能力を実証しました。
Google DeepMind は、AlphaDev が、コンピューティング エコシステム全体を最適化し、社会に利益をもたらすその他の問題の解決に役立つ AGI ツールの開発に向けた一歩であると信じています。
ただし、研究者らは、AlphaDev は現在、低レベルのアセンブリ命令を最適化する能力に非常に優れているものの、アルゴリズムの発展に伴い限界があることも認めています。
開発者にとってより使いやすいものにするために、高級言語 (C など) でアルゴリズムを最適化する AlphaDev の機能が研究されています。
「AlphaDev スワップ移動」や「AlphaDev コピー移動」などの AlphaDev の新しい発見は、アルゴリズムを改善できるだけでなく、新しい解決策も見つけられることを示しています。
研究者らは、これらの発見が研究者や開発者に、基盤となるアルゴリズムをさらに最適化して、より強力で持続可能なコンピューティング エコシステムを構築するための技術や手法を開発するきっかけとなることを期待しています。
ネチズンからの熱いコメント
NVIDIA の科学者 Jim Fan が AlphaDev について詳しくまとめました:
ソート アルゴリズムすべての鍵となるソフトウェアの基礎。 DeepMind の AlphaDev は、小さなシーケンス (3 ～ 5 項目) の並べ替えを 70% 高速化します。重要なポイント:
- 主要な RL アルゴリズムは、もともと囲碁、チェス、将棋をプレイしていた AlphaZero に基づいています。同じ考え方が検索プログラムにも当てはまります。
#- 研究者らは C コードではなく、アセンブリ コードを最適化しました。これは、低レベルにして、保存されたすべての命令を圧縮するための意図的な選択です。
- アセンブリ コードはリバース エンジニアリングされて C に変換され、LLVM でオープンソース化されました。
#- 表現ネットワークで Transformer が使用されている場合でも、それは基本モデルではありません。プロセス全体は並べ替えのみに機能するため、ハッシュなどの他のタスクについては再トレーニングする必要があります。
#ML を使用したアルゴリズム発見でもう 1 つの大きなマイルストーンが達成されました!
AlphaDev は、コア コンピューター サイエンス アルゴリズムを革新する DeepMind の革新的な人工知能です。シーケンス手法を再考し、短いシーケンスを 70% 高速化しています。ハッシュ アルゴリズムの検出速度も 30% 向上します。強化学習はアルゴリズムの状況を再構築しています。
一部のネチズンは、言語モデルに興奮している一方で、他の深層学習アルゴリズムの成功事例を忘れるべきではないと言いました: AlphaZero、AlphaFold、そして今はAlphaDevです。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
