机器学习-联邦学习

联邦学习简介

数据孤岛问题

训练机器学习模型通常需要大量的数据，但是在实际情况下通常会面临数据孤岛问题，即数据碎片化和数据隔离的问题。产生这一问题的原因通常有：

• 数据所有权问题，以及用户隐私和数据安全的问题
• 各方协同分享大数据的益处不明显
• 随着物联网和边缘计算的发展，数据的分布将会更分散

联邦学习的特点

联邦学习指的是一种建立机器学习模型的算法框架，它需要满足如下几个特点：

• 有两个或以上的参与方来协作构建一个共享的机器学习模型，每个参与方都有若干的训练数据
• 在模型训练过程中，每一个参与方拥有的数据都归自己所有，且不会离开自己
• 模型相关的信息通过加密方式在各方之间进行传输和交换，且需要保证任何一个参与方都不能推测出其他方的原始数据
• 最终得到的模型性能充分逼近理想模型（指的是将所有训练数据集合并在一起去训练模型所得到的机器学习模型）的性能

分类

根据训练数据在不同参与方之间的数据特征和样本ID的分布情况，联邦学习分为三个不同的类别：

• 横向联邦学习：又叫按样本划分的联邦学习，指的是参与方的数据具有相同的数据特征，但是参与方拥有不同的数据样本（即样本ID差别较大）。使用横向联邦学习可以使得样本的总数增加。
• 纵向联邦学习：又叫按特征划分的联邦学习，指的是参与方的样本ID重叠较多，但是数据特征重叠较少。使用纵向联邦学习使得样本的特征维数增多。
• 联邦迁移学习：指的是在联邦学习的过程中使用迁移学习的技术，通常适用于参与方的数据特征与样本ID重合度都很小的情况。

这三种不同的类型可以总结为下图：

联邦学习分类

优缺点

优点：

• 保护用户隐私和数据安全
• 允许若干方协同训练，从而使各方得到一个比自己训练的更好的模型

缺点：

• 参与方与聚合服务器之间的连接可能很慢且不稳定，从而使得系统变得不稳定且不可预测
• 不同参与方的数据会带来非独立同分布、样本数量不均衡等问题，导致模型训练效果不好甚至失败
• 容易遭到某个恶意参与方的攻击，比如恶意参与方发送破坏性的模型更新信息

使用案例

一个使用了联邦学习的案例是Google Gboard系统的输入预测模型，即自动输入补全键盘系统。这一系统可以在使用过程中为用户提供建议输入，并记录用户是否选择了建议输入的词。这一系统不仅可以根据用户自身的使用记录来进行改善和优化，而且可以使用联邦平均的技术让所有用户的数据都可以被利用起来。

联邦平均过程不需要用户将数据传输到某个数据中心，每个用户只需要将自己的预测模型加密上传到云端，而这些加密的模型也会被聚合到一个加密的全局模型中。在这一过程中，云端的服务器无法获知每个用户的数据或模型；而聚合后的模型也是加密的，因此每个用户也无法获取其他用户的数据。

机器学习的隐私和安全

隐私保护与安全机器学习

在机器学习中，主要有三种攻击类型：

• 完整性：对完整性的攻击会可能导致机器学习系统出现检测错误
• 可用性：对可用性的攻击可能会导致系统变得不可用
• 机密性：对机密性的攻击会导致一些机器学习系统中的敏感信息（如训练数据或者模型参数）发生泄露

使用了保护用户隐私和数据安全的防御技术的机器学习系统被称为面向隐私保护的机器学习（Privacy-Preserving Machine Learning，PPML）系统。

另一个容易混淆的概念是安全机器学习（Secure ML）。安全机器学习重点关注机器学习系统的完整性和可用性，而PPML重点关注机器学习模型的隐私性和机密性。

威胁与安全模型

隐私威胁模型

对机器学习系统的攻击可能发生在任何阶段，包括数据发送、模型训练、模型推理等。与隐私威胁相关的攻击方式包括但不限于：

