XGBoost算法思想

本章涉及到的知識(shí)點(diǎn)清單:

1、boosting模式

2、集成學(xué)習(xí)模型的偏差和方差

3、bagging的偏差和方差

4、boosting的偏差和方差

5、XGBoost的基礎(chǔ)模型

6、XGBoost的目標(biāo)函數(shù)

7、優(yōu)化目標(biāo)函數(shù)

8、樹的函數(shù)表達(dá)式的拆分

9、模型的復(fù)雜度定義

10、繼續(xù)優(yōu)化目標(biāo)函數(shù)

11、求解目標(biāo)函數(shù)極值

12、樹節(jié)點(diǎn)分裂算法

13、XGBoost的算法步驟

14、案例演示

15、XGBoost的優(yōu)點(diǎn)

一、boosting模式

boosting屬于集成學(xué)習(xí)框架之一,與bagging類似,boosting也不再是用單一的模型來進(jìn)行預(yù)測(cè),而是組合若干弱學(xué)習(xí)器來產(chǎn)生一個(gè)強(qiáng)學(xué)習(xí)器

boosting:整個(gè)訓(xùn)練過程呈階梯狀,弱學(xué)習(xí)器按照次序逐一進(jìn)行訓(xùn)練,與bagging不同在于每個(gè)弱學(xué)習(xí)器的訓(xùn)練集,都按照某種策略進(jìn)行一定的轉(zhuǎn)化,最后對(duì)所有弱學(xué)習(xí)器的預(yù)測(cè)結(jié)果進(jìn)行線性綜合來產(chǎn)生最終的預(yù)測(cè)結(jié)果。即:

boosting模型

boosting有如下特點(diǎn):

(1)所有弱學(xué)習(xí)器的學(xué)習(xí)過程均依賴于同一份訓(xùn)練集結(jié)果,訓(xùn)練集在每個(gè)弱學(xué)習(xí)器訓(xùn)練完成后,都會(huì)按照同一策略更新轉(zhuǎn)化

(2)所有弱學(xué)習(xí)器的訓(xùn)練過程是串行化的,即當(dāng)前弱學(xué)習(xí)器訓(xùn)練的參數(shù)依賴于上一個(gè)弱學(xué)習(xí)器訓(xùn)練的結(jié)果

(3)所有弱學(xué)習(xí)器對(duì)于訓(xùn)練集的每個(gè)樣本都有相同的初始化權(quán)重

(4)當(dāng)每個(gè)弱學(xué)習(xí)器學(xué)習(xí)完,而對(duì)于那些預(yù)測(cè)結(jié)果錯(cuò)誤的樣本會(huì)采用某個(gè)策略來增加其權(quán)重

(5)boosting總是更加關(guān)注被錯(cuò)誤預(yù)測(cè)的弱規(guī)則

關(guān)于boosting算法比較常見的有:AdaBoost、GBDT以及本文分析的XGBoost

二、集成學(xué)習(xí)模型的偏差和方差

偏差:描述模型的預(yù)測(cè)值和樣本的真實(shí)值之間的差異,反映模型的準(zhǔn)確度

方差:描述模型的預(yù)測(cè)值作為隨機(jī)變量的離散程度,反映模型的過擬合能力

這里我們可以用期望這個(gè)統(tǒng)計(jì)量來描述模型的偏差

由方差和協(xié)方差的基本定義出發(fā):

方差的定義
協(xié)方差的定義

對(duì)于集成學(xué)習(xí)模型,通過計(jì)算弱學(xué)習(xí)器模型的期望和方差,我們可以得到模型整體的期望和方差。而且不論是bagging還是boosting,其弱學(xué)習(xí)器都是線性組成的,我們?cè)O(shè)每個(gè)弱學(xué)習(xí)器為f_{i},總共有m個(gè)弱學(xué)習(xí)器,f_{i}對(duì)應(yīng)的權(quán)重為r_{i},F為整個(gè)模型

則模型的期望E(F)為:

模型的期望

模型的方差var(F)為:

模型的方差

