2022年のGoogleのAI研究の成果と今後の展望～その他の先進的なアルゴリズム編～(1/2)

１．2022年のGoogleのAI研究の成果と今後の展望～その他の先進的なアルゴリズム編～(1/2)まとめ

・堅牢なアルゴリズム設計はGoogle全体のシステム特に機械学習と人工知能モデルの屋台骨となっており優先度が高い
・教師、半教師あり、学習、グラフ、クラスタリングなど様々な分野で大規模データを扱うルゴリズムの開発を継続
・大規模なニューラルネットワークで差分プライバシー(DP)を実現し、大規模連合学習にも継続して取り組んだ

２．規模拡大可能なアルゴリズムと連合学習

以下、ai.googleblog.comより「Google Research, 2022 & beyond: Algorithmic advances」の意訳です。元記事は2023年2月10日、Vahab Mirrokniさんによる投稿です。

アルゴリズム編の後半です。中々、難しいお話が続きますが、繰り返し繰り返し出てくるキーワードはスケーラブル(Scalable)、すなわち規模拡大可能性です。モデルの規模を拡大するだけではダメだ！という意見を目にする事もありますが、まだ私達人類はAIの規模がこのまま拡大していった先に何があるのか知らないのですから、規模拡大に突き進むアプローチは間違っていないのではないかと思います。

アイキャッチ画像はstable diffusionのカスタムモデルによる生成でグラフニューラルネットワークを蜘蛛の巣で表現しようとしたのですが、蜘蛛要素が入るとどうしても全体がダークな画風に寄ってしまい、方向性を修正するよりStable Diffusion先生の描きたいように描いて頂く方が面白いイラストが出来そうなので先生に任せたイラスト

(本記事は、Googleの様々な研究分野を取り上げるシリーズの第5部です。このシリーズの他の記事は第1部「2022年のGoogleのAI研究の成果と今後の展望～言語・視覚・生成モデル編～」からご覧いただけます)

堅牢なアルゴリズム設計は、Google全体のシステム、特に機械学習(ML:Machine Learning)と人工知能(AI:Artificial Intelligence)モデルの屋台骨となっています。

したがって、Google 検索やGoogle 広告からGoogle マップやYouTubeに至るまでのサービスを強化するため、効率、パフォーマンス、スピードを向上させるアルゴリズムを開発することは、依然として高い優先度を誇っています。

Google Research はこの取り組みの最前線に立ち、プライバシーが保たれる推薦システムから大規模な ML のためのスケーラブルなソリューションまで、多くのイノベーションを開発してきました。2022 年、Google Research はこの取り組みを継続し、いくつかの関連領域で最先端技術を開発しました。

本投稿では、規模拡大可能性、プライバシー、市場アルゴリズム、アルゴリズム基礎と理論など、これらの一部における私たちの進歩に焦点を当てます。

・規模拡大可能なアルゴリズムグラフ、クラスタリング、最適化
・プライバシーと連合学習
・市場アルゴリズムと因果推論
・アルゴリズムの基礎と理論

規模拡大可能なアルゴリズムグラフ、クラスタリング、最適化

大規模なデータセットを扱う必要性が高まる中、複雑なアルゴリズムの規模拡大可能性と信頼性、さらに説明可能性、堅牢性、高速性を向上させることは、依然として高い優先事項となっています。私たちは、教師なし・半教師あり学習、グラフベース学習(graph-based learning)、クラスタリング、大規模最適化など、様々な分野で大規模データセットを扱う新しいアルゴリズムの開発に継続して取り組んできました。

このようなシステムの重要な構成要素は、類似性グラフ(物体間の類似性を表す最近傍グラフ)を構築することです。規模拡大の容易さと高速性の観点から、このグラフは品質を損なわずに、まばら(sparse)であることが望ましいです。

私達は、効率的な分散グラフ構築手法としてSTARと呼ばれる2ホップスパナー技法(2-hop spanner technique)を提案し、理論的にも実践的にも類似度計算の回数を大幅に減らし、高品質なグラフ学習やクラスタリング出力を生成しつつ、よりまばらなグラフを構築する方法を示しました。

