联邦学习简介

联邦学习概览：

联邦学习简介
在过去几年里，我们见证了机器学习在AI领域的快速发展，无论是在计算机视觉还是语音识别 自然语言处理还是在推荐 广告这些领域都取得了巨大的进步。

近年来人工智能可谓风风火火，掀起一波又一波浪潮，从人脸识别、活体检验发现刑事案件报警到阿尔法狗大战人类围棋手李世石、再到无人驾驶、以及已被普遍应用的精准营销，AI逐步进入人们生活的方方面面。当然也不免出现部分过度吹捧，导致对AI的误解–AI无所不能，在追逐AI的同时却忽略了一点，AI是靠数据来喂出来的，例如Facebook的目标检测系统就是由来自Instagram的3.5亿张图像训练得到的。一般而言训练人工智能应用所需要的数据量都是非常庞大的。现实生活中，除了少数巨头公司能够满足，绝大多数企业都存在数据量少，数据质量差的问题，不足以支撑人工智能技术的实现；同时国内外监管环境也在逐步加强数据保护，陆续出台相关政策，如欧盟最近引入 的新法案《通用数据保护条例》（GDPR），我国国家互联网信息办公室起草的《数据安全管理办法(征求意见稿)》，因此数据在安全合规的前提下自由流动，成了大势所趋；

在用户和企业角度下，商业公司所拥有的数据往往都有巨大的潜在价值。两个公司甚至公司间的部门都要考虑利益的交换，往往这些机构不会提供各自数据与其他公司做数据聚合，导致即使在同一个公司内，数据也往往以孤岛形式出现，为数据孤岛以及隐私保护问题联邦学习应运而生。
联邦学习定义：
联邦学习的概念最早由谷歌在2016年提出，最早是为了解决手机键盘的预测问题，且不会泄露用户隐私。此后联邦学习在人工智能领域越来越活跃。联邦学习旨在建立一个基于分布数据集的联邦学习模型，联邦学习包括两个过程，分别是模型训练和模型推理过程。模型训练过程中，模型的相关信息能够在各方之间交换（加密），但是数据不能，交换过程不会暴露每个站点上数据的任何受保护的部分。
已经训练好的模型，可以置于联邦学习系统的各参与方，也可以在多方共享。
联邦学习具有以下特征:

1)有两个或以上的联邦学习参与方协作构建一个共享的机器学习模型，每一个参与方都拥有若干用来训练的
训练数据。

2)在联邦学习模型的训练过程中，每一个参与方拥有的数据都不会离开该参与方，也即是说数据不离开数据拥有方。

3)联邦学习模型相关的信息能够以加密方式在各方之间进行传递和交换，并且保证任何一个参与方都不能推测出其他方的原始数据。

4)联邦学习的性能能够充分逼近理想模型（集中式训练数据）的性能。

联邦学习主要分为横向联邦学习、纵向联邦学习、联邦迁移学习三类。

联邦学习主要分为横向联邦学习、纵向联邦学习、联邦迁移学习三类。

隐私保护技术简介：
同态加密：

什么是同态加密？提出第一个构造出全同态加密（Fully Homomorphic Encryption）[Gen09]的Craig Gentry给出的直观定义最好：
A way to delegate processing of your data, without giving away access to it.

这是什么意思呢？传统的加密方案关注的都是数据存储安全。即，我要给其他人发个加密的东西，或者要在计算机或者其他服务器上存一个东西，我要对数据进行加密后在发送或者存储。没有密钥的用户，不可能从加密结果中得到有关原始数据的任何信息。只有拥有密钥的用户才能够正确解密，得到原始的内容。我们注意到，这个过程中用户是不能对加密结果做任何操作的，只能进行存储、传输。对加密结果做任何操作，都将会导致错误的解密，甚至解密失败。

同态加密方案最有趣的地方在于，其关注的是数据处理安全。同态加密提供了一种对加密数据进行处理的功能。也就是说，其他人可以对加密数据进行处理，但是处理过程不会泄露任何原始内容。同时，拥有密钥的用户对处理过的数据进行解密后，得到的正好是处理后的结果。
同态加密具体如何定义？我们在云计算应用场景下面进行介绍：