這里需要用到二項(xiàng)展開公式

二項(xiàng)展開

帶入模型方差展開得

模型的方差

我們?cè)僖?個(gè)統(tǒng)計(jì)量:標(biāo)準(zhǔn)差\sigma 和相關(guān)系數(shù)\rho ,用來代表整體模型的標(biāo)準(zhǔn)差和相關(guān)系數(shù),其基本定義為:

標(biāo)準(zhǔn)差和相關(guān)系數(shù)的定義

\sigma \rho 帶入模型方差,得

模型的方差

推導(dǎo)至此,我們得到了集成學(xué)習(xí)整體模型的期望E(F)方差var(F)的數(shù)學(xué)表達(dá)式

集成學(xué)習(xí)模型的期望和方差

集成學(xué)習(xí)模型的整體偏差和方差的關(guān)系可形象的展示為:

集成學(xué)習(xí)模型的整體偏差和方差

接下來我們分別討論在bagging或boosting算法下模型整體的期望和方差

三、bagging的期望和方差

對(duì)于bagging來說,每個(gè)弱學(xué)習(xí)器的權(quán)重r_{i}都為\frac{1}{m} ,且每個(gè)弱學(xué)習(xí)器訓(xùn)練的樣本都是從原始樣本采取有放回式隨機(jī)抽樣,故每個(gè)弱學(xué)習(xí)器的期望E(f_{i})近似相等\mu

則bagging的期望為:

bagging的期望

bagging的方差為:

bagging的方差

比較集成學(xué)習(xí)模型的期望和方差,可以總結(jié)出bagging:

(1)模型整體的期望近似等于單個(gè)弱學(xué)習(xí)器的期望

(2)隨著訓(xùn)練的進(jìn)行,模型整體的方差降低

我們也可以看到,隨機(jī)森林(Random Forest)采取對(duì)訓(xùn)練集的特征進(jìn)行隨機(jī)抽樣的策略,使得各個(gè)弱學(xué)習(xí)器的相關(guān)性降低,從而達(dá)到減少方差的效果

四、boosting的偏差和方差

對(duì)于boosting來說,訓(xùn)練集抽樣是強(qiáng)相關(guān)的,即模型的相關(guān)系數(shù) \rho近似等于1

則boosting的期望為:

boosting的期望

boosting的方差為:

boosting的方差

比較集成學(xué)習(xí)模型的期望和方差,可以總結(jié)出boosting:

(1)剛初始化時(shí),模型整體的期望較低,方差較低

(2)隨著訓(xùn)練的進(jìn)行,模型整體的期望升高,方差也增大

五、XGBoost的基礎(chǔ)模型

XGBoost(Extreme Gradient Boosting)是GBDT的一種高效實(shí)現(xiàn),其弱學(xué)習(xí)器除了可以是CART回歸樹,也可以是線性分類器。這里我們用CART樹來當(dāng)作弱學(xué)習(xí)器

考慮場景:我們要預(yù)測(cè)一家人對(duì)電子游戲的喜好程度,為此可以構(gòu)建2顆CART樹

第1顆CART樹:考慮到年輕和年老相比,年輕更可能喜歡電子游戲,故使用“年齡”作為第1個(gè)特征來二分樣本集;再考慮到男性和女性相比,男性更喜歡電子游戲,故使用“性別”作為第2個(gè)特征來二分子樣本集,最后逐一給各人在電子游戲喜好程度上打分

第2顆CART樹:考慮到喜歡電子游戲的人每天使用電腦的頻率較高,故使用“每天使用電腦的頻率”作為特征來二分子樣本集,最后逐一給各人在電子游戲喜好程度上打分

場景CART樹

對(duì)于上述兩顆CART樹,我們要計(jì)算小男孩的預(yù)測(cè)分?jǐn)?shù),只需在每顆CART樹中找到小男孩落在的樹葉位置,將樹葉對(duì)應(yīng)的分?jǐn)?shù)累加即可

上述物理場景的行為過程如下:

(1)有K顆CART樹

