【联邦学习之旅】B1 《联邦学习》读书笔记

离开微众后才开始看由之前同事写的国内第一本联邦学习专著，多做一点笔记以表敬意。

注：很多内容其实和本博客中 1 联邦学习简介有重复，这里不再赘述。

引言

重点关注谷歌将联邦学习用于智能手机上的语言预测模型这个案例，关键技术：联邦平均(Federated Averaging)
横向联邦学习（按样本划分的联邦学习）：参与方的数据有重叠的数据特征，但样本不同
纵向联邦学习（按特征划分的联邦学习）：参与方的样本是对齐的，但特征不同

隐私、安全及机器学习

面向隐私保护的机器学习(Privacy-Preserving Machine Learning, PPML) 中的著名方法
- 安全多方计算(Secure Multi-party Computation, MPC)
- 同态加密(Homomorphic Encryption, HE) 用于隐私保护模型训练和预测
- 差分隐私(Differential Privacy, DP) 用于防止数据泄露
同态加密的分类
- 部分同态加密 PHE: 只支持部分计算，如加法同态，乘法同态
- 些许同态加密 SHE: 一些运算操作只能执行有限次，使用了噪声数据，每次操作都会增加噪声量，所以不能超过上限
- 全同态加密 FHE: 无限次数的加法和乘法运算，太理想化

分布式机器学习

数据并行、模型并行、图并行、任务并行、混合并行、交叉并行
保护数据隐私的两类常用方法
- 模糊处理(Obfuscation)：随机化、添加噪声或修改数据使其拥有某一级别的隐私，如差分隐私
- 密码学方法：通过不将输入值传给其他参与方的方式或者不以明文方式传输，使分布式计算过程安全化，如 MPC，包括不经意传输、秘密共享、混淆电路和同态加密
这部分内容很多都需要看论文原文，重点关注下 FedAvg

横向联邦学习

两种常用的横向联邦学习系统架构：Client-Server 和 Peer-to-Peer
客户端-服务器架构的训练过程
- 各参与方在本地计算模型梯度，并使用同态加密、差分隐私或秘密共享等加密技术，对梯度信息进行掩饰，并将演示后的结果（简称为加密梯度）发送给聚合服务器
- 服务器进行安全聚合(secure aggregation)操作，如使用基于同态加密的加权平均
- 服务器将聚合后的结果发送给各参与方
- 各参与方对收到的梯度进行解密，并使用解密后的梯度结果更新各自的模型参数
传输加密梯度的就是梯度平均，传输模型参数的就是模型平均
梯度平均
- 优点：准确的梯度信息 + 有保证的收敛性
- 缺点：加重通信负担 + 需要可靠连接
模型平均
- 优点：不受 SGD 限制 + 可以容忍更新缺失 + 不频繁的同步
- 缺点：不保证收敛性 + 性能损失
对等网络架构：各方使用安全链路相互之间传输模型参数信息。发送和接收模型的参数信息一般使用循环传输或随机传输的方法。
全局模型评估的过程
- 每个参与方分别使用本地的测试数据集，对现有的横向联邦学习的模型进行性能评估。对于二分类任务，生成本地模型测试结果 $(N_{TP}^{(k)},N_{FP}^{(k)},N_{TN}^{(k)},N_{FN}^{(k)})$
- 每个参与方参与方给协调方发送本地模型测试结果
- 协调方收集到全部的本地模型测试结果后，可以进行全局模型性能测试结果的计算，比如对于二分类任务，全局召回率为 $ \frac{\sum_{k=1}^KN_{TP}^{(k)}}{\sum_{k=1}^K(N_{TP}^{(k)}+N_{FN}^{(k)})} $
- 协调方将最终结果发送给所有的参与方

联邦平均算法

联邦平均算法也被称为并行重启的随机梯度下降算法，或者 local SGD
联邦优化的关键特性
- 数据集的非独立同分布：不同参与方的数据分布可能不一致，模型更新的方式有变化
- 不平衡的数据量：不同参与方的数据量不同
- 数量很大的参与方：数量很多很分散，比如各个移动设备
- 慢速且不稳定的通信连接：网络相比数据中心不可靠得多

用联邦平均算法来解决联邦优化问题，可以用于深度神经网络训练中遇到的非凸损失函数，适用于任何下列有限加和形式的损失函数，其中 n 表示训练数据的数量，$\omega \in R^d$ 表示 d 维的模型参数（如 DNN 的权重值）

$$ min_{\omega \in R^d}f(\omega)=\frac{1}{n}\sum_{i=1}^n f_i(\omega)$$

