機器之心原創
作者：仵冀穎
編輯：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<C<=1, C=1 表示全部客戶端參與更新），這些客戶端基於本地數據根據全局狀態執行本地模型優化處理，本文使用隨機梯度下降（Stochastic gradient descent，SGD）算法實現優化。
本地優化完畢後，客戶端向中央伺服器發送更新的模型參數，中央伺服器基於客戶端更新的模型參數更新全局狀態。重複上述過程直至全局模型收斂。
在實際應用場景中，客戶端本地數據可能在優化過程中發生變化，例如生成數據、刪除數據等，一些客戶端可能會處於關閉等無法連接狀態。本文主要關注客戶端存儲的 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]={1,...,C}。點對 {x,y} 的分布為 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 分布的情況下獲得較好的建模性能，以及數據的哪些特性會影響不同策略的效果
作者介紹：仵冀穎，工學博士，畢業於北京交通大學，曾分別於香港中文大學和香港科技大學擔任助理研究員和研究助理，現從事電子政務領域信息化新技術研究工作。主要研究方向為模式識別、計算機視覺，愛好科研，希望能保持學習、不斷進步。