联邦学习——笔记001

2022.11.16周三

今天学习了联邦学习的开山之作———Communication-Efficient Learning of Deep Networks from Decentralized Data（从非中心化的数据中，高效通信地学习深度网络）

（一）论文概览

1.摘要

现代移动设备拥有大量的适合模型学习的数据，基于这些数据训练得到的模型可以极大地提升用户体验。例如，语言模型能提升语音设别的准确率和文本输入的效率，图像模型能自动筛选好的照片。然而，移动设备拥有的丰富的数据经常具有关于用户的敏感的隐私信息且多个移动设备所存储的数据总量很大，这样一来，不适合将各个移动设备的数据上传到数据中心，然后使用传统的方法进行模型训练。作者提出了一个替代方法，这种方法可以基于分布在各个设备上的数据（无需上传到数据中心），然后通过局部计算的更新值进行聚合来学习到一个共享模型。作者定义这种非中心化方法为“联邦学习”。作者针对深度网络的联邦学习任务提出了一种实用方法，这种方法在学习过程中多次对模型进行平均。同时，作者使用了五种不同的模型和四个数据集对这种方法进行了实验验证。实验结果表明，这种方法面对不平衡以及非独立同分布的数据，具有较好的鲁棒性。在这种方法中，通信所产生的资源开销是主要的瓶颈，实验结果表明，与同步随机梯度下降相比，该方法的通信轮次减少了10-100倍。

2.引言

手机和平板电脑逐渐成为了很多人主要的计算设备[30,2]。这些设备具有功能强大的传感器（包括相机、麦克风以及GPS），并且这些设备经常被人们随身携带，这意味着设备中存储了大量包含隐私信息的数据。基于这些数据训练的模型有望给更智能的应用程序提供动力，进而提升用户的使用效率。但是，这些数据富含用户的隐私信息，因此若将其上传存储在一个数据中心将具有很大的风险。

作者探索了一种学习技术，这种学习技术可以使用户享受到从这种隐私数据中训练出的共享模型所带来的益处，同时，不需要将其上传至统一的数据中心。作者定义这种方法为“联邦学习”，因为学习任务是由所参与学习的设备在一个中心服务器的协调下共同联合完成（称参与学习的设备为客户端）。每一个客户端拥有一个本地存储的训练数据集，该训练数据集不会上传到中心服务器。基于每个客户端的计算，服务器对当前全局模型进行更新，在客户端与服务器通信过程中，仅传输了更新值。这种方法直接践行了“重点收集”或“数据最小化”原则，这项原则被白宫于2012年在关于用户数据隐私的报告[39]中提出。由于这些更新值专门用于改进当前的模型，因此，一旦使用之后，无需对更新值进行存储。

3.贡献

img

img

img

img

作者假设一个同步更新框架，通过多轮通信进行更新。现有固定的\(K\)个客户端，每个客户端拥有一个固定的本地数据集。每轮更新的开始，随机选择\(C\)个客户端，并且服务器给每个客户端发送现有的全局算法状态（例如算法状态可以是当前全局模型的参数值）。在每轮学习过程中仅选用一部分客户端是为了提升性能，因为实验表明，当客户端超过一定数量后学习性能会下降。每一个被选择的客户端基于本地存储的数据以及全局状态进行计算更新，然后将更新后的算法状态发送给服务器。服务器利用客户端发送回来的算法状态对全局状态进行更新，并且重复这个过程。

本文目的是使用额外的计算来减少训练模型所需通信的轮次。有两种基本的额外计算方法：

  1. 提高并行度，每两轮通信间，使用更多的独立工作的客户端；
  2. 增加每个客户端的计算：每个客户端除了执行一个简单的计算（比如计算梯度），还要在每两轮通信间进行更复杂的计算；

（二）联邦平均算法

本文着重介绍了核心算法即联邦平均算法

补充知识一

以下为补充知识:

一、优化算法

大数据量优化算法——随机梯度下降法（Stochastic Gradience Descent,SGD）& 小批量梯度下降法

1.随机梯度下降法
1.1原理

简而言之，随机梯度下降法(Stochastic Gradience Descent,简称SGD)的核心思想就是每次迭代时只用一个样本来更新梯度，这样不停的遍历整个训练集，直到模型收敛为止。举例 ，其平方损失函数表示如下：

\[\operatorname{cost}\left(\theta,\left(x^{(i)}, y^{(i)}\right)\right)=\frac{1}{2}\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right)^2 \ldots \ldots(i \in[1, m])
\]

（注意：此处的\(\theta\)：\(costFunction\)中的\(\theta\) 是每次迭代优化计算得到参数）

