腾讯AI Lab与ETH联合提出为可解释性等机器学习估值问题提供新方法

近年来，估值问题在机器学习中变得越来越重要。一些典型的评估问题包括可解释性的特征归因、合作学习的数据评估以及集成的模型评估。开发合理有效的估值算法对于这些应用至关重要。因此，腾讯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}和价值函数（也称为特征函数）

构成，其中价值函数描述了任何联盟S 的集体利益。

例如，数据估值（Ghorbani Zou，2019）通常被表述为合作游戏中的玩家估值问题。玩家估值问题旨在估计本次合作博弈中每个玩家的价值。如图1所示，一个典型的数据评估问题使用n个训练样本

，执行某种机器学习任务：一个训练样本对应于一名玩家。此时，价值函数F(S)表示在给定的测试数据集上使用子集S中的训练样本训练的模型的预测器。表现。利用该方法，将样本点的估值转化为合作博弈中的玩家估值问题。

图1 典型的数据评估流程

概率处理方法。这种处理使得以统一的方式进行学习和推理成为可能，并将产生与经典评估方法的联系。具体来说，我们寻找一组概率分布p(S) 来衡量特定子集S 出现的概率。

在所有可能的概率质量函数中，应该如何构造一个合适的p(S)？我们选择熵最大的一个

概率分布。这种设计是有意义的，因为最大化熵可以最小化分布中内置的先验信息量，即不对未知进行假设并选择最“均匀”的分布。现在寻求合适的概率分布p(S) 就变成了以下约束优化问题：

假设每个联盟S 都有一个与概率p(S) 相关的收益F(S)。我们寻求最大化熵H(p)=-

，同时满足约束条件

也。

解决这个优化问题，我们得到以下形式的最大熵分布：

其中T0 是温度参数。这也是能量模型假设的最大熵分布。

上述基于能量学习的处理有两个好处：i）以监督的方式，它可以通过基于能量学习的有效训练技术来学习价值函数F（S），例如噪声对比估计（Gutmann Hyvrinen，2010）和分数匹配（Hyvarinen，2005）。 ii) 可以采用变分推理或抽样等近似推理技术来解决估值问题。具体来说，它能够执行平均场变分推断，其中推断的代理分布的参数可以用作原则上的玩家估计。

基于能量学习的平均场变分推理的另一个好处是我们可以直接建立其与经典评估标准的联系。具体来说，通过仅执行一次定点迭代来最大化平均场目标，我们恢复了经典的评估标准，例如Shapley 值（Shapley，1953）和Banzhaf 值（Penrose，1946；Banzhaf III，1964）。这一观察结果也进一步支持了现有的方法，因为它们都通过平均场方法解耦了玩家之间的相关性。通过运行多个定点迭代，我们获得了一系列估计轨迹，其中我们将具有最佳可想象解耦误差的估计定义为变分指标。

我们的主要贡献可概括如下：

我们提出了一种理论上合理的基于能量学习的合作游戏方法。通过平均场推断，我们为流行的博弈论估值方法提供了统一的视角。这通过解耦的观点为现有标准提供了另一种动机，即通过平均场方法解耦n 个参与者之间的相关性。为了获得更好的解耦性能，我们运行多次定点迭代，从而生成一系列变分估计。它们都满足一组博弈论公理，这些公理对于适当的评估标准是必需的。我们将具有最佳可想象解耦误差的估计定义为变分指数。多个实验证明了我们提出的变分估计的优异特性，包括较低的解耦误差和更好的估计性能。 2. 背景

1.现有球员估值方法

目前的估值方法均采用博弈论中的经典估值方法，如Shapley值（Shapley，1953）和Banzhaf值（Penrose，1946，Banzhaf III，1964）。 Shapley 值对玩家i 的估计如下：

其中|S|代表联盟S 中的玩家数量。可以看出，它给予规模为n/2 的联盟较小的权重。

Banzhaf 值分配给玩家i 的估计值是：

