Deepmind最新成果：博弈论视角下的主成分分析

原创 Ian Gemp等 集智俱乐部 收录于话题#复杂科学前沿202165个

导语

来自Deepmind 的论文“EigenGame: PCA as a Nash Equilibrium”获得了ICLR2021年的杰出论文奖，该文通过多主体建模，用一个全新的视角，审视了数据降维中常用用的主成分分析法（PCA）。

Brian McWilliams、Ian Gemp、Claire Vernade | 作者

郭瑞东 | 译者

赵雨亭 | 审校

邓一雪 | 编辑

1. 从单主体智能到多主体建模

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

人类的学习是通过与他人互动与玩耍来进行的。一个人独自解决极其复杂的问题是很少见的。通过让求解问题具备类似游戏的互动性， DeepMind 已经成功训练了人工智能进行 Capture the Flag 游戏，并在星际争霸中达到人类大师的水平。这使研究人员想知道，以博弈论的视角看待模型，可否帮助解决其他基本的机器学习问题。

主成分分析（Principal Component Analysis，PCA）于20世纪初期被提出，是高维数据处理流程中的第一步：通过数据聚类，让数据降维和可视化变得容易；同时也使得在分类及回归任务中，学到数据的低维表征成为可能。在 Deepmind 的论文中，研究人员将主成分分析重新表述为一个竞争性的多主体博弈，将其称为特征值游戏（EigenGame）。

主成分分析通常被表述为一个最优化问题（或单主体问题）。然而，该文提出，多主题建模带来了新的洞察力和算法：利用最新的计算资源。这使主成分分析能够扩展到以前需要太多计算资源的大规模数据集，并为未来的探索提供了一种替代方法。

最初的主成分分析，是由纸和笔完成的，之后转移到数据仓库的计算中心。但随着数据集的增大，这种常见的计算方法已成为计算瓶颈。研究人员已探索使用诸如引入随机化等方式，来改进大数据集上 PCA算法的性能。然而，这些方法，研究者发现其无法利用为深度学习准备的硬件资源，例如大规模并行的GPU和TPU。

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

图1. 一系列的机器学习任务，例如 PCA、最小二乘法、 谱聚类（Spectral Clustering）、潜在语义索引（Latent Semantic Indexing LSI）和排序都需要 SVD为其基础。

例如，通过提取特征值，可以在社交网络上进行谱聚类，如下图所示，图像展示了根据多主体建模找到的特征向量，经过 K-means算法得出的对脸书界面的聚类可视化，其中不同颜色代表真实的分类标签，不同的花瓣代表聚类得出的结果。结果显示聚类结果中7/8的标签都能对应到真实标签。

图2. 脸书页面通过特征值游戏聚类的可视化，来源：EigenGame Unloaded When playing games is better than optimizing Fig 7

2. 特征值游戏 EigenGame 的规则

和任何棋类游戏一样，为了将 PCA 重新定义为一种游戏，研究人员需要一系列的规则和目标供玩家遵循。有许多可能的方法来设计这样一个博弈；然而，关键的思路来自主成分分析本身：最佳解决方案由特征向量组成，这些特征向量捕捉数据中，方差最大并且彼此正交的维度。

图3. 该游戏中，每个玩家都希望对齐方向的差异最大（即更大的数据传播），但也需要保持与相对其编号较低的玩家呈正交垂直。

在特征值游戏中，每个玩家控制一个特征向量。玩家通过解释数据中的差异来提高他们的得分，但是如果他们与其他玩家太接近，就会受到处罚。该游戏还建立了一个层次结构：玩家1只关心方差的最大化，而其他玩家则不得不同时担心最大化他们可解释的方差，并最小化与编号比自己低的玩家的相似度。这种奖励和惩罚的组合决定了每个玩家获得的收益函数。

图4. 玩家参与特征值游戏的收益计算法示意图

通过经过适当设计的方差（var）和对齐（align）项，该论文证明了：

1）如果所有的玩家都表现最优，他们等价于一起实现了游戏的纳什均衡点，而这就是 PCA 算法的解决方案。