此处参考：https://www.cnblogs.com/xwh-blogs/p/13629085.html 中的解释
img

具体步骤为：

  • 对训练集进行随机化，打乱顺序。
  • 对数据集不断进行遍历，每次抽取一个样本进行梯度更新。
  • 直到模型收敛，或者达到一定更新次数为止。
1.2优缺点

与传统的梯度下降法相比，其优点很明显，即:

  • 更新速度快。

同时，其缺点也很明显：

  • 准确度下降，因为单个样本的所拥有的噪声较大，所以即使目标函数为强凸函数，SGD依然很难正确收敛。
  • 更容易达到局部最优。
  • 不利于并行化。
2.小批量梯度下降法
2.1原理

小批量梯度下降法(mini-batch Gradient Descent)为传统的批量梯度下降法与随机梯度下降法的折中，其核心思想为，指定一个常数\(b\)，每次选取训练集中\(b\)个样本进行数据更新，不停的遍历整个训练集，直到模型收敛为止。其损失函数为：

\[\operatorname{cost}\left(\theta,\left(x^{(i)}, y^{(i)}\right)\right)=\frac{1}{2 b} \sum_{i=k}^{k+b}\left(h_\theta\left(x^{(i)}\right)-y^{(i)}\right)^2 \ldots \ldots\left(k \epsilon\left[1, \frac{m}{b}\right]\right)
\]

具体步骤为：

  • 对训练集进行随机化，打乱顺序。
  • 对数据集不断进行遍历，每次抽取\(b\)个样本进行梯度更新。
  • 直到模型收敛，或者达到一定更新次数为止。
    通常会令\(b\)介于2-100之间，方便向量化处理。
2.2优缺点

其优点有：

  • 在每一l轮给batch上更新参数时，通过矩阵运算，并不会比单个数据慢太多。
  • 与SGD相比，每次使用一个batch可以大大的减小收敛所需要的迭代次数。
  • 易于并行化。

其缺点有：

  • 引入了batch这一参数。
    当batch_size在合理范围内增大时，能增大内存利用率；矩阵运算等并行化计算；减小迭代次数；使下降的方向更准确，减小震荡的可能。
    相应的当batch_size过大时，内存的容量可能不足；迭代次数虽然减少，但是每次迭代所需要的时间愈发增加，从而使得总体时间变慢；当其达到一定程度时，下降的方式基本不发生变化。

实用的经验建议是：先用较小的batch_size，步数多但收敛快；最后几轮时使用较大的batch_size，使得精度更大。

二、多机器优化

使用多主机或多GPU优化训练的方法可简单分为数据并行以及模型并行。

1.模型并行

其中基于模型的并行即为一个GPU或主机复制模型中一个部分的训练，即为流水线。在神经网络中可理解为一个GPU负责整个网络中的一个层次的训练。

2.数据并行

而基于数据的并行常见的有模型平均，同步随机梯度下降和异步随机梯度下降。

  • 模型平均(model average)是指将数据集划分到不同的GPU上，各个GPU分布训练自己的模型，最后汇总到主核上，所有参数取各个GPU模型的平均数。由于各个GPU之间没有互相交流，各个模型随数据集的偏差可能差距较大，所以效果不是很好。

  • 同步随机梯度下降(synchronous Stochastic Gradience Descent，简称SSGD)同样将数据集划分到不同的GPU上，只有主核上有模型。正式训练时主核将模型参数发送给各个GPU，各个GPU分别根据自己数据集计算出梯度，需要进行一次同步，然后将梯度统一发送给主核，主核用平均的梯度更新完自己的模型后，又将新的模型参数发送给各个GPU，如此往复。当模型收敛时，训练结束。

  • 异步随机梯度下降(Asynchronous Stochastic Gradience Descent，简称ASGD)有别于SSGD的地方在于每个GPU在计算出梯度后，就立马将梯度发送给主核。主核在收到梯度时就会立刻进行参数更新，然后将训练出的参数发送给梯度来源的核。这样各个GPU只要计算出了梯度就立刻发送给主核并立即得到反馈，不需要同步。但这也使得所有GPU上的模型参数的“版本”不一致。

参考：https://blog.csdn.net/weixin_41542958/article/details/104839306

1.联邦平均算法

下面回归联邦平均算法的学习

最近深度学习取得巨大成功在很大程度上依赖于随机梯度下降优化算法及其变种；事实上，在很多应用方面的进步可以理解为，采用了易于使用梯度下降进行优化的模型结构（以及损失函数）[16]。因此，作者在构建联邦优化算法时自然地使用了随机梯度下降。