对于机器学习问题，我们一般选取 $f_i(\omega)=\mathcal{L}(x_i, y_i; \omega)$，其中 $\mathcal{L}(x_i, y_i; \omega)$ 表示给定模型参数 $\omega$ 上对样本 $(x_i, y_i)$ 进行预测所得到的损失结果。

具体的算法请参考书本 65 和 67 页的说明。

联邦平均算法的改进

通信效率的提升
- 背景：每一个全局模型训练轮次中，每一个参与方都需要给服务器发送完整的模型参数更新。线代 DNN 模型通常有数百万个参数，通信开销非常大
- 方式 1：压缩的模型参数更新。压缩的模型参数更新通常是真正更新的无偏估计值，即平均值后是相通的
- 方式 2：结构化的模型参数更新。
- 梯度压缩也可以用来降低通信开销，例如 DGC（深度梯度压缩方法）
参与方选择方法，降低通信开销和时间消耗
- ① 资源检查，了解参与方的计算量和可能的时间
- ② 参与方选择，目标是在限定时间内选择尽可能多的参与方

挑战与展望

横向联邦学习发展仍处于初级阶段，且面临诸多技术挑战。

无法查看或检查分布式的训练数据 -> 很难选择模型的超参数和优化器
如何激励公司和机构参与到横向联邦学习系统中 -> 需要数据保护政策+激励机制+商业模型
如何防止参与方的欺骗 -> 恶意污染模型/上传虚假数据得到收益

纵向联邦学习

主要有两个步骤：

加密实体对齐，即在不知道对方数据的情况下，能够对齐用户 ID，并用这部分数据进行训练
加密模型训练，又分为四个步骤（这里 B 有标签）
1. 协调者 C 创建秘钥对，并将公钥发给 A 和 B
2. A 和 B 对中间结果进行加密和交换，中间结果用来帮助计算梯度和损失值
3. A 和 B 计算加密梯度并加入附加掩码(additional mask)。B 还会计算加密损失。A 和 B 将加密的结果发送给 C
4. C 对梯度和损失信息进行解密，并将结果发送回 A 和 B。A 和 B 解除梯度信息上的掩码，并根据这些梯度信息来更新模型参数

安全联邦线性回归

给定学习率 $\eta$，正则化参数 $\lambda$，A 方本地数据集 $\{x_i^A\}_{i\in D_A}$，B 方本地数据集和 Label $\{x_i^B, y_i\}_{i\in D_B}$，A 和 B 方的模型参数 $\Theta_A, \Theta_B$，则训练目标为

$$ \min_{\Theta_A, \Theta_B} \sum _{i} ||\Theta_A x_i^A + \Theta_B x_i^B - y_i||^2 + \frac{\lambda}{2}(||\Theta_A||^2 + ||\Theta_B||^2 ) $$

设 $u_i^A=\Theta_Ax_i^A, u_i^B=\Theta_Bx_i^B$，则加密损失如下，其中 $[[·]]$ 表示加法同态加密：

$$[[L]] = [[\sum _{i} (u_i^A + u_i^B - y_i)^2 + \frac{\lambda}{2}(||\Theta_A||^2 + ||\Theta_B||^2 )]]$$

设 $ [[L_A]] = [[\sum _{i} (u_i^A )^2 + \frac{\lambda}{2}||\Theta_A||^2]],\ [[L_B]] = [[\sum _{i} (u_i^B -y_i )^2 + \frac{\lambda}{2}||\Theta_B||^2]]$ 且 $[[L_{AB}]] = 2\sum _{i} [[u_i^A(u_i^B-y_i)]] $，则有：

$$[[L]]=[[L_A]]+[[L_B]]+[[L_{AB}]]$$

类似的，设 $[[d_i]]=[[u_i^A]]+[[u_i^B-y_i]]$，则关于 AB 两方的模型参数的损失函数的梯度为（就是求偏导，更新参数的时候用）：

$$[[\frac{\partial L}{\partial \Theta_A}]] = 2\sum _{i}[[d_i]]x_i^A + [[\lambda\Theta_A]] $$ $$[[\frac{\partial L}{\partial \Theta_B}]] = 2\sum _{i}[[d_i]]x_i^B + [[\lambda\Theta_B]]$$

通过公式我们可以看到，$u_i^A, u_i^B$，可以由 A 方或 B 方独立计算，而如果想要计算梯度，因为 $d_i$ 两边都需要，所以需要两方共同来进行计算。

