机器之心专栏
作者：卞亚涛
腾讯AI Lab与瑞士苏黎世联邦理工学院合作，提出了基于能量学习的合作博弈新范式，为可解释性等机器学习中的估值问题提供了新的理论和方法。论文已被ICLR 2022收到。
近年来，估值在机器学习中变得越来越重要。一些典型的评估问题包括可解释性的特征属性、合作学习的数据评估和集成学习的模型评估。为这些应用开发合理有效的估值算法是非常重要的。因此，腾讯AI实验室与瑞士苏黎世联邦理工学院联合发表论文《Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning》，共同提出了基于能量学习的合作博弈新范式，为可解释性等机器学习中的估值问题提供了新的理论和方法。
该论文已在《ICLR 2022:
论文链接：https://openreview.net/forum? id=xLfAgCroImw
项目主页：https://valuationgame.github.io/
1.引言：合作博弈的估值问题和最大熵概率分布。
估值在各种机器学习应用中越来越重要，从特征解释(Lundberg和Lee，2017)，数据估值(Ghorbani Zou，2019)到集成模型估值(Rozemberczki Sarkar，2021)。它们通常表示为合作博弈中的玩家估价问题。典型的合作博弈
由N个玩家N={1，n}和成本函数(也称为特征函数)
组成，其中价值函数描述了任何联盟的集体收入。
比如数据估值(Ghorbani Zou，2019)在合作博弈中通常表现为玩家估值问题。玩家估价问题的目的是估计这个合作博弈中每个玩家的价值。如图1所示，典型的数据估计问题使用N个训练样本。
，来执行某种机器学习任务：一个训练样本对应一个玩家，此时代价函数F(S)通过训练子集S中的训练样本来表示所得到的模型在给定测试数据集上的预测器性能，这样，样本点的估值就变成了合作博弈中的玩家估值问题。
图1典型的数据估算过程
本文研究合作博弈。
概率之道。这就使得统一学习和推送成为可能，并且会与经典的估值方法相关联。具体来说，我们寻求一组概率分布p(S)来度量特定子集S的出现概率。
在所有可能的概率质量函数中，我们应该如何构造一个合适的p(S)？我们选择熵最大的那个。
的概率分布。这种设计是恰当的，因为最大化熵将最小化构建到分布中的先验信息，即，对未知做出任何假设，并选择最“均匀”的分布。现在，寻找合适的概率分布p(S)变成了下面的约束优化问题：
假设每个联盟S都有一个收益F(S)，它与一个概率p(S)相关联。我们寻求最大化熵H(p)=-
，同时满足约束条件。
和。
为了解决这个优化问题，我们得到最大熵分布的形式为：
其中T0是温度参数。这是能量模型假设的最大熵分布。
基于能量的学习的上述优点如下：I)在监督下，它可以通过可以学习的有效训练技术来学习成本函数F(S)，例如噪声对比度估计(Gutmann Hyv rinen，2010)和分数匹配(hyv rinen，2005)。Ii)近似外推技术，如变分外推或抽样，可用于解决估价问题。具体来说，它可以进行均值场变分推断，其中推断出的世代分布参数原则上可以作为球员估值。
基于学习的平均场变分推断的另一个优点是，我们可以直接建立它与经典估值标准的联系。具体地说，通过仅仅进一步的不动点迭代来最大化平均场目标，我们恢复了经典的评价标准，例如Shapley值(Shapley，1953)和Banzhaf值(Penrose，1946；班扎夫三世，1964年).这一观察进一步支持了现有的方法，因为它们都通过平均场方法来解耦玩家之间的相关性。通过多步不动点迭代，我们得到了一系列的估计轨迹，在这些轨迹中，我们将具有最佳可想象解耦误差的估计定义为变分指标。
我们的主要贡献可以总结如下：
我们提出了一个基于学习的理论合作博弈。通过平均场推理，我们为流量的博弈论估值方法提供了一个统一的视角。这就通过解耦的观点为现有的标准提供了另一个动力，即通过平均场方法解耦N个玩家之间的相关性。为了获得良好的解耦性能，我们使用多步不动点迭代产生一系列变分估计。它们都满足一套博弈论公理，这是适当的估值标准所必需的。我们将具有最佳解耦误差的估计定义为变分指标。大量实验证明了我们提出的变分估计的优良特性，包括低解耦误差和良好的估计性能。二。背景
1.现有的球员估价方法
目前采用博弈论中经典的估值方法，如Shapley值)(Shapley，1953)和Banzhaf值(Penrose，1946，Banzhaf III，1964)。shapley值赋予参与人I的估价是：
其中|S|代表联盟S的玩家数量，可以看出它在n/2规模的联盟上的权重很小。
班夫价值赋予参与人I的估价是：
它对所有联盟使用统一的权重。
2.机器学习中的估值问题
目前，大多数类型的估值问题(Lundberg Lee，2017；Ghorbani Zou，2019；Sim等人，2020；Rozemberczki Sarkar，2021)使用Shapley值作为估价标准。随着可解释机器学习在过去几十年的快速发展(泽勒弗格斯，2014；里贝罗等人，2016；伦德伯格李，2017；Sundararajan等人，2017年；Petsiuk等人，2018；Wang et al，2021a)，基于属性的解释旨在为给定黑盒模型m的特定数据实例(x，y)的特征赋予重要性，每个特征映射到游戏中的玩家，代价函数F(S)通常是模型的响应，如子集S中的特征馈入模型时分类问题的预测概率。典型的数据估计问题使用N个训练样本N=
，来执行某种机器学习任务：一个训练样本对应一个玩家，此时，代价函数F(S)通过训练子集S中的训练样本来表示所获得的模型在给定测试数据集上的预测器性能，综合模型评估(Rozemberczki Sarkar，2021)度量集合中单个模型的重要性，其中每个预训练模型映射到一个玩家，代价函数度量模型子集的预测性能。
3.方法介绍：合作博弈中玩家估价的解耦视角。
对于合作博弈的概率分布，等式(1)所示的概率分布在所有可能的分布中达到最大熵。人们可以很自然地把合作博弈中的玩家估值问题看作是一个解耦问题：一个博弈中的n个玩家可能以非常复杂的方式任意关联。然而，为了给它们中的每一个分配单独的重要性值，我们必须分离它们的交互，这可以被视为简化它们的相关性的一种方式。
因此，我们考虑世代分布q(S；x).q(S；x)它必须简单，因为我们打算解耦N个玩家之间的相关性。一个自然的选择是把q(S；x)被限制为完全可分解的，这导致p(S)的平均场近似。q(S；x)的最简单形式是N独立伯努利分布，即。
接下来，我们最小化q(S；x)和p(S)来近似原始最大熵分布p(S)。
1.脱钩观点的目标函数
接下来，我们将两个分布之间的距离定义为kull back-lei bler散度，从而恢复了平均场推断方法。接下来，导出平均场方法的目标函数。
鉴于公式(1)中的最大熵分布，经典的平均场推断方法旨在分布q(S；x)来近似p(S)，通过最小化由q和p之间的kull back-lei bler散度测量的距离。因为
对与错，我们有：
在上面的公式中，
表示概率分布的熵。重新组织上面的公式，得到：
ELBO代表证据下限。
这是这个合作博弈的多线性扩展：
从上面的推导，我们得到解耦透视的目标函数，也就是公式(2)中的ELBO目标函数。
2.从解耦角度看变分估计的全梯度平均场算法。
为了计算变分估计，我们首先分析目标函数(2)的平衡条件。
对于坐标I，多线性扩展
的偏导数是
，对于熵项，它的偏导数是。通过将方程中总体的偏导数设置为0，我们得到如下平衡条件：
这个均衡条件意味着不可能通过改变分配给任何参与者的值来进一步提高整体解耦性能。这也意味着我们应该使用下面的定点迭代来更新每个玩家的估价：
基于以上分析，我们提出以下采用全梯度算法的平均场影响。流程如下：
这个算法产生的估计值满足一些博弈理论。它需要一个初始的边缘方向。
和迭代次数K.k次定点迭代后，返回估计的边际值。
通过将算法1作为子模块，我们可以将新的K步变分估计方法定义为：
第四，理论分析
我们可以证明，提出的K步变分估值一方面可以恢复经典估值算法，另一方面满足三个基本估值公理。
1.恢复经典的估计算法。
令人惊讶的是，经典的估价标准可以通过建议的K步变分估价来恢复。首先，很容易推导出Banzhaf值：
这是在0.5*1处初始化的一步变分估计。我们还可以通过连接多线性扩展来恢复Shapley值(Owen，1972；Grabisch等人，2000年):
其中的积分表示沿着单位超立方体的主对角线的积分多线性扩张的偏导数。附录D给出了独立的证明。
这些结论为这两个经典的评价指标提供了一个新颖而统一的解释：Shapley值和Banzhaf值都可以看作是通过一步不动点迭代来逼近ELBO目标解耦的变分指标。具体来说，对于Banzhaf的值，它将x初始化为，并运行定点迭代。对于Shapley值，它还执行定点迭代。然而，它从单个初始点开始，但是通过方程中的线积分平均所有可能的初始化值。
2.满足三个基本估值公理。
我们的能量学习框架引入了一系列由t和步数K控制的变分估值，我们可以证明提出的K步变分估值满足三个基本假设：零玩家、边缘主义和对称性。详细的证明在论文的附录E中。
动词（verb的缩写）实验结果
在实验过程中，我们试图解决以下两点：1)与其他估计方法相比，提出的变分估计方法是否具有较低的解耦误差？2)与经典估值标准相比，我们的变分指数是否能受益？
1.数据评估实验
我们根据Ghorbani Zou (2019)的设置重用了https://github.com/amiratag/DataShapley的代码。数据剔除：将训练样本按照同一个标准返回的估计值进行排序，然后剔除样本，以便检验测试精度下降了多少。直观来说，最好的估计算法会导致最快的性能下降。
图2中的结果表明，在某些情况下，变分指数达到最快的下降速率。它总是达到最低的去耦误差(如每个图中的图例所示)。有时变分指数和Banzhaf表现出相似的性能。我们估计这是因为Banzhaf值是变分指标的一步近似，对于所考虑的具体问题，一步不动点迭代后解的排序会发生变化。
2.特征归因/归因实验
我们遵循Lundberg Lee (2017)的设置，并在MIT许可下重用https://github.com/slundberg/shap的代码。我们在成人数据集上训练分类器，它根据人口普查数据预测成人的收入是否超过5万美元。
特征移除结果：本实验遵循与数据移除实验类似的方式：我们按照返回准则定义的顺序逐一移除特征，然后观察预测概率的变化。图3报告了三种方法。第一个显示来自xgboost分类器的结果(精度：0.893)，第二个显示逻辑回归分类器(精度：0.842)，第三个是多层感知器(精度：0.861)。对于概率下降的结果，变分指数通常引起最快的下降，它总能达到最小的解耦误差，正如其平均场性质所期望的那样。
从瀑布图可以看出，这三个标准确实产生了相同的特性排名。举第一个例子：所有标准都把“资金损失”和“关系”作为前两个特征。但其余特征排名相同：Variational Index和Banzhaf表示“婚姻状况”应该排在第三位，Shapley排在第四位。很难说哪个排名最好，因为：1)没有黄金标准来确定特性的真实排名；2)即使有一些“完美模型”的基本事实排名，这个经过训练的xgboost模型也不一定能复制出来，因为它可能与“完美模型”一致。
不及物动词结论和未来工作
介绍了一种基于学习能力的合作博弈方法来解决机器学习中的一些估值问题。未来值得在以下几个方向探索：1)选择温度t .控制温度公平性的高低，因为那时所有参与者的重要性相等，那时参与者的重要性为0或1。2)给定概率合作博弈的设定，自然要给玩家加入先验知识，对多领域知识进行编码。3)在基于能量学习的合作博弈框架中探讨一群玩家的互动是非常有意义的，有助于研究导致多个玩家联盟的“互动”指数。
一些参考
【戈尔巴尼邹，2019】a .戈尔巴尼和j .邹。数据沙普利：机器学习数据的公平估价。在机器学习国际会议上，第22422251页。PMLR，2019。
[沙普利，1953年] L. S .沙普利。n人游戏的一个值。对博弈论的贡献，2(28):307317，1953。
彭罗斯，1946年。多数投票的基本统计。皇家统计学会杂志，109(1):5357，1946年。
[班扎夫三世，1964年]加权投票不起作用：数学分析。罗格斯大学学报，19:317，1964年。
[Gutmann和hyv rinen，2010年]噪声对比估计：一种新的估计原理
非标准化的统计模型。第十三届国际会议记录
人工智能和统计，第297-304页。jmlr研讨会和会议记录，2010年。
[hyv rinen，2005年]a . hyv rinen。通过分数匹配估计非归一化统计模型。杂志
机器学习研究，6(4)，2005。
[明卡，2001年] T. P .明卡。近似贝叶斯推理的期望传播。《第十七届人工智能不确定性会议论文集》, 362369页，2001年。