基于博弈论的大规模数据分析

现代 AI 系统可以像勤奋的学生准备考试一样，去处理诸如识别图像中的对象以及预测蛋白质 3D 结构之类的任务。通过大量示例问题训练，这类系统可以逐渐降低错误，直至取得成功。

但这是一项需要独自完成的工作，并且只是已知的学习形式之一。学习也需要与他人互动和交流。一个单独的个体很难自行解决极其复杂的问题。通过让问题解决方案具有类游戏的特质，DeepMind 之前在研究中已经训练了 AI 智能体 (Agent) 来玩夺旗赛并在《星际争霸》中达到大师级水平。，我们希望了解基于，以博弈论为模型的视角能否帮助解决其他基本的机器学习问题。

最近，在 2021 年 ICLR 上，我们发表了论文 “EigenGame将 PCA 作为纳什均衡 (EigenGame: PCA as a Nash Equilibrium)”，并获得杰出论文奖。我们的研究探索了一种解决旧问题的新方法我们将主成分分析 (PCA)(一种特征值问题)重新表述为竞争性的多智能体博弈游戏，即 EigenGame。PCA 通常表现为优化问题(或单智能体问题);，我们发现多智能体视角可使我们利用最新的计算资源生成新的数据分析和算法。这使得我们能够将主成分分析扩展到以往计算密集型的大规模数据集，并为未来的研究探索提供一种替代方法。

将 PCA 作为纳什均衡

PCA (Principal ponent analysis) 最早于 20 世纪初期提出，之后便成为了分析高维数据结构长期使用的一项技术。现在，这种方法已普遍用作数据处理流水线中的第一步，简化了集群和可视化数据。，它也是学习低维表示以进行回归和分类的实用工具。自 PCA 提出后的一个多世纪，我们仍然有充分的理由对其进行学习和研究。

，数据最初是由人工用纸笔记录，而现在则存储在像仓库一样大的数据中心。结果，这种熟悉的分析方式成为了计算瓶颈。研究人员已经探索了随机算法和其他方向来改善 PCA 的扩展方式，我们发现，这些方法难以扩展到大规模数据集，因为它们无法完全利用计算领域以深度学习为中心的最新进展即访问多个并行 GPU 或 TPU。

，PCA 与许多重要的机器学习和工程问题都需要使用共同的解决方案，即奇异值分解 (SVD)。通过以正确的方式解决 PCA 问题，我们的数据分析和算法将更广泛地应用于机器学习树的各个分支。

图 1 以 SVD 为根基的知识树涵盖了机器学习中的多个基本概念，包括 PCA、最小二乘法、谱聚类、原型值函数、潜在语义索引和排序

与任何棋盘游戏一样，为了将 PCA 重新设计为游戏，我们需要制定一套规则和目标让玩家遵循。设计此类游戏的方式有很多种;，重要的设计理念源自 PCA 本身最佳解决方案由特征向量组成，而特征向量捕获数据中的重要方差并且彼此正交。

图 2 每个玩家都希望与最大方差(数据传播范围更大)的方向保持一致，但也希望与层次结构(编号较低的所有玩家)中的高层级的玩家保持垂直

在 EigenGame 中，每个玩家都控制一个特征向量。玩家通过解释数据中的方差来提高得分，但如果他们与其他玩家过于相似，则会受到惩罚。我们还建立了一个层次结构玩家 1 只关注最大化方差，而其他玩家则还必须关注如何最小化与层级结构中高于自己的玩家的相似度。这种奖励和惩罚的组合决定了每个玩家的效用。

图 3 上方每个玩家的效用

通过经适当设计的方差 Var 和对齐 Align 项，我们证明了

如果所有的玩家都表现最优，他们则一起实现了游戏的纳什均衡点，而这就是 PCA 算法的解决方案。 如果每个玩家单独且同步使用梯度上升法来最大化其效用，则可实现该目标。

图 4 EigenGame 引导每个玩家沿着单位球面从空的圆圈走向平行的箭头。蓝色代表玩家 1，红色代表玩家 2，绿色代表玩家 3

这种同步上升的独立性特别重要，因为它允许将计算分布在数十个 Google Cloud TPU 上，从而实现数据和模型并行。这使我们的算法适应真正的大规模数据成为了可能。EigenGame 可以在数小时内找到包含数百万个特征或数十亿行的上百兆字节数据集的主要成分。

图 5 每个彩色正方形都是一个单独的设备。(L) 每个玩家在单个设备上运行并计算更新。(R) 将每个玩家复制到多个设备，并使用独立的一批数据计算更新;然后平均不同的更新以形成更可靠的更新方向 效用、更新及两者之间的一切

通过从多智能体角度审视 PCA，我们能够提出可扩展的算法和新颖的分析方法。我们还发现了与赫布学习 (Hebbian Learning) 存在的惊人联系，或者也可以说神经元在学习时如何调整适应。在 EigenGame 中，每个最大化效用的玩家都会产生更新方程，该方程类似于从关于大脑中突触可塑性的赫布模型中衍生的更新规则。我们已知赫布更新可以收敛到 PCA 解决方案，但不能作为任何效用函数的梯度导出。博弈论为我们提供了一个新的视角来研究赫布学习，也为机器学习问题提供了一系列的解决方法。

机器学习连续曲线的一端是提出可优化的目标函数的完善路径使用凸优化和非凸优化理论，研究人员可以对解决方案的整体性质进行推理。而在另一端上，则直接指定了受神经科学启发的纯联结主义方法和更新规则，这可能增加了对整个系统的分析难度，常常需要研究复杂的动力系统。

像 EigenGame 这样的游戏理论方法则介于两者之间。玩家更新将不受限于函数的梯度，而只是对其他玩家当前策略的最佳响应。我们可以自由设计具有必要属性的效用函数程序和更新，例如，指定无偏或加速的更新，确保纳什属性仍然允许我们对整个系统进行分析。

图 6 允许使用多个效用函数弥合了优化方法和动态系统之间的鸿沟

EigenGame 形象地展示了如何将机器学习问题的解决方案设计为大型多智能体系统的输出。一般而言，将机器学习问题设计为多智能体游戏是颇具挑战性的机制设计问题;，研究人员已经使用两个玩家间的这类零和博弈来解决机器学习问题。最值得注意的是，生成对抗网络 (GAN) 这一生成建模方法的成功吸引了人们对博弈论与机器学习之间关系的兴趣。

EigenGame 超越了这一点，进入了更为复杂的多玩家非零和博弈设置。这优化了并行性，从而能够支持更大的规模和速度。它还为机器学习的相关社区提供了可量化的基准，以测试新颖的多智能体算法以及更丰富的领域，例如外交风云和足球。

我们希望我们的效用和更新设计蓝图能够鼓励其他人探索设计算法、智能体和系统的新方向。我们期待未来能看到其他问题也可表述为游戏，以及我们收集的数据分析是否会进一步增进我们对多智能体的智能本质的理解。