腾讯AI Lab与ETH联合提出为可解释性等机器学习估值问题提供新方法

它对所有联盟使用统一的权重。

2. 机器学习中的估值问题

目前，大多数类型的估值问题（Lundberg Lee，2017；Ghorbani Zou，2019；Sim et al.2020；Rozemberczki Sarkar，2021）都使用Shapley 值作为估值标准。随着可解释机器学习在过去几十年的快速发展（Zeiler Fergus，2014；Ribeiro et al，2016；Lundberg Lee，2017；Sundararajan et al，2017；Petsiuk et al，2018；Wang et al，2021a），属性基于-的解释旨在为给定黑盒模型M 的特定数据实例(x, y) 的特征分配重要性。这里每个特征映射到游戏中的玩家，价值函数F(S) 通常是模型的响应，例如当子集S 中的特征输入模型时分类问题的预测概率。典型的数据评估问题使用n 个训练样本N=

，执行某种机器学习任务：一个训练样本对应于一名玩家。此时，价值函数F(S)表示在给定的测试数据集上使用子集S中的训练样本训练的模型的预测器。表现。集成模型评估（Rozemberczki Sarkar，2021）衡量集成中各个模型的重要性，其中每个预训练模型映射到一个玩家，价值函数衡量模型子集的预测性能。

3.方法介绍：合作博弈中玩家估值的解耦视角

对于合作博弈的概率分布，式（1）所示的概率分布在所有可能的分布中实现了最大熵。人们自然可以将合作游戏中的玩家估值问题视为解耦问题：游戏中的n 个玩家可能以非常复杂的方式任意相关。然而，为了给它们每个人分配一个单独的重要性值，我们必须解耦它们的交互，这可以被视为简化它们相关性的一种方式。

因此，我们考虑由x 中的参数控制的代理分布q(S;x)。 q(S;x) 必须很简单，因为我们打算解耦n 个玩家之间的相关性。自然的选择是将q(S;x) 限制为完全可分解，这会导致p(S) 的平均场近似。 q(S;x) 最简单的形式是n 独立的伯努利分布，即。

接下来，我们通过最小化q(S;x) 和p(S) 之间的距离来近似原始最大熵分布p(S)。

1. 解耦视角的目标函数

接下来我们将两个分布之间的距离定义为Kullback-Leibler 散度，从而恢复平均场方法（平均场推断）。接下来，推导平均场法的目标函数。

给定方程（1）中的最大熵分布，经典平均场推断方法旨在通过完全分解的乘法分布q(S;x) 来近似p(S)，通过最小化q 和p 之间的Kullback-Leibler 散度测量距离。因为

是非负数，我们有：

在上面的公式中，

表示概率分布的熵。重新整理上式，我们可以得到：

上式中，ELBO代表Evidence Lower Bound。

这是这个合作博弈的多线性扩展：

由上述推导，我们从解耦的角度推导出目标函数，即式（2）中的ELBO目标函数。

2. 从解耦角度计算变分估计的全梯度平均场算法

为了计算变分估计，我们首先分析目标函数（2）的平衡条件（Equilibrium condition）。

对于坐标i，多线性展开

的偏导数是

，对于熵项，其偏导数为。将方程中的整体偏导数设置为0，我们得到平衡条件为：

这种均衡条件意味着分配给任何参与者的价值不能被改变以进一步提高整体解耦性能。这也意味着我们应该使用定点迭代来更新每个玩家的估值，如下所示：

基于以上分析，我们提出以下全梯度平均场推断算法（Mean Field Inference with Full Gradient）。流程如下：

该算法产生的估值满足某些博弈论公理。它需要一个初始边缘向量

和迭代次数K。经过K步定点迭代后，返回估计的边际值。

以算法1为子模块，我们可以将新的K步变分估计方法定义为：

腾讯AI Lab与ETH联合提出为可解释性等机器学习估值问题提供新方法

4 理论分析

我们可以证明所提出的K步变分估值一方面可以恢复经典估值算法，另一方面它满足三个基本估值公理。

