聯(lián)邦學(xué)習(xí)-安全樹模型 SecureBoost之Desicion Tree

聯(lián)邦學(xué)習(xí)-安全樹模型 SecureBoost之Desicion Tree

1 聯(lián)邦學(xué)習(xí)背景

鑒于數(shù)據(jù)隱私的重要性，國內(nèi)外對于數(shù)據(jù)的保護意識逐步加強。2018年歐盟發(fā)布了《通用數(shù)據(jù)保護條例》（GDPR），我國國家互聯(lián)網(wǎng)信息辦公室起草的《數(shù)據(jù)安全管理辦法(征求意見稿)》因此數(shù)據(jù)在安全合規(guī)的前提下自由流動，成了大勢所趨。這些法律法規(guī)的出臺，不同程度的對人工智能傳統(tǒng)處理數(shù)據(jù)的方式提出更多的挑戰(zhàn)。

AI高度發(fā)展的今天，多維度高質(zhì)量的數(shù)據(jù)是制約其進一步發(fā)展的瓶頸。隨著各個組織對于數(shù)據(jù)的重視程度的不斷提升，跨組織以及組織內(nèi)部不同部門之間的數(shù)據(jù)合作將變得越來越謹慎，造成了數(shù)據(jù)大量的以孤島的形式存在


在這里插入圖片描述

聯(lián)邦學(xué)習(xí)的本質(zhì)是基于數(shù)據(jù)隱私保護一種分布式機器學(xué)習(xí)技術(shù)或機器學(xué)習(xí)框架。它的目標(biāo)是在保證數(shù)據(jù)隱私安全及合法合規(guī)的基礎(chǔ)上，在模型無損的前提實現(xiàn)共同建模，提升AI模型的效果，進行業(yè)務(wù)的賦能。

那么既然是建模，在工業(yè)界最近若干年比較出名的大致可以分為GBDT和神經(jīng)網(wǎng)絡(luò)了，但是由于聯(lián)邦學(xué)習(xí)的特性，需要對用戶的特征與Label進行隱私安全保護，所以需要采用同態(tài)加密、秘鑰分享、差分隱私等隱私計算手段保障安全。但是基于此帶來了比較大的挑戰(zhàn)，神經(jīng)網(wǎng)絡(luò)的復(fù)雜運算，指數(shù)、對數(shù)等會給建模提出非常大的難題，以目前的硬件與軟件加密技術(shù)還是非常困難的，但是對于GBDT來說，只需要進行簡單的同態(tài)運算就解決，所以本篇文章會和大家分享下聯(lián)邦學(xué)習(xí)的安全樹模型-Secure Boost。

BTW，目前神經(jīng)網(wǎng)絡(luò)雖然比較難做安全屏障，無法很好的做到計算性能與模型性能的Balance，但是經(jīng)過筆者長期的思考，已經(jīng)有了一個自己認為靠譜的方案，后續(xù)會逐步驗證，如果最終驗證靠譜，會和大家Share出來一起分享。

由于樹模型相對來說知識較多，所以無法一步到位解決清晰SecureBoost，故本文章分成以下主題來進行，主要的脈絡(luò)就是：決策樹 -> 集成方法Bagging & Boosting -> GBDT -> XGBoost -> Secure Boost Tree。希望讀者可以通過這一系列文章，對聯(lián)邦學(xué)習(xí)的SecureBoost方法有一個整體的全方位的掌握。

其實，對于樹模型系列來說，筆者以前做算法的時候，也在大量的使用，并且覺得自己是理解到位的，但是在我寫聯(lián)邦學(xué)習(xí)安全樹模型的時候，發(fā)現(xiàn)很多的地方并沒有理解透徹，有很多細節(jié)是沒有考慮到的，寫著寫著就會發(fā)現(xiàn)自己的理論厚度不夠，細節(jié)沒有吃透。后來也花了大量的精力和時間去充電，這個事情也讓我明白了，很多東西你看起來懂了，其實并沒有懂，只有去真正的用心的去做過一遍，你才有些懂了，無論做什么事情腳踏實地才是最重要的。

2 Decision Tree

2.1 決策樹的定義

什么是決策樹呢？決策樹是一種監(jiān)督學(xué)習(xí)方法，既可以用來處理分類問題也可以處理回歸問題。

以職場為例吧，目前整個公司有一個比較難的行業(yè)技術(shù)領(lǐng)域要破局，這個時候職場里面很多沒有躺平的同事都希望自己可以能夠解決這個問題，但是既然是行業(yè)技術(shù)難題，就不是所有人可以解決的?；诖耸紫纫紤]的是這個事情，自己是否有勇氣去做，然后考慮自己是否有能力去做，如果自己沒有能力去做，自己是否可以和牛人一起合作去做這個事情，如果牛人自己就搞定，那就沒他什么事情了。


