关于non-IID数据

independent and identically distributed(IID)即独立同分布，指的是全体样本服从某一分布，而每次获得的样本都是独立地从这个分布上采样获得的。

独立：指的是每次采样之间不会有关系。例如多次投骰子，第一次投和第十次投之间没有什么关系；相较之下，出现乌云与下雨就非独立。

同分布：指的是随机变量服从统一分布。仍以骰子举例，若骰子质量分布不会变动，则每次投的结果将会呈现一定的规律；相较之下若采用作弊骰子（可以人为改变某一端的质量），则会破坏这一性质。

non-IID自然是以上概念的否命题（独立和同分布任意不满足即可）。

联邦学习中的non-IID数据分类

在真实世界中数据往往会因为各种各样的原因而呈现non-IID的特性（例如某地雨水天气多，生锈故障的样本会更多）。在机器学习领域，我们不妨从输入空间$X$与输出空间$Y$来考虑。

假设样本独立但不同分布

样本满足贝叶斯公式：$P(X,Y)=P(X)P(Y|X)$。对于客户端$i$与$j$，考虑$P_i(X)$（$i$输入分布）、$P_i(Y|X)$（$i$标签分布）与$P_j(X)$（$j$输入分布）、$P_j(Y|X)$（$j$输入分布）。

1. 若$P_i(X)\ne P_j(X)$，且$P_i(Y|X)=P_j(Y|X)$：客户端输入不相同，但输出相同。例如不同国家对于汽车行驶方向的规定不同，但都需要遵守相同的交通规则（跟随信号灯）。
2. 若$P_i(X)= P_j(X)$，且$P_i(Y|X)\ne P_j(Y|X)$：客户端输入相同，但输出不相同。例如不同地区对于交通法规的定义不同，有些地区红灯必须停止，而有些地区可以在确认安全的情况下通行。
3. 若$P_i(X)\ne P_j(X)$，且$P_i(Y|X)\ne P_j(Y|X)$：客户端输入输出均不相同。此为以上两种情况的组合，例如行驶方向与交通法规均不相同。

若$P_i(X)=P_j(X)$，且$P_i(Y|X)=P_j(Y|X)$：与假设不符（这是IID）。

假设样本不独立但同分布

对于全体样本而言考虑$X\sim B(n,p)$，那么若有$Y=(n-X)\sim B(n,p)$则输入与输出不独立但同分布。例如抛$n$次硬币$x$次正面朝上的概率与$n-x$次反面朝上的概率。

放在联邦学习的角度，可以理解为$P_i(X)$与$P_j(X)$不独立，而$P_i(Y|X)=P_j(Y|X)$服从同一分布。例如银行中用户数据异构但用户大多一样。

假设样本不独立且不同分布

比如读paper与掉头发的关系（？

再从样本特性上分类

属性倾斜

属性倾斜从客户端样本属性重叠程度出发考虑，分为：非重叠属性倾斜（Non-overlapping Attribute Skew）、部分重叠属性倾斜（Partial Overlapping Attribute Skew）与完全重叠属性倾斜（Full Overlapping Attribute Skew）。

非重叠属性倾斜

客户端的属性完全没有重叠（例如$k_1$拥有属性$A,B$，$k_2$拥有属性$C,D$），但展现强相关性，此时可以视为纵向联邦学习（Vertical FL）。

部分重叠属性倾斜

客户端的属性部分重叠（例如$k_1$拥有属性$A,B$，$k_2$拥有属性$B,D$）。

完全重叠属性倾斜

客户端的属性部分重叠（例如$k_1$拥有属性$A,B$，$k_2$也拥有属性$A,B$）。

标签倾斜

标签分布倾斜

标签偏好倾斜

客户端对样本的偏好不同（对于同一样本，客户端$A$喜欢，$B$不喜欢）。

时间倾斜

随着时间的推移，客户端的数据会有所倾斜（可参考联邦增量学习）。

其它

属性&标签倾斜

质量倾斜

Ref

• Non-IID data and Continual Learning processes in Federated Learning: A long road ahead
• Federated Learning on Non-IID Data: A Survey
• Federated Visual Classification with Real-World Data Distribution
• 《机器学习》 - 周志华著