Research press release

計算機科学:人工知能を使ってソートアルゴリズムの処理速度を高める

Nature

DeepMind社の人工知能(AI)エージェントであるAlphaDevを使って、C++(一般的なコンピュータープログラミング言語)のライブラリーで広く使用されているソートアルゴリズムをさらに改善した新しいアルゴリズムを発見できることが明らかになった。このことを報告する論文が、今週、Natureに掲載される。このAI生成アルゴリズムは、既にC++のソートライブラリーに追加された。この部分の前回の改訂は、10年以上も前のことだった。

アルゴリズムはコンピューターによる計算に不可欠であり、特定の計算タスクを実行するための一連の命令として機能する。基本アルゴリズム(例えば、「ソート」というタスクのアルゴリズム)は、1日に数兆回も実行されている。こうした基本アルゴリズムを最適化しようとする試みは、ボトルネックに達し、生身の専門家の手でさらなる最適化ができなくなっており、AIエージェントによるボトルネックの打破の可能性が指摘されている。ディープラーニング(深層学習)を用いてアルゴリズムを改善する取り組みは、アルゴリズムの発見と最適化が、深層学習システムを開発するために使用される訓練例の範囲内に限定されるという壁にぶつかっている。新しい深層強化学習エージェントとして登場したAlphaDevは、この限界を克服し、個々の問題に特化した訓練を必要とせずに新しいアルゴリズムを発見できることが示されている。

今回、Daniel Mankowitzらは、より優れたソートアルゴリズムを見つけるという課題をゲームに変え、AlphaDevを訓練して、このゲームをプレイできるようにした。AlphaDevは、このゲームをプレイして、既存の最先端アルゴリズムより優れた性能を示すソートアルゴリズムを発見した。これらの新しいソートアルゴリズムの一部は、標準C++ライブラリーのソート機能に追加された。標準C++ライブラリーには、数百万のユーザーがおり、その中には大学や国際的な企業も含まれている。

同時掲載のNews & Viewsでは、Armando Solar-Lezamaが、「この研究手法の威力は、このシステムが、訓練例から指針を得ることなく、報酬信号に基づいて、効率的なプログラムの生成を学習できるという事実に由来している」と述べている。また、Solar-Lezamaは、「この手法は、その普遍性と、問題に関する事前知識なしに課題を処理する能力によって、専門家の介入を最小限にとどめて高性能プログラミングを実現するための非常に重要な一歩になった」とも述べている。

AlphaDev, an artificial intelligence (AI) agent from DeepMind, is shown to discover new and improved computer sorting algorithms widely used in C++ (a common computer programming language) libraries. The AI-generated algorithms, reported in Nature this week, have been integrated into the C++ sorting library, the first change to this part of the library made in more than a decade.

Algorithms are integral to computing, acting as a set of instructions to perform a specific computational task. Fundamental algorithms, such as sorting tasks, are performed trillions of times every day. Attempts to optimize such algorithms have reached a bottleneck where human experts cannot optimize them any further, a problem that AI agents have the potential to solve. Efforts to use deep learning to improve algorithms have been limited by the ability to only discover and optimize within the realms of the training examples used to develop the deep learning system. A new deep reinforcement learning agent called AlphaDev is shown to overcome this limitation and can discover new algorithms without needing any problem-specific training.

Daniel Mankowitz and colleagues turned the task of finding better sorting algorithms into a game and trained AlphaDev to play it. By playing the game, AlphaDev discovered sorting algorithms that outperformed existing state-of-the-art algorithms. Some of the new sorting algorithms have been integrated into the standard sort function for the C++ library, a system used by several million users, including universities and international companies.

“The power of this approach comes from the fact that the system can learn to generate efficient programs on the basis of a reward signal, without needing any guidance from training examples,” writes Armando Solar-Lezama in an accompanying News & Views article. He adds that “the generality of the approach, and its ability to operate without any previous knowledge of the problem, make it a crucial step towards high-performance programming with minimal intervention from experts.”

doi: 10.1038/s41586-023-06004-9

「Nature 関連誌注目のハイライト」は、ネイチャー広報部門が報道関係者向けに作成したリリースを翻訳したものです。より正確かつ詳細な情報が必要な場合には、必ず原著論文をご覧ください。

メールマガジンリストの「Nature 関連誌今週のハイライト」にチェックをいれていただきますと、毎週最新のNature 関連誌のハイライトを皆様にお届けいたします。

「注目のハイライト」記事一覧へ戻る

プライバシーマーク制度