在這里插入圖片描述

下面筆者分別介紹下決策樹相關(guān)的知識。

2.2 決策樹基礎(chǔ)

為了下面更好的描述生成決策樹的相關(guān)算法，先介紹下一些基本概念。

2.2.1 熵

熵這個詞在各個學(xué)科都有涉及，熵的概念是由德國物理學(xué)家克勞修斯于1865年所提出，泛指某些物質(zhì)系統(tǒng)狀態(tài)的一種量度，某些物質(zhì)系統(tǒng)狀態(tài)可能出現(xiàn)的程度。在信息論與概率統(tǒng)計中，熵（entropy）是表示隨機變量不確定性的變量。假設(shè)X是個取有限個值的離散型的隨機變量，其概率分布為
P(X=x_i) = p_i, i=1,2,...,n
那么隨機變量X的熵的定義為：
H(X) = -\sum_i^np_ilogp_i

從上的定義可知，熵越大隨機變量的不確定性越強，那么從特征重要度的角度來說，該特征越不具備較強的表征分裂能力。

在這里插入圖片描述

2.2.2 條件熵

假設(shè)隨機變量（X，Y），他們的聯(lián)合分布如下：
P(X=x_i, Y=y_j)=p_{ij}, i = 1,2,...,n; \quad j=1,2,...,m

那么，我們定義條件熵H（Y|X）表示在已知隨機變量X的條件下隨機變量Y的不確定性，也就說在X給定條件下Y的條件概率分布的熵對X的數(shù)學(xué)期望：
H(Y|X)=\sum_i^np_iH(Y|X=x_i)

2.2.3 信息增益

特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g（D，A），那么信息增益定義為集合D的經(jīng)驗熵H（D）與特征A給定條件下關(guān)于D的條件熵H（D|A）之差，即
g(D,A)=H(D) - H(D|A)

如果信息增益越大，那么就是指分完之后的信息熵越小，那也就意味著分完之后的數(shù)據(jù)趨向于穩(wěn)定，而越穩(wěn)定的數(shù)據(jù)，意味著我們能更好地預(yù)測數(shù)據(jù)。

設(shè)訓(xùn)練數(shù)據(jù)集為D，則|D|表示樣本容量，即樣本的個數(shù)。
假設(shè)該批樣本總共有K個分類定義為c_k,k=1,2,...,K，則|C_k|定義為屬于C_k的樣本個數(shù)，則\sum_{k=1}^K|C_k|=|d|，設(shè)

特征A有n個不同的取值，{a_1,a_2, ...,a_n}。則根據(jù)特征A的取值將D劃分成n個子集D_1,D_2,...,D_n,|D_i|為D_i的樣本

個數(shù)，\sum_{i=1}^n|D_i|= |D|。同時定義子集D_i中屬于C_k的樣本的集合為D_{ij}，則D_{ij} = D_i \cap C_k,

|D_{ik}|定義為D_{ik}的樣本個數(shù)。

那么根據(jù)上述描述，特征A對數(shù)據(jù)集D的經(jīng)驗條件熵H（D|A）
H(D|A) = - \sum_{i=1}^n \frac{D_i}{D}\ \sum_{k=1}^K \frac{D_{ik}}{D_i} \ \log_2{ \frac{D_{ik}}{D_i} \ }

信息增益準則的一個問題在于它會偏愛那些具有很多取值的特征，而忽略其與分類的相關(guān)性。例如，考慮這么一個場景，假設(shè)我們在處理一個二分類的任務(wù)，且每個樣本有一個唯一的ID。此時若選擇這個ID作為特征進行節(jié)點分裂的時候，將會獲得較大的信息增益，因為他能準確的分類所有的訓(xùn)練樣本，但是，這樣的分類結(jié)果卻無法泛華，不能對位置樣例進行預(yù)測。這個時候就可以采用信息增益率來解決。ID3算法采用的是信息增益，而C4.5采用的是信息增益率，后續(xù)會詳細介紹。

2.3 剪枝策略

對于決策樹來說，經(jīng)常可以觀察到這樣一種現(xiàn)象：相對于一棵在訓(xùn)練集表現(xiàn)的不是那么好的決策樹，一棵在訓(xùn)練集上表現(xiàn)的十分完成的決策樹的泛化能力更差。這種現(xiàn)象就是“過擬合”，本質(zhì)原因在于學(xué)習(xí)器在學(xué)習(xí)的過程中把訓(xùn)練特征中的一個非樸素特質(zhì)當(dāng)做了潛在的真實分布造成的。也就是說，學(xué)習(xí)器學(xué)習(xí)的太好了，把一些噪音也血流量進去。

