Google Research：2019年の振り返りと2020年以降に向けて(4/8)

１．Google Research：2019年の振り返りと2020年以降に向けて(4/8)まとめ

・新たに開発した54量子ビットプロセッサで量子超越性を達成し一万年かかる計算を200秒で実現
・計算時に発生する量子エラーの訂正に焦点を当てており、以前より長時間実行可能になっている
・AIアルゴリズムでは広告主に代わってコンバージョンを最大化する最適戦略の研究などを行っている

２．量子コンピューターとAIアルゴリズム

以下、ai.googleblog.comより「Google Research: Looking Back at 2019, and Forward to 2020 and Beyond」の意訳です。元記事の投稿は2020年1月9日、Google Research部門トップのJeff Deanさんによる投稿です。アイキャッチ画像のクレジットはPhoto by Benjamin Davies on Unsplash

(7)量子コンピューティング
2019年、私達の量子コンピューティングチームは、指数関数的に計算量が増えるような複雑な計算を量子プロセッサーを使って高速に実行できる事を初めて実証しました。従来のコンピュータシステムでは世界最速のシステムであっても計算に10,000年かかる所をわずか200秒で計算したのです。

左：極低温実験装置に搭載されたSycamoreプロセッサをアーティストが美しく演出した画像
右：Sycamoreプロセッサの写真

量子コンピューターを実現するためには、これからも材料科学、量子化学、大規模な最適化などの領域で困難な問題が発生する可能性があります。しかし、量子コンピューターを実現するためには、引き続き各分野の研究を前進させなければなりません。

現在、計算時に発生する量子エラーを訂正する実装に焦点を当てており、以前より計算をより長時間実行できるようになってきています。

また、量子アルゴリズムの表現やハードウェアの制御を容易にし、深層強化学習などの従来の機械学習技術を使用して、より信頼性の高い量子プロセッサを構築する方法を見つけました。昨年の成果は心強いものであり、実用的な量子コンピューティングを様々な問題に対して現実的に使用できるものにするための初期段階に達しています。

また、GoogleのCEOであるSundarの量子コンピューティングのマイルストーンの意味に関する考えを「What our quantum computing milestone means」で読むこともできます。

(8)一般的なAIアルゴリズムと理論
AIに関する一般的なアルゴリズムと理論研究としては、アルゴリズムの基礎からアプリケーションまで研究を続け、グラフマイニングとマーケットアルゴリズムの研究も行いました。グラフ学習アルゴリズムでの作業の一部を要約したブログ投稿で、その作業の詳細を説明しています。

VLDB19で「Cache-aware load balancing of data center applications(データセンターアプリケーションのキャッシュ対応ロードバランシング)」というタイトルの論文を発表しました。しかし、この論文のもう一つのタイトルは「Increase the serving capacity of your data center by 40% with this one cool trick!(このクールなトリックでデータセンターのサービス容量を40％増やそうぜ！)」でした。

この論文では、グラフのバランスを考慮したパーティション分割を使用して、Web検索のバックエンドサービスシステムのキャッシュを特殊化する方法について説明しています。これにより、フラッシュドライブのクエリスループットが48%増加し、検索バックエンド全体のスループットが40%増加します。

Web検索サービスのフラッシュIOリクエストのヒートマップ(キャッシュミスの結果)
3つのこぶは、左から「ランダムなリーフ選択」、「負荷分散」、および「キャッシュ対応の負荷分散」を表しています。線は、50、90、95、および99.9パーセンタイルを示しています。VLDB’19の論文「Cache-aware load balancing of data center applications」より引用。

「A new dog learns old tricks: RL finds classic optimization algorithms(新しい犬は古いトリックを学ぶ：強化学習は古典的な最適化アルゴリズムを見つけます)」というタイトルのICLRの論文で、アルゴリズムと機械学習の新しいつながりを発表しました。強化学習が最適な(最悪なケースでも同等な)アルゴリズムを効果的に見つける方法を示し、オンラインのマッチングや割り当てなど、いくつかの古典的なオンライン最適化の組み合わせ問題に適用できる事を示しています。

スケーラブルアルゴリズムにおける私達の研究は、ビッグデータセット用の並列アルゴリズム、オンラインアルゴリズム、および分散アルゴリズムの両方に及びます。最近のFOCS’19の論文では、接続されたコンポーネントに対してほぼ最適な超並列計算アルゴリズムを提供しました。別の一連の論文では、「マッチング(理論と実践)」および「密度クラスタリング」の並列アルゴリズムが改善されました。

また、第三の研究は、ブラックボックスモデルのサブモジュラー関数を適応的に最適化することに関するもので、機能選択とボキャブラリ圧縮にいくつかの応用があります。

SODA’19の論文で、3つの面でほぼ最適なサブモジュラー最大化アルゴリズムを紹介しました。近似係数、ラウンドの複雑さ、クエリの複雑さについてです。

また、FOCS 2019の別の論文では、PCAおよび列サブセット選択のための最初のオンライン乗算近似アルゴリズムを提供しています。

他の研究では、未知の未来には予測可能な部分と予測に反する部分があると仮定する計算のセミオンラインモデルを紹介します。ITCS’19の２部一致やSODA’20のキャッシュなどの古典的な組み合わせ問題については、オンラインアルゴリズムとオフラインアルゴリズムを、可能な限り最良にスムーズに補間するセミオンラインアルゴリズムを発表しました。

マーケットアルゴリズムの分野における最近の研究には、学習とマーケットの間の相互作用に関する新しい理解、および実験計画法の革新が含まれています。

たとえば、このNeurIPSの19で口頭発表を行った論文「Strategizing against No-regret Learners」は、戦略エージェントが一般的な２プレイヤーゲームで学習エージェントと競合する際に持つ驚くべき競争上の優位性を明らかにしています。

広告の自動化に対する最近の関心は、自動入札と広告主の応答行動の理解への関心を高めています。WINE 2019の2つの論文では、広告主に代わってコンバージョンを最大化する最適な戦略を研究し、オークションの変更に対する広告主の反応行動を更に研究しています。

最後に、あるグループの行動が他のグループの結果に影響を与える可能性がある干渉の存在下での実験計画を研究しました。 KDD’19の論文とNeurIPS’19の論文では、ユニットまたはユニットのクラスターを定義して、実験力を維持しながら干渉を制限する方法を示しています。

KDD’19の論文「Randomized Experimental Design via Geographic Clustering」で発表したクラスタリングアルゴリズムを、米国内のユーザーが使うクエリに適用しました。このアルゴリズムは、例えば、サンフランシスコ・ベイエリア(訳注：有数のハイテク産業の集積地)にサンフランシスコ、バークレー、およびパロアルトが含まれていますが、サクラメントは含まれていないことを正確に予測して、大都市圏を自動的に識別する事に成功しています。