大規模データ分析のエンジンとしてのゲーム理論
'ゲーム理論は大規模データ分析のエンジンとして機能する'
EigenGameは基本的な機械学習の問題を解決する新しいアプローチを提案
現代のAIシステムは、画像内のオブジェクトを認識したり、タンパク質の3D構造を予測したりするタスクに取り組む際、勉学に励む学生のような姿勢で取り組んでいます。多くの例題に基づいてトレーニングを行い、時間とともにミスを最小化し、成功を達成します。しかし、これは一人で行う取り組みであり、学習の唯一の形態ではありません。学習はまた、他の人々との相互作用や遊びを通じて行われることもあります。非常に複雑な問題を一人で解決することは稀です。DeepMindの以前の取り組みでは、ゲーム理論に基づいたこの視点が、AIエージェントがCapture the Flagをプレイしたり、Starcraftでグランドマスターレベルに達したりするためのトレーニングに役立ちました。これが私たちに、このようなゲーム理論に基づいた視点が他の基本的な機械学習の問題の解決にも役立つのではないかと考えさせました。
本日、ICLR 2021（国際学習表現会議）にて、私たちは「EigenGame: PCA as a Nash Equilibrium」という研究を発表し、優れた論文賞を受賞しました。この研究では、古くからの問題に対する新しいアプローチを探求しました。具体的には、主成分分析（PCA）というタイプの固有値問題を、EigenGameと呼ばれる競争的なマルチエージェントゲームとして再定式化しました。通常、PCAは最適化問題（または単一エージェント問題）として定式化されますが、私たちはマルチエージェントの視点から新しい洞察とアルゴリズムを開発することができました。これにより、従来は計算上の負荷が高すぎて扱えなかった大規模なデータセットにスケールアップし、将来の探索における代替的なアプローチを提供することができます。
PCAをナッシュ均衡として
PCAは、高次元データの構造を理解するための長年の技術です。この手法は現在、データ処理パイプラインの最初のステップとして広く使用され、データのクラスタリングや可視化を容易にします。また、回帰や分類のための低次元表現を学習するための有用なツールでもあります。100年以上経った今でも、PCAを研究する魅力的な理由があります。
まず、データは元々手書きで紙のノートに記録されていましたが、現在は倉庫のサイズのデータセンターに保存されています。その結果、このよく知られた分析は計算上のボトルネックとなっています。研究者たちは、PCAのスケーリングを改善するためにランダム化アルゴリズムやその他の手法を探求してきましたが、これらのアプローチは最近の深層学習中心の計算リソース（特に多くの並列GPUやTPUへのアクセス）を十分に活用することができないため、大規模なデータセットにスケーリングするのが困難です。
また、PCAは、特異値分解（SVD）という多くの重要な機械学習やエンジニアリングの問題と共通の解を共有しています。適切な方法でPCA問題にアプローチすることで、私たちの洞察とアルゴリズムは機械学習の枝全体に広く適用されます。
ボードゲームと同様に、PCAをゲームとして再発明するためには、プレイヤーが従うルールと目的のセットが必要です。このようなゲームを設計する方法は多くありますが、PCA自体から重要なアイデアが生まれます。最適解は、データの重要な分散を捉え、互いに直交する固有ベクトルで構成されます。
EigenGameでは、各プレイヤーが固有ベクトルを制御します。プレイヤーはデータ内の分散を説明することでスコアを上げますが、他のプレイヤーとの間であまりにも近くなるとペナルティが科されます。また、私たちは階層を確立します。プレイヤー1は分散を最大化することだけを考えますが、他のプレイヤーは階層上のプレイヤーとのアライメントを最小化することも考慮する必要があります。この報酬とペナルティの組み合わせが各プレイヤーの効用を定義します。
適切に設計されたVarとAlignの用語を使用すると、次のことが示されます：
- すべてのプレイヤーが最適にプレイする場合、彼らはゲームのナッシュ均衡であるPCAソリューションを達成します。
- これは、各プレイヤーが独立してかつ同時に勾配上昇法を使用して自分の利用価値を最大化することで達成されます。
この同時上昇の独立性の特性は特に重要です。これにより、計算を数十のGoogle Cloud TPUに分散させることが可能になり、データとモデルの並列処理が可能となります。これにより、アルゴリズムは真に大規模なデータに適応することができます。EigenGameは、数百テラバイトのデータセット（数百万の特徴量または数十億の行を含む）に対して主成分を数時間で見つけます。
ユーティリティ、更新、およびその間のすべて
PCAをマルチエージェントの視点から考えることで、スケーラブルなアルゴリズムと新しい分析手法を提案することができました。また、ニューロンが学習時にどのように適応するかというヘビアン学習との意外な関連性も明らかにしました。EigenGameでは、各プレイヤーが自分の利用価値を最大化することにより、脳のシナプス可塑性のヘビアンモデルから導かれる更新方程式と類似した更新ルールが生じます。ヘビアン更新はPCA解に収束することが知られていますが、それ自体は任意のユーティリティ関数の勾配として導かれたものではありません。ゲーム理論は、ヘビアン学習を見るための新しいレンズを提供し、機械学習問題への連続したアプローチを示唆します。
機械学習の連続したスペクトルの一方では、解を最適化できる目的関数の提案というよく開発されたパスがあります。凸および非凸最適化の理論を使用して、研究者は解のグローバルな特性について推論することができます。他方では、純粋な結合主義的な手法や神経科学に触発された更新ルールは直接指定されますが、システム全体の分析はより困難であり、しばしば複雑な動的システムの研究を引き起こします。
EigenGameのようなゲーム理論的なアプローチはその間に位置します。プレイヤーの更新は関数の勾配である必要はなく、他のプレイヤーの現在の戦略に対する最良応答である必要があります。望ましい特性を持つユーティリティと更新を設計する自由があります。たとえば、バイアスのないまたは高速化された更新を指定し、同時にナッシュ特性を確保することで、システム全体を分析することができます。
EigenGameは、大規模なマルチエージェントシステムの出力として機械学習問題の解を設計する具体的な例です。より一般的には、機械学習問題をマルチエージェントゲームとして設計することは、チャレンジングなメカニズムデザインの問題です。ただし、既に2人プレイヤー、ゼロサムゲームのクラスを使用して機械学習問題を解決した研究者もいます。特に、生成的モデリングへのアプローチとしての敵対的生成ネットワーク（GAN）の成功は、ゲーム理論と機械学習の関係に関心を集めています。
EigenGameは、より複雑な多人数、一般和設定に進化します。これにより、より明確な並列性が可能になり、規模と速度が向上します。また、これにより、外交やサッカーなどのより豊かな領域とともに、新しい多エージェントアルゴリズムをテストするための定量的な基準がコミュニティに提供されます。
私たちは、ユーティリティと更新の設計のための私たちのブループリントが他の人々にこの方向性を探索することを奨励することを望んでいます。私たちは、ゲームとして定式化できる他の問題と、私たちが得る洞察が知能の多エージェント性の理解をさらに向上させるかどうかを楽しみにしています。
詳細については、私たちの論文「EigenGame: PCA as a Nash Equilibrium」と、それに続く作品「EigenGame Unloaded: When playing games is better than optimizing」をご覧ください。
We will continue to update VoAGI; if you have any questions or suggestions, please contact us!
Was this article helpful?
93 out of 132 found this helpful
Related articles
