本章涉及到的知識(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有如下特點(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ā):


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

模型的方差為:

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

帶入模型方差展開得

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

將和
帶入模型方差,得

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

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

接下來我們分別討論在bagging或boosting算法下模型整體的期望和方差
三、bagging的期望和方差
對(duì)于bagging來說,每個(gè)弱學(xué)習(xí)器的權(quán)重都為
,且每個(gè)弱學(xué)習(xí)器訓(xùn)練的樣本都是從原始樣本采取有放回式隨機(jī)抽樣,故每個(gè)弱學(xué)習(xí)器的期望
近似相等為
則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ù)近似等于1
則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樹:考慮到喜歡電子游戲的人每天使用電腦的頻率較高,故使用“每天使用電腦的頻率”作為特征來二分子樣本集,最后逐一給各人在電子游戲喜好程度上打分

對(duì)于上述兩顆CART樹,我們要計(jì)算小男孩的預(yù)測(cè)分?jǐn)?shù),只需在每顆CART樹中找到小男孩落在的樹葉位置,將樹葉對(duì)應(yīng)的分?jǐn)?shù)累加即可
上述物理場景的行為過程如下:
(1)有K顆CART樹
(2)對(duì)于任意n維樣本
,找到其在每顆樹中所在葉子的位置和該葉子的權(quán)重
(3)將這些權(quán)重相加,作為
最后的預(yù)測(cè)分?jǐn)?shù)
我們將上述場景數(shù)學(xué)化
設(shè)是樣本
的最終預(yù)測(cè)分?jǐn)?shù),
是第i顆樹的葉子打分映射,則預(yù)測(cè)函數(shù)為

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

(PS:注意這里不再是模型的參數(shù)空間,而是函數(shù)空間
)
六、XGBoost的目標(biāo)函數(shù)
我們繼續(xù)定義出模型的損失函數(shù)為

其中
是單個(gè)樣本
的損失函數(shù),可以是任意可微函數(shù),比如平方誤差和邏輯誤差函數(shù)


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

其中
可以用樹的深度、葉子的數(shù)量、葉子權(quán)重的L2范式等量化
我們對(duì)上述模型的損失函數(shù)和復(fù)雜度進(jìn)行線性組合,便得到了XGBoost的目標(biāo)函數(shù)

顯然,XGBoost的目標(biāo)函數(shù)加入了正則項(xiàng),即:用表示模型的偏度(期望),用
表示模型的復(fù)雜度(方差)
七、優(yōu)化目標(biāo)函數(shù)
從數(shù)學(xué)角度看,目標(biāo)函數(shù)的定義是一個(gè)泛函,優(yōu)化目標(biāo)函數(shù)等價(jià)于泛函最優(yōu)化問題,這使得我們很難進(jìn)行優(yōu)化
(PS:的自變量包含K個(gè)函數(shù)
,即
是函數(shù)的函數(shù)—泛函)
為此我們需要對(duì)目標(biāo)函數(shù)進(jìn)行變換,根據(jù)boosting的思想:
(1)每次迭代,都是在現(xiàn)有模型的基礎(chǔ)上,增加一個(gè)弱學(xué)習(xí)器
(2)新增加的弱學(xué)習(xí)器就是一個(gè)新函數(shù)
,用來擬合當(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é)果為

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

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

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

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

下面我們需要對(duì)目標(biāo)函數(shù)進(jìn)行一些數(shù)學(xué)上的近似處理
我們知道二階泰勒公式的迭代形式為

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

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

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

我們繼續(xù)優(yōu)化目標(biāo)函數(shù)
由于目標(biāo)函數(shù)只受到基學(xué)習(xí)器的影響,上一次的誤差
是常數(shù)項(xiàng),對(duì)本次迭代沒有影響(常量微分為0),于是我們可以刪除掉常數(shù)項(xiàng),即

至此我們得到了迭代過程下,目標(biāo)函數(shù)的近似表達(dá)式,繼續(xù)優(yōu)化之前,我們需要先討論每棵樹的函數(shù)表達(dá)式
八、樹的函數(shù)表達(dá)式的拆分
我們將第t顆樹的函數(shù)表達(dá)式,拆分成樹結(jié)構(gòu)部分q和葉子權(quán)重部分w,即

如上圖,樹的物理意義為:
每個(gè)樣本均落在樹中對(duì)應(yīng)的葉子中,且每片葉子都有權(quán)重分?jǐn)?shù)值
我們將其數(shù)學(xué)化,即定義:
在樹中,任意樣本
落在葉子的位置
在樹中,任意樣本
所在葉子的權(quán)重
至此,我們可以將樹的函數(shù)表達(dá)式寫為

九、模型的復(fù)雜度定義
緊接著我們定義出模型的復(fù)雜度
我們用葉子節(jié)點(diǎn)的個(gè)數(shù)和每片葉子的權(quán)重
的L2范數(shù)來共同描述模型的復(fù)雜度,即

其中和
是超參數(shù),
用來收縮葉子個(gè)數(shù),
控制葉子權(quán)重分?jǐn)?shù)不會(huì)過大,二者同時(shí)防止模型過擬合
十、繼續(xù)優(yōu)化目標(biāo)函數(shù)
有了樹的函數(shù)表達(dá)式的拆分和模型的復(fù)雜度
,我們繼續(xù)優(yōu)化目標(biāo)函數(shù)
將二者帶入目標(biāo)函數(shù),得

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

上式中,紅色部分表示:對(duì)整個(gè)樣本集合的遍歷;藍(lán)色部分表示:對(duì)所有葉節(jié)點(diǎn)的遍歷
為了將二者的累加形式統(tǒng)一,我們有如下結(jié)論
(1)由于所有樣本在樹結(jié)構(gòu)中,最終都會(huì)落在葉子節(jié)點(diǎn)上
(2)則遍歷所有樣本
?遍歷所有葉子節(jié)點(diǎn)中的子樣本
因此我們定義表示樹中第j個(gè)葉子中樣本的集合,即

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

緊接著我們定義和
來簡化目標(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)確定,為了使得目標(biāo)函數(shù)達(dá)到最小值,我們令對(duì)每個(gè)葉子的偏導(dǎo)數(shù)為0,即

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

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

至此,我們完成了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)分裂的增益量化

按照貪心算法構(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樹
(2)用貪婪算法構(gòu)建樹,包含用損失函數(shù)一階和二階導(dǎo)數(shù)信息計(jì)算葉子的最優(yōu)權(quán)重
和節(jié)點(diǎn)分裂的最優(yōu)增益
(3)用構(gòu)建好的樹迭代優(yōu)化函數(shù)空間:
(4)重新更新計(jì)算損失函數(shù)的一階和二階導(dǎo)數(shù)
(5)重復(fù)第(1)步,直到生成K顆樹
從上面步驟可以看到,關(guān)鍵點(diǎn)是樹的構(gòu)造和剪枝
十四、案例演示
下面我們用原生python來實(shí)現(xiàn)myXGBoost模型(不考慮并行計(jì)算)
訓(xùn)練樣本集為

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




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







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



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

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

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

可以看到自己寫的模型的預(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)于
的二次函數(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算法思想