主要内容：
目标：对用户的贡献进行评估，主要是为了激励机制打基础，根据用户的贡献，发放对应的奖励。
问题：Shapley值计算成本巨大，难以应用。
想了解shapley推荐学习一下这篇文章，讲的很好，很好理解 添加链接描述
这篇文章解决思路：
1）通过梯度计算Shapley减少计算量，不用重新训练数据
2）设计了一种截断的抽样方法，减少排列组合数（我的理解），基于Monte-Carlo estimation的基础上进行
Introduction 部分主要介绍了一下背景和SV（Shapley Value）
---- 这个地方展现出了本文的贡献了
1、主要方法1：通过梯度聚合减少计算
2、主要方法2：减少排列组合数，过去是随机抽样，本文是有重点的基于单轮特征的抽样 Monte Carlo sampling technique基础上进一步改进
具体方法：1、注意抽样时，抽样排列组合中节点的位置，如果抽到的组合中节点的位置总是考后的，这样计算出来的贡献会较少。（实验证明后加入的节点往往贡献较低）
Related Work
这个我觉得挺好，记录下来。
现有的FL学习贡献评估方法，大致分为：1）自我报告 2）个人表现 3）utility game 4）基于Shapley Value 的方法
接下来就是就这四个方法分别进行介绍
因为我主要关注的是他的模型方法到底是如何构建，解决改问题的，所以没有仔细阅读，感兴趣的可以细读。嗖嗖嗖又翻过去2页，这种感觉太爽了，哈哈哈~
因为本文的方法就是基于shapley值方法，所以到这
2.4 FL Participant Contribution Evaluation via Shapley Value
我仔细看了一下，一般来说related work最后引用的几篇paper都是该文在这个基础上进行的更新，因此理解一下这几篇paper表达的内涵，也会更好的理解这篇paper想要做什么，以及如何做，改进在哪里
这里面多次提到Monte-Carlo (MC) estimation，我不太了解，所以不太懂在做什么，因此我去搜索了一下，该方法到底能做什么
MC方法指的是一个概念，即利用随机采样去逼近真实解，我们利用模拟中子运动来全面了解蒙特卡洛方法如何在实际中应用。 Monte Carlo 方法
通过这篇博客我了解到MC就是用来随机采样的，也和该paper之前提到的选择部分排列组合进行训练对应上了。那我们现在就该去了解，这篇paper怎么在原有抽样采用的基础上进行改进了。
继续
2.5 FL Participant Contribution Evaluation via Gradient Shapley Techniques
这部分就是说Shapley Value 要基于梯度进行计算。
3 PRELIMINARIES
有以下几个公式，我们一起来看一下
梯度更新
FedAvg更新FL模型：
Shapley Value
采用蒙特卡罗估计方法，近似的Shapley值
再次澄清，我比较愚
钝，可能大家很简单就懂得，我就不太容易理解，敬请谅解哈
这个公式最开始我就不能理解Π是什么意思，因此我找到了该paper引用的原文 这个paper
Let Π be the uniform distribution over all n! permutations of data points。因此小Π服从均匀分布。 这个i就是值我们要求的那个节点的位置，比如ABC，我们想求A当 A在第2位的时候 BAC，i=2，SiΠ = B 就是这样，同理i=1,3也是这样，当然看具体规则i是从0开始计数，还是1开始计数。
现在我们了解了该paper所借鉴的别人的方法，现在我们来看一下该paper的方法。
4 THE PROPOSED APPROACH
这个图挺清晰的，但是具体的内容还是给看一下。
其实读到这，加上第一次浅看，我觉得这篇paper主要就是提供了如何给与相对公平的比如抽样的排列组合中节点位置不能太靠前太靠后这种，并且抽样排序大小要和每轮参与的节点数挂钩，不同太大或太小。
现在我们具体的来看一下。
首先通过梯度，来计算value，这里我很好奇使用梯度的什么值来作为value，是准确率还是召回率还是其他的这类的。
4.2 Guided Truncation of Model Evaluation
1）放弃低边际效用增益的轮
2）根据参与者参与位置，比如最靠后的收益很小，可以忽略
3）确保参与者有公平的机会在多个排列中占据不同的位置
提出了一种引导抽样策略，以公平地将FL参与者分配到多个排列的不同位置。
4.3 The GTG-ShapleyAlgorithm
终于！终于！到算法了，前面铺垫了那么多，现在让我们具体看看算法吧。
.第1-2行显示了两个输入模型的参数初始化和性能评估。
第4行，如果该轮的效益不大于预定义的阈值，整轮忽视，不进行计算，GTG Shapley为每个参与者返回0。
否则评估t轮的Shapley Value。
第5行是收敛判断，若认为Shapley Value 在继续计算也不会有多少改变了，就停止计算，达到收敛。
第6行，是进行计数
第7行：是根据guided sampling进行加以引导的参与者排序，例如先是第一位排序必须是按照顺序排序
比如ABC 然后下一个先是B BCA 然后是C CBA这种，这种是前１为固定顺序，前两位固定顺序也是，
比如ＡＢＣＤ 前两位固定排序两个的组合有AB、AC、AD、BA、BC、BD、CA、CB、CD、DA、DB、DC、 这样的话可以按照前两位排序 AB BC CD DA AC BD CA DB AD BA CB DC 类似于这种，后面的就可以随机组合了，因为后面的排序并不影响Ｓｈａｐｌｅｙ值的计算。
第八行就是初始的权重，因为比如只要A的时候，我们需要将A和这一轮的储时权重进行比较，看贡献度，因为是在上一轮的基础上进行训练的
第10行：这个就是依次计算n个节点的贡献度了
第11行：就是判断，如果贡献过小就截断，默认没有贡献，所有跳转到第16行，比如V{ABC} =V{AB}
这样计算18行的时候减完就是0了
第12行就是，为了计算权重准备的，比如Π={ABC} C={A,B,C} 当j=1的时候就是{A} j=2的时候就是{A,B}
第13行：就是聚合权重，得到几个节点共同创造的价值
第14行：就是计算其价值了V{ }
第18行就是分别计算节点的贡献度了，例如当Π={ABC} 时，j=1时，得到A的SV j=2时得到 B的SV j=3时得到C的SV 同理 Π={BCA}时 j=1得到B的SV j=2时得到 C的SV j=3时得到A的SV (这个地方最开始我就懵了一下)
好啦，基本上就完成啦，然后就可以得到每个节点的SV了
这里在最后说一下，为什么要用（k-1）/k **** + 1/k 这种公式，我觉得需要进一步查阅资料，我就先不查阅啦，不过我验算了一下，的确这样做和直接计算SV得到的值是一样的，这时不由赶趟数学的博大精深啊！
下面一部分就是复杂度分析和实验了了，复杂度这个地方对于我来说一直是个痛点，我就先不看了，看了的话，我在进行补充啦！ 实验小伙伴们页自己去体会一下吧~
通过算法这部分其实我体会到的就是，该paper主要新增的一个特性就是， guided sampling 了，再有就是结合权重计算和抽取样本的思想，不知道我的理解有误没，如果存在问题欢迎小伙伴们进行留言~
本文全篇基于个人理解，由于想的不够深入，以及英语水平有限，可能有理解错误的地方，尽情谅解。