(2)對(duì)于任意n維樣本x_{i},找到其在每顆樹中所在葉子的位置和該葉子的權(quán)重

(3)將這些權(quán)重相加,作為x_{i}最后的預(yù)測(cè)分?jǐn)?shù)

我們將上述場景數(shù)學(xué)化

設(shè)\hat{y}_{i}是樣本x_{i}的最終預(yù)測(cè)分?jǐn)?shù),f_{i}是第i顆樹的葉子打分映射,則預(yù)測(cè)函數(shù)

模型的預(yù)測(cè)函數(shù)

所有樹的葉子打分映射將共同構(gòu)成模型的函數(shù)空間,即

模型的函數(shù)空間

(PS:注意這里不再是模型的參數(shù)空間\theta ,而是函數(shù)空間f

六、XGBoost的目標(biāo)函數(shù)

我們繼續(xù)定義出模型的損失函數(shù)

模型的損失函數(shù)

其中l(y_{i}, \hat{y}_{i})是單個(gè)樣本x_{i}的損失函數(shù),可以是任意可微函數(shù),比如平方誤差邏輯誤差函數(shù)

平方誤差函數(shù)
邏輯誤差函數(shù)

接下來我們?cè)俣x出模型的復(fù)雜度為

模型的復(fù)雜度

其中\Omega(f_{i})可以用樹的深度、葉子的數(shù)量、葉子權(quán)重的L2范式等量化

我們對(duì)上述模型的損失函數(shù)和復(fù)雜度進(jìn)行線性組合,便得到了XGBoost的目標(biāo)函數(shù)Obj

XGBoost的目標(biāo)函數(shù)

顯然,XGBoost的目標(biāo)函數(shù)加入了正則項(xiàng),即:L(F)表示模型的偏度(期望),用 \Omega (F)表示模型的復(fù)雜度(方差)

七、優(yōu)化目標(biāo)函數(shù)

從數(shù)學(xué)角度看,目標(biāo)函數(shù)Obj的定義是一個(gè)泛函,優(yōu)化目標(biāo)函數(shù)等價(jià)于泛函最優(yōu)化問題,這使得我們很難進(jìn)行優(yōu)化

(PS:\hat{y}_{i}的自變量包含K個(gè)函數(shù)f_{i}(x_{i}),即\hat{y}_{i}函數(shù)的函數(shù)—泛函

為此我們需要對(duì)目標(biāo)函數(shù)進(jìn)行變換,根據(jù)boosting的思想:

(1)每次迭代,都是在現(xiàn)有模型的基礎(chǔ)上,增加一個(gè)弱學(xué)習(xí)器

(2)新增加的弱學(xué)習(xí)器就是一個(gè)新函數(shù)f,用來擬合當(dāng)前模型的預(yù)測(cè)結(jié)果和真實(shí)值的殘差

(3)通過不斷迭代K個(gè)弱學(xué)習(xí)器來不斷降低模型的預(yù)測(cè)結(jié)果和真實(shí)值的殘差

我們將上述思想進(jìn)行數(shù)學(xué)化,即

加入第0顆樹,當(dāng)前模型的預(yù)測(cè)結(jié)果為

加入第0顆樹

加入第1顆樹,當(dāng)前模型的預(yù)測(cè)結(jié)果為

加入第1顆樹

加入第2顆樹,當(dāng)前模型的預(yù)測(cè)結(jié)果為

加入第2顆樹

根據(jù)數(shù)學(xué)歸納法,加入第t顆樹,即第t次迭代,當(dāng)前模型的預(yù)測(cè)結(jié)果為

加入第t顆樹

將上述迭代結(jié)果帶入目標(biāo)函數(shù),則目標(biāo)函數(shù)改為迭代版本如下

迭代版本的目標(biāo)函數(shù)

下面我們需要對(duì)目標(biāo)函數(shù)進(jìn)行一些數(shù)學(xué)上的近似處理

我們知道二階泰勒公式的迭代形式為

二階泰勒公式的迭代形式

這里我們將目標(biāo)函數(shù)類比二階泰勒公式,即

類比二階泰勒公式

且定義g_{i}h_{i}類比二階泰勒公式中的一階導(dǎo)數(shù)和二階導(dǎo)數(shù),即

類比二階泰勒公式

有了上述近似類比,我們將目標(biāo)函數(shù)在f_{t}(x_{i})處進(jìn)行二階泰勒展開,得

目標(biāo)函數(shù)的泰勒二階展開

我們繼續(xù)優(yōu)化目標(biāo)函數(shù)

由于目標(biāo)函數(shù)只受到基學(xué)習(xí)器f的影響,上一次的誤差l(y_{i},\hat{y_{i}}^{(t-1)}) 是常數(shù)項(xiàng),對(duì)本次迭代沒有影響(常量微分為0),于是我們可以刪除掉常數(shù)項(xiàng),即

優(yōu)化目標(biāo)函數(shù)

至此我們得到了迭代過程下,目標(biāo)函數(shù)的近似表達(dá)式,繼續(xù)優(yōu)化之前,我們需要先討論每棵樹的函數(shù)表達(dá)式 f_{t}(x_{i})

八、樹的函數(shù)表達(dá)式的拆分

我們將第t顆樹的函數(shù)表達(dá)式 f_{t}(x_{i}),拆分成樹結(jié)構(gòu)部分q葉子權(quán)重部分w,即

樹結(jié)構(gòu)和葉子權(quán)重

如上圖,樹的物理意義為:

每個(gè)樣本均落在樹中對(duì)應(yīng)的葉子中,且每片葉子都有權(quán)重分?jǐn)?shù)值

