联邦学习中的非独立同分布Non-IID

在联邦学习Federated Learning中，出现的很高频的一个词就是Non-IID，翻译过来就是非独立同分布，这是一个来自于概率论与数理统计中的概念，下面我来简单介绍一下在Federated Learning中IID和Non-IID的概念。

何为IID（独立同分布）

IID是数据独立同分布（Independent Identically Distribution，IID），它是指一组随机变量中每个变量的概率分布是相同的，且这些随机变量互相独立。下面介绍IID中的“独立”和“同分布”这两个概念：

• 独立性：采样样本之间相互独立，互不影响。用数学公式表达：如果随机变量X和Y独立，那么它们的联合概率分布可以分解为$P(X,Y)=P(X)\ast P(Y)$。

例如抛骰子，我抛两次，上一次抛的结果并不会影响到下一次的结果，这两次采样样本之间就是独立的。但是假如说我想要两次结果之和大于8，那么这时候两次抛就不独立了。

• 同分布：所有采样样本均来自同一个分布。

还是抛骰子，每次采样的样本都来自于同一个分布，即每次抛都会随机得到一个1~6的点数，每个点数的概率为1/6。

现在很多机器学习中的方法都是基于数据IID的假设，这是一种理想情况，因为在现实中往往是Non-IID的。

何为Non-IID（非独立同分布）

首先要明确一个概念，Non-IID是非·独立同分布，解释来说就是，Non-IID可以分为三类：非独立但同分布、独立但非同分布、非独立也非同分布。上述的任何一种我们都可以称之为Non-IID。

• 非独立：两个或多个随机变量之间存在一定程度的关联，一个随机变量的值可能受到其他随机变量的影响。

比如要求两次抛骰子结果之和大于8、不放回地摸黑球白球。

• 非同分布：样本并不是从同一个分布中采样得到的。

来自不同的分布，一个样本我从抛骰子中获取1_{6，另一个样本我从扑克中抽A}K。

联邦学习中的Non-IID

在机器学习中，有特征Features和标签Labels这两个概念。由这两个概念，我们就能引申出FL中的5种Non-IID情况：

1. Feature Distribution Skew 特征分布偏差；
2. Label Distribution Skew 标签分布偏差；
3. Same Label，different features 相同标签，不同特征；
4. Same Feature，different labels 相同特征，不同标签；
5. Quantity skew or unbalancedness 数量倾斜或不平衡；

在FL中，数据是存储在不同的设备上的，而各个设备可能采集不同类型的数据、数据量不同、数据质量不同、数据采集的时间和地点也不同，因此不同设备之间的数据可能是非独立或非同分布的。
由于数据Non-IID，在联邦学习模型训练时，可能会受到的影响：

1. 模型收敛困难：当各设备的本地数据分布不同或数据质量差异较大时，全局模型收敛会受到影响，因为不同设备间的本地模型更新合并起来不太容易。
2. 性能不稳定：由于数据Non-IID，全局模型可能在某些设备上表现良好，而在另一些设备上表现很差。

在FL中，Non-IID通常伴随着异构性Heterogeneity一起出现。我们通常认为，Non-IID是异构性Heterogeneity的一种表现，而异构性Heterogeneity在概念上更为广泛。
在FL中，异构性Heterogeneity一般分为三种：

1. 设备异构性：不同的设备有不同的硬件性能，如cpu、gpu、内存等，导致计算能力不同。此外网速和稳定性方面也各有不同；
2. 统计异构性：设备的数据可能来自于不同的数据源、采集方式、时间段、环境等，导致数据的统计性质存在差异；
3. 数据异构性：设备的数据可能是不同的类型（文本/图像/音频等）；