Alice通过Cloud，以Homomorphic Encryption（以下简称HE）处理数据的整个处理过程大致是这样的：
1）Alice对数据进行加密。并把加密后的数据发送给Cloud；
2）Alice向Cloud提交数据的处理方法，这里用函数f来表示；
3）Cloud在函数f下对数据进行处理，并且将处理后的结果发送给Alice；
4）Alice对数据进行解密，得到结果。

据此，我们可以很直观的得到一个HE方案应该拥有的函数：KeyGen函数：密钥生成函数。这个函数应该由Alice运行，用于产生加密数据Data所用的密钥Key。当然了，应该还有一些公开常数PP（Public Parameter）；
Encrypt函数：加密函数。这个函数也应该由Alice运行，用Key对用户数据Data进行加密，得到密文CT（Ciphertext）；
Evaluate函数：评估函数。这个函数由Cloud运行，在用户给定的数据处理方法f下，对密文进行操作，使得结果相当于用户用密钥Key对f(Data)进行加密。
Decrypt函数：解密函数。这个函数由Alice运行，用于得到Cloud处理的结果f(Data)。
那么，f应该是什么样子的呢？HE方案是支持任意的数据处理方法f？还是说只支持满足一定条件的f呢？根据f的限制条件不同，HE方案实际上分为了两类：Fully Homomorphic Encryption (FHE)：这意味着HE方案支持任意给定的f函数，只要这个f函数可以通过算法描述，用计算机实现。显然，FHE方案是一个非常棒的方案，但是计算开销极大，暂时还无法在实际中使用。
Somewhat Homomorphic Encryption (SWHE)：这意味着HE方案只支持一些特定的f函数。SWHE方案稍弱，但也意味着开销会变得较小，容易实现，现在已经可以在实际中使用。
a)如果满足f(A) + f(B) = f(A+B),我们把这种加密函数叫做加法同态
b)如果满足f(A) * f(B) = f(A*B),我们把这种加密函数叫做乘法同态
如果一个加密函数f只满足加法同态，就只能进行加减法计算。
如果一个加密函数f只满足乘法同态，就只能进行乘除法计算。

隐私保护技术——差分隐私
什么是差分隐私：
差分隐私顾名思义就是用来防范差分攻击的，举个简单的例子，假设现在有一个婚恋数据库，2个单身8个已婚，只能查有多少人单身。刚开始的时候查询发现，2个人单身；现在张三跑去登记了自己婚姻状况，再一查，发现3个人单身。所以张三单身。

当张三不在数据集中时，我们查询到，数据集中的单身人数为2，在张三加入到数据库当中后，我们又查询到单身人数变成了3，于是我们便知道了张三的单身贵族身份，他的隐私泄露了！在整个过程中，我们并没有直接对张三的隐私数据进行查询，却仍然成功获取了他的隐私信息。再举个具体的例子就是明日之星选举的例子强力最后投票。

这个问题乍一看非常棘手，但其实只要引入一定的随机性就可以被解决。比如在刚才的例子中，我们的两次查询分别是确定的结果2和3，现在我们给查询结果加入一个噪声，两次查询的结果也就变成了两个随机变量，这是它们的概率分布图：

我们重复一下刚才的查询。现在，我们查询到的结果是随机的，如果张三不在数据库中，查询结果可能是1.9，也可能是2.5，甚至有概率超过3.5，如果张三在数据库中，我们的查询结果也可能是1.8、2.9等。在没有加入噪声时，前后两次输出的差就是张三的数据，但是加入噪声后，这个差值从确定的值变成了一个随机变量，我们也就不能由它来确定张三的数据了。加上了噪声之后，查询的结果不就不准确了吗？没错！事实上，差分隐私就是一个通过“牺牲一定的准确性来换取隐私安全”的概念。

刚才只是讲到概念上的理解，现在从数学上理解一下。上面的查询函数可以用 表示（这里暂时只考虑输出结果为1维的情况），随机噪声可以用 表示，最终得到的查询结果就是 ，对于两个汉明距离为1的数据集 ，对于任意的输出集合 ，应该有：

我们的目的是使的这两个分布尽可能地接近，那么衡量两个分布的差异自然可以用到我们熟悉的KL-Divergence散度：