我們將其數(shù)學(xué)化,即定義:

q(x_{i}):=在樹中,任意樣本x_{i}落在葉子的位置

w_{q(x_{i})}:=在樹中,任意樣本x_{i}所在葉子的權(quán)重

至此,我們可以將樹的函數(shù)表達(dá)式 f_{t}(x_{i})寫為

樹的函數(shù)表達(dá)

九、模型的復(fù)雜度定義

緊接著我們定義出模型的復(fù)雜度\Omega(f_{t})

我們用葉子節(jié)點(diǎn)的個(gè)數(shù)T和每片葉子的權(quán)重w_{j}的L2范數(shù)來共同描述模型的復(fù)雜度,即

模型的復(fù)雜度

其中\gamma\lambda是超參數(shù),\gamma用來收縮葉子個(gè)數(shù),\lambda控制葉子權(quán)重分?jǐn)?shù)不會(huì)過大,二者同時(shí)防止模型過擬合

十、繼續(xù)優(yōu)化目標(biāo)函數(shù)

有了樹的函數(shù)表達(dá)式 f_{t}(x_{i})的拆分和模型的復(fù)雜度\Omega(f_{t}),我們繼續(xù)優(yōu)化目標(biāo)函數(shù)

將二者帶入目標(biāo)函數(shù),得

目標(biāo)函數(shù)

下面需要用到一個(gè)數(shù)學(xué)技巧,仔細(xì)觀察上式

目標(biāo)函數(shù)

上式中,紅色部分表示:對(duì)整個(gè)樣本集合的遍歷;藍(lán)色部分表示:對(duì)所有葉節(jié)點(diǎn)的遍歷

為了將二者的累加形式統(tǒng)一,我們有如下結(jié)論

(1)由于所有樣本在樹結(jié)構(gòu)中,最終都會(huì)落在葉子節(jié)點(diǎn)上

(2)則遍歷所有樣本\Leftrightarrow?遍歷所有葉子節(jié)點(diǎn)中的子樣本

因此我們定義I_{j}表示樹中第j個(gè)葉子中樣本的集合,即

第j個(gè)葉子中樣本集合

I_{j}帶入目標(biāo)函數(shù),我們就可以統(tǒng)一兩個(gè)\sum的物理意義和數(shù)學(xué)形式,即

目標(biāo)函數(shù)

緊接著我們定義G_{i}H_{i}來簡化目標(biāo)函數(shù)