• 重构攻击：敌手的目标是在模型训练期间抽取训练数据，或抽取训练数据的特征向量。在机器学习过程中，如果数据结构已知，那么梯度信息就可能会被利用，从而泄露关于训练数据的额外信息。因此，应当避免使用存储显式特征值的机器学习模型（如SVM、KNN等），仅仅授予黑盒访问权限，同时使用安全多方计算和同态加密来保护计算中间结果。
• 模型反演攻击：敌手被假设为对模型拥有白盒访问权限或者黑盒访问权限。对于白盒访问，敌手可以直接获取模型的明文内容；而对于黑盒访问，敌手可以根据模型的输入和输出，建立方程求解来得到一个与原始模型相似的模型。为了抵御这类攻击，在对模型的访问设置为黑盒的基础上，对于模型的输出也应该做一些限制，例如返回舍入后的预测值、仅返回预测的标签、返回聚合的多个样本的预测结果等。
• 成员推理攻击：敌手对模型至少有黑盒访问权限，同时拥有一个特定的样本作为先验知识，目标是判断模型训练集中是否包含特定样本。敌手通过模型输出，判断样本是否属于模型的训练集。
• 特征推理攻击：敌手出于恶意目的，将数据去匿名化或者锁定记录的拥有者。在数据被发布之前，删除数据的敏感特征可以一定程度上实现匿名化。但是如果敌手可以获取到其他背景知识，这种方法可能会失效。使用群组匿名化隐私方法可以应对这种攻击方式。

攻击者和安全模型

对于PPML系统，通常考虑两种类型的敌手。一种是半诚实的敌手，或者叫被动敌手，这种敌手会诚实地遵守协议，但是试图从接收到的信息中学习更多除了输出之外的信息；另一种是恶意的敌手，或者叫主动敌手，敌手不会遵守协议，可以执行任意的攻击行为。

大多数的PPML系统都考虑半诚实的敌手模型，因为在联邦学习中，诚实地遵守协议对各方都有利。而对于每个安全模型，敌手也会攻击一部分参与方使之腐败，而腐败的参与方可能会相互勾结。

隐私保护技术

安全多方计算

定义

安全多方计算指的是每个参与方\(P_i\)只能根据自己的输入\(x_i\)来获知输出值\(y_i\)，而无法得知其他的额外信息。安全多方计算可以通过三种不同的框架来实现：不经意传输、秘密共享和阈值同态加密。

不经意传输

在不经意传输中，发送方有一个“消息-索引”对\((M_1,1),\cdots,(M_N,N)\)。在每次传输时，接收方选择一个满足\(1\le i \le N\)的索引\(i\)，并接收\(M_i\)。接收方不能得知除了\(M_i\)之外的其它信息，发送方也不能了解接收方选择的\(i\)值。

#### 秘密共享

秘密共享指的是将秘密值分为随机多份，并将这些份分发给不同方，从而隐藏秘密值。也就是说，每一方只能拥有一个通过共享得到的值，即秘密值的一小部分。

同态加密

定义

同态加密方法指的是一种通过对相关密文进行有效操作（不需要知道解密密钥），从而允许在加密内容上进行特定代数运算的方法。一个同态加密方法\(\mathcal{H}\)由一个三元组组成：\(\mathcal{H}=\{\text{KeyGen, Enc, Dec}\}\)。其中\(\text{KeyGen}\)指的是密钥生成函数；\(\text{Enc}\)表示加密函数，\(\text{Dec}\)表示解密函数。同态加密方法可以是对称加密，也可以是非对称加密。如果一个安全密码系统满足以下条件，则被称为同态的： \[ \forall m_1,m_2\in \mathcal{M}, \text{Enc}_{k}(m_1 \odot_{\mathcal{M}} m_2)= \text{Enc}_{k}(m_1) \odot_{\mathcal{C}} \text{Enc}_{k}( m_2) \] 其中\(\mathcal{M}\)表示明文空间，\(\mathcal{C}\)表示密文空间，\(k\)表示加密密钥。

分类

同态加密算法可以分为如下三种类别：

