深層強化学習を使用して発見された高速ソートアルゴリズム

Nature volume 618、pages 257–263 (2023)この記事を引用

355k アクセス

1 引用

1148 オルトメトリック

メトリクスの詳細

ソートやハッシュなどの基本的なアルゴリズムは、毎日何兆回も使用されます1。計算の需要が高まるにつれて、これらのアルゴリズムのパフォーマンスを可能な限り高めることが重要になってきています。過去に目覚ましい進歩が達成されました 2 が、これらのルーチンの効率をさらに改善することは、人間の科学者にとっても、計算によるアプローチにとっても困難であることが判明しています。ここでは、これまで知られていなかったルーチンを発見することで、人工知能がどのように現在の最先端技術を超えることができるかを示します。これを実現するために、私たちはシングルプレイヤーゲームとしてより良い並べ替えルーチンを見つけるというタスクを定式化しました。次に、このゲームをプレイするために新しい深層強化学習エージェント AlphaDev をトレーニングしました。 AlphaDev は、これまで知られていた人間のベンチマークを上回る小さな並べ替えアルゴリズムをゼロから発見しました。これらのアルゴリズムは、LLVM 標準 C++ ソートライブラリ 3 に統合されています。ソートライブラリのこの部分に対するこの変更は、強化学習を使用して自動的に検出されたアルゴリズムによるコンポーネントの置き換えを表します。また、追加のドメインでの結果も示し、アプローチの一般性を示します。

アルゴリズムを改善するには、人間の直感とノウハウが非常に重要です。しかし、多くのアルゴリズムは人間の専門家がそれ以上最適化できない段階に達しており、計算上のボトルネックが増大し続けています。何十年にもわたる古典的なプログラム合成文献の研究は、正しいプログラムを生成したり、レイテンシのプロキシを使用してプログラムを最適化したりすることを目的としています。これらには、列挙的検索手法 4、5、6、7 や確率的検索 5、6、8、9、10 に加え、正しいプログラムを生成するためにプログラム合成で深層学習を使用するという最近の傾向 11、12、13、14、15、16 が含まれます。。深層強化学習 (DRL) を使用すると、CPU 命令レベルで実際に測定されたレイテンシーを最適化し、以前の研究と比較して正確で高速なプログラムのスペースをより効率的に検索および考慮することで、正確でパフォーマンスの高いアルゴリズムを生成することで、これをさらに一歩進めることができます。。

コンピューターサイエンスにおける基本的な問題の 1 つは、シーケンスをどのようにソートするかということです 17、18、19、20。これは、世界中の初等コンピュータサイエンスのクラスで教えられており 21、22、広範囲のアプリケーションで遍在的に使用されています 23、24、25。数十年にわたるコンピュータサイエンスの研究は、並べ替えアルゴリズムの発見と最適化に焦点を当ててきました26、27、28。実際的なソリューションの重要な要素は、短い一連の要素に対する小さな並べ替えです。このアルゴリズムは、分割統治アプローチを使用する大きな配列をソートするときに繰り返し呼び出されます29。この作業では、(1) 固定ソートと (2) 変数ソートの 2 種類の小規模ソートアルゴリズムに焦点を当てます。固定ソートアルゴリズムは固定長のシーケンスをソートします (たとえば、ソート 3 は長さ 3 のシーケンスのみをソートできます)。一方、可変ソートアルゴリズムはさまざまなサイズのシーケンスをソートできます (たとえば、変数ソート 5 は 1 から 5 の範囲のシーケンスをソートできます)。要素）。

私たちは、新しく効率的な並べ替えアルゴリズムを発見するという問題を、AssemblyGame と呼ぶシングルプレイヤーゲームとして定式化します。このゲームでは、プレーヤーは、アセンブリ命令 30 と呼ばれる一連の低レベル CPU 命令を選択し、組み合わせて新しい効率的なソートアルゴリズムを生成します。プレーヤーはアセンブリ命令の組み合わせ空間を考慮して、正確かつ高速なアルゴリズムを生成する必要があるため、これは困難です。 AssemblyGame の難しさは、チェス (10120 ゲーム) 31 や囲碁 (10700 ゲーム) 32 などの非常に難しいゲームに似た検索空間のサイズだけでなく、報酬関数の性質からも生じます。 AssemblyGame での 1 つの間違った命令により、アルゴリズム全体が無効になる可能性があり、このゲーム空間での探索は信じられないほど困難になります。

) to the current algorithm generated thus far. A reward rtis received that comprises both a measure of algorithm correctness and latency. Algorithm correctness (Fig. 2b) involves inputting a set of N test sequences into the current algorithm Pt to generate N outputs. These outputs are then compared to the expected outputs and a correctness reward rt is computed. Latency rewards can be generated by either (1) penalizing the agent for increasing the length of the algorithm (when length and latency are highly correlated) that we refer to as the algorithm length reward, or (2) measuring the actual latency of the algorithm. The game is executed for a limited number of steps, after which the game is terminated. Winning the game corresponds to generating a correct, low-latency algorithm using assembly instructions. Losing the game corresponds to generating an incorrect algorithm or a correct but inefficient algorithm./p> assembly instruction, which is appended to the current algorithm. The agent receives a reward that is a function of the algorithm’s correctness, discussed in b, as well as the algorithm’s latency. The game is won by the player discovering a low latency, correct algorithm. b, The program correctness and latency computations are used to compute the reward rt. In this example, test sequences are input to the algorithm; for example, in the case of sorting three elements, test inputs comprise all sequences of unsorted elements of length 3. For each sequence, the algorithm output is compared to the expected output (in the case of sorting, the expected output is the sorted elements). In this example, the output \({\bf{D}}{\boldsymbol{{\prime} }}\) does not match the expected output \({\bf{B}}{\boldsymbol{{\prime} }}\) and the algorithm is therefore incorrect./p>

ブログ