随机梯度下降天然地可以被用于联邦优化，因为，每轮通信完成一次基于一个批次数据的梯度计算（在被随机选择的客户端上进行）。（注：该批次数据即一个batch,是从随机选取的客户端的数据集中选取的部分数据） 这种方法具有很高的计算效率，但是若想学习出好的模型，需要大量轮次的训练（甚至即使使用了一个如批次归一化的高级方法，Ioffe和Szegedy[21]构建手写数字识别的模型训练了50000轮，每次训练使用60个样本），作者在CIFAR-10数据集上的实验考虑了该基准（即训练出好的模型所需要的训练次数）。

在联邦框架下，更多用户的参与几乎不会增加时间消耗，所以作者使用大批量同步随机梯度下降法作为对比的基准，因为Chen等人[8]的实验验证了该方法在数据中心化学习框架下可以达到很好的效果，且优于异步方法。为了在联邦学习中应用该方法，作者每轮选择\(C(0\leqslant C\leqslant 1)\)比例的客户端 （注：每轮选取部分样本，即客户端进行随机梯度的更新），在这些客户端上基于全部数据计算损失函数的梯度值。因此，\(C\)控制了全局批次大小，如果\(C=1\)，那么意味着全批次梯度下降2。 作者称这种基线算法为联邦随机梯度下降(FedSGD)。（注：FedSGD中的\(C\)不一定等于1，下文中说的\(C=1\) 的情况是一种典型情况，我的理解）

img