具体的训练过程如下，其中 $R_A,R_B$ 是 A 方和 B 方的随机掩码，主要用于保证 C 方（信息汇总方，用于协调和评估训练过程）无法还原真实准确的梯度信息。

初始化+秘钥分发
1. A 方：初始化 $\Theta_A$
2. B 方：初始化 $\Theta_B$
3. C 方：创建加密密钥对，并将公钥发送给 A 方和 B 方
计算 Loss
1. A 方：计算 $[[u_i^A]], [[L_A]]$ 并发送给 B 方（用于计算 $[[d_i]]$
2. B 方：收到 A 方传输过来的结果后，计算 $[[u_i^B]], [[d_i]], [[L]]$
汇总 Loss 并求解梯度
1. A 方：初始化 $R_A$，计算 $[[\frac{\partial L}{\partial \Theta_A}]] + [[R_A]] $，并发送给 C 方
2. B 方：初始化 $R_B$，计算 $[[\frac{\partial L}{\partial \Theta_B}]] + [[R_B]] $，并发送给 C 方
3. 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 方
更新模型参数
1. A 方：利用梯度信息更新 $\Theta_A$
2. B 方：利用梯度信息更新 $\Theta_B$

预测时 A 方和 B 方需要协作计算结果，具体过程如下：

ID 对齐
1. C 方：将用户 ID i 发送给 A 方和 B 方
计算结果
1. A 方：计算 $u_i^A$ 并发送给 C 方
2. B 方：计算 $u_i^B$ 并发送给 C 方
3. C 方：计算 $u_i^A+u_i^B$ 的结果，即为最终的预估值

安全联邦提升树

SecureBoost 与需要将数据收集于一处的非联邦梯度提升树算法具有相同的精确度。参与计算的两方为：

主动方(active party)：同时拥有样本特征和样本标签，也是协调者，计算每个树节点的最佳分割
被动方(passive party)：只提供样本特征，需要和主动方共同构建模型来预测标签

SecureBoost 有两个主要步骤，第一步是在隐私保护下对参与方之间具有不同特征的重叠用户进行样本对齐。第二步是所有参与方通过隐私保护协议共同学习一个共享的梯度提升树模型。

XGBoost 回顾

给定一个拥有 n 个样本和 d 个特征的数据集 $D=\{(x_i, y_i)\}$，其中 $|D|=n,x_i\in \mathbb{R}^d, y_i \in \mathbb{R}$。XGBoost 通过使用 K 个决策树 $f_k, k=1,2,...,K$ 的集成来预测输出，用下面的公式表示：

$$\hat{y_i}=\sum_{k=1}^K f_k(x_i), \forall x_i \in \mathbb{R^d}, i=1,2,...,n$$

决策树集成模型的学习是通过寻找一组最佳的决策树以达到较小的分类损失，并且具有较低的模型复杂度。在梯度提升树中，这个目的是通过迭代优化真实标签和预测标签的损失（例如损失的平方或损失函数的泰勒近似）来达到的。在每次迭代中，我们尝试添加一棵新的树，以尽可能地减少损失，同时不会引入过多的复杂度。因此，第 t 轮的迭代目标函数为：

$$L^{(t)}\triangleq \sum_{i=1}^n[l_{loss}(y_i, \hat{y_i}^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t)$$

其中 $l_{loss}$ 表示损失函数；$g_i=\partial_{\hat{y}^{(t-1)}}l_{loss}(y_i, \hat{y}^{(t-1)}); h_i=\partial_{\hat{y}^{(t-1)}}^2 l_{loss}(y_i, \hat{y}^{(t-1)}) $ 是在损失函数上的一阶梯度和二阶梯度；$\Omega(f_t)$ 表示新添加的树的复杂度。

构建一棵决策树是从深度零开始，然后决定每个节点的分割，直到达到最大深度。那么如何在树的每一层决定某一节点的最佳分割(Optimal Split)呢？一个简单的方法是通过分割带来的增益去判断，计算分割的公式如下，其中 $I_L, I_R$ 分别表示分割后左右子节点的样本空间，$\lambda$ 表示超参数，分数最高的就是最佳分割：

$$L_{split}=\frac{1}{2}\left[ \frac{(\sum_{i\in I_L} g_i)^2 }{ \sum_{i\in I_L} h_i + \lambda} + \frac{(\sum_{i\in I_R} g_i)^2 }{ \sum_{i\in I_R} h_i + \lambda} - \frac{(\sum_{i\in I} g_i)^2 }{ \sum_{i\in I} h_i + \lambda}\right]$$

当得到了一个最佳树结构时，可以通过以下公式计算叶节点 $j$ 的最佳权值 $w^*$，其中 $I_j$ 是节点 $j$ 的样本空间：

$$w_j^*=-\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}$$