但是我们并不关心这两个分布的整体差异，我们只需要两个分布在差距最大的情况下能够被hold住，所以引入了MAX-Divergence，并且使得它小于 ：

化简一下，利用 e指数运算将ln符号消去，然后将左边分母移到右边，就可以得到最开始的差分隐私定义中定义的内容了。

而 就被称为隐私预算，一般而言，
越小，隐私保护越好，但是加入的噪声就越大，数据可用性就下降了，数据相对于正确的中心值更加分散。对于应用差分隐私的算法，首先会设定整体的隐私预算，每访问一次数据，就会扣除一些预算，当预算用完，数据就无法再访问

横向联邦学习
横向联邦学习——客户/服务器架构
横向联邦学习也称为按样本划分的联邦学习，可以应用于联邦学习的各个参与方的数据集有相同的特征空间和不同的样本空间的场景。
横向联邦学习架构：
客户——服务器架构

步骤1. 各参与方在本地计算梯度，使用加密技术
把梯度进行加密，将加密后的结果发给聚合服务
器。

步骤2.服务器进行安全聚合，例如使用基于同态
加密的加权平均。

步骤3.服务器将聚合后的结果发给各参与方。

步骤4.各参与方对接收到的梯度进行解密，并使用
解密后的梯度结果，并且更新各自的模型参数。

需要注意的是在上面示意图中，如果参与方发送的是梯度信息给服务器，服务器将接收到的梯度进行聚合，在把聚合后的梯度信息发送给参与方，那么这种方法被称为梯度平均。

如果参与方是在本地计算模型参数，参与方发送的是参数信息给服务器，服务器对模型参数进行聚合，再将聚合后的模型参数发送给参与方，那么这种方法被称为模型平均。
梯度平均和模型平均都被称为联邦平均。

横向联邦学习——对等网络架构

在对等网络结构中，不存在中央服务器或者协调方，在这种架构中横向联邦学习的K个参与方也被称为训练方，由于对等网络不存在中央服务器，训练方必须商定发送和接收模型的顺序，主要方法为循环传输和随机传输。
对等网络架构传输方法：
循环传输：
循环传输过程中，训练方被串成一条链，第一个训练方将当前模型的参数发送给它的下一个训练方，下游的训练方接收来自上游的模型参数后，将使用本地的小批量数据更新接收到的模型参数，然后把更新后的模型参数传输给下一个训练方，例如训练方1传给2,2给3…训练方K，然后K在回传到1，如此训练往复直到模型收敛或者到迭代次数。

随机传输：
随机传输模式中，第k个训练方从{1，…. ,L }{k}中选取i，并将模型参数发送给训练方i。当第i个训练方收到来自第k个训练方的模型参数后，它将使用来自本地数据集的数据的minibatch更新收到的模型参数。之后，第i个训练方也从{1，…，L}{i}中等概率的随机选取一个数字j，并将自己的模型参数收敛或者达到允许达到
的最大训练时间。这种方法叫做Gossip学习。

与客户-服务器模式相比，对等网络架构的一个明显优点便是去除了中央服务器（参数服务器/协调方）

横向联邦学习——全局性能评估
对客户——服务器架构来说，参与方和协作方能协作的获取全局性能。在横向联邦学习模型训练过程中，我们可以根据以下步骤得到全局性能：

1）第k个参数方使用本地的测试数据集，对现有的横向联邦学习模型进行性能评估。对于二分类任务，这一步会生成本地模型的测试结果（N_TP^((𝑘)), N_𝐹P^((𝑘)), N_𝑇𝑁^((𝑘)), N_𝐹𝑁^((𝑘))）,其中N_TP^((𝑘)), N_𝐹P^((𝑘)), N_𝑇𝑁^((𝑘)), N_𝐹𝑁^((𝑘))表示真阳、假阳、真阴、假阴测试结果的数量，参与方𝑘=1,2,3,4,5…𝑘都执行此操作。
2）第k个参与方给协调方发送本地模型预测结果（N_TP^((𝑘)), N_𝐹P^((𝑘)), N_𝑇𝑁^((𝑘)), N_𝐹𝑁^((𝑘))），参与方𝑘=1,2,3,4,5…𝑘都执行此操作。
3）在收集K个参与方的本地模型测试结果〖{N〗TP^((𝑘)), N_𝐹P^((𝑘)), N_𝑇𝑁^((𝑘)), N_𝐹𝑁^((𝑘)) }(𝑘=1)^𝐾 之后，协调方能够计算全局模型测试结果。例如对二分类任务，全局召回率能够通过(∑2_(𝑘=1)^𝐾▒N_𝑇P^((𝑘) ) )/(∑2_(𝑘=1)^𝐾▒〖(N_𝑇P^((𝑘) )+N_𝐹𝑁^((𝑘)))〗) 计算得到。
4）协调方计算得到全局模型性能

