2020-03-28 17:26:00 聯邦學習

前言

Gradient Boosting Decision Tree (GBDT) 是一個非常流行的機器學習模型，經常在機器學習及數據挖掘競賽中被使用。隨著人們對隱私越來越注重，聯邦學習最近得到了越來越多的關注。GBDT和聯邦學習結合是一個重要的研究課題。今天為大家介紹的是一篇被AAAI 2020接收的論文《Practical Federated Gradient Boosting Decision Trees》，作者來自新加坡國立大學的Qinbin Li, Bingsheng He和西澳大學的Zeyi Wen，論文地址https://arxiv.org/pdf/1911.04206.pdf。在這篇文章中，作者提出了一個實用的GBDT聯邦學習框架。

背景

GBDT模型由多顆決策樹組成。在進行預測時，預測值為所有樹上的對應葉子值的和。一個示例如圖1所示。在構造決策樹時，需要用到各個樣本的損失函數在當前預測值上的一階和二階導數 (用g和h表示)。

圖1 GBDT示例

本文中作者考慮橫向聯邦學習的場景。多個組織擁有不同的數據，如何在不交換數據的情況下聯合訓練一個有效的GBDT模型？作者提出了SimFL (Similarity-based Federated Learning)，一個新的聯邦學習框架。

方法介紹

整個聯邦學習框架分為兩個階段：預處理階段和訓練階段。

預處理階段的目標是收集相似信息，如圖2所示。這裡作者使用到了局部敏感哈希 (Locality-Sensitive Hashing, LSH)，這種哈希函數的特點是兩個相似的樣本得到相同哈希值的可能性也較高，而且無法從哈希值逆推出樣本值。作者採用了多個LSH函數，每個組織首先計算自己樣本對應的哈希值，然後廣播這些值給其他的組織。經過廣播後，所有的組織都可以構建一個哈希表，裡面存儲著樣本序號和對應的哈希值。然後，每個組織都可以通過這個哈希表來計算相似信息。具體來說，如果兩個樣本有更多相同的哈希值，那麼他們相似的可能性更大。每個組織對於自己的每個樣本，都在其他組織中尋找一個擁有相同哈希值最多的樣本，標記為相似樣本。預處理階段過後，每個組織對於自己的樣本，都能在其他各個組織中找到一個相似樣本。

圖2 預處理階段

收集完相似信息後，接下來進入到訓練階段。圖3給出了一個簡單示例。總的來說，每個組織輪流訓練一些樹，最終的模型為各個組織訓練的樹之和。在訓練一棵樹前，所有組織都需要用目前已經構建的決策樹來更新各個樣本的g和h，並將g和h傳給接下來訓練新的一顆決策樹的組織。這個組織利用自己的樣本和所有的g和h來訓練一棵樹，然後將這棵樹發送給其他的組織。最終，就可以訓練完成整個GBDT模型。

這裡作者提出了一個新的訓練方法，取名為加權梯度下降 (weighted gradient boosting)。傳統的GBDT使用g和h來構建決策樹，這裡作者將相似樣本的g相加，將得到的結果作為加權梯度來代替原來的g進行訓練 (h同理)。這種訓練方式可以有效的整合其他組織的數據分佈信息，即使沒有獲取到其他組織的具體樣本值。論文中有提供這種方法的理論分析。

圖3 訓練階段

實驗結果

作者在6個公開數據集上進行了實驗。這裡作者嘗試了兩種不同的數據劃分方法:均勻劃分和不均勻劃分。在均勻劃分中，作者將數據集隨機等分成幾份，每份表示一個組織的本地數據集，這樣不同組織的數據服從獨立同分布。在不均勻劃分中，作者按照樣本標籤來進行劃分，保證部分組織某一種樣本的比例要比另一部分要高，這樣不同組織數據不服從獨立同分布。實驗具體細節請參考論文，下面展示論文中的部分實驗結果。

圖4 不均勻劃分下的實驗

圖4中橫座標為組織的數量，縱座標為測試集上的錯誤率。藍線為作者提出的方法 (SimFL)，灰線為所有組織直接分享數據進行訓練 (ALL-IN)，黑線為組織之間不合作只進行本地訓練 (SOLO)，紅線為另一篇發表於INFOCOM 2018 (http://nisplab.whu.edu.cn/paper/infocom_2018_3.pdf) 的一個框架 (TFL)。可以看到，SimFL的效果不錯，比TFL和SOLO好，並且在組織數目少的時候非常逼近ALL-IN。