Krum算法是一种基于欧氏距离的拜占庭容错机器学习算法，是一种在分布式机器学习中保证其在具有拜占庭错误时仍然可以收敛的算法。
拜占庭错误
所谓的拜占庭错误在机器学习中是指，客户端在提交模型更新时，可以提交任意的随机数，或者选择不提交。当然，这有可能是由于机器故障或者网络故障等不可抗力的原因，也可能是由于恶意的用户故意提交错误的更新，来破坏训练过程。
算法假设
我们具有n n n个客户端{ c 1 , c 2 , ⋯ , c n } {c_1,c_2,\cdots,c_n}{c 1 ,c 2 ,⋯,c n }和一个服务器s s s，每个客户端都具有一部分数据，c i c_i c i 具有数据D i D_i D i 。一般假设数据是独立同分布的，也就是iid.
在这n n n个客户端中，有f f f个是不诚实的，也就是可能发起拜占庭攻击的。且满足2 f + 2 < n 2f+2.
算法步骤
初始化：协商模型和各种必须参数；
1、s s s将全局的参数W W W分发给所有客户端；
2、对于每个客户端c i c_i c i ，同时进行：根据本地的数据计算本地的梯度g i g_i g i ，然后发送给客户端；
3、模型收到客户端的梯度后，两两计算梯度之间的距离d i , j = ∣ ∣ g i − g j ∣ ∣ 2 d_{i,j}=||g_i-g_j||^2 d i ,j =∣∣g i −g j ∣∣2;
4、对于每个梯度g i g_i g i ，选择与他最近的n − f − 1 n-f-1 n −f −1个距离，即{ d i , 1 , d i , 2 , ⋯ , d i , i − 1 , d i , i + 1 , ⋯ , d i , n } {d_{i,1},d_{i,2},\cdots,d_{i,i-1},d_{i,i+1},\cdots,d_{i,n}}{d i ,1 ,d i ,2 ,⋯,d i ,i −1 ,d i ,i +1 ,⋯,d i ,n }中最小的n − f − 1 n-f-1 n −f −1个，不妨设为{ d i , 1 , d i , 2 , ⋯ , d i , n − f − 1 } {d_{i,1},d_{i,2},\cdots,d_{i,n-f-1}}{d i ,1 ,d i ,2 ,⋯,d i ,n −f −1 }，然后加起来作为该梯度g i g_i g i 的得分K r ( i ) = ∑ j = 1 n − f − 1 d i , j Kr(i)=\sum_{j=1}^{n-f-1}d_{i,j}K r (i )=∑j =1 n −f −1 d i ,j .
5、计算所有的梯度的得分后，求得分最小的梯度g i ∗ g_{i^}g i ∗；
6、更新W = W − l r ⋅ g i ∗ W=W-lr\cdot g_{i^}W =W −l r ⋅g i ∗；
7、重复1-6，直到模型收敛。
Multi-Krum
在Krum的算法中的第5步，选出一个最低得分的梯度后，再返回4步，继续选择，直到选择出了m个梯度，最后的梯度为这m个的平均。
Original: https://blog.csdn.net/watqw/article/details/124370843
Author: 咸鱼菲菲
Title: 拜占庭容错机器学习算法之Krum算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/618440/
转载文章受原作者版权保护。转载请注明原作者出处！