Loading article…
AlphaDev は、強化学習を使用してコンピュータサイエンスのアルゴリズムを強化するためにGoogle DeepMindによって開発された人工知能システムです。AlphaDev は、チェス、将棋、囲碁を自己対戦でマスターしたシステムAlphaZeroをベースにしています。AlphaDev は、ソートやハッシュなどの基本的なタスクのより高速なアルゴリズムを見つけるために同じアプローチを適用しています。[ 1 ] [ 2 ] [ 3 ]
2023 年 6 月 7 日、Google DeepMind はNature 誌にAlphaDev を紹介する論文を発表しました。AlphaDevは、小規模ソートアルゴリズムの最先端手法を上回る新しいアルゴリズムを発見しました。 [ 1 ]例えば、AlphaDev は5 要素のシーケンスをソートするためのより高速なアセンブリ言語シーケンスを発見しました。 [ 4 ]アルゴリズムを詳細に分析した結果、AlphaDev は、適用されるたびに 1 つのアセンブリ命令を回避する AlphaDev スワップ移動とコピー移動と呼ばれる 2 つの独自のアセンブリ命令シーケンスを発見しました。[ 1 ] [ 3 ]可変ソートアルゴリズムについては、AlphaDev は根本的に異なるアルゴリズム構造を発見しました。例えば、VarSort4 (最大 4 要素のソート) の場合、AlphaDev は人間のベンチマークよりも 29 アセンブリ命令短いアルゴリズムを発見しました。[ 1 ]また、AlphaDev は、特定のケースでハッシュアルゴリズムの速度を最大 30% 向上させました。[ 2 ]
2022年1月、Google DeepMindは、世界で最も人気のあるプログラミング言語の1つであるC++を管理する組織に新しいソートアルゴリズムを提出し、独立した検証を経て、AlphaDevのアルゴリズムがライブラリに追加されました。 [ 5 ]これは、10年以上ぶりのC++標準ライブラリのソートアルゴリズムの変更であり、AIを使用して発見されたアルゴリズムを含む最初の更新でした。 [ 5 ] 2023年1月、DeepMindは、9～16バイトの入力に対するハッシュアルゴリズムもオープンソースのC++ライブラリAbseilに追加しました。[ 6 ] [ 5 ] Googleは、これら2つのアルゴリズムが毎日数兆回使用されていると推定しています。[ 7 ]
AlphaDev は、DeepMind が囲碁やチェスなどのゲームをマスターするように訓練した強化学習モデル AlphaZero をベースに構築されています。[ 5 ]同社の画期的な点は、より高速なアルゴリズムを見つける問題をゲームとして扱い、AI を訓練してそのゲームに勝つようにしたことです。[ 2 ] AlphaDev は、アセンブリ言語で高速かつ正確なアルゴリズムを反復的に構築することを目的としたシングルプレイヤーゲームをプレイします。[ 1 ] AlphaDev は、最適な動きの探索をガイドするためにニューラルネットワークを使用し、自身の経験と合成デモンストレーションから学習します。[ 1 ]
AlphaDevは、AIがコンピューティングの基盤を進歩させ、さまざまな基準に合わせてコードを最適化する可能性を示しています。Google DeepMindは、AlphaDevがAIを使用して新しいアルゴリズムを発見し、既存のアルゴリズムを改善する研究をさらに促進することを期待しています。[ 2 ]
AlphaDevの主要な学習アルゴリズムは、AlphaZeroの拡張版である。
AlphaZeroをアセンブリプログラミングに適用するために、著者らはアセンブリプログラムの基盤となる構造を捉えるように設計されたTransformerベースのベクトル表現を作成した。 [ 1 ]この有限表現により、ニューラルネットワークはアセンブリプログラミングを有限個の可能な手があるゲーム（囲碁など）のようにプレイすることができる。
この表現では、以下のコンポーネントを使用します。
ゲームの状態とは、特定の時点までに生成されたアセンブリプログラムのことである。
ゲームの動きは、現在のアセンブリプログラムに追加される追加の命令です。
このゲームの報酬は、アセンブリプログラムの正確性とレイテンシによって決まります。コスト削減のため、AlphaDevは生成されたプログラムのうち、実際の測定レイテンシを計算対象とするのは0.002%未満にとどめています。これは、検索プロセス中にレイテンシを評価しないためです。代わりに、実際の測定された正確性とレイテンシの値を用いて教師あり学習によって学習された2つの関数を使用し、正確性とレイテンシを推定します。
AlphaDevは、9～16バイトの入力に対応するハッシュアルゴリズムを、事前に記述されたC++アルゴリズムのオープンソースコレクションであるAbseilに開発した。[ 8 ]
AlphaDev は新しいソート アルゴリズムを発見し、LLVM libc++ ソート ライブラリにおいて、短いシーケンスでは最大 70%、250,000 要素を超えるシーケンスでは約 1.7% の改善を実現しました。これらの改善は、ARMv8、Intel Skylake、AMD Zen 2 CPU アーキテクチャの uint32、uint64、float データ型に適用されます。AlphaDev の分岐なし条件付きアセンブリと新しいスワップ移動が、これらのパフォーマンス向上に貢献しました。発見されたアルゴリズムは、低レベル アセンブリから C++ にリバース エンジニアリングされ、libc++ 標準ソート ライブラリに正式に組み込まれました。[ 6 ]
AlphaDev はprotobufの最適化された VarInt 逆シリアル化関数を学習し、[ 9 ]単一値入力の速度で人間のベンチマークを約 3 倍上回りました。AlphaDev はまた、レイテンシを削減するために 2 つの操作を 1 つの命令にまとめた新しい VarInt 代入ムーブを発見しました。
AlphaDev のパフォーマンスは、論理的 AI アプローチである確率的超最適化[ 10 ]と比較されました。後者は、AlphaDev と少なくとも同量のリソースと実時間で実行されました。結果は、AlphaDev-S がレイテンシを直接最適化するには膨大な時間が必要であることを示しました。これは、レイテンシが各変異後に計算される必要があるためです。そのため、AlphaDev-S はレイテンシのプロキシ、具体的にはアルゴリズムの長さを最適化し、トレーニングの最後に、AlphaDev-S によって生成されたすべての正しいプログラムが検索されます。