Shapley Value，shapley的局限性，异质性，差分隐私

Shapley Value（夏普利值）

Shapley值是各种各样具有不同良好性质的解中最重要的一种

它将成本或者收益按照所有的边际成本进行分摊,即每个参与人获得的利益等于参与人对所有联盟的边际贡献的平均值

Shapley是满足匿名性、有效性、可加性和虚拟性四个性质的唯一的解

• 合作博弈

博弈根据是否可以达成具有约束力的协议，分为合作博弈和非合作博弈。合作博弈是指一些参与者以同盟、合作的方式进行的博弈，博弈活动就是不同集团之间的对抗。 合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。合作博弈采取的是一种合作的方式，或者说是一种妥协。 合作博弈亦称为正和博弈，是指博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害，因而整个社会的利益有所增加的。

• Shapley Value

由美国洛杉矶加州大学教授罗伊德·夏普利（Lloyd Shapley）提出。夏普利值，指所得与自己的贡献相等，是一种分配方式。

例子：

甲、乙、丙三人合作经商。倘若甲、乙合作可获利7万元，甲、丙合作可获利5万元，乙、丙合作可获利4万元，三人合作则获利11万元，每人单干各获利1万元。问三人合作时如何分配获利?

对题目，简单分析如下：

甲+乙 = 7万

甲+丙 = 5万

乙+丙 = 4万

甲+乙+丙 = 11万

甲 = 乙 = 丙 = 1万

夏普利值方法，加入了顺序的概念，并以此来判断关键加入者，和他的边际贡献。

这里发现有两种方式来算，另一种是套用夏普利值的公式来算，这一套公式可以去百度百科上看看

shapley的局限性

1. 计算量 需要知道所有合作的利润，即要定义I = { 1 , 2 , 3 , . . . , n } I=\{1,2,3,...,n\}I={1,2,3,...,n}的所有子集（2 n − 1 2^n-12 n−1个）特征函数，在世纪中难以做到

其次，公式本身计算随着节点的提升是NP难的问题

2. 优势即缺点 优势：利润分配上是平等的

缺点：忽略了无法转换为利润的因素

根源在于设定是使用Shapley值时参与人都是平等的，有些因素不能够直接影响利润改变而是造成了地位的不平等，但是在利润分配时各个参与人的地位是不同的，这些因素也不会在利润分配上体现

对于此项缺点也有了很多的研究，例如引入权重等

异质性

一种遗传性状可以由多个不同的遗传物质改变所引起

克隆来源的肿瘤细胞在生长过程中形成侵袭能力、生长速度、对激素的反应、对抗癌药物的敏感性等方面有所不同的亚克隆的过程

差分隐私分

假设现在有一个婚恋数据库，2个单身8个已婚，只能查有多少人单身。刚开始的时候查询发现，2个人单身；现在张三跑去登记了自己婚姻状况，再一查，发现3个人单身。所以张三单身。

这里张三作为一个样本的的出现，使得攻击者获得了奇怪的知识。而差分隐私需要做到的就是使得攻击者的知识不会因为这些新样本的出现而发生变化。

那怎么做到呢？加入随机噪声。比如刚才的例子，本来两次查询结构是确定的2和3，现在加入随机噪声后，变成了两个随机变量，画出它们概率分布图。

现在，如果张三不在数据库的话，得到结果可能是2.5；张三在的话，得到的结果也可能是2.5；两个数据集查询得到某一个结果的概率很接近，以至于我们根本分不清这个结果来自于哪一个数据集，这样也就实现了攻击者的知识不会因为张三这个样本的出现与否而发生变化。

这些只是概念上的理解，总结一下就是对查询的结果加入噪声，使得攻击者无法辨别某一样本是否在数据集中。一个形象的说法就是，双兔傍地走安能辨我是雄雌。