横向联邦学习——联邦平均算法
谷歌的H.BrendanMahan等人提出使用联邦平均算法求解联邦优化问题。联邦平均算法适用于任何下列的加和形式的损失函数。

               min 𝑓(𝑤)=1/𝑛 ∑2_(𝑖=1)^𝑛▒𝑓_𝑖  (𝑤)

上面𝒏表示训练数据的数量，𝑤"∈" 𝑅^𝑑表示d维模型参数。

对于机器学习问题我一般选择𝑓_𝑖 (𝑤)=𝑙(𝑥𝑖,𝑦𝑖;𝑤) 其中， 𝑙(𝑥𝑖,𝑦𝑖;𝑤) 表示在给定模型参数𝑤上对样本（𝑥𝑖,𝑦𝑖）
进行预测得到的损失结果， 𝒙𝒊,𝒚𝒊分别表示第i个训练数据点和标签。

假设我们有K个参与方在一个横向联邦学习系统中，设𝐷_𝑘 表示第𝑘个参与方所拥有的数据集，p_𝑘 表示位于客户𝑘的数据的索引集合。设n_𝑘="|" p_𝑘 “|” 表示p_𝑘的大小。我们假设第𝑘个参与方有n_𝑘个数据点。因此，当总共有K个参与方时，上面的式子可以写成

              𝑓(𝑤)=∑_(𝑘=1)^𝐾▒𝑛_𝑘/𝑛 𝐹_𝑘  (𝑤) 〖        𝐹〗_𝑘  (𝑤) =1/𝑛_𝑘  ∑2_(𝑖=1)^𝑛▒𝑓_𝑖  (𝑤)

min 𝑓(𝑤)=1/𝑛 ∑2_(𝑖=1)^𝑛▒𝑓_𝑖 (𝑤)

𝑓(𝑤)=∑_(𝑘=1)^𝐾▒𝑛_𝑘/𝑛 𝐹_𝑘 (𝑤) 〖 𝐹〗𝑘 (𝑤) =1/𝑛_𝑘 ∑2(𝑖=1)^𝑛▒𝑓_𝑖 (𝑤)
联邦平均算法的计算量由以下三个参数控制：
1）参数𝒑 在每一轮中进行计算的客户的占比
2）参数𝑺 在每一轮中，每一个客户在本地数据集上进行训练的步骤数
3）参数𝑀 客户更新时使用的mini_batch的大小，我们使用M=无穷大，表示完整的本地数据集作为一个批量进行处理
在该算法中， 𝑝控制着全局批的大小，当𝒑=1 时，表示所有参与方拥有的数据都参与训练。
在梯度下降中，假设学习率是𝜼，在第t轮更新全局模型参数时，第𝑘个参与方将会计算𝒈_𝒌=〖𝜵𝑭〗𝒌 (𝒘_𝒕) 也即计算在当前模型参数𝒘_𝒕的本地数据的平均梯度，并且协调方将会以下面的公式聚合这些梯度并使用模型参数的更新信息。𝑤(t+1)= 𝑤_t−η∑_(𝑘=1)^𝐾▒〖𝑛_𝑘/𝑛 g_𝑘 〗 〖 g〗_𝑘=〖𝛻𝐹〗_𝑘 (𝑤_t)

那么，∑_(𝑘=1)^𝐾▒〖𝑛_𝑘/𝑛 g_𝑘 〗= 𝛻𝑓(𝑤_t)
如果不同参与方拥有的数据集符合IID条件。协调方之后会把更新后的模型参数𝑤_(t+1)发送给各方。
协调方将会把平均梯度(g_t ) ̅=∑_(𝑘=1)^𝐾▒〖𝑛_𝑘/𝑛 g_𝑘 〗 发送给各参与方，这种方法叫做梯度平均。
min 𝑓(𝑤)=1/𝑛 ∑2_(𝑖=1)^𝑛▒𝑓_𝑖 (𝑤)