• 部分同态加密：运算符\(\odot_{\mathcal{C}}\)可以无限次数地用于密文，但是只 限于加法或者乘法运算符中的一种。如果\(\odot_{\mathcal{M}}\)是加法运算符，则被称为加法同态；如果\(\odot_{\mathcal{M}}\)是乘法运算符，则被称为乘法同态。
• 些许同态加密：指的是同态加密方法中的一些运算操作只能被使用有限次。
• 全同态加密：允许对密文进行无限次的加法运算和乘法运算操作。通过使用加法和乘法，可以实现任意的函数计算。

差分隐私

定义

差分隐私的思想是，当敌手试图从数据库中查询个体信息时将其混淆，使得敌手无法从查询结果中辨别个体级别的敏感性。因此，它可以被用于抵抗成员推理攻击。

\((\epsilon,\delta)\)-差分隐私的定义为：对于只有一个记录不同的两个数据集\(D\)和\(D'\)，一个随机化机制\(\mathcal{M}\)可以保护\((\epsilon,\delta)\)-差分隐私，并且对于所有的\(S\subset \text{Range}(\mathcal{M})\)，有： \[ \text{Pr}[\mathcal{M}(D)\in S]\le \text{Pr}[\mathcal{M}(D')\in S]\times e^{\epsilon}+\delta \] 其中\(\epsilon\)表示隐私预算，\(\delta\)表示失败概率。差分隐私在向数据引入噪声的同时，权衡了实用性和隐私性。

方法

差分隐私的实现方法有两种，一种是根据函数的敏感性增加噪声，另一种是根据离散值的指数分布选择噪声。

差分隐私可以根据噪声扰动使用的方式和位置来分类：

• 输入扰动：噪声被加入训练数据
• 目标扰动：噪声被加入学习算法的目标函数
• 算法扰动：噪声被加入中间值，如迭代算法的梯度
• 输出扰动：噪声被加入训练后的输出参数

横向联邦学习

定义

横向联邦学习又叫按样本划分的联邦学习，指的是参与方的数据具有相同的数据特征，但是参与方拥有不同的数据样本（即样本ID差别较大）。使用横向联邦学习可以使得样本的总数增加。

一个例子是不同地区的银行，它们所拥有的客户重叠很少，但是对于每一个客户所保存的用户数据却通常十分相似。通过使用联邦学习，可以帮助这些银行建立更加精确的风控模型。

系统架构

客户-服务器架构

在客户-服务器架构中，具有同样数据结构的\(K\)个参与方（客户）在服务器（又叫参数服务器或者聚合服务器）的帮助下，协作地训练一个机器学习模型。

训练过程通常包含如下四步：

1. 各个参与方在本地计算模型梯度（或者模型参数），并使用同态加密、差分隐私或者秘密共享等加密技术，对梯度（模型参数）信息进行掩饰，并将掩饰后的结果发送给聚合服务器
2. 服务器进行安全聚合操作，例如使用同态加密的加权平均
3. 服务器将聚合后的结果发送给各个参与方
4. 各个参与方对收到的梯度进行解密，并使用解密后的梯度结果更新各自的模型参数；或者是使用聚合后的模型参数去更新模型

上述步骤持续迭代进行，直到损失函数收敛或者达到允许迭代次数的上限。这种架构独立于特定的机器学习算法，并且所有参与方可以共享最终的模型参数。

如果联邦平均算法使用了安全多方计算或者加法同态加密技术，则上述架构可以防范半诚实的服务器的攻击，并防止数据泄露。但是如果有一个恶意的参与方去训练生成对抗网络（GAN），则会导致系统容易遭受攻击。

对等网络架构

在对等网络架构下，不存在中央服务器或者协调方，此时\(K\)个参与方也被称为是训练方。每一个训练方只使用本地数据来训练同一个机器学习模型，并使用安全链路在两两之间传输模型参数信息。为了保证两方的通信安全，需要使用如非对称加密等安全措施。

在对等网络架构中，训练方之间必须提前商定发送和接收模型参数信息的顺序。主要有两种方法：