簡化目標(biāo)函數(shù)

帶入則目標(biāo)函數(shù)最終可以化簡為

目標(biāo)函數(shù)

至此,我們一步步推導(dǎo)出了XGBoost目標(biāo)函數(shù)的最終表達(dá)式,接下來就可以求解其極值

十一、求解目標(biāo)函數(shù)極值

此時(shí)弱學(xué)習(xí)器—樹已經(jīng)構(gòu)造完成,即樹結(jié)構(gòu)q(x)確定,為了使得目標(biāo)函數(shù)達(dá)到最小值,我們令對(duì)每個(gè)葉子的偏導(dǎo)數(shù)為0,即

每個(gè)葉子的偏導(dǎo)數(shù)為0

求解上述偏導(dǎo)數(shù),便可解出每個(gè)葉子的最優(yōu)權(quán)重w_{j}^{*}為:

每個(gè)葉子的最優(yōu)權(quán)重

將其帶入目標(biāo)函數(shù),便得到模型的最小損失obj^{*}為:

模型的最小損失

至此,我們完成了XGBoost對(duì)目標(biāo)函數(shù)的最優(yōu)化過程。且從本質(zhì)上講,這就是轉(zhuǎn)化為一個(gè)二次函數(shù)最優(yōu)化問題

十二、樹節(jié)點(diǎn)分裂算法

下面我們需要關(guān)心XGBoost的基學(xué)習(xí)器—樹到底長什么樣子?

顯然,一棵CART樹的生長過程,是由一個(gè)根節(jié)點(diǎn)開始二分裂,然后各子節(jié)點(diǎn)繼續(xù)二分裂直到分裂產(chǎn)生葉子節(jié)點(diǎn)停止

那么一個(gè)節(jié)點(diǎn)應(yīng)該怎么分裂?就成為了接下來我們要探討的關(guān)鍵

我們采取貪心算法來分裂樹節(jié)點(diǎn)

(1)從根節(jié)點(diǎn)開始對(duì)每個(gè)節(jié)點(diǎn),都遍歷所有特征

(2)將所有特征的特征值進(jìn)行排序,選取不同分位點(diǎn)作為候選點(diǎn)

(3)遍歷所有候選點(diǎn),量化計(jì)算按照當(dāng)前候選點(diǎn)分裂后產(chǎn)生的增益Gain

(4)選擇Gain最高的特征和候選點(diǎn)作為當(dāng)前節(jié)點(diǎn)的最優(yōu)特征和最優(yōu)分割點(diǎn)

(5)直到產(chǎn)生葉子節(jié)點(diǎn),則停止節(jié)點(diǎn)分裂

關(guān)于Gain增益的計(jì)算,我們使用當(dāng)前樹的最小損失,用節(jié)點(diǎn)分裂前的損失值減去分裂后的損失值,作為按當(dāng)前特征和候選點(diǎn)分裂的增益量化

Gain的計(jì)算

按照貪心算法構(gòu)建樹,有下面兩種構(gòu)建方案

方案一:當(dāng)Gain為負(fù)值則停止分裂,樹生長完成,這樣做效率會(huì)高,但有可能會(huì)放棄一些更好的情況(預(yù)剪枝)

方案二:先讓樹生長到最大深度,再遞歸到Gain為負(fù)數(shù)的節(jié)點(diǎn)進(jìn)行修剪(后剪枝)

這里我們選取方案二進(jìn)行建樹剪枝

十三、XGBoost的算法步驟

(1)循環(huán)增加一顆CART樹 f_{t}(x_{i})

(2)用貪婪算法構(gòu)建樹,包含用損失函數(shù)一階和二階導(dǎo)數(shù)信息計(jì)算葉子的最優(yōu)權(quán)重w_{j}和節(jié)點(diǎn)分裂的最優(yōu)增益Gain

(3)用構(gòu)建好的樹迭代優(yōu)化函數(shù)空間:\hat{y}^{(t)}_{i} = \hat{y}^{(t-1)}_{i} + f_{t}(x_{i})