客户端侧采用的差分隐私机制一般被称为本地化(Local)差分隐私 通过可信中间节点进行扰动可以被称为分布式( Distributed)差分隐私 由服务器完成的扰动被称为中心化(Centralized)差分隐私 而融合了上述两种或以上的差分隐私方法则被称为混合( Hybrid )差分隐私 （1）本地化差分隐私 本地化差分隐私意味着对数据的训练以及对隐私的保护过程全部在客户端就可以实现。直觉来看，这种差分隐私机制显然优于其他方案，因为用户可以全权掌握数据的使用与发布，也无需借助中心服务器，最有潜力实现完全意义上的去中心化联邦学习。

谷歌公司的Abadi等于2016年在传统机器学习中实现了差分隐私，并在当时就提出了在手机、平板电脑等小型设备上训练模型的设想，认为该差分隐私机制凭借轻量化的特点，更加适用于本地化、边缘化场景。

但是，本地化差分隐私本身及其在联邦学习的应用中仍然存在着不少问题。首先是它所需求的样本量极其庞大，例如前文所述的Snap公司将本地化差分隐私应用到垃圾邮件分类器的训练中，最终收集了用户数亿份样本才达到较高的准确度。谷歌、苹果、微软公司在用户设备上大量部署了本地化差分隐私，用来收集数据并进行模型训练，相较无噪模型的训练需要更多的数据量，往往多达2个数量级。其次，在高维数据下，本地化差分隐私要取得可用性、隐私性的平衡将会更加困难。

另外，在去中心化的联邦学习场景中，由于没有中心服务器的协调，参与者无法得知来自其他参与者的样本信息，因此很难决定自己所添加随机噪声的大小，噪声的分布不均将会严重降低模型性能。

（2）中心化差分隐私 差分隐私方法最初被提出时大多采用中心化的形式，通过-一个可信的第三方数据收集者汇总数据，并对数据集进行扰动从而实现差分隐私。B2C架构下的联邦学习同样可以在中心服务器上实现这种扰动。在服务器端收集用户更新后的梯度，通过逐个加噪的方式来隐藏各个节点的贡献；并证明了中心化加噪方案可以实现用户级别的差分隐私而不仅仅是本地化方案的数据点级别，这意味着它不会暴露出任何一个曾参与过训练的用户；最后通过实验证实了这种方法的模型训练效果要优于本地化差分隐私。

中心化差分隐私在实际应用中同样存在缺陷，因为它受限于一个可信的中心化服务器，但是很多场景下服务器并不可信。因此，可以采用分布式差分隐私来作为本地化与中心化的折中，或采用混合差分隐私回避这两者的部分缺陷。

（3）分布式差分隐私 分布式差分隐私指的是在若干个可信中间节点上先对部分用户发送的数据进行聚合并实施隐私保护，然后传输加密或扰动后的数据到服务器端，确保服务器端只能得到聚合结果而无法得到数据。该方案需要客户端首先完成计算并进行简单的扰动（例如较高隐私预算的本地化差分隐私）或加密，将结果发送至一个可信任的中间节点，然后借助可信执行环境（TEE）、安全多方计算、安全聚合（Secure Aggregation）或安全混洗（Secure Shuffling）等方法，在中间节点实现进一步的隐私保护，最终将结果发送至服务器端。

Bittau等于2017年提出了一种安全混洗框架Encode- Shuffle-Analyze（ESA），通过在客户端与服务器端额外增加一次匿名化混洗的步骤，允许用户在本地只添加少量噪声就实现较高级别的隐私保护。此后，Erlingsson等、Cheu等均对此框架进行了改进，并考虑了与联邦学习的结合。类似的分布式差分隐私解决方案同样都兼具了本地化与中心化差分隐私的优势，既不需要信任等级极高的服务器，也不需要在本地添加过多噪声。但相对的，分布式差分隐私普遍需要极高的通信成本。

本地化、中心化与分布式差分隐私的区别与联系如表所示：

（4）混合差分隐私 混合差分隐私方案由Avent等提出，它通过用户对服务器信任关系的不同对用户进行分类。举例而言，最不信任服务器的用户可以使用最低隐私预算的本地化差分隐私，而最信任服务器的用户甚至可以直接发送原始参数；服务器也将根据用户的信任关系对数据进行不同程度的处理。该方案的问题是同样需要一定的通信成本，并且还需要付出额外的预处理成本以划分信任关系。