針對決策樹來說，為了防止“過擬合”造成較差的泛化能力，常用策略就是使用“剪枝”老進行去噪，進而學(xué)到更加樸素的特質(zhì)，學(xué)到數(shù)據(jù)的本質(zhì)。常用的剪枝方案有以下兩種：

  1. 預(yù)剪枝：在樹的生成階段進行剪枝。
  2. 后剪枝：在樹生成后，在檢查需要去掉哪些分支。
在這里插入圖片描述

2.4 ID3算法

ID3算法最早是由羅斯昆（J. Ross Quinlan）于1975年在悉尼大學(xué)提出的一種分類預(yù)測算法，算法的核心是“信息熵”。ID3算法通過計算每個屬性的信息增益，認為信息增益高的是好屬性，每次劃分選取信息增益最高的屬性為劃分標(biāo)準，重復(fù)這個過程，直至生成一個能完美分類訓(xùn)練樣例的決策樹。

決策樹的技術(shù)核心在于樹的節(jié)點的分裂思想，ID3算法采用在分裂節(jié)點采用信息增益準則進行特征選擇，進而遞歸的進行整棵樹的構(gòu)建。ID3算法是一種貪心算法，用來構(gòu)造決策樹。ID3算法起源于概念學(xué)習(xí)系統(tǒng)（CLS），以信息熵的下降速度為選取測試屬性的標(biāo)準，即在每個節(jié)點選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標(biāo)準，然后繼續(xù)這個過程，直到生成的決策樹能完美分類訓(xùn)練樣例。

2.4.1 ID3算法構(gòu)建決策樹方案

  • 首先，從根節(jié)點開始，針對節(jié)點計算所有可能特征的信息增益。
  • 然后，選擇信息增益最大的特征作為節(jié)點的特征進行分裂。
  • 然后，針對這個信息增益最大的特征，根據(jù)蓋特征的不同取值簡歷子節(jié)點。
  • 然后，在對子節(jié)點重復(fù)上面的過程。
  • 最后，知道所有特征的信息增益均很小達到閾值或者沒有特征可以選擇為止。

2.4.2 ID3算法優(yōu)缺點總結(jié)

  • 模型結(jié)構(gòu)：N叉樹，如果特征的取值較多，計算量非?？捎^。
  • 模型目標(biāo)：適合處理分類問題。
  • 特征相關(guān)：沒有給出連續(xù)型特征的處理方法，適合處理離散型特征，對于缺失的特征沒有需要在預(yù)處理階段自行解決缺失值問題。
  • 模型優(yōu)化：沒有模型的剪紙優(yōu)化操作，容易發(fā)生過擬合。
  • 內(nèi)存消耗：隨著樣本的特征空間維度迅速膨脹。
  • 計算效率：N叉樹，隨著樣本的特征空間進行分支，計算耗時較高。

2.5 C4.5算法

C4.5算法是由Ross Quinlan開發(fā)的用于產(chǎn)生決策樹的算法。該算法是對Ross Quinlan之前開發(fā)的ID3算法的一個擴展。C4.5算法產(chǎn)生的決策樹可以被用作分類目的，因此該算法也可以用于統(tǒng)計分類。C4.5算法與ID3算法類似，如上面所說，C4.5相對于ID3算法進行了改進，在數(shù)的生成過程中使用了信息增益比進行特征的選擇，其他的基本是一致的。

2.5.1 C4.5算法構(gòu)建決策樹方案

請參考ID3算法，有些不一樣的地方是對連續(xù)特征進行離散化。

2.5.2 C4.5算法優(yōu)缺點總結(jié)

  • 模型結(jié)構(gòu)：N叉樹，如果特征的取值較多，計算量非常可觀。
  • 模型目標(biāo)：適合處理分類問題。
  • 特征相關(guān)：連續(xù)特征離散化（離散化的方法，針對M個特征，有M-1個特征選擇，也要進行特征取值排序，每個候選的分割閾值點的值為上述排序后的屬性值中兩兩前后連續(xù)元素的中點，相當(dāng)于離散特征變多）。支持處理離散型特征，對于缺失的特征征值以一定的概率劃分到不同的節(jié)點。
  • 模型優(yōu)化：悲觀剪枝策略進行樹的剪枝。
  • 內(nèi)存消耗：需要對特征值進行排序，內(nèi)存操作，容易OOM。
  • 計算效率：N叉樹，隨著樣本的特征空間進行分支，并且需要多次掃描與排序，計算耗時較高。

2.6 CART算法

熟悉機器學(xué)習(xí)算法與框架的朋友，都會有這樣的感受，那就是很多算法都是在尋求算法和工程的平衡，既要良好的算法效果，也有較高的計算效率，二者是缺一不可的。