(4)重新更新計(jì)算損失函數(shù)的一階和二階導(dǎo)數(shù)

(5)重復(fù)第(1)步,直到生成K顆樹

從上面步驟可以看到,關(guān)鍵點(diǎn)是樹的構(gòu)造和剪枝

十四、案例演示

下面我們用原生python來實(shí)現(xiàn)myXGBoost模型(不考慮并行計(jì)算)

訓(xùn)練樣本集為

訓(xùn)練樣本集

首先構(gòu)造樹節(jié)點(diǎn)類和方法

樹節(jié)點(diǎn)類
計(jì)算樣本所在葉子權(quán)重
遞歸統(tǒng)計(jì)回歸樹葉子節(jié)點(diǎn)數(shù)量和葉子節(jié)點(diǎn)的父節(jié)點(diǎn)數(shù)量
剪枝操作

下面構(gòu)造樹模型類和方法

樹模型類
訓(xùn)練CART樹
遞歸構(gòu)建回歸樹
選擇使得節(jié)點(diǎn)分裂最好的特征
計(jì)算葉節(jié)點(diǎn)的權(quán)重值
計(jì)算節(jié)點(diǎn)分裂后的增益
根據(jù)特征和分割點(diǎn)二分化

最后我們構(gòu)建XGBoost類和方法

XGBoost類
貪婪算法構(gòu)建樹
預(yù)測(cè)測(cè)試集類別

接下來我們定義損失函數(shù),這里用logistic函數(shù)

定義損失函數(shù)

logistic函數(shù)的一階和二階偏導(dǎo)數(shù)為:

logistic函數(shù)

最后比較我們自己寫的myXGBoost和官方封裝好的黑盒模型xgboost的預(yù)測(cè)結(jié)果差異,用準(zhǔn)確度和ROC曲線下面積這兩個(gè)統(tǒng)計(jì)量來比較

和官方黑盒模型比較預(yù)測(cè)結(jié)果

可以看到自己寫的模型的預(yù)測(cè)結(jié)果,很逼近官方黑盒模型的預(yù)測(cè)效果

十五、XGBoost的優(yōu)點(diǎn)

最后我們可以總結(jié)出XGBoost有如下優(yōu)點(diǎn):

(1)泰勒二階

XGBoost對(duì)Loss函數(shù)的數(shù)學(xué)處理用到了泰勒二階展開,除了提高了誤差精度,更將待優(yōu)化的Loss函數(shù)轉(zhuǎn)化為關(guān)于f_{t}(x)的二次函數(shù)最優(yōu)化問題

(2)支持自定義損失函數(shù)

XGBoost對(duì)Loss函數(shù)進(jìn)行泰勒二階展開,即支持任意二階可導(dǎo)的函數(shù)作為模型的損失函數(shù)

(3)正則化

XGBoost的Loss加入了正則化項(xiàng),包含了對(duì)復(fù)雜模型的懲罰,比如懲罰了葉子的節(jié)點(diǎn)數(shù)量和葉子權(quán)重的分?jǐn)?shù)值大小,降低了模型的方差,防止模型過擬合

(4)特征列抽樣

XGBoost借鑒了隨機(jī)森林的做法,對(duì)每個(gè)訓(xùn)練集特征進(jìn)行隨機(jī)不放回式抽樣,降低了不同樹之間的相關(guān)性,從而降低了模型的方差,防止模型過擬合

(5)貪心構(gòu)建樹

采取貪心策略構(gòu)建最大深度的樹,在遞歸剪枝

(6)支持并行

樣本數(shù)據(jù)事先排好序并以block的形式存儲(chǔ),利于并行計(jì)算

還可把XGBoost模型高度抽象為:

把樣本從根分配到葉子結(jié)點(diǎn),本質(zhì)是一個(gè)排列組合,而不同的組合對(duì)應(yīng)不同的損失函數(shù),我們要優(yōu)化尋找的,就是使得損失函數(shù)達(dá)到最小值的那一種組合方案

案例代碼見:XGBoost算法思想

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

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

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