Google DeepMindが強化学習を応用してアルゴリズム（algorithm）を改良する新しいAIシステム「AlphaDev」を発表しました。このAlphaDevを利用して、データを並べ替える（ソート／整列）ための高速アルゴリズムを発見したとの論文を natureに発表しています。1日に何兆回と実行されている重要なアルゴリズムを高速化したことで、コンピューティングに必要なリソースを大幅に削減できたとしています。
- AlphaDev discovers faster sorting algorithms（6/7 Google DeepMind）
- Faster sorting algorithms discovered using deep reinforcement learning（6/7 nature）
Right: AlphaDev Swap Move – AlphaDev discovers that you only need min(A,B).
ソート／整列のアルゴリズムは検索結果やSNS投稿のランク付けをはじめ、一般的なアプリのあらゆる部分で活用されています。世界中を合わせると毎日何兆回と実行され、非常に重要なアルゴリズムのため、世界中の研究者たちによって何十年と改善され続けていました。
しかし、人間による改善は主にC++のコードレベルで行われています。C++で書かれたコードは、実際にコードが実行される前にアセンブリ言語にコンパイルされ機械語に変換するという手順を踏みます。DeepMindの研究チームはこの「アセンブリ言語」レベルであれば、C++のコードからは見つからないような改良点が見つかると考えたとのことです。
改良例では、3要素のソート（上図）では、AlphaDevは前の処理で2つの入力の大小が事前に固定されている場合があることを見逃さずに命令数を1つ減らすことができています。また、従来であれば「下図左」のように要素数次第で「4要素用の処理」「3要素用の処理」「2要素用の処理」と分けていたところを、「下図右」のように3要素以上の場合においてはいったん3要素用のソート処理を行い、もし4要素だった場合は後から単純な処理を付け足すという手法で処理速度を大きく改善しています。
「AlphaDev」は、囲碁、チェス、将棋などのゲームで世界チャンピオンを破った強化学習モデルである「AlphaZero」に基づいています。AlphaDevが開発したソートアルゴリズムはLLVM libc++に導入済みで、すでに何百万人もの開発者たちに利用されています。
- How MuZero, AlphaZero, and AlphaDev are helping optimise the entire computing ecosystem that powers our world of devices（6/7 Google DeepMind）
最適化テストでは、Googleのデータセンターで使用されていないハードウエア、つまりフル稼働していないサーバーをAIによって最大19％削減できたということです。
- DeepMindが深層強化学習を利用してアルゴリズムを改善するAI「AlphaDev」を発表、すでにソートアルゴリズムやハッシュ関数の高速化に成功（6/7 gigazine）
- グーグル・ディープマインド、新AIシステム発表 アルゴリズム高速化へ（6/8 WSJ）