CART樹相對于ID3和C4.5做了一些簡化處理，它使用了了二叉樹而不是多叉樹，進而提高生成決策樹的效率，減少運算量。并且分類樹通過Gini系數(shù)作為變量的不純度量，減少大量的對數(shù)運算耗時。

2.6.1分類樹

下面我來介紹下基于CART的分類樹。CART作為分類樹時，特征屬性可以是連續(xù)類型也可以是離散類型，樹的節(jié)點分裂策略基于基尼指數(shù)，接下來就先介紹下基尼指數(shù)。

2.6.1.1 基尼指數(shù)

定義：在分類問題中，假設(shè)有K個類，樣本點屬于第K個類的概率為pk，則概率分布的基尼指數(shù)為
Gini(p) = \sum_{k=1}^Kp_k(1-P_k) = 1 - \sum_{k=1}^K{p_k}^2

對于給定的樣本集合D來說，其基尼指數(shù)為：
Gini(D) = 1 - \sum_{k=1}^K{( \frac{|C_K|}{|D|} \ )}^2

那么，在特征A條件下，結(jié)合D的基尼指數(shù)為，D1和D2為按照特征A的某個取值進行切分后的兩個范圍。
Gini(D,A) = \frac{|D_1|}{|D|} \ Gini（D_i)+ \frac{|D_2|}{|D|} Gini(D_2) \

基尼指數(shù)Gini代表數(shù)據(jù)的不確定性，Gini（D，A）表示經(jīng)過特征A=a分裂后集合D的不確定性，那么和信息增益不一樣的是，基尼指數(shù)越小代表模型的不純度卻低，特征約好。

2.6.1.2 分類樹的生成

CART分類樹采用基尼指數(shù)進行二叉樹的分裂，枚舉所有特征的所有可能切分點進行計算，選取基尼指數(shù)最小的分裂點，降低模型的不純度。同時對于決策樹建立后做預(yù)測的方式，CART分類樹采用葉子節(jié)點里概率最大的類別作為當(dāng)前節(jié)點的預(yù)測類別。

2.6.2 回歸樹

回歸樹的特征基本是連續(xù)型的，利用平方誤差最小化準則。

流程如下： 對于任意特征A，依次計算所有可能的分裂點取值，通過該取值將樣本數(shù)據(jù)劃分成D1和D2兩部分，通過MSE的方式計算各自的Loss并相加（回歸樹輸出不是類別，它采用的是用最終葉子的均值或者中位數(shù)來預(yù)測輸出結(jié)果。），進而選擇損失最小的特征取值，然后進行節(jié)點分裂，并且重新劃分各自節(jié)點的數(shù)據(jù)集，然后遞歸執(zhí)行本過程即可。

\min\limits_{j,s}[\min\limits_{C1}\sum_{x_i \in R_1(j,s)}(y_i - c_1)^2 + \min\limits_{C1}\sum_{x_i \in R_2(j,s)}(y_j - c_2)^2 ]

其中，氣氛便利為j，切分點為s，將數(shù)據(jù)集切分為C1和C2兩部分，我們通過上述算法找到損失最小的。

CART樹的優(yōu)缺點

  • 模型結(jié)構(gòu)：使用二叉樹的形式，提升決策樹整理效率。
  • 模型目標(biāo)：支持分類樹與回歸樹。
  • 特征相關(guān)：采用代替測試來估計缺失值，并且特征可以在各層之間反復(fù)使用。
  • 模型優(yōu)化：使用剪枝踐行優(yōu)化，基于代價復(fù)雜度的方式進行剪枝。
  • 計算代價：分類樹采用Gini系數(shù)的方式減少復(fù)雜運算。

3 自我介紹

個人介紹：杜寶坤，京東聯(lián)邦學(xué)習(xí)從0到1構(gòu)建者，帶領(lǐng)團隊構(gòu)建了京東的聯(lián)邦學(xué)習(xí)解決方案，實現(xiàn)了電商營銷領(lǐng)域支持超大規(guī)模的工業(yè)化聯(lián)邦學(xué)習(xí)解決方案，支持超大規(guī)模樣本PSI隱私對齊、安全的樹模型與神經(jīng)網(wǎng)絡(luò)模型等眾多模型，建模不受限，同時帶領(lǐng)團隊實現(xiàn)了業(yè)務(wù)側(cè)的落地，開創(chuàng)了新的業(yè)務(wù)增長點，產(chǎn)生了顯著的業(yè)務(wù)經(jīng)濟效益。

個人喜歡研究技術(shù)?；趶娜溌匪伎寂c決策技術(shù)規(guī)劃的考量，研究的領(lǐng)域比較多，從架構(gòu)、大數(shù)據(jù)到機器學(xué)習(xí)算法與框架均有涉及。歡迎喜歡技術(shù)的同學(xué)和我交流，郵箱：baokun06@163.com

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容