例えば、10T個のエッジを持つグラフに対して、ペアワイズ類似度比較で100倍以上の改善と、無視できる品質低下での大幅な実行時間短縮を実証しました。私達は以前、このアイデアを応用して、指標用の超並列アルゴリズムと最小サイズクラスタリングを開発しました。

さらに、クラスタリングの分野では、初の線形時間階層的凝集型クラスタリング(HAC:Hierarchical Agglomerative Clustering)アルゴリズムと、HACのための初の対数深度並列アルゴリズムであるDBSCANを開発し、100Bエッジのグラフで50倍の高速化を達成しました。

また、様々な種類のクラスタリング問題に対して、改善された準線形アルゴリズムを設計しました。幾何学的リンケージクラスタリング、一定ラウンド相関クラスタリング、完全に動的な k クラスタリングなどです。

マルチコア処理の成功(GBBSなど)に触発され、私達は1台のマルチコアマシンで100Bエッジのグラフを扱えるグラフマイニング用アルゴリズムを開発するミッションに着手しました。ここでの大きな課題は、高速(例えば、準線形)な並列実行時間(＝深さ)を実現することです。

私達は、コミュニティ検出や相関クラスタリングに関するこれまでの研究成果を受けて、HACのためのアルゴリズム「ParHAC」を開発しました。このアルゴリズムは、証明可能なポリロガス深度(polylogarithmic depth)で準線形に機能し、50倍の高速化を達成しました。

一例として、100B以上のエッジを持つグラフに対して近似的親和性階層(approximate affinity hierarchy)を求めるのに、ParHACはわずか～10分、完全なHACを求めるには～3時間を1台のマシンで要しました。私たちは、分散HACに関するこれまでの研究成果に従い、テラ規模のグラフを扱うために、これらのマルチコアアルゴリズムを分散アルゴリズム内のサブルーチンとして使用しています。

また、2022年にはグラフニューラルネットワーク(GNN:Graph Neural Networks)に関する興味深い成果を多数得ました。多くのグラフ学習手法を統一するモデルベースの分類法を提供しました。

さらに、構造の異なる数千のグラフに対する性能から、GNNモデルに対する知見を見出しました(下図)。また、最短経路や最小木などの基本的なグラフ問題を解くために、既存のGNNが要求する深さを克服する新しいハイブリッドアーキテクチャを提案しました。

GraphWorldのノード分類データセット50,000個に対する3種のGNN(GCN, APPNP, FiLM)の相対性能の比較結果。学術的なGNNベンチマークデータセットには、モデルの順位が変わらない領域が存在することがわかります。GraphWorldは、GNNアーキテクチャに関する新しい洞察を明らかにし、これまで未開拓だったグラフを発見することができます。

さらに、これらの多くの進歩の一部をより広いコミュニティに提供するために、TensorFlowでグラフニューラルネットワークを構築するための代表的モデリングライブラリ(TF-GNN)の3つのリリースがありました。

そのハイライトは、GNNソリューションを簡単に構成するためのモデルライブラリとモデルオーケストレーションAPIです。NeurIPS2020のワークショップ「Mining and Learning with Graphs at Scale」に続き、ICML2022でグラフベースの学習に関するワークショップを、NeurIPS2022でTensorFlowにおけるGNNのチュートリアルを開催しました。

「Robust Routing Using Electrical Flows」では、障害(閉鎖、事故など)に強い道路網の代替経路を効率的に計算するGoogle Mapsソリューションを提案した最近の論文を紹介しました。実世界の道路ネットワークにおいて、最先端のプラトー且つペナルティな手法(plateau and penalty)を大幅に凌駕することを実証しています。

道路網に対応する電気回路を構築する手法の例
電流は3つの流れ、i1、i2、i3に分解でき、それぞれがカリフォルニア州フリーモントからカリフォルニア州サンラファエルへの実行可能な代替経路に対応します。

最適化の面では、Googleのブラックボックス最適化およびハイパーパラメータチューニングの主力ライブラリであるVizierをオープンソース化しました。

また、線形計画法(LP:Linear Programming)ソルバーのために新しい技術を開発しました。これにより、行列分解に依存しているために並列処理や分散アプローチの機会が制限されていた規模拡大の限界に対処しました。

この目的のために、私達は、大規模LP問題のための新しい一次ソルバーであるプライマル・デュアル線形計画法(PDLP:Primal-Dual Hybrid Gradient)と呼ばれるLPのためのプライマル・デュアルハイブリッド勾配(PDHG:Primal-Dual Linear Programming)ソリューションをオープンソースで提供しました。