𝑓(𝑤)=∑_(𝑘=1)^𝐾▒𝑛_𝑘/𝑛 𝐹_𝑘 (𝑤) 〖 𝐹〗𝑘 (𝑤) =1/𝑛_𝑘 ∑2(𝑖=1)^𝑛▒𝑓_𝑖 (𝑤)

∀𝑘,𝑤_(𝑡+1)^𝑘= (𝑤_t ) ̅−ηg_𝑘 〖 g〗_𝑘=〖𝛻𝐹〗_𝑘 (𝑤_t)

(𝑤_(t+1) ) ̅= ∑_(𝑘=1)^𝐾▒𝑛_𝑘/𝑛 𝑤_(𝑡+1)^𝑘

每一个客户在本地对现有模型参数 (𝑤_t ) ̅使用本地数据执行梯度下降的一个步骤，并且本地更新的模型参数
发给服务器，之后服务器对模型进行加权平均计算，将更新后的模型(𝑤_(t+1) ) ̅发给各个参与方，这种方法叫做模型平均。
归纳
联邦平均算法（模型平均）过程伪代码：
1.在协调方执行：
2. 初始化模型参数𝑤0 ，并将原始的模型参数𝑤0 广播给所有的参与方。
3.for 每一全局模型更新轮次 𝑡=1, 2, 3 …𝑑𝑜
4. 协调方确定 Ct 也即确定随机选取的k个参与方的集合。
5. for 每一参与方k"∈" Ct 并行的 do
6. 本地更新模型参数： 𝑤_(𝑡+1)^((𝑘)) 参与方更新（k,(𝑤_t ) ̅ ）
7. 将更新后的模型参数 𝑤_(𝑡+1)^((𝑘)) 发给协调方。
8. end for
9. 协调方将收到的模型参数进行聚合，即对收到的模型参数使用加权平均

10. 协调方检查模型参数是否已经收敛，如果收敛，则协调方给各参与方发信号，使其全部停止模型训练
11. 协调方将聚合后的模型参数 广播给所有参与方
12. end for

安全联邦平均算法（模型平均）过程伪代码：⟦ .⟧表示加法同态加密（AHE）
1.在协调方执行：
2. 初始化模型参数𝑤0 ，并将原始的模型参数𝑤0 广播给所有的参与方。
3.for 每一全局模型更新轮次 𝑡=1, 2, 3 …𝑑𝑜
4. 协调方确定 Ct 也即确定随机选取的k个参与方的集合。
5. for 每一参与方k"∈" Ct 并行的 do
6. 本地更新模型参数： ⟦𝑤_(𝑡+1)^((𝑘)) ⟧ 参与方更新（k,⟦(𝑤_t ) ̅ ⟧ ）
7. 将更新后的模型参数⟦𝑤_(𝑡+1)^((𝑘)) ⟧发给协调方。
8. end for
9. 协调方将收到的模型参数进行聚合，即对收到的模型参数使用加权平均

              ⟦(𝑤_(t+1) ) ̅ ⟧           

协调方检查模型参数是否已经收敛，如果收敛，则协调方给各参与方发信号，使其全部
停止模型训练
11. 协调方将聚合后的模型参数 广播给所有参与方
12. end for
纵向联邦学习

第一部分：加密实体对齐
企业A和企业B的用户群体不同，系统使用一种基于加密的用户ID对齐技术，确保A和B不需要暴露各自原始数据的情况下便可以对齐共同用户。
第二部分：加密模型训练
在确定共有实体后，各方可以使用这些共有实体的数据协同的训练一个机器学习模型。
1）协调者C创建密钥对，并将公共密钥发送给A和B

2）A和B对中间结果加密和交换，中间结果用来帮助计算梯度和损失值

3）A和B计算加密梯度并分别加入附加的掩码（additional mask，B还会计算加密损失，
A和B将加密的结果发送给C

4. C对梯度和损失信息进行解密，并将结果发送回A和B，A和B解除梯度上的掩码，并且根据梯度
   来更新模型参数。