若DL没了独立同分布假设，样本不独立的机器学习方法综述

机器之心原创

作者：仵冀颖

编辑：H4O

现有的机器学习任务默认训练数据遵循独立同分布 (idependently and identically distributed, IID)，神经网络、深度学习等常见算法一般都将数据遵循 IID 的假设作为其推导的一部分。

然而，在真实世界中样本数据相关性（inter-dependent）几乎无处不在，非同源数据/标签的分布也可能具有不同的概率分布，这些数据都遵循非独立、同分布（Non-IID）。

在一些场景中，直接应用已有机器学习算法基于 Non-IID 数据完成模型训练，由于算法本身的先进性训练结果仍然较好。但对于某些应用场景，基于现有的机器学习算法和框架，使用 Non-IID 数据训练会出现意想不到的负面效果，比如模型准确度低、模型无法收敛等。

比较常见的需要处理 Non-IID 数据问题的应用场景包括：

异常检测（Outlier Detection）。训练样本数据中存在的异常值（例如人脸识别中的眼镜、头发遮挡等），会在估计过程中引入较大方差。传统机器学习算法一般通过扩大样本数据集来解决这一问题。但当异常值以及样本数据存在系统性相关性时，会在估计过程中引入系统性偏移。这种情况下即使增加样本数据，也无法解决该问题。

生物医学应用（Medical Data）。在医学图像处理中，一些病变结构（例如肺中的附壁结节）在图像中空间位置相近，因此候选迭代算法（Candidate generation, CG）的计算结果将这些病变结构都指向同一潜在生理区域（例如同一肺结节）。其他类型的病变结构（例如非附壁结节）由于 CG 算法存在估计偏差，可能由于具有相似的基础特征也被指向该区域。也就是说，如果我们简单地将所有数据视为来自 IID 数据源的数据，则疾病潜在结构原因的发生频率和其他统计特性将可能存在系统性地改变。因此，在利用医学图像辅助疾病诊断的机器学习算法中由于 Non-IID 数据存在系统性偏差，即使提供大量的训练数据，也无法解决偏差带来的问题。

联邦学习 (Federated Learning)。在联邦学习的应用场景中，各个设备上的数据是由设备/用户独立产生的，不同设备/用户的非同源数据具有不同的分布特征，而每一个设备在进行本地学习的时候，所学习的训练数据是 Non-IID 的。因此研究提升 Non-IID 数据的学习效率，对于联邦学习具有重要意义。联邦学习允许用户在不需要集中存储数据的情况下，从本地存储的数据中共同获得共享模型的好处。客户端的本地数据通常基于特定用户对移动设备的使用，因此任何特定用户的本地数据集都不能代表总体分布。

近年来，针对 Non-IID 数据的机器学习算法以及联邦学习、医学数据分析等的应用文章越来越多，本文选择其中有代表性的五篇进行方法和应用情况的分析。包括：

《Learning Classifiers When The Training Data Is Not IID》主要解决经典统计分析进行分类器预测过程中针对 Non-IID 数据的处理方法

