联邦学习中的non-IID数据

关于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
  • 《机器学习》 - 周志华著