DeepMind亲解ICLR杰出论文：博弈论作为大规模数据分析的引擎

作者 | Brian McWilliams团队

编译 | 刘冰一

在ICLR 2021（国际表征学习大会）上，Brian McWilliams团队展示的“ EigenGame: PCA as a Nash Equilibrium”获得了杰出论文奖。

这篇论文提出了一种天然并行化的随机梯度上升方法 EigenGame（特征值博弈），结合了 Oja 规则、Krasulina 矩阵和 Riemannian 优化方法的优点，来计算Top-K主成分。其中，PCA即主成分分析算法。

这种方法为大规模矩阵的PCA计算提供了一种可扩展方法，可计算出近200 TB的 ImageNet 的 RESNET-200 激活矩阵的前32个主成分。

1 EigenGame提出机器学习问题的新解法

现代人工智能系统处理诸如识别图像中的物体、预测蛋白质的3D结构这样的任务，就像一个勤奋的学生准备考试一样，通过大量习题训练以来减少失误率，直到取得成功。这是一项孤独的努力，也是机器学习中通用的训练学习方式。

人们可以通过与他人互动、玩耍来进行学习，一个人独自解决极其复杂的问题并不常见。通过让求解问题具备类似游戏的互动特质，DeepMind已经成功训练了人工智能玩“夺旗”一类的游戏，还在“星际争霸”中达到了大师级水平。这使研究人员想了解：以博弈论的视角看待模型，能否帮助解决其他基本的机器学习问题。

本篇论文中，Brian团队探索了一种新的方法来解决一个老问题：将特征主成分分析（Principal Component Analysis，PCA）问题（一种特征值问题）重新表述为一个竞争性的多主体博弈，将其称之为特征值博弈（EigenGame）。其中每个近似特征向量都由一个玩家控制，其目标是最大化函数的效用。

该文发现，利用最新的计算资源，多主体视角建模带来了新的洞察力和算法。这使研究能扩展到曾经需要海量计算资源的数据集上，并为以后的探索提供了一种替代方法。

2 作为纳什均衡点的 PCA

主成分分析（PCA）在20世纪初期首次被提出，是一种通过最大化每个维度的方差来将较高维度空间中的数据投影到较低维度空间中的方法。它是高维数据处理流水线的第一步：通过数据聚类，让数据降维、集群和可视化变得容易；同时也使得在分类及回归任务中，学到数据的低维表征成为可能。

主成分分析通常被表述为一个最优化问题(或单主体问题) ，最初主成分分析是手工记录在纸质稿页上，随后储存在数据仓库的计算中心。但随着数据集的增大，这种常见的计算方法已成为计算瓶颈。研究人员已引入随机算法以及其他方式，来改进大数据集上 PCA 算法的性能。然而，研究者发现这些方法很难扩展到大规模数据集，无法利用为深度学习准备的硬件资源，例如大规模并行的GPU和TPU。

其次，PCA 与许多重要的机器学习和工程问题一样，需要共同的解决方案，即奇异值分解分解（singular value decomposition）。通过用正确的方式处理 PCA 问题，该研究提出的算法可以更广泛地应用于机器学习树的各个分支。

图1：知识树以奇异值分解为基础，包含了诸多机器学习任务，如PCA、最小二乘法、 谱聚类、原始值函数、潜在语义索引和排序。

和任何棋盘游戏一样，为了将 PCA 重新定义为一种游戏，研究人员需要制定一套规则和目标供玩家遵循。设计此类游戏博弈的方式有很多种，但是，重要思路来自主成分分析本身: 最佳解决方案由特征向量组成，特征向量捕获数据中的最大方差，并且彼此垂直正交。给定二维，三维或更高维空间中的点集合，可以将“最佳拟合”线定义为最小化从点到线的平均平方距离的线。可以从垂直于第一条直线的方向类似地选择下一条最佳拟合线。重复此过程会产生一个正交的基础，其中数据的不同单个维度是不相关的。这些基向量称为主成分。

图2：每个玩家都希望对齐方向的差异最大（更大的数据扩展），但也要保持与层次结构中的其他玩家（所有较低编号的玩家）呈现正交垂直状态。