《Communication-Efficient Learning of Deep Networks from Decentralized Data (http://arxiv.org/abs/1602.05629)》为解决联邦学习中 Non-IID 数据问题，提出一种基于迭代模型平均的深层网络联合学习方法（Federated Averaging，FedAvg）

《Federated Learning with Non-IID Data》是针对（2）的分析和改进，使用客户端数据分布和中央服务器数据总体分布之间的土方运距 (earth mover』s distance, EMD) 计算权重散度，同时提出了一种数据共享（Data-Sharing）策略改进 FedAvg 的性能

《On the Convergence of FedAvg on Non-IID Data》重点讨论联邦学习问题中 FedAvg 在处理 Non-IID 数据时的收敛性问题，从理论角度证明了 FedAvg 的有效性

《LoAdaBoost:Loss-Based AdaBoost Federated Machine Learning on medical data》基于 FedAvg 和数据共享策略提出了一种针对医学数据的提高联邦学习效率的自适应增强方法

1. Learning Classifiers When The Training Data Is Not IID

原文地址：http://people.ee.duke.edu/~lcarin/IJCAI07-121.pdf

现有的分类器设计主要是基于独立同分布（IID）未知数据中生成得到的训练样本数据实现的。本文重点解决现实中非独立同分布（Non-IID）样本数据的分类器学习问题，即一批或一小组样本数据或数据标签之间具有高度的互相关性，在这种情况下如何改进分类器的学习效果。

算法分析

图 1. 显示随机和固定效应的混合效应模型

图 1 中给出一个典型的医疗领域 Non-IID 数据混合效应示例，与病人相关的数据保存在不同医院中，每个病人针对不同的病情有具体的病历记录数据，这些数据遵循非独立同分布（Non-IID）。使用 x 表示数据特征，y 表示数据分类标签，针对分类问题计算 y 的经典后验概率模型为广义线性模型（Generalized Linear Models，GLM）：

其中 i 为样本数据计数，j 为病人计数，k 为医院计数。GLM 主要描述样本之间的条件独立性，忽略了来自同一患者或来自同一医院的样本数据之间的相关性。为解决这一问题，提出了广义线性混合效应模型（Generalized Linear Mixed Effects Model，GLMM），GLMM 的核心是引入一对随机变量来解释患者特异性效应和医院特异性效应。GLMM 的预测函数为：

根据贝叶斯理论，用训练过的 GLM 对一个新的测试样本 x 进行分类时，需要对分类器固定效果参数进行边缘化处理：

同理，对于 GLMM 的边缘化处理扩展如下：

[Image: image.png] 使用 GLMM 进行模型训练，针对同一患者或同一医院的样本数据分类预测不是独立完成的。在测试阶段，给定新病人或新医院的样本数据进行分类（不存在随机效应），此时可直接应用 GLM，但需依赖于 GLMM 学习得到的边缘后验分布概率：

由于不能用解析形式确定精确的后验概率值，利用上式计算每一个测试样本分类时的积分运算计算复杂度非常高。为解决这一问题，本文提出使用点分类器代替贝叶斯积分的 GLMM 分类计算。对于任一样本数据，将其与随机效应变量组合后形成新的增强向量：

当只考虑硬分类问题时（如 SVM），引入符号函数 sign（•），基于点分类器的分类函数为：

通过使用点分类器，避免了计算线性超平面分类器的贝叶斯积分。然而这种处理仅适用于解决硬分类问题，如果我们使用其他的链接函数来计算软分类，点分类器不再适用。此外，上式主要适用于对称后验分布的计算（例如高斯近似分布），如需计算拉普拉斯近似分布的后验概率可以计算其近似平均值，即在最大后验概率（MAP）估计过程中最大化其后验概率。

针对本文提出的 Non-IID 问题，首先，对于所有的训练样本，构建包含附加特征的增强特征向量。以样本 x 的原始特征向量为基础，在除患者 ID 位置外的所有位置附加一个由零组成的向量，以及与医院 ID 位置相对应的另一个向量，形成包含附加特征的增强特征向量如下：

接下来，使用这个增强的特征向量来训练分类器，这一阶段任何标准的训练算法都适用，如 Fisher 判别法或 SVM 等。基于增强特征训练得到的分类器不仅基于原始特征预测分类结果，还同时指定了一个特定于患者和医院的「随机效应」解释来消除样本数据相关性，从而有效解决 Non-IID 数据带来的非独立性问题。

测试阶段，本文使用基于增强向量的 Fisher 判别法（Fisher』s Discriminant with Augmented Feature Vectors, FD-AFV）如下：

实验结果

本文使用的对比算法包括：Fisher 判别法（Fisher』s Discriminant, FD），FD-AFV 以及 GLMM。本文将 FD-AFV 和 GLMM 与 FD 进行比较，目的是验证算法能否显著提高分类器的准确度。此外还研究了在分类器灵敏度方面，计算成本较低的 FD-AFV 是否与计算成本较高的 GLMM 相当。

（1）结肠癌（Colon Cancer）

数据库：高质量的 CT 图片（来源于 NYU 医学中心），将 275 例患者数据随机分为训练集（152 例，15596 例患者中 126 例息肉）和测试集（123 例，12984 例患者中 104 例息肉）。为每个候选对象提取了总共 48 个特征。

图 2. 结肠癌图像实验结果

统计分析表明，FD-AFV 准确度高于 FD(p 值为 0.01)，GLMM 准确度高于 FD（p 值为 0.07），而 FD-AFV 准确度高于 GLMM（p 值为 0.18）。不同算法的计算时间见表 1。

表 1:FD、FD-AFV 和 GLMM 的肺栓塞 (PE) 和结肠癌 (Colon) 图像数据的训练时间（秒）比较

（2）肺栓塞（Pulmonary Embolism）

数据库：作者在两个不同的机构收集了 68 例病症的肺栓塞图片，这些图片由专业胸部放射科医生进行标记（共计 208 个血块）。随机分为两组：训练集（45 例 142 个血块，共 3017 名候选人）和测试集（23 例 66 个血块，共 1391 名候选人）。为每个候选对象提取了总共 115 个特征。

图 3. 肺栓塞图像实验结果

统计分析表明，FD-AFV 比 FD 更加敏感（p 值为 0.08），GLMM 比 FD 更加敏感（p 值为 0.25），FD-AFV 比 GLMM 更加敏感（p 值为 0.38）。不同算法的计算时间见表 1。

总结与分析

针对 Non-IID 数据，本文提出一种利用样本的随机效应辅助样本数据特征向量的分类器训练方法。与传统忽略样本间相关性的方法相比，该方法提高了 Non-IID 数据集的分类准确度。此外，通过引入点分类器，大大提升了算法的计算效率。本文是为了解决医学图像中 Non-IID 问题所提出的，但该算法是通用的，能够有效处理各类训练样本数据间的层次关联结构。

2、Communication-Efficient Learning of Deep Networks from Decentralized Data

原文地址：https://arxiv.org/abs/1602.05629

本文重点解决联邦学习中 Non-IID 数据的学习问题。在联邦学习的应用场景中，各个设备上的数据是由设备/用户独立产生的，因此任何特定设备/用户的本地数据集都不能代表总体分布，联邦学习的样本数据属于 non-IID 数据。

联邦学习任务通过由中央服务器协调的客户端的松散联合来解决，这种方法的一个主要优点是将模型训练与直接访问原始训练数据的需求分离开来，这在对数据隐私有严格要求或数据集中共享难度较大的领域中有着重要的现实意义。本文提出了一种基于迭代模型平均的深层网络联合学习方法（Federated Averaging，FedAvg）解决 Non-IID 数据学习问题，并对五种不同的模型结构和四种数据集进行了广泛的实证评价。

算法分析

联邦学习的流程是：初始化模型及各个参数，中央服务器将初始化的模型参数等全局状态发送至全部客户端。随机选择比例为 C 的客户端（0

本地优化完毕后，客户端向中央服务器发送更新的模型参数，中央服务器基于客户端更新的模型参数更新全局状态。重复上述过程直至全局模型收敛。

在实际应用场景中，客户端本地数据可能在优化过程中发生变化，例如生成数据、删除数据等，一些客户端可能会处于关闭等无法连接状态。本文主要关注客户端存储的 Non-IID 数据对联邦学习效果的影响，因此假设实验环境为理想状态，即全部客户端都处于随时可连接的状态、客户端的本地数据不变。

假设 K 表示全部客户端数量，P_k 表示客户端 k 上数据的索引集，n_k = |P_k|。非凸神经网络目标函数为：

当 P_k 是通过将训练样本数据均匀随机分配到客户端而形成的，即客户端中的本地数据遵循 IID，此时有 E_Pk[F_k(w)]=f(w)。当客户端数据遵循 Non-IID，此时 F_k 可能为 f 的任意错误近似。SGD 为近年来广泛应用的深度学习模型，通过改进模型、优化参数等处理在不同的机器学习任务中都获得了较好的效果。

在联邦学习中，引入客户端所需的时间成本很低，因此本文使用大批量客户端同步 SGD（Large-batch synchronous SGD）作为基线方法，称为 FederatedSGD（FedSGD）。

随机选择比例为 C 的客户端，计算这些客户端本地数据的损失梯度：g_k=Nabla(F_k(w_t))，当前模型下本地数据的平均梯度为 w_t。中央服务器聚合这些梯度值并更新：

每个客户端使用其本地数据对当前模型进行梯度下降优化，然后中央服务器对生成的模型进行加权平均。基于 FedSGD 算法框架，本文提出在中央服务器进行加权平均步骤之前多次执行本地更新迭代，从而向每个客户端添加更多的计算过程如下：

该方法称为 FederatedAveraging（FedAvg）。FedAvg 的计算量由三个关键参数控制：C，在每轮执行计算的客户端的分数比例；E，每个客户端每轮对其本地数据集进行训练的次数；B，用于客户端更新的本地小批量大小。FedAvg 的完整算法如下：

对于非凸的目标函数来说，在中央服务器端直接对各个客户端训练得到的模型参数进行平均化处理，会导致训练结果生成「坏」模型，即影响中央服务器端得到的全局模型效果。当我们对两个从不同初始条件训练得到的 MNIST 数字识别模型结果进行平均化处理时，可以看到这种较差的效果（见图 1 左侧）。

图 1 中父模型 w 和 w『分别基于 MNIST 库中 600 个不重叠的 IID 样本训练得到，这说明对于本地数据库来说模型的训练出现了过拟合现象。

最近的研究表明，充分过参数化神经网络的损失函数能够有效提升性能，特别是能够保证优化过程不容易陷入局部极小值。实际上，当从相同的随机初始化中启动两个模型，然后在不同的数据子集上对每个模型进行独立的训练时，我们发现简单的参数平均法非常有效，即 1/2 w+ 1/2w』，其中 w』为损失函数的更新值。

由图 1 右侧实验结果图可以看到，在整个 MNIST 训练集上实现的损失显著低于在任何一个小数据集上独立训练所获得的最佳模型。

图 1：通过平均两个模型的参数生成模型的完整 MNIST 训练集的损失值

实验分析

本文针对图像分类和语言建模两个任务构建五个模型进行实验评价。

a. 图像分类

数据库：MNIST 字符识别

模型：1）一个简单的多层感知器，具有两个隐藏层，每个层有 200 个单元，使用 ReLu 激活（总参数 199210），我们称之为 MNIST 2NN。2）一个具有两个 5x5 卷积层的 CNN（第一个有 32 个通道，第二个有 64 个通道，每个通道都跟着一个 2x2 的池化操作），一个有 512 个单元的全连接层和 ReLu 激活，以及一个最终的 Softmax 输出层（总参数 1663370）。

我们研究了两种在客户端划分 MNIST 数据的方法，1）IID，数据清洗后分为 100 个客户端，每个客户端有 600 个样本。2）Non-IID，首先按数字标签对数据进行排序，将其划分为 200 个大小为 300 的碎片，然后将每个客户端分配 2 个碎片（共 100 个客户端）。

b. 语言建模

数据库：The Complete Works of William Shakespeare。客户端数据集中针对每场戏剧中的每个口语角色给定至少两行语言，共 1146 个客户端。对于每个客户端，将数据分成一组训练行（角色的前 80% 行）和测试行（最后 20%，四舍五入到至少一行）。最终生成的数据集训练集有 3564579 个字符，测试集中有 870014 个字符。

模型：字符级别 LSTM 语言模型。模型以一系列字符作为输入，并将每个字符嵌入到一个已知的 8 维空间中。然后通过两个 LSTM 层处理嵌入的字符，每个层有 256 个节点。最后，将第二个 LSTM 层的输出发送到 SoftMax 输出层，每个字符一个节点。整个模型有 866578 个参数，我们使用 80 个字符的展开长度进行训练。

图 2. MNIST CNN、 Shakespeare LSTM 的测试集准确度与通信轮次

图 2 给出图像分类和语言建模的实验结果。针对不同的模型、不同的数据库 FedAvg 都能获得较好的效果。此外图 2 表明，每轮增加更多的本地 SGD 更新可以显著降低通信成本，具体通信速度提升的情况见表 1。

表 1. 达到 FedAvg 目标准确度的通信轮数

c. 图像分类

数据库：CIFAR-10。将 50000 个训练样本和 10000 个测试样本分成 100 个客户端，每个客户端包含 500 个训练样本和 100 个测试样本；由于此数据没有自然的用户分区，因此实验只考虑 IID 设置。

模型：TensorFlow。由两个卷积层、两个全连接层和一个线性变换层组成。

图 3. CIFAR-10 LSTM 的测试集精度与通信轮次

图 3 给出 CIFAR-10 数据库中图像分类的实验结果，使用 FedSGD 在全训练集中的实验（没有用户划分）作为对比基线。其中 FedSGD 消退概率约为每轮 0.9934，FedAvg（B=50，E=5）的消退概率约为 0.99。FedSGD 经过 197500 次更新后达到 86% 的准确度，而 FedAvg 约需 2000 次更新能够达到 85% 的准确度。

d. 语言建模

数据库：大尺度语言预测，训练数据集包括来自大型社交网络的 1000 万个公开发帖。我们按作者对这些帖子进行分组，总共形成 50 多万个客户端。该数据集能够模拟真实场景下用户移动设备上存在的文本输入数据情况。

模型：256 节点 LSTM，词汇表 10000 字。每个字的输入和输出嵌入特征尺寸为 192，并与模型共同训练，共有 4950544 个参数。具体实验结果见图 4。

图 4. 大型语言模型单词 LSTM 的单调学习曲线。

分析与总结

本文针对 Non-IID 的联邦学习提出了一种能够应用于实际场景的 FedAvg 算法，FedAvg 基于迭代模型平均的深层网络联合学习。理论分析和实验结果表明，FedAvg 对不平衡和 Non-IID 数据具有鲁棒性，此外，FedAvg 的通讯消耗很低。与基线算法 FedSGD 相比，FedAvg 具有更好的实用性，从模型效果和通信效率两个角度都能够有效解决实际应用场景中的问题。

3、Federated Learning with Non-IID Data

原文地址：https://arxiv.org/abs/1806.00582

本文是基于《Communication-Efficient Learning of Deep Networks from Decentralized Data (http://arxiv.org/abs/1602.05629)》中所提出的经典 FedAvg 进行的算法和策略改进。当联邦学习场景中 Non-IID 数据高度倾斜时，客户端的学习仅基于某一类数据完成，此时会造成 FedAvg 的准确度大幅下降。

本文首先给出了在不同实验条件下 FedAvg 的准确度结果，实验表明准确度下降的趋势可由权重散度指标表征。第二，本文提出使用土方运距 (earth mover』s distance, EMD) 计算权重散度，能够提升联邦学习在 Non-IID 数据中的准确度。第三，本文提出了一种数据共享（Data-Sharing）的联邦学习策略，通过在中央服务器创建所有客户端设备之间全局共享的一小部分数据来改进对 Non-IID 数据的训练效果。本文具体内容是按照上述三个突破点的实验或理论分析、实验验证的结构组织完成的。

FedAvg 准确度实验分析

数据库：MNIST，CIFAR-10, Speech commands datasets（语音命令数据集由 35 个词组成，每个词的持续时间为 1 秒。为了使其一致，本文使用数据的一个子集和 10 个关键字作为关键字定位（KWS）数据集，对于每一个音频片段，我们提取 10 个 MFCC 特性，每帧 30 毫秒，步幅 20 毫秒，生成 50x10 特性，用于神经网络训练）。

模型：CNN。

数据情况：训练集平均划分为 10 个客户端。对于 IID 设置，每个客户端随机分配一个超过 10 个类的统一分布。对于 Non-IID 设置，数据按类排序并划分为两种极端情况：

（a）1 类 Non-IID，其中每个客户端仅保存单个种类的数据；

（b）2 类 Non-IID，将数据排序后划分为 20 个分区，每个客户端随机分配两类中 2 个分区的数据。

FedAvg 参数：E，每个客户端每轮对其本地数据集进行训练的次数；B，用于客户端更新的本地小批量大小。

图 1. FedAvg 实验结果

表 1. Non-IID 情况下 FedAvg 准确度下降情况

由图 1，在 IID 情况下，FedAvg 的收敛曲线与所有三个数据集的 SGD(Bx10) 的收敛曲线基本重合。对于 CIFAR-10，只有一个很小的差异，即 B=10 的 FedAvg 收敛到 82.62%，B=100 的 SGD 收敛到 82.62%。

然而，在 Non-IID 情况下，同等大小 B 取值情况下，FedAvg 的效果明显比 SGD 差。Non-IID 情况下的准确度下降详细数据见表 1，其中 1 类 Non-IID 的下降最严重。全部实验的准确度详见表 2。

表 2. 用 IID 和 Non-IID 数据测试 SGD 和 FedAvg 的准确度

计算权重散度 EMD

图 2. IID、2 类 Non-IID 和 1 类 Non-IID 情况下 CNN 层权重散度结果

由图 2 所示，在 Non-IID 情况下 2 类 Non-IID 的实验效果要优于 1 类 Non-IID，这就说明，FedAvg 的效果受到客户端数据分布情况的影响，即数据倾斜程度。由于测试结果准确度是由训练的权重决定的，另一种比较 FedAvg 和 SGD 的方法是在相同的初始化权重下，观察权重相对于 SGD 的影响，本文定义该指标为权重散度（weight divergence），它量化了两个不同训练过程在相同权重初始化下的权重差异：

下面给出权重散度的数学分析。给定紧致空间 X，对应包含 C 类的类别空间 Y，Y=[C]，[C]=。点对 的分布为 p。f 为 x 到对应概率单纯型 S 的映射，其中 f_i 表示第 i 类的概率。f 在假设类别 w 上参数化处理，例如神经网络的权重。基于广泛应用的交叉熵损失损失函数 l(w) 为：

忽略泛化误差，直接优化种群损失，则学习问题变为：

使用 SGD 循环优化计算 w 值。中央化的 SGD 执行以下更新：

在联邦学习问题中，假设有 K 个客户端，在每个客户端本地执行单独的 SGD 优化。k 客户端中第 i 轮优化为：

每执行 T 轮优化后在中央服务器端进行一次同步处理：

本地散度权重 w_mT^(f) 与中央服务器平均散度权重 w_mT^(c) 之间的偏差规律如图 1 所示。在 IID 情况下，对于任意一个客户端来说，本地的散度权重与中央服务器的平均散度权重相差很小。然而，在 Non-IID 情况下，由于数据分布问题，客户端本地散度权重和中央服务器的平均散度差距随着迭代次数的增加会加大。

图 3. IID 和 Non-IID 情况下数据联合学习的权重散度图解

对于 K 个客户端，每个客户都有 n（k）个 IID 样本，对于第 k 个客户端其分布为 p（k)。如果有

对于每一类 i 都为 lambda-Lipschitz 的，且每隔 T 步骤进行一次同步处理，则 m 次同步后的权重散度有如下不等式：

m 次同步后的权重散度主要来自于两部分：一是 (m-1) 次同步后的权重散度，另一部分是客户端 k 上数据分布的概率距离相对于实际整体分布的权重散度。(m-1) 次同步后的权重散度以下式的强度增强：

且有

因此，如果联邦学习中不同的客户端从不同的初始 w 开始，那么即使数据遵循 IID 仍然会遇到较大的权重差异，从而导致精度下降。当所有客户端从相同的初始化和中心设置开始，则权重散度为：

该值为客户端 k 上的数据分布和中央服务器端总体分布之间的土方运距 (earth mover』s distance, EMD)。EMD 受学习速率、同步前步数 T 和梯度的影响。图 4 给出不同 CNN 层的散度差异与 EMD 的对比。对每个 EMD 的 5 个分布计算权重散度的平均值和标准偏差，对于三个实验数据集，每层的权重散度随着 EMD 的增加而增大。由上述分析，客户端中数据分布和总体分布之间的 EMD 为合适的权重散度量化指标。

图 4. 不同 CNN 层的散度差异与 EMD 对比

在每个 EMD 的 5 个相同分布上计算测试准确度的平均值和标准偏差，结果见图 5。对于三个实验数据集，测试准确度随 EMD 增加而降低。同时，随着数据 Non-IID 程度加强，下降速度也越来越快。由图 4 和图 5 分析可知，在平衡 Non-IID 数据与提高 FedAvg 的准确性之间需要权衡协调。

图 5.（a）FedAvg 的测试准确度与 EMD；（b）散度发散的箱线图

数据共享策略

本文提出了一种数据共享策略（Data-Sharing），通过构建在所有客户端设备之间全局共享的一小部分数据来改进 Non-IID 数据的 FedAvg。由图 5 中的实验结果可知，对于高度倾斜的 Non-IID 数据，可以通过减小本地分布和全局分布之间 EMD 的方式提升测试准确度。

在联邦学习场景中，我们无法控制客户端的数据，因此可以在初始化阶段将具有统一分布的全局数据中的一部分数据子集部署到客户端中。基于中央服务器中的共享数据训练初始化模型，各个客户端的权重并不是随机分配的，而是根据初始化模型确定的。全局共享数据的应用可以减小 EMD，从而提升整体测试准确度。数据共享策略详见图 6。

图 6. 数据共享策略

部署在中央服务器中的全局共享数据子集 G 具有各类数据的统一分布。基于 G 初始化训练全局模型，G 的大小比例为 alpha 的随机子集分配部署到各个客户端中，之后各个客户端基于本地数据库和分配的 G 子集的总和训练本地模型。然后，中央服务器从客户端聚合本地模型，用 FedAvg 训练全局模型。G 的大小影响数据共享策略的效果：

其中 D 表示客户端的数据量。

本实验中将 CIFAR-10 训练集分为两部分，其中客户端 D 包含 40000 个样本数据，剩余部分 H 包含 10000 个样本。D 划分为 10 个 1 类 Non-IID 数据分区，H 生成 10 个随机的（belta=2.5% 至 25%）G』s 子集。实验结果见图 7。

图 7. 数据共享策略实验结果

由图 7 的实验结果可知，随着 belta 值的增大，测试准确度不断提升，最高达到 78.72%。即使 belta 取值较小（belta=10%），对于 1 类 Non-IID 数据的准确度也能达到 74.12%，而在没有使用数据共享策略的情况下，准确度仅为 44%。此外，图 7（b）的实验表明，在进行数据分发时并不需要将 G 整体分发到客户端，相反，只需要将 G 的一个随机部分分发给每个客户端就可以获得很好的效果。

总之，数据共享策略为使用 Non-IID 数据的联邦学习提供了一个有效解决方案。全局共享数据集的大小和随机分配至客户端的子集大小可以根据具体问题和应用进行调整。由于该策略仅需在初始化阶段执行一次，因此并不会对联邦学习的整体通信效率产生影响。此外，全局共享数据与客户端本地数据是不同的数据集，因此该策略不存在隐私敏感性问题。

总结与讨论

本文重点解决的是联邦学习场景中存在数据严重倾斜的情况下，FedAvg 的性能影响及解决方案。本文提出使用客户端中数据分布和总体分布之间的 EMD 定义权重散度，同时还提出了一种数据共享策略，通过创建在所有客户端之间全局共享的一小部分数据来改进对 Non-IID 数据的训练效果。

本文中对于 Google 论文 Communication-Efficient Learning of Deep Networks from Decentralized Data 重点实验有严格的重现，但是在图 1 呈现 FedAvg 实验结果时，作者只给出了 500 轮通信内达到的精度，然后有可能最终通过更多轮通信（Google 论文中给出了 4000 轮），non-IID 也达到了预定精度，只是需要更多轮通信。而本文的论点是 non-IID 数据影响模型质量，无法达到预定精度。在和论文作者沟通后，论文作者表示观察到 1000 轮之后 non-IID 仍然达不到预定精度，而且精度增长趋势进入平台期，涨幅非常小。

4、On the Convergence of FedAvg on Non-IID Data

原文地址：https://arxiv.org/abs/1907.02189

本文重点讨论联邦学习问题中 Federated Averaging（FedAvg）算法在处理 Non-IID 数据时的收敛性问题。FedAvg 在客户端并行运行 SGD，并对各个客户端的结果进行周期性的平均化处理。FedAvg 适用于 Non-IID 数据，各个客户端中的数据不需要遵循统一的分布规律。本文重点研究 FedAvg 凸优化问题的理论依据，针对强凸和光滑问题的 FedAvg 进行理论分析，此外本文是首次在不设假设约束前提下（不要求遵循 IID 分布和所有客户端为活动状态）论证 FedAvg 的收敛速度。

理论证明

在标准 FedAvg 中，中央服务器将当前状态下最新的模型 W_t 广播至各个客户端，各个客户端执行本地优化如下：

中央服务器汇聚客户端模型后进行平均化处理，生成新的全局模型 W。

在之前的 FedAvg 分析中，一般会做两个假设：一是各个客户端中的数据为 IID 分布的，二是各个客户端都处于活跃状态中（非关闭）。这样，中央服务的平均化处理满足下式：

然而在实际应用中，这两种假设都很难满足。不同客户端中存储的本地数据无法满足遵循统一分布的要求，而一些客户端设备也可能处于关闭状态。本文改变中央服务器的平均化处理策略，每次只选择前 K 个客户端处理，S_t 为客户端标签集合（|S_t|=K）:

为了分析 FedAvg 在 non-IID 条件下的收敛性质，本文做了以下四个假设：

假设 1：F1,...Fn 为 L-平滑的，对于任意 v 和 w：

假设 2：F1,...Fn 为 miu-凸的，对于任意 v 和 w：

假设 3：客户端中的随机梯度方差满足：

假设 4：随机梯度的期望平方范数是一致有界的：

令 F*和 F*_k 分别表示 F 和 F_k 的最小值，数据的 Non-IID 分布可由下式量化表示：

如果数据遵循 IID，则上式随着样本数量的增加值趋于零。如果数据为 Non-IID，则上式值非零，且值的大小反映了数据分布的异质性程度。

当全部客户端参与平均化处理时，FedAvg 最终结果 w_T 满足：

部分客户端参与的情况下，中央服务器可以有两种平均化处理策略。

策略 1（Scheme I）：假设 S_t 包含的 K 个子集是随机抽取的，采样概率为 p_1,...,p_N。则 FedAvg 执行的中央服务器平均化处理策略为：

策略 2（Scheme II）：假设 S_t 包含从|N|中均匀无替换抽样得到的子集。数据进行平衡化处理 p_1=...=p_N=1/N。则 FedAvg 执行的中央服务器平均化处理策略为：

当部分客户端参与时（|S_t|=K），FedAvg 最终结果 w_T 满足：

因此，在不同客户端活跃状态下，FedAvg 都具备收敛性。详细及完整的数学证明过程可见论文原文。

本文论证了不同参数对于 FedAvg 收敛性能的影响。其中，E 表示每个客户端每轮对其本地数据集进行训练的次数，K 表示处于活跃状态的客户端数量，最后是中央服务器的平均化处理策略。

a. 参数 E 的选择

T_epsilon 表示 FedAvg 达到「epsilon」准确度时所需要的迭代次数，由上式可知，中央服务器与客户端之间所需的通信轮数大致为：

T_epsilon 是 E 的一个先减小后增大的函数，这就意味着 E 过小或过大会导致较高的通信成本，并且存在最优 E。如果 E 设置较大，那么 w_t 能够收敛到 F_k 的极小值，则 FedAvg 成为局部解的一次平均值。如果数据为 Non-IID，F_1,...,F_N 的最小加权平均值不等于 F 的最小值，则一次平均值不再适用。因此 Non-IID 情况下 E 的最大值为 Omega(sqrt(T))。

b. 参数 K 的影响

对于 IID 数据，FedAvg 的收敛速度随着 K 的增加而显著提高。然而，在 Non-IID 情况下，收敛速度对 K 的依赖性较弱。在实际应用中，可以将参与比 K/N 设置得很小，从而在保证整体收敛速度的情况下减小落后者带来的影响。

c. 平均化处理策略

本文提出了两种平均化处理策略 Scheme I 和 Scheme II。Scheme I 根据概率 p_1,...,p_N 选择 K 个设备进行替换。从各个客户端中非均匀采样的收敛速度比均匀采样快，尤其是当 p_1,...,p_N 高度不均匀时。如果系统可以选择在任何时候激活 N 个设备中的任何一个，那么应该使用 Scheme I。

但是，通常联邦学习的系统对于客户端的采样规则并没有控制权，一般都是对前 K 个反馈的结果进行更新。在这种情况下，我们可以假设 K 个客户端是从所有 N 个客户端中均匀采样的，当 p_1,...,p_N 高度不均匀，则 FedAvg 收敛速度较慢。

实验分析

数据库：

a. MNIST。将 MNIST 数据库中的数据分布到 N=100 个客户端中，每个客户端包含两位数的样本。生成两个数据库：平衡的 MNIST 库（balanced data，将各个客户端的样本数量设定为相同）和非平衡的 MNIST 库（unbalanced data，根据功率定律不同客户端的样本数量不同）。

b. 人工生成数据（X_k,Y_k）。数据生成模型为：

[Image: image.png] 数据库详细配置见表 1。

表 1. 联邦学习实验数据库

实验结果见图 1。图 1（a）给出在给定准确度的条件下，E 的改变对于达到收敛状态所需要的迭代次数的影响。对于四种实验数据来说，所需的迭代次数首先减少，之后随着 E 增大而逐渐增多。图 1（b）表示在人工生成的样本数据库 Synthetic(0,0) 中，处于活跃状态的客户端数量 K 对收敛情况的影响不大。

图 1（c）表示，在 MNIST balanced 数据库中，在中央服务器中使用 Scheme I 的效果优于 Scheme II，而 Scheme I 和 II 的效果都优于原始 FedAvg。图 1（d）表示，在 MNIST unbalanced 数据库中，Scheme I 效果优于 Scheme II 和 FedAvg。在该实验条件下，Scheme II 受到 unbalanced 数据不稳定的因素影响，收敛速度较慢。

图 1. 不同条件和参数下实验效果

总结与分析

本文研究了经典启发式算法 FedAvg 的收敛性，针对客户端样本数据生成方式和中央服务器的平均化处理策略进行了分析和论证。提出了两种平均化处理策略，并从理论分析和实验结果两方面进行了验证。本文主要是对 FedAvg 的理论分析和证明，同时也讨论了实际应用中的算法设计。本文的论证主要针对凸优化问题，对于其他类型问题的分析将是今后研究的主要方向。

5、LoAdaBoost : Loss-Based AdaBoost Federated Machine Learning on medical data

原文地址：http://arxiv.org/abs/1811.12629v2

医疗数据分析是联邦学习的一个重要应用场景。医疗从业者可以使用健康数据提供医疗保健，研究人员可以使用健康数据构建机器学习模型，以改进临床服务并做出健康预测。但由于数据量大、保密性要求高，这些数据大多分散存储在移动设备或不同医院，这意味着传统的基于集中数据的机器学习方法不再可行。因此，避免数据收集和中央存储的联邦学习变得非常必要，到目前为止已经取得了重大进展。

然而，由于不同医院、不同病症、不同采集渠道获取的医疗数据不具备独立同分布的特点，不同来源的 Non-IID 数据异质性是应用联邦学习的主要挑战。本文基于 Federated Averaging（FedAvg）算法和数据共享（Data-Sharing）策略提出了一种提高联邦学习效率的自适应增强方法。

本文同时考虑解决联邦学习中的三个问题，即本地客户端计算复杂度、通信成本和测试准确度。本文以 FedAvg 为基础提出一种基于损失的自适应增强联合平均（LoAdaBoost FedAvg）算法，该算法在中央服务器上进行模型平均化处理之前，对具有高交叉熵损失的局部模型进行了进一步优化。

算法分析

由我们上面介绍的文章《Federated Learning with Non-IID Data》可知，在客户端数据 Non-IID 的条件下，FedAvg 的随机梯度不再是中央服务器全局梯度的无偏估计，因此其处理准确度会大幅下降。本文设计了一种 LoAdaBoost FedAvg 方法，利用中值交叉熵损失函数自适应地提高学习能力较差的客户端的训练过程。

使用中值损失函数而不是平均损失函数的原因在于，后者对显著不足或过度拟合的客户端模型异常值的鲁棒性较差。在本文方法中，客户端和中央服务器之间不仅传递模型权重，还需要传递交叉熵损失。LoAdaBoost FedAvg 的工作流程见图 1。

图 1. 客户端和中央服务器之间的通信过程

LoAdaBoost FedAvg 需要对客户端的模型进行再训练，整个流程如下：对于客户端 k，初始化模型 w_average 后基于本地数据划分为 B 个小组。E 表示每个客户端每轮对其本地数据集进行训练的次数。与 FedAvg 不同的是，LoAdaBoost FedAvg 仅对其中 E/2 进行训练优化。交叉熵损失函数表示为 L_k，模型为 w_k。当满足下述条件时客户端 k 的计算过程停止：

若上式条件不满足，则执行另外 E/2 的训练。该过程循环 E/2-r+1 次，r 为次数，首次时 r=0，当总次数达到 3E/2 时或满足下式时循环停止，将最终的 L_k 和 w_k 上传至中央服务器。

LoAdaBoost 是自适应的，是因为其在第一个 E/2 阶段之后性能较差的客户模型能够通过连续再训练来提高其性能。训练质量是通过比较模型的损失和中值损失来确定的。这样，该方法能够确保大多数客户端模型的损失低于之前迭代时的中值损失，从而使学习过程更加有效。

此外，由于在一次迭代中，预计只有极少的客户端模型需要进行完整的 3E/2 个周期的训练，因此每个客户端运行的周期平均数将小于 E，这意味着使用 LoAdaBoost 本地计算负载比 FedAvg 小。最后，由于损失函数和模型参数是同时传输的，LoAdaBoost 并不会引入额外的通信负载损耗。

与其他基于随机优化的机器学习方法类似，上述方法的一个重要假设前提是，客户端本地数据的随机梯度是对中央服务器中总体数据完全梯度的无偏估计。实际上，在 Non-IID 情况下这个假设是不成立的。Non-IID 情况下一个客户端中低损失的优化模型并不能推广到中央服务器中，即使增加客户端的训练机会来减少损失，也不能有效提升中央服务器中全局模型的效果。因此，本文提出引入数据共享策略（Data-Sharing），当本地数据与一小部分 IID 数据集成时，Non-IID 数据会变少，从而缓解该问题带来的影响。

实验分析

对比算法：FedAvg、FedAvg+datasharing、LoAdaBoost FedAvg、LoAdaBoost FedAvg+datasharing。

模型：在每个客户端上训练的神经网络由三个隐藏层组成，分别有 20、10 和 5 个单元，使用 ReLu 激活函数，共有 56571 个参数。使用自适应矩估计（Adam）作为随机优化算子，根据经验结果，该算法所需内存较少，计算效率较高。

评估参数：（1）使用 ROC 曲线下面积（AUC）评估预测性能；（2）通过迭代次数或等效的通信轮数来衡量通信成本；（3）使用客户端每轮通信的平均时间（表示为 E_average）来测量本地计算量。

数据库：MIMIC-III，数据库的具体组成见表 1。其中训练库包含 20000 个样本，测试库包含 8000 个样本，保留 2000 个样本作为数据共享策略中使用的共享数据库。采用两种方式组织训练库：（1）IID：随机划分数据至 100 个客户端，每个客户端包含 200 个样本；（2）Non-IID：首先根据年龄（AGE_GROUP）和性别（GENDER）对数据进行分类，然后将数据划分至 100 个大小相等的客户端。

表 1. 数据库摘要

（1）预测性能

图 1 给出 FedAvg 在 IID 和 Non-IID 数据中应用的效果。C 表示在每轮执行计算的客户端的分数比例；E 表示每个客户端每轮对其本地数据集进行训练的次数。本实验中，E=5。图中曲线通过采用在所有之前的通信回合中获得的最高测试集 AUC 来保证数据单调增加。显然，在 C 不同取值的条件下，基于 IID 数据训练的全局模型优于 Non-IID 数据拟合的全局模型。在相同的本地数据分布条件下，在每一轮中选择一个较小的客户端部分进行计算往往会产生更好的性能。例如，针对 IID 数据，当 C=0.1 时在通信次数较少的情况下达到了略高于 C=0.2、0.5 和 0.9 的最大 AUC。

图 1. 针对 IID 和 Non-IID 数据的 FedAvg 的性能差异

（2）通信成本

作为基线方法，在实验设置 C=0.1 和 E=5、10 和 15 的情况下，将 FedAvg 与 LoAdaBoost FedAvg 进行比较。结果如图 2 所示，其中水平虚线代表目标测试集 AUC。除 E=15 的 FedAvg 曲线外，所有其他曲线都高于虚线目标线且呈上升状态，所采用的通信轮数与 E 成反比。给定相同的 E，可以注意到尽管在最初的几轮测试中稍微落后，但本文提出的方法通信轮数始终少于 FedAvg。

图 2. IID 数据评估：FedAvg 和 LoAdaBoost FedAvg 性能比较，C=0.1

（3）本地计算量

对于 Non-IID 数据，FedAvg 的实验结果和本文提出的使用共享数据的方法如图 3 所示。E 值较大，收敛速度快，对于不同的 E 值，本文提出的方法效果都优于 FedAvg：E=5，本文方法效果始终优于 FedAvg；E=10 或 15 时，前面几轮通信过程中 FedAvg 效果较好，但随着通信轮数增加，本文方法的效果优于 FedAvg。

图 3. 在 Non-IID 数据中应用数据共享策略 FedAvg、LoAdaBoost FedAvg 性能对比

表 2 总结了图 3 中的实验结果。E=5 时，采用相同的通信轮数（11）LoAdaBoost FedAvg 比 FedAvg 平均周期少 0.4。当 E=10 和 15 时，LoAdaBoost FedAvg 达到目标 AUC 分别进行了 8 轮和 5 轮通信，以及 7.0 和 10.7 的平均周期。而 FedAvg 在有限通讯轮数内都未能达到目标 AUC。

这些实验结果证明，LoAdaBoost FedAvg 改进了优化过程的正则化处理效果。对于实际应用场景来说，通信成本是最主要的关注点，必须为客户端增加更多的时间来加速模型训练，因此 LoAdaBoost FedAvg 有着很好的实用价值。

表 2. 对 Non-IID 数据的评估：不同方法达到 AUC=0.79 所需的平均周期和通信轮数

总结与分析

大量高度隐私的分布式医疗健康数据可以通过联邦学习有效的加以利用，同时满足数据存储和模型计算过程在本地完成的要求。在本文的医学数据实验条件下，FedAvg 在 Non-IID 数据分布情况下的效果明显不如 IID 数据，而本文提出的 LoAdaBoost FedAvg 通过使用数据共享策略，能够大大提升 Non-IID 数据的联邦学习效果。但是，在数据倾斜非常严重的情况下，例如在一些语言数据库中，数据共享策略效果不好，LoAdaBoost FedAvg 的性能也会受到影响。在今后的研究中，将会重点考虑哪种类型的数据库可以在 Non-IID 分布的情况下获得较好的建模性能，以及数据的哪些特性会影响不同策略的效果

作者介绍：仵冀颖，工学博士，毕业于北京交通大学，曾分别于中国香港中文大学和中国香港科技大学担任助理研究员和研究助理，现从事电子政务领域信息化新技术研究工作。主要研究方向为模式识别、计算机视觉，爱好科研，希望能保持学习、不断进步。

本文为机器之心原创，转载请联系本公众号获得授权。

------------------------------------------------