• 循环传输：训练方被组织成一条环形链路，训练方1，2，……，\(K\)依次相连，且\(K\)与1相连。训练方\(i\)接收来自训练方\(i-1\)的模型参数，并使用本地数据集去训练并更新模型参数，然后将更新后的参数发给训练方\(i+1\)。重复此过程，直到参数收敛或者超过训练时间上限。
• 随机传输：当前第\(i\)个训练方使用自己的本地数据集训练模型之后，将模型参数发给一个随机的训练方\(k\)继续训练。重复此过程直到\(K\)个训练方同意模型参数收敛或者达到时间上限。

全局模型评估

对于客户-服务器架构，每个参与方可以分别用自己本地的测试数据集来对模型进行性能评估，并将结果发送给服务器。服务器在收集到每个参与方的本地评估结果之后，将其汇总并计算总体的性能评估，并发送给每个参与方。

而对于对等网络架构，则需要选择某个参与方当成临时的协调方，然后就可以使用类似于客户-服务器架构的评估方法。

联邦平均算法

联邦优化问题

联邦学习中的优化问题被称为联邦优化。相比于传统的分布式优化，它具有如下的关键特性：

• 数据集的非独立同分布
• 数据量不平衡
• 数量较大的参与方
• 慢速且不稳定的通信连接

联邦平均算法便是为了解决上述问题而提出的模型训练方法。它适用于任何具有有限加和形式的损失函数\(L(w)=\frac{1}{n}\sum_{i=1}^{n}\ell_i(w)\)。

算法描述

我们假设共有\(K\)个参与方，每个参与方拥有的数据集大小为\(n_k\)，训练数据的总数为\(n\)，那么损失函数也可以表示为： \[ L(w)=\sum_{k=1}^{K}\frac{n_k}{n}F_k(w) \\ F_k(w)=\frac{1}{n_k}\sum_{i=1}^{n_k}f_i(w) \] 以使用固定学习率\(\eta\)的分布式梯度下降为例，在第\(t\)轮更新全局模型参数时，第\(k\)个参与方将会计算\(g_k=\nabla F_k(w_t)\)，即它在当前模型参数\(w_i\)的本地数据的平均梯度。

协调方会使用如下公式对梯度进行聚合并更新模型： \[ w_{t+1}\leftarrow w_{t}-\eta\sum_{k=1}^{K}\frac{n_k}{n}g_k \] 协调方可以将更新之后的模型参数\(w_{t+1}\)发给参与方；或者是将所有参与方的平均梯度\(\sum_{k=1}^{K}\frac{n_k}{n}g_k\)发送给各个参与方，每个参与方自行计算更新后的参数。这种方法叫做梯度平均。

另一种等价的方式使用如下方式训练模型： \[ w_{t+1}^{(k)}\leftarrow \bar{w}_t-\eta g_k \\ \bar{w}_{t+1}\leftarrow \sum_{k=1}^{K}\frac{n_k}{n}w_{t+1}^{(k)} \]

安全性

在联邦平均算法中，可以使用前面介绍的一些隐私保护方法，例如在梯度传递与聚合的时候使用同态加密算法，从而保护用户隐私和数据安全。

纵向联邦学习

定义

纵向联邦学习又叫按特征划分的联邦学习，指的是参与方的样本ID重叠较多，但是数据特征重叠较少。使用纵向联邦学习使得样本的特征维数增多。

一个例子是医院与制药公司的合作，医院的就诊数据可以帮助制药公司研发新药物，而医院也可以利用制药公司的数据为病人提供治疗方案。

系统架构

下面用一个例子来说明纵向联邦学习的架构。假设有两家公司A和B想要协同地训练一个机器学习模型，每一家公司都拥有各自的数据，此外B方拥有进行模型预测任务所需的标注数据。由于用户隐私和数据安全的原因，A和B不能直接交换数据。为了保证训练过程中的数据保密性，加入了一个第三方协调者C，我们假设C是诚实的（如权威机构或者安全计算节点）且不与A和B共谋，但是A和B都是诚实且好奇的。

VFL系统的训练过程通常分为如下两个部分：

第一部分：加密实体对齐。系统使用一种基于加密的用户ID对齐技术，来确保A方和B方不需要暴露各自的原始数据便可以对齐用户。在实体对齐期间，系统不会将属于某一家公司的用户暴露出来。

