type
status
slug
summary
tags
category
password
date
icon
Quantum Algorithms for Shapley Value Calculation
本文是《Quantum Algorithms for Shapley Value Calculation》的进一步扩充,有更多的数学推导,问题定义和处理方法也与之前稍有出入。
code
使用我们的量子算法来估计每个玩家的夏普利值来解决随机投票游戏。脚本还执行对一些基本数据进行分析预测。代码和结果的摘要如下所示。
本次复现主要是通过
python
语言进行复现此文件夹下的
python
脚本使用我们的量子算法来处理随机投票游戏,以估计每个玩家的 Shapley
值。 这些脚本还对预测执行一些基本数据分析。随机投票游戏和量子
Shapley
值生成随机投票游戏并使用量子算法来估计每个玩家的 Shapley 值。
那么它对预测进行一些基本数据分析。
首先引入了一些库(便于后续的操作)
定义了一些变量
numTrails
表示试验次数为32,maxEll
表示最大值为7。然后,定义了三个不同条件的列表:numPlayersCond
表示玩家数量,thresholdBitCond
表示阈值位数,roughVarianceCond
表示粗略方差。进行模拟
执行一系列模拟,计算量子和经典Shapley值,并将结果存储在
simulations
字典中。- 外层循环 (
for trialNum in tqdm(range(numTrails), desc="Current Trial"):
): - 遍历试验次数,
trialNum
从0到numTrails-1
。 - 使用
tqdm
库显示循环进度。
- 第二层循环 (
for ell in tqdm(range(1, maxEll), desc="Current Ell"):
): - 遍历
ell
值,从1到maxEll-1
。 - 同样使用
tqdm
库显示循环进度。
- 第三层循环 (
for n, thresholdBits, roughVariance in zip(numPlayersCond, thresholdBitCond, roughVarianceCond):
): - 通过
zip
函数同时遍历三个条件列表:玩家数量(n
)、阈值位数(thresholdBits
)、和粗略方差(roughVariance
)。
- 生成试验 (
trial = (n, ell, trialNum)
): - 创建一个代表试验的元组,包含玩家数量、
ell
值和试验次数。
- 生成新随机游戏 (
playerVals = vg.randomVotingGame(...)
): - 利用某个
vg
模块的randomVotingGame
函数生成一个新的随机游戏,具体细节未提供。
- 计算量子Shapley值 (
qshaps = vg.quantumVotingShap(...)
): - 利用某个
vg
模块的quantumVotingShap
函数计算量子Shapley值,使用随机生成的游戏参数。
- 计算经典Shapley值 (
cshaps = vg.classicalVotingShap(...)
): - 利用某个
vg
模块的classicalVotingShap
函数计算经典Shapley值,同样使用随机生成的游戏参数。
- 存储结果 (
simulations[trial] = (qshaps, cshaps)
): - 将计算得到的量子和经典Shapley值以试验、
ell
和条件为索引存储在simsulations
字典中。
这段代码系统地探索并记录在不同条件下的量子和经典Shapley值的变化,提供对这些值的定量分析。
(参照跑出来的结果) 用时比较长
存储结果
使用
pickle
库将之前计算的模拟结果存储到名为shapleyVoteResults.pkl
的二进制文件中。with open('shapleyVoteResults.pkl', 'wb') as f:
: 打开文件shapleyVoteResults.pkl
以二进制写入模式,使用f
作为文件对象。
pickle.dump(simulations, f)
: 使用pickle
库的dump
函数将模拟结果simulations
存储到文件对象f
中。这一步将 Python 对象转换为二进制格式以便于存储。
分析结果
用于生成一个条形图,展示不同条件下(不同玩家数量)的量子Shapley值和经典Shapley值之间的平均绝对误差的倒数(Reciprocal Mean Absolute Error)。
- 函数定义 (
def meanAbsError(qshaps, cshaps):
): - 定义了一个计算平均绝对误差的函数,该函数接收量子Shapley值 (
qshaps
) 和经典Shapley值 (cshaps
),并返回它们的平均绝对误差。
- 设置图形参数 (
plt.rcParams['figure.figsize'] = [12, 5]
): - 设置图形的大小参数。
- 创建图形 (
fig, ax = plt.subplots(1, len(numPlayersCond))
): - 创建一个子图,具有一行和列数等于
numPlayersCond
列表长度的数量。每个子图将用于表示不同玩家数量的结果。
- 循环遍历玩家数量 (
for i, n in enumerate(numPlayersCond):
): - 针对每个玩家数量,进行以下操作:
- 初始化存储结果的列表
resultsX
、resultsY
和resultErr
。 - 在每个
ell
值下,计算不同试验的平均绝对误差,并将结果存储在相应的列表中。
- 绘制条形图 (
ax[i].bar(...)
): - 在当前子图中,绘制条形图,横坐标为
ell
,纵坐标为平均绝对误差的倒数。 - 使用不同颜色的条形表示不同的
ell
值。 - 横坐标标签为
$\\ell$
,纵坐标标签为Reciprocal Mean Absolute Error
。 - 图例显示了不同
ell
值的颜色对应关系。
- 设置图形标题和标签 (
ax[i].set_title(...), ax[i].set_xlabel(...), ax[i].set_ylabel(...)
): - 为每个子图设置标题、横坐标标签和纵坐标标签。
- 调整子图布局 (
plt.tight_layout()
): - 调整子图布局,以确保它们适当排列在图形中。
- 显示图形 (
plt.show()
): - 显示生成的图形。
通过条形图清晰展示了在不同玩家数量条件下,量子Shapley值和经典Shapley值之间的平均绝对误差的倒数。
然后可以便于理解在不同情境下两种Shapley值的差异。
在上图中,我们为每种条件生成了 32 个随机加权投票游戏。 对于每种情况,我们生成随机权重 ,使得。
主要场景有3种:
(1)4名玩家,投票门槛q=8;
(2)8名玩家,投票门槛q=16;
(3) 12名玩家,投票门槛q=32。
对于每个场景,我们使用各种 ‘s的量子算法来近似每个玩家的 Shapley 值,假设 接下来,我们使用绝对误差将每个近似 Shapley 值与其真实值进行比较。 最后,我们取每个条件下每个随机游戏中所有沙普利值误差的平均值的倒数。
最后使用
plot.py
跑出来的最后的数据这段代码包含了一些函数和主程序,用于生成一个包含多个子图的图形,展示了二项式函数的面积逼近过程。以下是代码的详细解释:
binomialFunct
函数:- 接受两个整数参数
n
和m
,返回一个二项式函数的匿名函数,表示二项式分布的概率质量函数。
plotFunction
函数:- 接受一个函数
funct
,一个图形对象ax
,以及可选的横坐标范围和分辨率参数。 - 使用
numpy
生成横坐标x
,计算纵坐标y
,然后在图形上绘制函数曲线。
getSamples
函数:- 接受一个函数
funct
,可选的是否进行平移的参数shift
,横坐标范围和分辨率参数。 - 生成并返回按照指定参数采样的函数值。
plotApproxArea
函数:- 接受一个函数
hFunct
,一个图形对象ax
,采样点、条形宽度、横坐标范围和分辨率等参数。 - 在图形上绘制采样点和近似的面积条形图。
initAxBinomialArea
函数:- 接受一个函数
funct
,图形对象ax
,面积逼近的分辨率参数areaRes
和函数曲线的分辨率参数functionRes
。 - 通过调用其他函数,初始化并展示图形中的二项式函数及其面积逼近过程。
- 打印估计的面积、真实的面积和它们之间的相对误差。
main
函数:- 设置初始参数和绘图布局。
- 调用
initAxBinomialArea
函数生成多个子图,每个子图展示了不同分辨率下的面积逼近情况。 - 显示生成的图形。
这段代码用于演示如何通过条形面积逼近方法来近似二项式函数的曲线下面积,并在不同分辨率下展示逼近过程。
- 作者:fufu酱
- 链接:https://csfufu.life/article/d1b37e4e-b4e5-4b51-83a1-32d8343d98b4
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
相关文章