在EigenGame中，每个玩家控制一个特征向量。玩家通过解释数据中的差异来提高他们的得分，但如果他们与其他玩家过于接近，则会受到惩罚。团队还建立了一个层次结构: 玩家1只关心方差的最大化，而其他玩家也不得不担心最大化方差、以及最小化时，与层次结构中编号较低的玩家的一致性。奖励和惩罚的结合起来定义了每个玩家的收益效用。

图3：玩家参与EigenGame游戏的收益效用函数。

通过适当设计的方差（Var）和对齐（Align）术语，论文作者证明:

• 如果所有玩家都发挥最佳状态，那么他们将共同实现游戏的纳什均衡点（Nash equilibrium），这就是PCA算法的解决方案。
• 如果每个玩家都独立且同时使用梯度上升最大化其效用，最优点目标则可能实现。

图4：EigenGame引导每个玩家在单位球面上，沿着空圆圈路径到箭头位置（代表找到特征向量）。蓝色、红色和绿色分别代表不同玩家。

图5：每个玩家 i 的效用函数取决于编号比TA小的玩家，这里用有向无环图来表示。每个编号更低的玩家必须以固定的顺序比对其它玩家传播它的当前向量。

天然并行化的同步梯度上升特别重要，因为这种特质允许将计算分布在数十个Google Cloud TPU上，从而实现数据和模型并行运行。这使该文算法有可能适应真正的大规模数据。EigenGame可以在几小时内找到包含数百万个特征，或数十亿行的字节数据集中的主成分。

图6：EigenGame并行计算示意图：每个彩色方块都是一个独立主体。每个主体在单个独立设备上的计算更新；随之，每个主体被复制到多个设备，并使用独立批次数据计算更新；然后，平均复制后的更新主体，以形成更强大的更新方向。

3 实用程序、更新以及介于两者之间的所有内容

通过从多智能体的角度思考 PCA，我们能够提出可拓展的算法和新颖的分析。我们还发现了与赫布法则（Hebbian Learning，一种神经科学理论，解释了在学习过程中脑神经元所发生的变化。）之间令人惊讶的联系。在 EigenGame 中，每个玩家发挥最大效用的过程中都会产生更新方程，该方程类似于赫布法则中大脑中可塑神经元的突触，不断习得规训并保持更新。已知赫布法则更新的结果可以收敛到PCA解决方案，但并不能导出任何效用函数及其梯度。博弈论为研究者提供了一个新的视角审视赫布法则，也为诸多机器学习问题的解决提供助益。

机器学习，存在一个连续的曲线，其一端是提出一个可优化的目标函数路径: 利用凸和非凸优化理论，研究人员可以对解决方案的整体性质进行推理。另外一端上，是由神经科学引发的纯联结主义方法——例如赫布式的连接更新法则，但是对整个系统的分析可能会更加困难，通常会调用复杂的动力学系统。

像EigenGame这样的游戏理论方法介于两者之间，玩家更新不限于功能的梯度，只是对其他玩家当前策略的最佳响应。玩家可以自由设计公用程序和更新需要的属性(例如，指定无偏差加速或更新) ，同时确保主体游戏符合纳什均衡这一特性，仍然允许玩家对系统进行整体的分析。

图7: 多主体建模的视角，为基于优化和基于连接主义这两种机器学习的模式搭建了沟通的桥梁。

EigenGame代表了“将机器学习问题的解决方案设计为大型多智能体系统输出”的具体示例。一般而言，将机器学习问题设计为多主体博弈是一个具有挑战性的机制设计问题，研究人员已经使用两人零和博弈来解决机器学习问题。最值得注意的是，作为生成建模方法的对抗生成网络（GAN）的成功，激发了人们对博弈论与机器学习之间关系探索的兴趣。

EigenGame超越了两人零和博弈，进入了更复杂的多玩家、正和博弈的设置。这样可以使算法具有更明显的并行性，实现更大的运算规模和速度。它还为机器学习研究者提供了一个可量化的基准，以在更广阔的领域测试新的多主体算法，如外交和足球。

该文研究人员希望经由EigenGame，鼓励更多人探索设计新算法、智能主体和智能系统方向。期待看到其他问题得以解决、以及希望该研究进一步增进人们对多智能体本质的理解。

更多细节，请参阅团队论文 《 EigenGame: PCA as a Nash Equilibrium》，以及团队后续工作《EigenGame Unloaded: When playing games is better than optimising》。

原文链接：https://www.deepmind.com/blog/article/EigenGame

论文地址：https://openreview.net/forum?id=NzTU59SYbNq