SecureBoost 的训练过程

从上面的公式可以看到，$g_i,h_i$ 都包含类标签，所以只能由主动方计算得到。为了主动方能够更好地进行分割评估，在将 $g_i,h_i$ 进行加法同态加密后发送给被动方，被动方需要进行梯度聚合，之后再由主动方进行分割评估。

聚合梯度统计值算法

输入 1：I，当前节点的样本空间
输入 2：d，特征维度
输入 3：$\{[[g_i]],[[h_i]]\}_{i\in I}$ （即每个样本的一阶和二阶梯度）
输出：$G\in \mathbb{R}^{d \times l}, H\in \mathbb{R}^{d \times l}$ （这里 l 就是分桶的个数，就是后面的百分位数个数）

$$ \begin {split} for\ &k = 0 \to d\ do \\ \ \ &通过特征 k 的百分位数，得到 S_k={s_{k1}, s_{k2}, ..., s_{kl}} \\ end &\ for \\ for\ &k = 0 \to d\ do \\ \ \ &G_{k,v} = \sum_{i \in \{i|s_{k,v} \ge x_{i,k} \gt s_{k,v-1}\}}[[g_i]] \\ \ \ &H_{k,v} = \sum_{i \in \{i|s_{k,v} \ge x_{i,k} \gt s_{k,v-1}\}}[[h_i]] \\ end &\ for \end {split} $$

上面的算法中，每个被动方首先要对其所有的特征进行分桶，然后将每个特征的特征值映射至每个桶中。基于分桶后的特征值，被动方将聚合响应的加密梯度统计信息。通过这种方法，主动方只需要从所有被动方处收集聚合的加密梯度信息，即可更高效地确定全局最优分割，记为 $[参与方 id(i),特征 id(k_{opt}),阈值 id(v_{opt})]$。

在主动方得到全局最优分割之后，将 $特征 id(k_{opt}),阈值 id(v_{opt})$ 返回给被动方 i，被动方 i 基于此决定选中特征值的阈值。然后，被动方 i 根据选中特征的阈值对当前样本空间进行划分。此外，被动方 i 会在本地建立一个 lookup table 记录选中特征的阈值，表示为 [记录 id，特征，阈值]。此后，被动方 i 将记录 id 和划分后节点左侧的样本空间 $I_L$ 发送给主动方。主动方会根据收到的样本空间 $I_L$ 对当前节点进行分割，并将当前节点 [参与方 id，记录 id] 关联。算法将继续对树进行划分，直到达到停止条件或最大深度，最终主动方直到整个数的结构。

预测过程

新的样本特征分散在各个参与方，并且不能公开。所以分类过程从主动方的 root 节点开始：

主动方查询与当前节点相关联的 [参与方 id，记录 id] 记录。基于该记录，主动方向相应参与方发送待标注样本的 id 和记录 id，并且询问下一步的树搜索方向（左子节点还是右子节点）
被动方接收到待标注样本的 id 和记录 id 后，将待标注样本中相应特征的值与本地查找表中的记录 [记录 id，特征，阈值] 中的阈值进行比较，得到下一步树的搜索方向。然后，该被动方将搜索决定发往主动方
主动方接收到被动方传来的搜索决定，前往相应的子节点
迭代步骤 1~3，直到达到一个叶节点得到分类标签以及该标签的权值

挑战与展望

非常依赖通信的可靠性
传输模型中间结果很耗时间 -> 流水线计算
基于隐私保护的实体对齐技术

联邦迁移学习

在横向和纵向取得比较大进展之前，迁移学习还需要继续努力，这一章暂略。

联邦学习激励机制

最大化联邦的可持续经营，最小化参与方间的不公平性，动态地将给定的预算分配给联邦中的各个参与方。

这一节非常前沿，这里只简单列举一下，有需要再深入研究

收益分享博弈
1. 平等
2. 边际收益
3. 编辑损失
反向拍卖
注重公平的收益分享框架
1. 建模贡献
2. 建模代价
3. 建模期望损失
4. 建模时间期望损失
5. 策略协调
6. 计算收益评估比重

联邦学习与 CV/NLP/推荐系统

联邦计算机视觉

允许多家公司在不损害数据隐私的前提下，利用所有数据协作地构建共享的目标检测模型：