第二部分：加密模型训练。在确定共有实体之后，各方便可以使用这些共有实体的数据来协同地训练一个机器学习模型。训练过程可以分为如下四个步骤：

1. 协调者C创建密钥对，将公钥发给A方和B方
2. A方和B方使用公钥对中间结果进行加密和交换。中间结果用来帮助计算梯度和损失值
3. A方和B方计算梯度并分别加入附加掩码且加密，同时B方还会计算损失并对其加密。A方和B方将加密后的结果发送给C方
4. C方对梯度和损失信息进行解密，并将结果发送给A方和B方。A方和B方解除梯度信息上的掩码，并根据这些梯度信息来更新模型参数

示例：安全联邦线性回归

相比于普通的线性回归，联邦线性回归使用了同态加密算法，在联邦线性回归的过程中保护属于每一个参与方的本地数据。算法的详细描述如下。

给定学习率\(\eta\)，正则化参数\(\lambda\)，数据集\(D_A=\{\boldsymbol{x}_i^A\}\)，\(D_B=\{\boldsymbol{x}_i^B,y_i\}\)，与\(\boldsymbol{x}_i^A\)和\(\boldsymbol{x}_i^B\)相关的模型参数\(\Theta_A\)和\(\Theta_B\)，训练目标可以表示为： \[ \min _{\Theta_A,\Theta_B}\sum_{i} ||y_i-\Theta_A\boldsymbol{x}_i^A-\Theta_B\boldsymbol{x}_i^B||^2+\frac{\lambda}{2}(||\Theta_A||^2+||\Theta_B||^2) \] 设\(u_i^A=\Theta_A\boldsymbol{x}_i^A\)，\(u_i^B=\Theta_B\boldsymbol{x}_i^B\)，加法同态加密操作为\([[\cdot]]\)，那么加密后的损失可以记作： \[ \begin{aligned} ~[[L]] &=[[\sum_{i}(u_i^A+u_i^B-y_i)^2+\frac{\lambda}{2}(||\Theta_A||^2+||\Theta_B||^2)]] \\ &=[[\sum_{i}(u_i^A)^2+\frac{\lambda}{2}||\Theta_A||^2]]+[[\sum_{i}(u_i^B-y_i)^2+\frac{\lambda}{2}||\Theta_B||^2]]+2\sum_{i}[[u_i^A(u_i^B-y_i)]] \\ &=[[L_A]]+[[L_B]]+[[L_{AB}]] \end{aligned} \] 我们设\([[d_i]]=[[u_i^A]]+[[u_i^B-y_i]]\)，则关于训练函数的损失函数的梯度可以表示为： \[ [[\frac{\partial L}{\partial \Theta_A}]]=2\sum_{i}[[d_i]]\boldsymbol{x}_i^A+[[\lambda\Theta_A]] \\ [[\frac{\partial L}{\partial \Theta_B}]]=2\sum_{i}[[d_i]]\boldsymbol{x}_i^B+[[\lambda\Theta_B]] \]

由于\(d_i\)依赖于A和B的本地计算结果，因此这一过程首先要求A方和B方使用C方提供的公钥，对自己的计算结果进行加密，然后再传送计算结果。

整个训练步骤可以表述为：

步骤	A	B	C
1	初始化\(\Theta_A\)	初始化\(\Theta_B\)
2	计算\([[u_i^A]]\)和\([[L_A]]\)，并将其发送给B	计算\([[u_i^B]]\)，\([[d_i]]\)和\([[L]]\)，并将\([[d_i]]\)发送给A，将\([[L]]\)发送给C
3	初始化一个随机掩码\(R_A\)，计算\([[\frac{\partial L}{\partial \Theta_A}]]+[[R_A]]\)，然后发送给C	初始化一个随机掩码\(R_B\)，计算\([[\frac{\partial L}{\partial \Theta_B}]]+[[R_B]]\)，然后发送给C	解密\([[L]]\)，\([[\frac{\partial L}{\partial \Theta_A}]]+[[R_A]]\)和\([[\frac{\partial L}{\partial \Theta_B}]]+[[R_B]]\)，然后将\(\frac{\partial L}{\partial \Theta_A}+R_A\)发送给A，将\(\frac{\partial L}{\partial \Theta_B}+R_B\)发送给B
4	更新\(\Theta_A\)	更新\(\Theta_B\)

