EigenGame描绘了解决基本机器学习问题的新方法
现代人工智能系统处理诸如识别图像中的对象和预测蛋白质的三维结构等任务，就像一个勤奋的学生为考试做准备一样。通过训练解决许多示例问题，它们随着时间的推移减少错误，直到取得成功。但这是一项孤独的努力，只是已知的学习形式之一。学习还可以通过与他人互动和玩耍来进行。很少有一个人可以独自解决非常复杂的问题。通过允许问题解决具有这些游戏般的特点，DeepMind此前的努力已经训练AI代理玩捉旗并在星际争霸中达到特级大师级别。这使我们想知道这种基于博弈论的视角是否有助于解决其他基本的机器学习问题。
今天在ICLR 2021（国际学习表示会议）上，我们提出了“EigenGame: PCA作为Nash均衡”，该论文获得了杰出论文奖。我们的研究探索了一个旧问题的新方法：我们将主成分分析（PCA），一种特征值问题，重新定义为我们称之为EigenGame的竞争多智能体游戏。PCA通常被形式化为一个优化问题（或单智能体问题）；然而，我们发现多智能体的视角使我们能够开发出利用最新计算资源的新见解和算法。这使我们能够扩展到以前计算要求过高的大规模数据集，并为未来的探索提供了一种替代方法。
PCA作为Nash均衡
PCA最早在20世纪初被描述出来，是一种理解高维数据结构的长期技术。这种方法现在已经普遍应用于数据处理流程的第一步，使得数据的聚类和可视化变得容易。它也是学习回归和分类的低维表示的有用工具。一个多世纪后，研究PCA仍然有令人信服的理由。
首先，数据最初是手工记录在纸质笔记本中，现在存储在仓库大小的数据中心中。因此，这种熟悉的分析已经成为计算的瓶颈。研究人员已经探索了随机算法和其他方向来改进PCA的扩展性，但我们发现这些方法在无法充分利用最近深度学习为中心的计算进展（即访问许多并行GPU或TPU）时很难扩展到大规模数据集。
其次，PCA与许多重要的机器学习和工程问题共享一个公共解，即奇异值分解（SVD）。通过正确的方法来解决PCA问题，我们的见解和算法在机器学习树的各个分支上都具有更广泛的适用性。
与任何棋盘游戏一样，为了将PCA重新定义为一款游戏，我们需要制定一套规则和玩家需要遵循的目标。设计这样一个游戏有很多可能的方式；然而，重要的思想来自PCA本身：最优解由捕捉数据中重要方差且彼此正交的特征向量组成。
在EigenGame中，每个玩家控制一个特征向量。玩家通过解释数据中的方差来增加分数，但如果他们与其他玩家过于接近，就会受到惩罚。我们还建立了一个等级制度：玩家1只关心最大化方差，而其他玩家还必须担心与他们在等级上方的玩家保持垂直。奖励和惩罚的组合定义了每个玩家的效用。
通过适当设计的Var和Align术语，我们可以得出以下结论：
- 如果所有玩家都以最佳方式进行游戏，他们将一起实现游戏的纳什均衡，也就是PCA解。
- 只要每个玩家独立且同时地使用梯度上升来最大化他们的效用，就可以实现这一点。
同时上升的独立性质非常重要，因为它使计算可以分布在数十个Google Cloud TPUs上，实现数据和模型的并行计算。这使得我们的算法能够适应真正大规模的数据。对于由数百万个特征或数十亿行组成的百万兆字节数据集，EigenGame可以在几小时内找到主成分。
效用、更新和一切之间
通过从多智能体的角度思考PCA，我们能够提出可扩展的算法和新颖的分析方法。我们还发现与Hebbian学习（即神经元学习时的自适应）有一个令人惊讶的联系。在EigenGame中，每个玩家最大化他们的效用会导致类似于大脑突触可塑性Hebbian模型导出的更新方程。Hebbian更新已知会收敛到PCA解，但并不是由任何效用函数的梯度推导出来的。博弈论给了我们一个全新的视角来看待Hebbian学习，还提出了一系列解决机器学习问题的方法。
在机器学习的连续谱的一端，是已经发展完善的通过提出可以优化的目标函数的路径：使用凸优化和非凸优化理论，研究人员可以推理解的全局属性。另一端是纯连接主义方法和受神经科学启发的更新规则，但整个系统的分析可能更困难，通常需要涉及复杂的动力系统研究。
像EigenGame这样的博弈论方法位于两者之间。玩家的更新不受约束，不必是函数的梯度，而是对其他玩家当前策略的最佳响应。我们可以自由地设计具有期望特性的效用和更新，例如指定无偏或加速的更新，同时确保纳什特性仍然允许我们对整个系统进行分析。
EigenGame是将机器学习问题的解设计为一个大型多智能体系统的具体示例。更一般地说，将机器学习问题设计为多智能体博弈是一个具有挑战性的机制设计问题；然而，研究人员已经使用了二人零和博弈类来解决机器学习问题。最值得注意的是，生成对抗网络（GANs）作为生成建模方法的成功推动了博弈论和机器学习之间的关系的研究。
EigenGame超越了这一点，进入了更复杂的多人、总和博弈的领域。这为更大规模和更快速度的明显并行性提供了可能。它还为社区提供了一个定量基准，以测试新的多智能体算法和更丰富的领域，如外交和足球。
我们希望我们设计效用和更新的蓝图能够鼓励其他人探索这个方向，设计新的算法、智能体和系统。我们期待看到其他问题是否可以被形式化为博弈，并且我们从中获得的见解是否能进一步提高我们对多智能体本质的理解。
更多详细信息请参阅我们的论文《EigenGame：作为纳什均衡的PCA》以及我们的后续工作《EigenGame Unloaded：当玩游戏比优化更好》。