Google DeepMind’s game-playing AI just found another way to make code faster

ディープマインドがAIで高速アルゴリズムを発見、C++に採用

ディープマインドはAI「アルファデブ」を使って、人間が考案したアルゴリズムよりも高速にソートを実行するアルゴリズムを発見した。アルゴリズムはすでにC++に取り入れられ、使用されているという。 by Will Douglas Heaven2023.06.13

ディープマインド（DeepMind）は、基礎コンピューター科学における発見を続けている。昨年、同社はゲームをプレイする人工知能（AI）「アルファゼロ（AlphaZero）」を使って、さまざまなコードの核となる重要な数式の計算を高速化する新たな手法を発見し、50年前の記録を更新した。

そして今、同社（2023年4月に姉妹会社のAI研究所と統合し、グーグル・ディープマインドと改名）は同じ偉業を再度達成した。それも二度もだ。英国を拠点とする同社はアルファゼロの新バージョンである「アルファデブ（AlphaDev）」を使用し、それまで最善とされていた手法よりも最大70％速くリスト内のアイテムをソートする手法を発見した。

同社はさらに、暗号化に使用される重要なアルゴリズムの速度を30％も向上させる手法も発見した。これらはソフトウェアにおいて最も一般的な基盤となるアルゴリズムだ。わずかな速度向上でも大きな違いを生み、コスト削減やエネルギー節約に寄与する。

「ムーアの法則が終焉を迎え、チップは基礎物理的な限界に近づいています」とグーグル・ディープマインドの研究科学者、ダニエル・マンコウィッツ博士は語る。「コンピューティングを最適化するため、新たに革新的な手法を見つけ出さねばなりません」。

「今回の新たな取り組みは興味深いものです」と、ドイツのカールスルーエ工科大学で効率的なアルゴリズムの設計と実装を研究するピーター・サンダース教授（ディープマインドの取り組みには参加していない）は述べる。「今もなお、ソーティングはコンピューティングで最も広く使用されるサブルーチンの一つですから」。

ディープマインドはその成果を2023年6月7日付けで『ネイチャー』誌に公表した。だが、アルファデブが発見した手法は、すでに何百万人ものソフトウェア開発者たちが利用している。2022年1月、ディープマインドは新しいソーティング・アルゴリズムを、世界で最も利用されているプログラミング言語の一つ、C++を管理する組織に提出した。そして、2カ月間にわたる厳格な第三者審査の結果、アルファデブのアルゴリズムがC++に取り入れられることとなったのだ。これにより、C++のソーティングアルゴリズムが10年以上ぶりに変更された。そして、AIを使用して発見したアルゴリズムが導入されたのは今回が初めてである。

ディープマインドは、その他にも新たなアルゴリズムを「アブセイル（Abseil）」に追加した。アブセイルは記述済みのC++アルゴリズムのオープンソースコレクションで、C++によるプログラミングの際に誰でも使用することができる。これらの暗号化アルゴリズムは、任意のデータに対してユニークなIDとして用いることができるハッシュという数値を計算する。ディープマインドは、新たなアルゴリズムが現在、1日に何兆回も使用されていると推定している。

アルファデブは、囲碁やチェスなどのゲームを学習してマスターさせるためにディープマインドが訓練した強化学習モデル、アルファゼロを基盤としている。ディープマインドのブレークスルーは、より高速なアルゴリズムを見つけるための問題をゲームに見立てて、そのゲームでAIを勝たせるというアプローチだった。これは昨年の研究で計算を高速化するために用いたのと同じ手法である。

アルファデブにとって、コンピューターの命令を選択し、それらを適切な順序で配置することがゲームであり、その結果として生じるコード列がアルゴリズムを構成する。そのアルゴリズムが正確で、かつ既存のものより高速なら、ゲームはアルファデブの勝利となる。簡単なことのように聞こえるだろうが、アルファデブはゲームに勝つために天文学的な量の可能な手を探索しなければならない。

ディープマインドはアセンブリというプログラミング言語をゲームに採用した。アセンブリはコンピューター・チップ上での数値の移動の仕方について具体的な指示を与えることができる言語であるが、アセンブリでプログラムを記述する人はほとんどいない。C++のような言語で書かれたコードが実行される前に翻訳される言語だ。アセンブリの利点は、アルゴリズムをより細かいステップに分解できることにある。ショートカットを探している場合には、これが良い出発点となるのだ。

コンピューターチップには、数値を配置して処理するさまざまなスロットが存在する。アセンブリには、これらのスロット内で実行される動作を操作する基本的な命令がある。例えば、「mov(A,B)」はスロットAにある数値をスロットBに移動するようコンピューターに命令する。「cmp(A,B)」はスロットAの内容がスロットBの内容と比べて小さいか、等しいか、それとも大きいかを調べる命令だ。このような命令を長い系列にすることで、コンピューターに可能な操作をすべて実行できる。

アルファデブにとって、構築中のアルゴリズムに新しいアセンブリ命令を追加することは、ゲームに一手を加えることに該当する。初期段階では、アルファデブは命令をランダムに追加し、実行不能なアルゴリズムが生成されることもある。しかし、時間を経ると、アルファゼロがボードゲームでそうしたように、アルファデブも有効な手を打つことを学んでいく。結果として、アルファデブは、動作するだけでなく、正確かつ高速なアルゴリズムを導き出す命令を追加するようになる。