1.还原经典估值算法

令人惊讶的是，经典的评估标准可以通过所提出的K 步变分评估来恢复。首先，很容易推导出Banzhaf 值：

这是初始化为0.5*1 的1 步变分估计。我们还可以通过与多线性扩展串联来恢复Shapley 值（Owen，1972；Grabisch 等人，2000）：

其中积分表示沿单位超立方体主对角线积分的多线性扩展的偏导数。论文附录D给出了独立证明。

这些结论为这两个经典估值指数提供了一种新颖、统一的解释：Shapley 值和Banzhaf 值都可以被视为通过对解耦ELBO 目标运行一步定点迭代来逼近变分指数。具体来说，对于Banzhaf 值，它将x 初始化为并运行一次定点迭代。对于Shapley 值，它还执行一次定点迭代。然而，它不是从单个初始点开始，而是通过方程（1）中的线积分对所有可能的初始化值进行平均。

2.满足三个基本估值公理

我们的能量学习框架引入了一系列由T 和运行步数K 控制的变分估计。我们可以证明所提出的K 步变分估值满足三个基本估值公理：零玩家、边际主义和对称性。详细证明见论文附录E。

5. 实验结果

在实验过程中，我们试图了解以下两点：1）与其他评估方法相比，所提出的变分评估方法是否具有更低的解耦误差？ 2）与经典估值标准相比，我们提出的变分指数能否获益？

1. 数据评估实验

我们遵循Ghorbani Zou (2019) 的设置，并重用https://github.com/amiratag/DataShapley 的代码。我们执行数据删除：根据不同标准返回的估计对训练样本进行排序，然后删除样本以检查测试准确率下降了多少。直观上，最好的评估算法会导致最快的性能下降。

图2 的结果表明，在某些情况下，变分指数达到最快的下降速度。它始终实现最低的解耦误差（如每个图中的图例所示）。有时变分指数和Banzhaf 表现出相似的性能，我们估计这是因为Banzhaf 值是变分指数的一步逼近，并且对于所考虑的特定问题，一步定点迭代后解的排名不会改变。

2. 特征评估/特征归因实验

我们遵循Lundberg Lee (2017) 的设置，并在MIT 许可证下重用来自https://github.com/slundberg/shap 的代码。我们在Adult 数据集上训练一个分类器，该分类器根据人口普查数据预测成年人的年收入是否超过50,000 美元。

特征去除结果：该实验遵循与数据去除实验类似的方法：我们根据返回标准定义的顺序一一去除特征，然后观察预测概率的变化。图3 报告了这三种方法的行为。第一行显示xgboost 分类器的结果（准确度：0.893），第二行显示逻辑回归分类器（准确度：0.842），第三行是多层感知器（准确度：0.861）。对于概率下降的结果，变分指数通常会引起最快的下降，并且总是实现最小的解耦误差，正如其平均场性质所预期的那样。

6 结论和未来工作

一些参考资料

[Ghorbani Zou，2019] A. Ghorbani 和J. Zou。数据shapley: 机器学习数据的公平评估。国际机器学习会议，第2242-2251 页。 PMLR，2019。

[沙普利，1953] L.S.沙普利。 n 人游戏的值。对博弈论的贡献，2(28):307317，1953。

[彭罗斯，1946]L.S.彭罗斯。多数投票的基本统计数据。《皇家统计学会杂志》，109(1):5357，1946 年。

[班扎夫三世，1964] J.F.班扎夫三世。加权投票不起作用：数学分析。罗格斯大学出版社，19:317，1964 年。

[Gutmann 和Hyvrinen，2010] M. Gutmann 和A. Hyvrinen。噪声对比估计：一种新的估计原理

非标准化统计模型。第十三届国际会议论文集

人工智能和统计，第297-304 页。 JMLR 研讨会和会议记录，2010 年。

[Hyvrinen，2005] A. Hyvrinen。通过分数匹配估计非标准化统计模型。杂志