2）如果每个玩家独立地使用梯度上升法，最大化他们的效用，那最优点是有可能实现的。

图5. 特征值游戏引导每个玩家沿着单位球面从空的圆圈走向平行的箭头（代表找到的特征向量）。蓝色代表玩家1。红色代表玩家2。绿色代表玩家3。

图6. 每个玩家 i 的效用函数取决于编号比TA小的玩家，这里用有向无环图来表示。每个编号更低的玩家必须以固定的顺序比对其它玩家传播它的当前向量。（来源：EigenGame: PCA as a Nash Equilibrium）

算法中，玩家能够同时独立地进行梯度上升，这一特性尤其重要，因为它允许让计算分布在几十个谷歌云的TPU上，从而实现了数据和模型的并行计算。这使得该文提出的算法能够适应真正的海量数据。特征值游戏能在数小时内为包含数百万特性或数十亿行的数据集找到主成分。

图7. 特征值游戏并行运算示意图：每个有色方块都是一个独立的主体。首先，每个主体在一个设备上计算更新；之后每个主体被复制到多个设备，并使用独立的批次数据计算更新；然后对被复制后的不同主体进行平均，以形成一个更健壮的更新方向。

3. 多智能主体，从优化到赫布法则

通过从多智能主体的角度审视 PCA，该文对可扩展到大数据集的算法进行了新颖的分析。该文还发现了一个与赫布法则（Hebbian Learning ，神经元在学习时如何调整其连接权重）的令人惊讶的联系。在特征值游戏中，每个玩家最大化他们的效用过程中，如何更新其特征，类似于赫布法则中，大脑具有可塑性的神经元的突触，如何从周围的环境习得规则。按照赫布法则，更新得出的连接会收敛到已知的 PCA 解决方案，但其中不会派生出任何效用函数及其梯度。博弈论为研究人员提供了一个新的视角来看待赫布法则，同时也为一系列机器学习问题提出了解法。

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

如何看待机器学习，存在一个连续的曲线，其一端是提出一个可优化的目标函数：利用凸和非凸优化理论来解决问题，该方向可以找出解决方案的整体性质。而在另一端上，是由神经科学引发的纯联结主义方法——例如赫布式的连接更新法则。但该方法会使得对整个系统的分析更加困难，常常需要对系统的复杂动力学进行研究。

像特征游戏这样的基于博弈论的方法介于两者之间。玩家的更新不受限于某个特定函数的梯度，只是对其他玩家当前策略的最佳反应。每个人可以自由地设计效用函数程序，以及更新中所需的特定属性（例如，指定特定方向上的进行无偏的更新，或某方向的更新需要加速）；同时， 多主体游戏符合纳什均衡这一特性，仍然允许玩家对系统进行整体的分析。

特征值游戏代表了一个通过设计多主体游戏，来解决机器学习问题的具体例子，其解决方案，是一个大型多智能体系统的输出。一般来说，将机器学习问题设计为多智能体博弈是一个具有挑战性的机制设计问题，然而，研究人员已经利用两人间的零和博弈，来解决机器学习问题。最值得注意成果就是生成性对抗性网络（GANs）这一建模方法的成功。这推动了人们对博弈论与机器学习之间关系的兴趣。

特征值游戏超越了两人间的零和游戏，其采用了更复杂的多玩家，正和博弈的设置。这使得算法具有了更好的并行性，从而可实现在更大数据集上的可扩展性和速度优势。它还为机器学习研究者提供了一个可量化的基线，以测试新的多主体建模在更丰富的领域——如外交和足球上的应用。

该文作者希望能经由特征值游戏，鼓励其他人探索设计算法、智能主体和智能系统的新方向。期待未来能找出还有什么其他问题，可以被定义为游戏。同时希望该研究能进一步提高人们对多智能体的智能本质的理解。

来源：

https://deepmind.com/blog/article/EigenGame

复杂科学最新论文

集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「集智斑图」推送论文信息。扫描下方二维码即可一键订阅：

原标题：《Deepmind最新成果：博弈论视角下的主成分分析》

阅读原文