PDLPは、12Bの非ゼロ数を持つ実問題の解決に使用されています。(また、社内の分散バージョンでは92Bの非ゼロ数まで拡張可能です。)PDLPの有効性は、基礎理論開発とアルゴリズム工学の組み合わせによるものです。

OSS Vizierでは、複数のクライアントがそれぞれ提案リクエストをService APIに送り、Service APIはPythiaのポリシーを使ってクライアント向けの提案を生成します。クライアントはこれらの提案を評価し、計測値を返します。全てのトランザクションは保存され、障害耐性を実現しています。

プライバシーと連合学習

ユーザーのプライバシーを尊重しながら質の高いサービスを提供することは、Googleのすべてのシステムにとって最優先事項であり続けています。この分野の研究は多くの製品にまたがり、差分プライバシー(DP:Differential Privacy)連合学習の原理を利用しています。

まず、大規模なニューラルネットワークをDPでトレーニングする問題に対処するために、様々なアルゴリズムの進歩を遂げてきました。DP-FTRLアルゴリズムに基づくDPニューラルネットワークを立ち上げることができた以前の研究を基に、行列分解DP-FTRLアプローチを開発しました。

この研究は、特定の学習問題に最適なDPメカニズムを見つけるために、可能なDPメカニズムの大規模な集合に対して最適化した数学的プログラムを設計できることを実証しています。

また、ニューラルネットワークやカーネルベース手法のDP学習において、入力特徴量の次元に依存しないマージン保証を確立しました。さらに、この概念をより広範なMLタスクに拡張し、300倍少ない計算量でベースライン性能に匹敵する性能を実現しました。大規模モデルの微調整については、一度事前学習したモデルは(DPであっても)本質的に低次元部分空間上で動作するため、DPが課す次元の呪いを回避できることを論じました。

アルゴリズム面では、高次元分布のエントロピーを推定するために、局所DPメカニズム(これは1サンプルあたり1ビットしか利用できない場合でも動作します)および効率的なシャッフルDP機構を得ました。

また、データベース中の上位k位までの人気アイテムを同時にプライベート手法で推定する、より高精度な方法を提案し、Plumeライブラリに採用しました。さらに、超並列計算(MPC:Massively Parallel Computing)モデルにおけるDPクラスタリングの最適に近い近似アルゴリズムを示し、規模拡大且つ分散した設定において、これまでの研究をさらに改善しました。

また、プライバシーとストリーミングの交わりも興味深い研究の方向性です。私達はプライベートな周波数モーメントに対して、ほぼ最適な近似-空間トレードオフを得ることができました。また、スライディングウィンドウ・ストリーミングモデルにおいて、異なる要素をプライベートにカウントするための新しいアルゴリズムを提案しました。更に、敵対的なストリーミングを研究するための一般的なハイブリッドフレームワークを提示しました。

セキュリティとプライバシーの交差点にあるアプリケーションに取り組み、パブリッシャー間のリーチと頻度を測定するための、安全かつプライベートで通信効率の良い新しいアルゴリズムを開発しました。世界広告主連盟(World Federation of Advertisers)は、このアルゴリズムを測定システムの一部として採用しています。

さらに、DPの2サーバモデルにおいて、まばらなヒストグラムを計算するための安全かつプライベートな新しいプロトコルを開発しました。これらのプロトコルは、計算と通信の両方の観点から効率的で、標準的な手法で得られるものより大幅に優れており、スケッチ、暗号、マルチパーティ計算、DPのツールやテクニックを組み合わせています。

私達はDPを用いてBERTやtransformers の学習を行っていますが、大規模言語モデル(LLM:Large Language Models)が学習サンプルを記憶してしまう原因を理解することは、そのプライバシー性能を評価するための経験則的な手法です。

特に、LLMが学習中に(潜在的に記憶していた)学習サンプルをいつ、なぜ忘れてしまうのかを調査しました。その結果、先に見たサンプルが後に見たサンプルを犠牲にする事で、プライバシー上の利点を守っている可能性があることが示唆されました。また、LLMが記憶した学習データをどの程度出力しているかを定量的に評価しました。