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

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

・広告オークション研究も引き続き継続し、入札が代理入札者経由で行われる設定での最適化を研究した
・柔軟なオンライン配分問題のための新しいアルゴリズムであるデュアルミラー降下について紹介した
・アルゴリズムの基礎的な研究を継続し、40年来の未解決問題を、驚くほど簡潔な論文で肯定的に解決した

２．マーケットアルゴリズムとアルゴリズムの基礎理論

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

アイキャッチ画像はstable diffusionのカスタムモデルによる生成

マーケットアルゴリズムと因果関係推論

また、2022年のオンラインマーケットプレイスの改善に関する研究も継続しました。

例えば、広告オークション研究における最近の重要な分野は、自動入札オンライン広告の研究です。ここでは、入札の大部分が広告主に代わってより高いレベルで目的を最適化する代理入札者経由で行われます。

この分野では、ユーザー、広告主、入札者、広告プラットフォームが複雑に絡み合うため、自明ではない問題が発生します。私達は、自動入札オークションにおけるメカニズムの分析と改善に関する以前の研究に続き、ユーザー体験や広告主の予算などの異なる側面を考慮しながら、自動化される前提でオンラインマーケットプレースの改善に関する研究を行いました。

私達の発見は、非真実オークション(non-truthful auctions)においてさえ、MLアドバイスとランダム化技術を適切に取り入れることで、自動入札アルゴリズム間の均衡における全体の繁栄を堅牢に改善できることを示唆しています。

自動入札のオンライン広告システムの構造

自動入札システム以外にも、複雑な環境におけるオークションの改善についても研究しています。買い手が仲介者によって代表されている設定や、各広告がいくつかの可能なバリエーションのうちの一つで表示されるリッチ広告などです。

この分野での私達の研究は、最近の調査報告でまとめています。オークション以外にも、マルチエージェントや敵対的な設定における契約(contract)の使用について調査しています。オンライン確率最適化は、最適入札や予算消化速度計画に応用され、オンライン広告システムにおいて重要な役割を担っています。

オンライン配分の長期的な研究を基に、私達は最近、シンプルで堅牢かつ柔軟なオンライン配分問題のための新しいアルゴリズムであるデュアルミラー降下についてブログで紹介しました。

この最新アルゴリズムは、様々な敵対的・確率的入力分布に対して頑健であり、公正さなど、経済効率以外の重要な目的を最適化することができます。また、最近増えているROI制約の特殊な構造にデュアルミラー降下を合わせることで、広告主価値を最適化できることを示しました。デュアルミラー降下法は幅広い応用が可能であり、アルゴリズムによるより良い意思決定を通じて、広告主がより多くの価値を獲得できるよう、長い間使用されてきました。

デュアルミラー降下アルゴリズムの概要

さらに、ML、メカニズムデザイン、市場の相互作用に関する私達の最近の研究成果を紹介します。

私達は、非対称オークション設計のためのtransformersを研究し、後悔しない学習型買い手(no-regret learning buyers)のための効用最大化戦略を設計しました。

また、オークションにおける入札や値付けのための新しい学習アルゴリズムを開発しました。

エンティティ間の因果的相互作用を低減する二分実験デザインの概要

洗練されたオンラインサービスの重要な構成要素は、新たな介入があった際のユーザーや他のプレイヤーの反応を実験的に測定する能力です。

このような因果効果を正確に推定するための大きな課題は、これらの実験における対照群と実験群の間の複雑な相互作用、すなわち干渉(interference)を取り扱うことです。

私達は、グラフクラスタリングと因果推論の専門知識を組み合わせ、この分野における私達の以前の研究の結果を拡張しました。新しい実験デザインと柔軟な応答モデルを使いました。これは、実験割り当てと指標測定が二分プラットフォームの同じ側で発生したとき、相互作用を低減する事ができます。

また、合成制御と最適化技術を組み合わせることで、特に小データ領域において、より強力な実験デザインを実現できることを示しました。

アルゴリズムの基礎と理論

最後に、長年の未解決問題に取り組むことで、アルゴリズムの基礎的な研究を継続しました。買い手の価値が売り手のコストを弱く上回るときに達成可能な取引利益の一定割合を保証するメカニズムが存在するかという40年来の未解決問題を、驚くほど簡潔な論文で肯定的に解決しました。

更に、最近の論文では、古典的で研究の多いk-means問題に対して、最新の近似解を求めました。また、相関クラスタリング問題に対する最良近似を改良し、近似係数を2倍以上に向上させた。

最後に、最小コスト問題やその他のネットワークフロー問題を解くための動的データ構造に関する研究が、古典的な離散最適化問題を解決するために連続最適化技術を適用する画期的な研究にも貢献しました。

まとめ

効果的なアルゴリズムとメカニズムの設計は、テラ規模のデータを堅牢に扱い、重要なプライバシーと安全性を考慮する必要がある多くのGoogleシステムにとって重要な要素です。

私たちの手法は、製品システムで効果的に展開できる、確かな理論的基盤を持つアルゴリズムを開発することです。

更に、私たちの最も新しく開発した技術のいくつかをオープンソース化し、その背後にある高度なアルゴリズムを公開することで、これらの進歩の多くをより広いコミュニティに提供しています。

この記事では、プライバシー、市場アルゴリズム、規模拡大が可能なアルゴリズム、グラフベース学習、最適化におけるアルゴリズムの進歩の一部を取り上げました。

自動化がさらに進み、AIファーストのGoogleへと向かう中、堅牢でスケーラブル、かつプライバシーセーフなMLアルゴリズムを開発することは、依然として高い優先度を誇っています。私たちは、新しいアルゴリズムを開発し、より広く展開することに興奮しています。

謝辞

この記事は、多くのチームの研究をまとめたものです。
Gagan Aggarwal, Amr Ahmed, David Applegate, Santiago Balseiro, Jennifer Brennan, Vincent Cohen-addad, Yuan Deng, Alessandro Epasto, Matthew Fahrbach, Badih Ghazi, Sreenivas Gollapudi, Rajesh Jayaram, Ravi Kumar, Sanjiv Kumar, Silvio Lattanzi, Kuba Lacki, Brendan McMahan, Aranyak Mehta, Bryan Perozzi, Jean Pougetabadie, Daniel Ramage, Ananda Theertha Suresh, Andreas Terzis, Sergei Vassilvitskii, Erik Vee, Di Wang, and Song Zuoなどの研究者からの情報提供がもとになっています。

Badih Ghazi, Sreenivas Gollapudi, Rajesh Jayaram, Ravi Kumar, Sanjiv Kumar, Silvio Lattanzi, Kuba Lacki, Brendan McMahan, Aranyak Mehta, Bryan Perozzi, Jean Pougetabadie, Daniel Ramage, Ananda Theertha Suresh, Andreas Terzis, Sergei Vassilvitskii, Erik Vee, Di Wang そして Son Zuo. Ravi Kumarに感謝します。