ゲーム理論に基づく大規模データ分析

現代の AI システムは、試験に向けて熱心に勉強する学生のように、画像内の物体を識別したり、タンパク質の 3D 構造を予測したりするタスクに取り組むことができます。多数の例題を訓練することで、このようなシステムは徐々にエラーを減らしていき、最終的には成功します。

しかし、これは孤独な作業であり、既知の学習形態の 1 つにすぎません。学習には他者との交流やコミュニケーションも必要です。非常に複雑な問題を一人で解決するのは困難です。 DeepMind はこれまで、問題解決にゲームのような性質を持たせることで、AI エージェントを訓練し、キャプチャー・ザ・フラッグをプレイして StarCraft のマスターレベルに到達できるようにしてきました。したがって、ゲーム理論モデリングに基づく視点が、他の基本的な機械学習の問題の解決に役立つかどうかを理解したいと考えています。

[[419288]]

先日、ICLR 2021にて「EigenGame: PCA as a Nash Equilibrium」という論文を発表し、優秀論文賞を受賞しました。私たちの研究では、古い問題に対する新しいアプローチを探求しています。つまり、固有値問題である主成分分析 (PCA) を、競争的なマルチエージェント ゲーム、つまり EigenGame として再定式化します。 PCA は通常、最適化問題 (または単一エージェント問題) として提示されますが、マルチエージェントの観点では、最先端の計算リソースを活用して新しいデータ分析とアルゴリズムを生成できることがわかります。これにより、以前は計算集約的だった大規模なデータセットに PCA を拡張できるようになり、将来の研究探究のための代替アプローチが提供されます。

ナッシュ均衡としての PCA

PCA (主成分分析) は 20 世紀初頭に初めて提案され、それ以来、高次元データ構造を分析するための長年の手法となっています。このアプローチは現在、データ処理パイプラインの最初のステップとして一般的に使用されており、クラスタリングとデータの視覚化を簡素化します。同時に、回帰や分類のための低次元表現を学習するための実用的なツールでもあります。 PCA が提案されてから 1 世紀以上が経過しましたが、依然として PCA を研究し調査する十分な理由があります。

まず、データはもともとペンと紙を使って手作業で記録されていましたが、現在では倉庫ほどの規模のデータセンターに保存されています。その結果、このよく知られた分析アプローチは計算上のボトルネックになります。研究者たちは、PCA のスケーリング方法を改善するためにランダム化アルゴリズムやその他のアプローチを研究してきましたが、これらのアプローチでは、ディープラーニングを中心としたコンピューティングの最近の進歩、つまり複数の並列 GPU または TPU へのアクセスを十分に活用できないため、大規模なデータセットにスケーリングするのが難しいことがわかりました。

2 番目に、PCA は多くの重要な機械学習およびエンジニアリングの問題、つまり特異値分解 (SVD) と共通のソリューションを共有しています。 PCA の問題を適切な方法で解決することで、データ分析とアルゴリズムを機械学習ツリーのさまざまなブランチに広く適用できるようになります。

他のボードゲームと同様に、PCA をゲームとして再設計するには、プレイヤーが従うべき一連のルールと目標を作成する必要があります。このようなゲームを設計する方法は多数ありますが、重要な設計概念は PCA 自体から生まれます。つまり、最適なソリューションは、データ内の重要な分散を捉え、互いに直交する固有ベクトルで構成されます。

EigenGame では、各プレイヤーが固有ベクトルを制御します。プレイヤーはデータの差異を説明することでスコアを向上させますが、他のプレイヤーとあまりにも似ている場合はペナルティが課せられます。また、階層も設定しました。プレイヤー 1 は分散を最大化することのみを気にしますが、他のプレイヤーは階層内で自分より上位のプレイヤーとの類似性を最小化することにも気を配る必要があります。この報酬とペナルティの組み合わせによって、各プレイヤーの効用が決まります。

適切に設計された分散 Var とアライメント Align 項を使用して、次のことを証明します。

• すべてのプレイヤーが最適なパフォーマンスを発揮すると、ゲームのナッシュ均衡が達成され、これが PCA アルゴリズムの解となります。
• この目標は、各プレイヤーが個別に、かつ同期的に勾配上昇法を使用して効用を最大化することで達成できます。

この同期ランピングの独立性は、数十の Google Cloud TPU に計算を分散して、データとモデルの並列処理を可能にするため、特に重要です。これにより、当社のアルゴリズムを真に大規模なデータに適応させることが可能になります。 EigenGame は、数百万の特徴または数十億の行を含む数百メガバイトのデータセットの主成分を数時間で見つけることができます。

ユーティリティ、アップデート、その他すべて

PCA をマルチエージェントの観点から検討することで、スケーラブルなアルゴリズムと新しい分析方法を提案することができます。また、ヘッブ学習、つまりニューロンが学習するにつれて適応する仕組みとの驚くべき関連性も発見しました。 EigenGame では、効用を最大化する各プレイヤーが、脳のシナプス可塑性のヘブビアン モデルから導出された更新規則に似た更新方程式を生成します。ヘブビアン更新は PCA ソリューションに収束しますが、任意の効用関数の勾配として導出することはできないことが知られています。ゲーム理論は、ヘブブ学習を研究するための新しい視点を提供し、機械学習の問題に対する一連の解決策も提供します。

機械学習の連続体の一方の端には、最適化可能な目的関数を導き出す確立された道があります。凸最適化理論と非凸最適化理論の両方を使用して、研究者はソリューションの全体的な特性について推論することができます。もう一方の極端な例では、純粋にコネクショニストの方法と神経科学にヒントを得た更新規則が直接指定されていますが、これによりシステム全体の分析が困難になる可能性があり、複雑な動的システムの研究が必要になることがよくあります。

EigenGame のようなゲーム理論的手法は、その中間に位置します。プレイヤーの更新は関数の勾配に制限されず、他のプレイヤーの現在の戦略に対する最適な応答だけになります。必要なプロパティを持つユーティリティ関数プログラムと更新を自由に設計できます。たとえば、ナッシュ プロパティによってシステム全体の分析を実行できることを保証しながら、偏りのない更新や加速された更新を指定できます。

EigenGame は、機械学習の問題に対するソリューションを大規模なマルチエージェント システムの出力として設計する方法をグラフィカルに示します。一般的に、機械学習の問題をマルチエージェントゲームとして定式化することは、難しいメカニズム設計の問題ですが、研究者は、2 人のプレイヤー間のこのタイプのゼロサムゲームを使用して、機械学習の問題を解決してきました。最も注目すべきは、生成的敵対ネットワーク (GAN) と呼ばれる生成モデリング手法の成功により、ゲーム理論と機械学習の関係への関心が高まったことです。

EigenGame は、これを超えて、より複雑なマルチプレイヤーの非ゼロサム ゲーム設定を実現します。これにより並列処理が最適化され、規模と速度が向上します。また、機械学習コミュニティに、新しいマルチエージェント アルゴリズムや外交やサッカーなどのより豊富なドメインをテストするための定量化可能なベンチマークも提供します。

私たちの有用性と更新された設計ブループリントが、他の人々がアルゴリズム、エージェント、およびシステムの設計における新しい方向性を模索するきっかけとなることを願っています。今後、どのような問題がゲームとして定式化されるのか、また、収集したデータの分析によってマルチエージェントインテリジェンスの性質に関する理解がさらに深まるかどうかが楽しみです。