各参与公司从服务器下载现有的共享目标检测模型，如 YOLO
各公司使用本地标记数据对模型进行训练
各公司通过安全协议，将训练后的模型参数上传至服务器
服务器聚合所有参与方的模型参数，并更新共享目标检测模型

联邦学习最优前途、最具挑战性的应用之一可能是基于分散在各种设备商的已购数据而构建的 CV 驱动自动驾驶系统。

联邦学习自然语言处理

典型应用：基于移动设备用户频繁键入的单词来学习词库外(Out-of-Vocabulary, OOV)单词。具体的模式和 CV 类似，都是用户本地训练模型，然后共享模型参数。

联邦学习与推荐系统

推荐模型分四种

协同过滤
基于内容的推荐系统
基于模型的推荐系统
混合推荐系统

联邦推荐步骤：

每一个客户从服务器下载全局商品因子矩阵。该矩阵可以是随机初始化的模型或预训练模型
每一个客户聚合显式数据和隐式数据。显式数据包括用户的反馈，例如对商品的评分和评论。隐式数据由用户订单历史、购物车清单、浏览历史、点击历史、搜索日志等信息组成
每一个客户使用本地数据和全局商品因子矩阵对本地用户因子向量进行更新
每一个客户使用本地数据和本地用户因子想来那个，计算全局商品因子矩阵的本地更新，并通过一个安全协议将更新上传至服务器
服务器通过联邦加权算法（例如联邦平均算法）聚合从各个客户端上传的本地模型更新。并使用聚合的结果对全局商品因子矩阵进行更新。之后，服务器将全局商品因子矩阵发送给各个客户。

联邦强化学习

强化学习是机器学习的一个分支，主要研究序列决策问题。强化学习系统通常由一个动态环境和与环境交互的一个或多个智能体(agent)组成。智能体根据当前环境条件选择动作决策，环境在智能体决策的影响下发生相应改变，智能体可以根据自身的决策、环境的改变过程得出奖励。智能体必须处理顺序决策问题，从而获得最大化价值函数的结果（即期望的折扣奖励总和或期望奖励）。循环：Status-Action-Reward-Status-Action-Reward-SARS-SARS。

问题的难点在于：

智能体对于一个给定状态的最优操作的知识有限。一般情况下，对于给定状态，智能体需要在特定的时间步长内解决最优化决策过程。
智能体的动作将影响环境的未来状态，进而影响智能体未来的决策。智能体必须在当前回报和未来期望回报之间进行权衡。最佳动作的选择需要考虑动作的影响、未来的后果，因此可能需要前瞻或计划。

除了智能体和环境，强化学习系统还包括四个关键子元素：

策略(Policy)：定义了智能体在给定状态时选择动作的方式。策略可以是确定性的，也可以是随机性的。策略是强化学习智能体的核心所在，其定义了智能体根据环境状态和智能体记忆知识生成决策的过程。
奖励信号(Reward)：奖励定义了在强化学习问题中，环境到智能体的即时反馈。智能体的目标是最大化其长期获得的总奖励。奖励信号是策略调整的主要依据和基础
价值函数(Value function)：价值函数是一种在给定状态下测量动作的长期回报奖励的方法。奖励是由环境直接给出或由智能体根据相应奖励函数计算得出的，而价值是根据对一个智能体在其整个生命周期中进行的系列观察后评估计算得出
环境模型(可选)：一种模拟环境动作的虚拟模型，可能预测结果的下一状态和下一奖励，以及在实际发生之前考虑到未来可能的情况。

强化学习算法分类

基于模型与无模型
基于价值与基于策略
蒙特卡洛更新与时间差分更新
在策略与离策略
1. SARSA 是一种在策略的时间差分算法，使用当前策略来生成动作并以此更新当前策略
2. Q-Learning 是一种离策略的时间差分算法，使用一个不同的探索性策略来生成动作，目标策略将基于这些动作来更新

关于联邦强化学习，目前应用较少，等强化学习发展更完善再进一步深挖。

应用场景

这一章说实话比较虚，有个概念就好。

智惠消费金融(Smart consumer finance)：利用机器学习技术，为信用良好的消费者人群提供定制化的金融服务，以鼓励其消费
医疗相关数据进行联邦建模
跨学科课程教育系统
城市计算和智慧城市
边缘计算与物联网
区块链与 5G

写在最后

总体来说，这本书还是能够完成介绍和引入这个任务的。不过总体来说不够深入，各个章节太零散，行文风格差距较大，除了核心两三章外很多内容都有划水的嫌疑。当然，作为行业第一本，也不能苛求太多，先跑起来！