一种典型的联邦随机梯度下降设置\(C=1\)以及一个固定的学习率\(\eta\) ，第\(k\)个客户端计算梯度为\(g_k=\nabla F_k\left(w_t\right)\)，中心服务器聚合每个客户端计算的梯度以此来更新模型参数 (注：比较简单的梯度加权求平均），即：

\[w_{t+1} \leftarrow w_t-\eta \sum_{k=1}^K \frac{n_k}{n} g_k=w_t-\eta \nabla f\left(w_t\right)
\]

其中，\(\sum_{k=1}^K \frac{n_k}{n} g_k=\nabla f\left(w_t\right)\) (注：以各个客户端依据数据量多少对梯度下降求加权平均作为模型损失函数下降的梯度)。

另一种等价更新方法为：每个客户端给予本地数据分别各自对当前模型参数\(w_t\)进行更新，即：

\[w_{t+1}^k \leftarrow w_t-\eta g_k
\]

然后中心服务器对每个客户端更新后的参数进行加权平均：

\[w_{t+1} \leftarrow \sum_{k=1}^K \frac{n_k}{n} w_{t+1}^k
\]

两种方法的区别在于：第一种方法客户端求出梯度就给中心服务器，而自己暂不更新模型参数，而是等待服务器汇总梯度的加权平均，对中心服务器的模型进行更新，更新好之后返回模型参数给客户端。而第二种方法则是客户端求出梯度之后直接对自己的模型参数进行更新（可以更新多个批次），最后各个客户端将得到的模型参数汇总给中心服务器（聚合），中心服务器对模型参数求加权平均，将更新好的模型参数返回给客户端。

补充知识二

补充知识：区分几个概念batch & iteration & epoch & round

  1. Batch(批次)
    每次迭代时使用的一批样本就叫做一个Batch，样本的数量称为Batch Size。Batch大小是一个超参数，用于定义在更新内部模型参数之前要处理的样本数。深度学习每一次参数的更新的Loss Function并不是由一个样本得到的，而是由一个Batch的数据加权得到。
  2. Iteration(迭代)
    使用Batch Size个样本训练一次的过程叫做一个Iteration。
  3. Epoch
    一个epoch就是使用训练集中的全部样本训练一次。通俗的讲，epoch的值就是整个训练数据集被反复使用几次。
    Epoch数是一个超参数，它定义了学习算法在整个训练数据集中的工作次数。一个Epoch意味着训练数据集中的每个样本都有机会更新内部模型参数。Epoch由一个或多个Batch组成。
  4. Round
    一个round是一个轮次，一般在论文算法中被用到，例如本篇论文中指一个通信轮次或者一个联邦学习过程就是一个Round

举例：
我们有1000个样本，batch_size=100，
意思就是我们总共有10个batch，每次使用这100个样本数量训练一次的过程，就是一个Iteration。
然后我们把这1000个样本都训练完了，就叫做一个Epoch。

参考：https://blog.csdn.net/qq_28640763/article/details/109260902

补充知识三

补充知识：改变batchsize会不会影响神经网络输入节点的尺寸？即batch在神经网络训练中怎样体现？(Does the input size to CNN change depending on the batch size?)
通常，卷积神经网络(CNN)的输入由具有给定 \(width*height*channels\)的图像描述。对于不同的批次大小，输入节点的尺寸也会有所不同吗？意思是，输入节点的尺寸会变成 \(batch\_size*width*height*channels\)吗？

批处理大小定义了将通过网络传播的样本数量。批大小不会影响网络的体系结构，包括输入的尺寸。（即神经网络设计只需要考虑基本单元的尺寸即可，如在计算机视觉中常是一个图片张量的尺寸）
假设你有1000张RGB图像，尺寸为32x32，并且将批处理大小设置为100。卷积网络的输入形状应为32x32x3。为了训练网络，训练算法从总数为1,000的图像中选择100个图像的样本，然后在该子集中的每个图像上训练网络，这个子集就是你的"批次"。神经网络体系结构并不关心您的子集(批次)具有100、200或1,000个图像，它只关心单个图像的形状。当对网络进行所有100张图像的训练后，便完成了一个批次，并且更新了网络参数。因此批次是进行参数更新的单位，即每经过一个批次更新一次网络参数（即小批量梯度下降），而不是每张图片更新一次梯度。
训练算法将为每个时期选择不同批次的图像，但是以上情况始终成立：网络一次只能看到一个图像，因此图像形状必须与输入层形状匹配，而不必考虑有多少个图像在该特定批次中。
关于为什么要进行批处理而不是对整个集合进行批处理(即，将批处理大小设置为100％并针对一个时期进行训练)？ 理由是借助GPU，它可以使训练更快，并且还意味着在训练时更新参数的频率降低了，更平滑，更可靠的融合。

参考：https://www.codenong.com/50812816/

按照第二种参数更新方法，每个客户端可以独立地更新模型参数多次，然后再将更新好的参数发送给中心服务器进行加权平均：

\[w^k \leftarrow w^k-\eta \nabla F_k\left(w^k\right)
\]

作者称这种方法为联邦平均（FedAvg）。算法的计算量与三个参数有关：

  1. \(C\)：每轮训练选择客户端的比例；
  2. \(E\)：每个客户端更新参数的循环次数所设计的一个因子；
  3. \(B\)：客户端更新参数时，每次梯度下降所使用的数据量；

记\(B=\infty\)为将全部本地数据作为一个批次进行梯度下降，\(E=1\)算法就变成了联邦随机梯度下降。对于一个拥有\(n_k\)个数据样本的客户端，每轮本地参数更新的次数为\(u_{k}=E\times{\frac{n_{k}}{B}}\) (这里的次数指的是：更新一次梯度算一次，即本地客户端模型更新轮数\(E\times\)每轮中梯度下降的次数，其中每轮中梯度下降的次数\(=\)该客户端数据量\(n_k\)/批大小\(B\))。算法1给出了联邦平均算法的伪代码描述。

img

2.实验

略

3.未来展望

本文实验部分展示了联邦学习具有实用性，因为联邦平均可以使用相对少的通信次数就可以得到一个高质量模型，不同模型结构的实验结果均证明了这一结论，包括多层感知机，两个不同的卷积神经网络，一个两层的字符LSTM，和一个大规模词级别的LSTM。

虽然联邦学习有助于保护隐私，但可以基于差分隐私[14,13,1]、安全多方计算[18] ，或它们的组合可以具备更强的隐私保护，这是未来工作的研究方向。注意这类技术可以很自然的应用在同步算法上，如联邦平均7。

7: 在这项工作完成之后，Bonawitz等人[6]介绍了一种对于联邦学习而言有效的安全聚合协议，并且Konecny等人[23]提出了一种算法可以进一步降低通信开销。

Reference:
[14] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science. Now Publishers, 2014.
[13] John Duchi, Michael I. Jordan, and Martin J. Wainwright. Privacy aware learning. Journal of the Association for Computing Machinery, 2014.
[1] Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In 23rd ACM Conference on Computer and Communications Security (ACM CCS), 2016.
[18] Slawomir Goryczka, Li Xiong, and Vaidy Sunderam. Secure multiparty aggregation with differential privacy: A comparative study. In Proceedings of the Joint EDBT/ICDT 2013 Workshops, 2013.
[6] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for federated learning on user-held data. In NIPS Workshop on Private Multi-Party Machine Learning, 2016.
[23] Jakub Koneˇ cn ́ y, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop on Private Multi-Party Machine Learning, 2016.

参考：https://zhuanlan.zhihu.com/p/515756280