AlphaDevは、より高速なソートアルゴリズムを発見しました
AlphaDev has discovered a faster sorting algorithm.
新しいアルゴリズムがコンピューティングの基盤を変革する
デジタル社会はコンピューテーションとエネルギーの需要を増大させています。過去50年間、私たちはハードウェアの改良に頼ってきましたが、マイクロチップが物理的な限界に近づくにつれて、それら上で実行されるコードを改善することが重要になります。特に、1日に何兆回も実行されるコードの一部であるアルゴリズムについては、科学者やエンジニアによって磨かれたものを超える人工知能（AI）システムであるAlphaDevを紹介します。
AlphaDevは、強化学習を使用してコンピューターサイエンスのアルゴリズムを改善する人工知能（AI）システムです。私たちが今日Natureに発表した論文では、AlphaDevがソートのためのより速いアルゴリズムを発見したことを紹介しています。ソートはデータの順序付けの方法です。何十億人もの人々がこれらのアルゴリズムを日常的に使用していますが、それに気付いていないことがあります。オンライン検索結果やソーシャルメディアの投稿のランキングから、コンピューターや携帯電話でのデータ処理まで、あらゆることに基づいています。AIを使用してより優れたアルゴリズムを生成することは、コンピュータープログラムの作成方法を変革し、ますますデジタル化する社会のあらゆる側面に影響を与えるでしょう。
私たちの新しいソートアルゴリズムをC++のメインライブラリでオープンソース化することで、世界中の何百万人もの開発者や企業がクラウドコンピューティングやオンラインショッピング、サプライチェーン管理など、様々な産業でAIアプリケーションに使用しています。これはソートライブラリのこの部分における10年以上ぶりの変更であり、強化学習を用いて設計されたアルゴリズムがこのライブラリに追加された初めての例です。私たちはこれを、AIを使用して世界のコードを最適化するための重要な一歩と考えています。
ソートとは何ですか？
ソートは、一定の順序でアイテムを整理する方法です。アルファベットの3文字をアルファベット順に並べる、5つの数字を大きい順に並べる、数百万のレコードからなるデータベースを整理するなどの例があります。
この方法は歴史を通じて進化してきました。初期の例の一つは、紀元2世紀から3世紀にかけて、アレクサンドリアの大図書館の本棚で数千冊の本を手作業でアルファベット順に並べたことです。産業革命の後には、ソートを助けるための機械の発明がありました。タブレーションマシンはパンチカードに情報を保存し、アメリカの1890年の国勢調査結果を集めるために使用されました。
そして、1950年代に商用コンピューターが登場すると、ソートのための初期のコンピューターサイエンスのアルゴリズムが開発されました。今日では、世界中のコードベースで使用されるさまざまなソート手法やアルゴリズムがあり、大量のオンラインデータを整理するために使用されています。
現代のアルゴリズムは、コンピューターサイエンティストやプログラマーが数十年にわたる研究で開発したものです。これらは非常に効率的であり、さらなる改善をすることは、電力の節約やより効率的な数学的なアプローチを見つけることと同様に重要な課題です。これらのアルゴリズムはまた、大学の初級コンピューターサイエンスの授業で教えられるコンピューターサイエンスの基礎です。
新しいアルゴリズムを探す
AlphaDevは、既存のアルゴリズムを洗練するのではなく、ゼロから始めることでより速いアルゴリズムを発見しました。そして、人間のほとんどが見ない場所、つまりコンピューターのアセンブリ命令を見つけることから始めました。
アセンブリ命令は、コンピューターが実行するためのバイナリコードを作成するために使用されます。開発者がC++などの高水準言語で書くのに対して、これはコンピューターが理解できるようにするために「低水準」のアセンブリ命令に変換される必要があります。
私たちは、この低水準のレベルには多くの改善の余地があると考えていますが、それを高水準のコーディング言語では発見するのは難しいかもしれません。このレベルでは、コンピューターのストレージと操作はより柔軟であり、速度とエネルギー使用量により大きな影響を与える可能性があります。
.png)
ゲームで最適なアルゴリズムを見つける
AlphaDevはAlphaZeroに基づいており、Go、チェス、将棋などのゲームで世界チャンピオンを倒した強化学習モデルです。AlphaDevでは、このモデルがゲームから科学的な課題、さらにはシミュレーションから現実世界のアプリケーションにも転用できることを示しています。
新しいアルゴリズムを見つけるためにAlphaDevを訓練するために、ソートを単一プレイヤーの「アセンブリゲーム」に変換しました。各ターンでは、AlphaDevは生成されたアルゴリズムと中央処理ユニット(CPU)に含まれる情報を観察します。その後、アセンブリ命令を選択してアルゴリズムに追加することで、一手を打ちます。
アセンブリゲームは非常に困難であり、AlphaDevは効率的に大量の命令の組み合わせを探索して、ソートが可能で現在の最良のアルゴリズムよりも高速なアルゴリズムを見つけなければなりません。命令の組み合わせの数は、宇宙の粒子の数やチェスのゲーム(10^120ゲーム)や囲碁のゲーム(10^700ゲーム)の組み合わせの数と類似しています。そして、一つの間違った動きがアルゴリズム全体を無効にする可能性があります。
.png)
アルゴリズムが1つずつ命令を追加して構築される過程で、AlphaDevはアルゴリズムの出力を予想される結果と比較して正しいかどうかを確認します。ソートアルゴリズムの場合、これは順不同の数値が入力されて正しくソートされた数値が出力されるかどうかを意味します。AlphaDevは、数値を正しくソートするだけでなく、それを行う速さと効率性にも報酬を与えられます。AlphaDevは正しいかつより速いプログラムを発見することでゲームに勝利します。
より高速なソートアルゴリズムの発見
AlphaDevは、LLVM libc++ソーティングライブラリの改善につながる新しいソートアルゴリズムを発見しました。これにより、短いシーケンスでは最大70%、250,000要素を超えるシーケンスでは約1.7%高速化されました。
我々は、3から5要素の短いシーケンスのソートアルゴリズムの改善に重点を置きました。これらのアルゴリズムは、より大きなソート関数の一部として何度も呼び出されることが多いため、改善することで任意のアイテムのソートの全体的な高速化が実現できます。
新しいソートアルゴリズムを人々がより使いやすくするために、我々はアルゴリズムを逆解析し、開発者がよく使う最も人気のあるプログラミング言語であるC++に変換しました。これらのアルゴリズムは、世界中の何百万人もの開発者や企業が使用しているLLVM libc++標準ソーティングライブラリで利用できるようになりました。
新しいアプローチの発見
AlphaDevは、高速なアルゴリズムだけでなく、新しいアプローチも発見しました。ソートアルゴリズムには、適用されるたびに1つの命令を節約する新しい命令のシーケンスが含まれています。これは、これらのアルゴリズムが1日に何兆回も使用されるため、大きな影響を与えることができます。
これらを「AlphaDevのスワップとコピーの移動」と呼んでいます。この斬新な手法は、AlphaGoの「37手」に似ており、伝説的な囲碁プレーヤーの敗北につながった直感に反するプレーです。スワップとコピーの移動により、AlphaDevは実際にはショートカットであるが、間違いのように見える方法でアイテムを接続するためのステップをスキップします。これは、AlphaDevのオリジナルな解決策を発見する能力を示し、コンピュータサイエンスのアルゴリズムの改善方法に対する考え方に挑戦します。
ソートからハッシュへのデータ構造
より高速なソートアルゴリズムを発見した後、AlphaDevが異なるコンピュータサイエンスのアルゴリズムであるハッシングを一般化し、改善できるかどうかをテストしました。
ハッシングは、データを取得、格納、圧縮するためにコンピューティングで使用される基本的なアルゴリズムです。特定の本を見つけるために分類システムを使用する司書のように、ハッシングアルゴリズムはユーザーに何を探しているかとそれを正確に見つけるための情報を提供します。これらのアルゴリズムは、特定のキー（例：ユーザー名「Jane Doe」）のデータを取り、そのデータを一意の文字列（例：1234ghfty）に変換するプロセスであるハッシュ化を行います。このハッシュは、コンピュータがデータを検索するために使用され、すべてのデータを検索するのではなく、キーに関連するデータを迅速に取得するのに役立ちます。
AlphaDevをデータ構造のハッシングに最も一般的に使用されるアルゴリズムの1つに適用し、より高速なアルゴリズムを発見しようとしました。そして、ハッシュ関数の9-16バイトの範囲に適用したところ、AlphaDevが発見したアルゴリズムは30％速くなりました。
今年、AlphaDevの新しいハッシュアルゴリズムはオープンソースのAbseilライブラリにリリースされ、世界中の何百万人もの開発者が利用できるようになり、現在では1日に何兆回も使用されていると推定されています。
世界のコードを最適化する、1つのアルゴリズムずつ
世界中の開発者が使用するソートやハッシュアルゴリズムを最適化し、実世界に影響を与える新しいアルゴリズムを発見することで、AlphaDevは一般化し、新しいアルゴリズムを発見する能力を示しました。AlphaDevは、低レベルのアセンブリ命令の領域で最適化することは非常に強力ですが、アルゴリズムが成長するにつれて制約があり、高レベルの言語（C++など）でアルゴリズムを直接最適化するAlphaDevの能力を現在調査しています。
スワップやコピーの移動など、AlphaDevの発見は、アルゴリズムを改善するだけでなく、新しい解決策を見つけることも示しています。これらの発見が、研究者や開発者に、基本的なアルゴリズムをさらに最適化し、より強力で持続可能なコンピューティングエコシステムを作り出すための技術やアプローチを創造することに影響を与えることを願っています。
コンピューティングエコシステムの最適化について詳しく学ぶ：
ケーススタディを読む：https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools
We will continue to update VoAGI; if you have any questions or suggestions, please contact us!
Was this article helpful?
93 out of 132 found this helpful
Related articles