在训练完成之后，A得到\(\Theta_A\)，B得到\(\Theta_B\)。

在接下来的预测过程中，C方会给A和B发送用户ID，然后A方和B方各自计算出\(u^A\)和\(u^B\)并发给C，C方通过计算\(u^A+u^B\)得到最终的结果。

联邦迁移学习

在实际情况下，联邦学习的参与方所拥有的数据集可能存在高度的差异。比如参与方的数据集之间可能只有少量重叠的特征或者样本ID；数据集的分布或者规模可能差别很大；某些参与方可能只有数据，而缺少标注数据。为了解决这些问题，联邦学习可以结合迁移学习技术，使其应用于更广的业务范围，同时帮助只有少量数据和弱监督的应用建立有效且精确的机器学习模型，并且遵守数据隐私和安全条例的规定。这种组合被称为联邦迁移学习。

联邦迁移学习分为如下三种类别：

• 基于实例的联邦迁移学习：对于横向联邦学习，参与方的数据通常来自于不同的分布，这可能会导致在这些数据上训练的机器学习模型的性能较差，参与方可以有选择地挑选或者加权训练样本，以减小分布差异，从而可以将目标损失函数最小化；而对于纵向联邦学习，参与方可能具有不同的业务目标，因此对齐的样本及某些特征可能会对联邦学习产生负面影响，此时参与方可以有选择地挑选用于训练的特征和样本，从而避免负面影响。
• 基于特征的联邦迁移学习：参与方协同学习一个共同的表征空间，这一空间可以缓解从原始数据转换而来的表征之间的分布和语义差异，从而使知识可以在不同领域之间传递。对于横向联邦学习，可以通过最小化参与样本之间的最大平均差异；而对于纵向联邦学习，则可以通过最小化对齐样本中属于不同参与方的表征之间的距离。
• 基于模型的联邦迁移学习：参与方共同学习一个共享模型，这个模型可以用于迁移学习；或者是参与方利用预训练模型作为联邦学习任务的全部或者部分初始模型。横向联邦学习本身就是一种基于模型的联邦迁移学习；而对于纵向联邦学习，则可以从对齐的样本中学习预测模型，或者是利用半监督学习技术推断缺失的特征或者标签，然后使用扩大的训练样本去训练更加准确的共享模型。

相比于传统的迁移学习，联邦迁移学习基于分布在多方的数据来建立模型，并且每一方的数据不能集中到一起或者公开；同时，联邦迁移学习要求对用户隐私和数据进行安全保护。

激励机制

对于联邦而言，参与方持续地参与到联邦的学习进程是其长期成功的关键所在。参与方加入联邦，构建一个机器学习模型，从而为联邦做出贡献，训练出的模型可以产生收益。联邦可以与参与方们共享收益，以此作为激励。

一般广泛使用的收益分享方法可以分为三类：

• 平等：由数据联邦产生的任何效用，都平均分配给帮助生成它的参与方
• 边际收益：数据联邦中参与方的效益是它加入团队时所产生的效用
• 边际损失：数据联邦中的参与方的效益是它离开团队时所产生的效用

虽然参与方对于数据联邦的贡献是一个重要的考虑因素，但是在为联邦学习设计激励机制时，除此之外还需要考虑一些其它因素。比如一个拥有高质量数据的公司占有很大市场份额，它在参与联邦学习之后将会在无意间帮助到它的竞争者。也就是说它加入联邦之后会付出一些代价。

因此为了维持数据联邦的长期稳定，并逐渐吸引更多的参与方加入，就需要综合考虑各种因素，制定一个强调公平性，并且适合联邦学习环境的激励机制。

除了基于收益分享博弈的方法，反向拍卖也可以被用来制定激励计划，以提高各个参与方贡献数据的质量。

参考

1. 联邦学习，杨强等
2. 《数据价值-密码学篇》：同态加密 - 知乎 (zhihu.com)
3. 联邦学习资料整理 - 知乎 (zhihu.com)