ディープマインドが注目したのは、3つから5つの項目からなる短いリストをソートするアルゴリズムだった。このようなアルゴリズムは、長いリストをソートするプログラム内で繰り返し呼び出される。したがって、これらの短いアルゴリズムにおける高速化は、累積的なドミノ効果をもたらす。

しかし、短いアルゴリズムは、これまで何十年もの間にわたって人間によって研究され、最適化されてきた。マンコウィッツ博士と同僚らは概念実証の一環として、3つの項目のリストをソートするアルゴリズムから研究を始めた。このアルゴリズムの人間による最善のバージョンは18の命令から成るものである。マンコウィッツ博士らはこのアルゴリズムを改良することはできないと考えていた。

「正直に言って、これ以上改良できるとは思っていませんでした」と同博士は語る。「しかし驚いたことに、アルゴリズムをさらに高速化することに成功したのです。最初はこれが何かの誤りやバグではないかと思ったのですが、プログラムを解析した結果、アルファデブが何か新しい発見をしたということがわかりました」。

アルファデブは、3つのアイテムのリストをソートする方法を見つけ出し、そのために必要な命令を18から17に削減した。アルファデブが発見したのは、省略できるステップがあるという事実だった。「後から見た時には、『すごい、確かに納得がいく』と思いました」とマンコウィッツ博士は語る。「しかし、アルファデブなしでこのような事実を発見するには、アセンブリ言語の専門家が必要です」。

アルファデブは、4つのアイテムのリストをソートするための人間の最善のアルゴリズム（28の指示が必要）よりも良いアルゴリズムを見つけることはできなかった。しかし、5つのアイテムのリストに対しては、人間を上回る結果を達成した。これまでの最善のアルゴリズムの命令数は46であったが、これを42に削減した。

これは、相当なスピードアップと言えるだろう。5つのアイテムのリストをソートするための既存のC++アルゴリズムは、一般的なインテルのスカイレイク（Skylake）チップ上で約6.91ナノ秒を要していた。それに対して、アルファデブのアルゴリズムはわずか2.01ナノ秒でソートを行い、約70%の高速化を実現している。

ディープマインドはアルファデブの発見を、2016年の囲碁のグランドマスター、李世乭（リ・セドル）との対局で「アルファ碁（AlphaGo）」が放った、奇抜だが勝利につながった一手にたとえる。「すべての専門家がこの一手を見て『正しい手ではない、悪手だ』と評価しました」とマンコウィッツ博士は語る。「しかし、実際には正しい一手だったのです。結果的にアルファ碁が試合に勝利しただけでなく、プロの囲碁プレイヤーが新たに取り入れ始めた戦略にも影響を及ぼしました」。

サンダース教授はこの結果に感銘を受けているが、過大評価すべきではないと考えている。「機械学習技術がプログラミングにおけるゲームチェンジャーになりつつあることには同意します。誰もがAIがすぐに、新しい、より優れたアルゴリズムを生み出せるようになるだろうと考えていますが、まだまだです」。

その理由の一つとして、サンダース教授はアルファデブがアセンブリ言語の命令の一部しか使用していないことを指摘する。多くの既存のソートアルゴリズムは、アルファデブが試すことのなかった命令を使用していると同教授は言う。これにより、アルファデブの手法を、人間の最善の手法とを比較するのが難しくなっている。

アルファデブに限界があるのは確かだ。最大5つのアイテムをソートするためにアルファデブが作り出した最長のアルゴリズムは、130の命令で構成されていた。各ステップで、アルファデブは297種類の可能なアセンブリ命令を選択していたが、これは全体の一部にすぎない。「297を超える命令や、130の命令以上の長さのアルゴリズムでは、学習が遅くなってしまいます」とマンコウィッツ博士は語る。

なぜなら、たとえ297の命令（あるいはゲームの手）であっても、アルファデブが構築可能なアルゴリズムの総数は、チェスの可能なゲームの数（10の120乗）や宇宙に存在する原子の数（約10の80乗）を超えるからだ。

ディープマインドの研究チームは、より長いアルゴリズムについては、アルファデブをアセンブリではなくC++の指示に対応するよう調整することを計画している。こうすると細かい制御ができなくなる分、アルファデブが一部のショートカットを見落とす可能性は出てしまうが、より広範なアルゴリズムに適用可能となるだろう。

サンダース教授はまた、特に長いアルゴリズムについて、人間が開発した最善の手法とより詳細に比較することを望んでおり、ディープマインドはそのことを計画の一部とすると述べている。マンコウィッツ博士は、アルファデブを人間が考案した最善の手法と組み合わせたいと考えている。アルファデブにアルゴリズムをゼロから構築させるのではなく、人間の直感をベースにして構築させるのだ。

そうすれば、さらなるスピードアップが可能な場所が見つかるかもしれない。「人間がやろうとすると、高度な専門知識と、プログラムを詳細に見て改善点を見つけ出すためのかなりの時間、おそらく何日も、あるいは何週間もが必要になるでしょう」とマンコウィッツ博士は言う。「これまで誰もが試みなかったのはそのせいです」。

人気の記事ランキング

ウィル・ダグラス・ヘブン [Will Douglas Heaven]米国版 AI担当上級編集者: AI担当上級編集者として、新研究や新トレンド、その背後にいる人々を取材しています。前職では、テクノロジーと政治に関するBBCのWebサイト「フューチャー・ナウ（Future Now）」の創刊編集長、ニュー・サイエンティスト（New Scientist）誌のテクノロジー統括編集長を務めていました。インペリアル・カレッジ・ロンドンでコンピュータサイエンスの博士号を取得しており、ロボット制御についての知識があります。