xgboost 已然火爆機(jī)器學(xué)習(xí)圈佳晶，相信不少朋友都使用過(guò)抄瓦。要想徹底掌握xgboost，就必須搞懂其內(nèi)部的模型原理蚕泽。這樣才能將各個(gè)參數(shù)對(duì)應(yīng)到模型內(nèi)部蛇更，進(jìn)而理解參數(shù)的含義，根據(jù)需要進(jìn)行調(diào)參赛糟。本文的目的就是讓大家盡可能輕松地理解其內(nèi)部原理。主要參考文獻(xiàn)是陳天奇的這篇文章introduction to xgboost砸逊。在我看來(lái)璧南，這篇文章是介紹xgboost最好的，沒(méi)有之一师逸。英語(yǔ)好的同學(xué)建議直接看英文司倚，若有不是很理解的地方，再來(lái)參考本文篓像。

1动知、你需要提前掌握的幾個(gè)知識(shí)點(diǎn)

1、監(jiān)督學(xué)習(xí)
監(jiān)督學(xué)習(xí)就是訓(xùn)練數(shù)據(jù)有標(biāo)簽的學(xué)習(xí)员辩。比如說(shuō)盒粮，我有10萬(wàn)條數(shù)據(jù)，每個(gè)數(shù)據(jù)有100個(gè)特征奠滑，還有一個(gè)標(biāo)簽丹皱。標(biāo)簽的內(nèi)容取決于學(xué)習(xí)的問(wèn)題，如果數(shù)據(jù)是病人進(jìn)行癌癥診斷做的各項(xiàng)檢查的結(jié)果宋税，標(biāo)簽就是病人是否得癌癥摊崭。是為1，不是為0.

監(jiān)督學(xué)習(xí)就是要從這10萬(wàn)條數(shù)據(jù)中學(xué)習(xí)到根據(jù)檢查結(jié)果診斷病人是否得癌癥的知識(shí)杰赛。由于學(xué)習(xí)的范圍限定在這10萬(wàn)條數(shù)據(jù)中呢簸，也就是說(shuō)，學(xué)習(xí)的知識(shí)必須是從這10萬(wàn)條數(shù)據(jù)中提煉出來(lái)。形象地理解根时，就是在這10萬(wàn)條帶標(biāo)簽數(shù)據(jù)的“監(jiān)督”下進(jìn)行學(xué)習(xí)瘦赫。因此稱為監(jiān)督學(xué)習(xí)。
2啸箫、監(jiān)督學(xué)習(xí)的成果
監(jiān)督學(xué)習(xí)學(xué)習(xí)到的知識(shí)如何表示耸彪，又是如何被我們?nèi)祟愂褂媚兀亢?jiǎn)單講忘苛，學(xué)習(xí)到的知識(shí)用一個(gè)模型來(lái)表示蝉娜，我們?nèi)祟惥陀眠@個(gè)模型來(lái)使用學(xué)習(xí)到的知識(shí)。
那么扎唾，模型是什么東西召川？
模型就是一個(gè)數(shù)學(xué)表達(dá)式。最簡(jiǎn)單的一個(gè)模型就是線性模型胸遇，它長(zhǎng)這個(gè)樣子：y^i=∑_j θ_j*x_ij荧呐。用我們上面的例子講，x_i就是我們10萬(wàn)條數(shù)據(jù)中的第i條纸镊，x_ij就是第i條數(shù)據(jù)中的第j個(gè)檢查結(jié)果倍阐。y^i就是模型對(duì)這條數(shù)據(jù)的預(yù)測(cè)結(jié)果，這個(gè)值越大逗威，表明病人得癌癥的概率也大峰搪。通常，我們還需將y^i處理成0到1的值凯旭，以更清晰地表明這是一個(gè)概率預(yù)測(cè)概耻，處理的方法一般是用sigmoid函數(shù)，不熟悉的朋友可參考其他資料罐呼。θ_j就是第j個(gè)檢查結(jié)果對(duì)病人是否得癌癥的“貢獻(xiàn)度”鞠柄，它是我們模型的參數(shù)，也就是我們從10萬(wàn)條數(shù)據(jù)中學(xué)習(xí)到的知識(shí)嫉柴。

可見(jiàn)厌杜，所謂監(jiān)督學(xué)習(xí)，就是兩步计螺，一是定出模型確定參數(shù)期奔，二是根據(jù)訓(xùn)練數(shù)據(jù)找出最佳的參數(shù)值，所謂最佳危尿，從應(yīng)用角度看呐萌，就是最大程度地吸收了10萬(wàn)條訓(xùn)練數(shù)據(jù)中的知識(shí)，但從我們尋找參數(shù)的過(guò)程來(lái)看谊娇，卻有另一番解釋肺孤，下文會(huì)詳細(xì)解釋罗晕，找到最佳參數(shù)后，我們就得出一個(gè)參數(shù)都是已知的模型赠堵，此時(shí)小渊，知識(shí)就在其中，我們可以自由使用茫叭。

3酬屉、如何找出最佳參數(shù)
以上面的線性模型為例，病人有100個(gè)檢查結(jié)果揍愁，那么就有100個(gè)參數(shù)θ_j（j從1到100）呐萨。每個(gè)參數(shù)可取值都是實(shí)數(shù)，100個(gè)參數(shù)的組合顯然有無(wú)窮多個(gè)莽囤，我們?cè)趺丛u(píng)判一組參數(shù)是不是最佳的呢谬擦？
此時(shí)，我們需要另外一個(gè)函數(shù)來(lái)幫助我們來(lái)確定參數(shù)是否是最佳的朽缎，這就是目標(biāo)函數(shù)(object function)惨远。

目標(biāo)函數(shù)如何確定呢？用我們上面的例子來(lái)講话肖，我們要判斷病人是否得癌癥北秽，假設(shè)我們對(duì)上面的線性模型的值y^i進(jìn)行了處理，將它規(guī)約到了0到1之間最筒。我們的10萬(wàn)條訓(xùn)練數(shù)據(jù)中羡儿，得癌癥的病人標(biāo)簽為1，沒(méi)得的標(biāo)簽為0.那么顯然是钥，最佳的參數(shù)一定就是能夠?qū)⒌冒┌Y的病人全預(yù)測(cè)為1，沒(méi)得癌癥的病人全部預(yù)測(cè)為0的參數(shù)缅叠。這幾乎就是完美的參數(shù)悄泥！
因此，我們的目標(biāo)函數(shù)可以設(shè)為MSE函數(shù)：obj = ∑_i (sigmoid(∑_jθ_j*x_ij) - y_i)^2

上面的函數(shù)的意思就是對(duì)第i條數(shù)據(jù)肤粱，將模型預(yù)測(cè)的值規(guī)約到0到1弹囚，然后與該條數(shù)據(jù)的真是標(biāo)簽值（0和1）做差，再求平方领曼。這個(gè)平方值越大鸥鹉，表明預(yù)測(cè)的越不準(zhǔn)，就是模型的預(yù)測(cè)誤差庶骄，最后毁渗，我們將模型對(duì)10萬(wàn)條數(shù)據(jù)的預(yù)測(cè)誤差求和。就得出了一組具體的參數(shù)的預(yù)測(cè)好壞的度量值单刁。

果真這樣就完美了嗎灸异？
不是的。上面的目標(biāo)函數(shù)僅僅評(píng)測(cè)了參數(shù)對(duì)訓(xùn)練數(shù)據(jù)來(lái)說(shuō)的好壞，并沒(méi)有評(píng)測(cè)我們使用模型做預(yù)測(cè)時(shí)肺樟，這組參數(shù)表現(xiàn)好壞檐春。也就是說(shuō)，對(duì)訓(xùn)練數(shù)據(jù)來(lái)說(shuō)是好的參數(shù)么伯，未必在預(yù)測(cè)時(shí)就是好的疟暖。為什么？

• 一是10萬(wàn)條數(shù)據(jù)中有錯(cuò)誤存在
• 二是10萬(wàn)條數(shù)據(jù)未必涵蓋了所有種類的樣本田柔，舉個(gè)極端的例子俐巴，假如10萬(wàn)條數(shù)據(jù)全是60歲以上老人的檢查結(jié)果，我們用學(xué)習(xí)到的模型取預(yù)測(cè)一個(gè)10歲的小孩凯楔，很可能是不準(zhǔn)的窜骄。

那么，怎么評(píng)測(cè)一組參數(shù)對(duì)預(yù)測(cè)是好是壞呢摆屯？
答案是測(cè)了才知道邻遏！

這不是廢話嗎。

事實(shí)就是這樣虐骑。真實(shí)的預(yù)測(cè)是最權(quán)威的評(píng)判准验。但我們還是可以有所作為的，那就是正則化廷没。

所謂正則化就是對(duì)參數(shù)施加一定的控制糊饱，防止參數(shù)走向極端。以上面的例子來(lái)說(shuō)颠黎，假如10萬(wàn)條數(shù)據(jù)中另锋，得癌癥的病人都是60歲以上老人，沒(méi)得癌癥的病人都是30歲以下年輕人狭归，檢查結(jié)果中有一項(xiàng)是骨質(zhì)密度夭坪，通常，老人骨質(zhì)密度低过椎，年輕人骨質(zhì)密度高室梅。那么我們學(xué)習(xí)到的模型很可能是這樣的，對(duì)骨質(zhì)密度這項(xiàng)對(duì)應(yīng)的參數(shù)θ_j設(shè)的非常大疚宇，其他的參數(shù)都非常小亡鼠，簡(jiǎn)單講，模型傾向于就用這一項(xiàng)檢查結(jié)果去判斷病人是否得癌癥敷待，因?yàn)檫@樣會(huì)讓目標(biāo)函數(shù)最小间涵。

明眼人一看便知，這樣的參數(shù)做預(yù)測(cè)肯定是不好的榜揖。

正則化可以幫助我們規(guī)避這樣的問(wèn)題浑厚。

常用的正則化就是L2正則股耽，也就是所有參數(shù)的平方和。我們希望這個(gè)和盡可能小的同時(shí)钳幅，模型對(duì)訓(xùn)練數(shù)據(jù)有盡可能好的預(yù)測(cè)物蝙。

最后，我們將L2正則項(xiàng)加到最初的目標(biāo)函數(shù)上敢艰，就得出了最終的目標(biāo)函數(shù)：
obj = ∑_i(sigmoid(∑_j θ_j*x_ij) - y_i)^2 + ∑_j(θ_j^2)

能使這個(gè)函數(shù)值最小的那組參數(shù)就是我們要找的最佳參數(shù)诬乞。這個(gè)obj包含的兩項(xiàng)分別稱為損失函數(shù)和正則項(xiàng)。
這里的正則項(xiàng)钠导，本質(zhì)上是用來(lái)控制模型的復(fù)雜度震嫉。

Notes:
上面，我們?yōu)榱吮M可能簡(jiǎn)單地說(shuō)明問(wèn)題牡属，有意忽略了一些重要的方面票堵。比如，我們的例子是分類逮栅，但使用的損失函數(shù)卻是MSE悴势，通常是不這樣用的。
對(duì)于回歸問(wèn)題措伐，我們常用的損失函數(shù)是MSE特纤，即：

回歸.PNG

對(duì)于分類問(wèn)題，我們常用的損失函數(shù)是對(duì)數(shù)損失函數(shù)：

分類.PNG

乍一看侥加，這個(gè)損失函數(shù)怪怪的捧存，我們不免要問(wèn)，為什么這個(gè)函數(shù)就是能評(píng)判一組參數(shù)對(duì)訓(xùn)練數(shù)據(jù)的好壞呢担败？

我們用上面的例子來(lái)說(shuō)明昔穴，假如有一條樣本，它的標(biāo)簽是1提前，也就是y_i = 1吗货，那么關(guān)于這條樣本的損失函數(shù)中就只剩下了左邊那一部分，由于y_i = 1岖研，最終的形式就是這樣的：

對(duì)數(shù)1.PNG

頭上帶一個(gè)小尖帽的yi就是我們模型的預(yù)測(cè)值，顯然這個(gè)值越大警检，則上面的函數(shù)越傾向于0孙援，yi趨向于無(wú)窮大時(shí)，損失值為0扇雕。這符合我們的要求拓售。

同理，對(duì)于yi=0的樣本也可以做出類似的分析镶奉。

至于這個(gè)損失函數(shù)是怎么推導(dǎo)出來(lái)的础淤，有兩個(gè)辦法崭放，一個(gè)是用LR，一個(gè)是用最大熵鸽凶。具體的推導(dǎo)過(guò)程請(qǐng)參閱其他資料币砂。

2、xgboost

既然xgboost就是一個(gè)監(jiān)督模型玻侥，那么我們的第一個(gè)問(wèn)題就是：xgboost對(duì)應(yīng)的模型是什么决摧？
答案就是一堆CART樹(shù)。
此時(shí)凑兰，可能我們又有疑問(wèn)了掌桩，CART樹(shù)是什么？這個(gè)問(wèn)題請(qǐng)查閱其他資料姑食，我的博客中也有相關(guān)文章涉及過(guò)波岛。然后，一堆樹(shù)如何做預(yù)測(cè)呢音半？答案非常簡(jiǎn)單则拷，就是將每棵樹(shù)的預(yù)測(cè)值加到一起作為最終的預(yù)測(cè)值，可謂簡(jiǎn)單粗暴祟剔。

下圖就是CART樹(shù)和一堆CART樹(shù)的示例隔躲，用來(lái)判斷一個(gè)人是否會(huì)喜歡計(jì)算機(jī)游戲：

predict1.PNG

predict2.PNG

第二圖的底部說(shuō)明了如何用一堆CART樹(shù)做預(yù)測(cè)，就是簡(jiǎn)單將各個(gè)樹(shù)的預(yù)測(cè)分?jǐn)?shù)相加物延。

xgboost為什么使用CART樹(shù)而不是用普通的決策樹(shù)呢宣旱？
簡(jiǎn)單講，對(duì)于分類問(wèn)題叛薯，由于CART樹(shù)的葉子節(jié)點(diǎn)對(duì)應(yīng)的值是一個(gè)實(shí)際的分?jǐn)?shù)浑吟，而非一個(gè)確定的類別，這將有利于實(shí)現(xiàn)高效的優(yōu)化算法耗溜。xgboost出名的原因一是準(zhǔn)组力，二是快，之所以快抖拴，其中就有選用CART樹(shù)的一份功勞燎字。

知道了xgboost的模型，我們需要用數(shù)學(xué)來(lái)準(zhǔn)確地表示這個(gè)模型阿宅，如下所示：

predict3.PNG

這里的K就是樹(shù)的棵數(shù)候衍，F(xiàn)表示所有可能的CART樹(shù)，f表示一棵具體的CART樹(shù)洒放。這個(gè)模型由K棵CART樹(shù)組成蛉鹿。模型表示出來(lái)后，我們自然而然就想問(wèn)往湿，這個(gè)模型的參數(shù)是什么妖异？因?yàn)槲覀冎劳锵罚爸R(shí)”蘊(yùn)含在參數(shù)之中。第二他膳，用來(lái)優(yōu)化這些參數(shù)的目標(biāo)函數(shù)又是什么响逢？

我們先來(lái)看第二個(gè)問(wèn)題，模型的目標(biāo)函數(shù)矩乐，如下所示：

predict4.PNG

這個(gè)目標(biāo)函數(shù)同樣包含兩部分龄句，第一部分就是損失函數(shù)，第二部分就是正則項(xiàng)散罕，這里的正則化項(xiàng)由K棵樹(shù)的正則化項(xiàng)相加而來(lái)分歇，你可能會(huì)好奇，一棵樹(shù)的正則化項(xiàng)是什么欧漱？可暫時(shí)保持住你的好奇心职抡，后面會(huì)有答案。現(xiàn)在看來(lái)误甚，它們都還比較抽象缚甩，不要著急，后面會(huì)逐一將它們具體化窑邦。

3擅威、訓(xùn)練xgboost

上面，我們獲取了xgboost模型和它的目標(biāo)函數(shù)冈钦，那么訓(xùn)練的任務(wù)就是通過(guò)最小化目標(biāo)函數(shù)來(lái)找到最佳的參數(shù)組郊丛。

問(wèn)題是參數(shù)在哪里？

我們很自然地想到瞧筛，xgboost模型由CART樹(shù)組成厉熟，參數(shù)自然存在于每棵CART樹(shù)之中。那么较幌，就單一的 CART樹(shù)而言揍瑟，它的參數(shù)是什么呢？
根據(jù)上面對(duì)CART樹(shù)的介紹乍炉，我們知道绢片，確定一棵CART樹(shù)需要確定兩部分，第一部分就是樹(shù)的結(jié)構(gòu)岛琼，這個(gè)結(jié)構(gòu)負(fù)責(zé)將一個(gè)樣本映射到一個(gè)確定的葉子節(jié)點(diǎn)上底循，其本質(zhì)上就是一個(gè)函數(shù)。第二部分就是各個(gè)葉子節(jié)點(diǎn)上的分?jǐn)?shù)衷恭。

似乎遇到麻煩了此叠，你要說(shuō)葉子節(jié)點(diǎn)的分?jǐn)?shù)作為參數(shù)纯续，還是沒(méi)問(wèn)題的随珠，但樹(shù)的結(jié)構(gòu)如何作為參數(shù)呢灭袁？而且我們還不是一棵樹(shù)，而是K棵樹(shù)!

讓我們想像一下窗看，如果K棵樹(shù)的結(jié)構(gòu)都已經(jīng)確定茸歧，那么整個(gè)模型剩下的就是所有K棵樹(shù)的葉子節(jié)點(diǎn)的值，模型的正則化項(xiàng)也可以設(shè)為各個(gè)葉子節(jié)點(diǎn)的值的平方和显沈。此時(shí)软瞎，整個(gè)目標(biāo)函數(shù)其實(shí)就是一個(gè)K棵樹(shù)的所有葉子節(jié)點(diǎn)的值的函數(shù)，我們就可以使用梯度下降或者隨機(jī)梯度下降來(lái)優(yōu)化目標(biāo)函數(shù)±叮現(xiàn)在這個(gè)辦法不靈了涤浇，必須另外尋找辦法。

4魔慷、加法訓(xùn)練

所謂加法訓(xùn)練只锭，本質(zhì)上是一個(gè)元算法，適用于所有的加法模型院尔，它是一種啟發(fā)式算法蜻展。關(guān)于這個(gè)算法，我的另一篇講GBDT的文章中有詳細(xì)的介紹邀摆，這里不再重復(fù)纵顾，不熟悉的朋友，可以看一下栋盹。運(yùn)用加法訓(xùn)練施逾，我們的目標(biāo)不再是直接優(yōu)化整個(gè)目標(biāo)函數(shù)，這已經(jīng)被我們證明是行不通的贞盯。而是分步驟優(yōu)化目標(biāo)函數(shù)音念，首先優(yōu)化第一棵樹(shù)，完了之后再優(yōu)化第二棵樹(shù)躏敢，直至優(yōu)化完K棵樹(shù)闷愤。整個(gè)過(guò)程如下圖所示：

predict6.PNG

在第t步時(shí)，我們添加了一棵最優(yōu)的CART樹(shù)f_t件余，這棵最優(yōu)的CART樹(shù)f_t是怎么得來(lái)的呢讥脐？非常簡(jiǎn)單，就是在現(xiàn)有的t-1棵樹(shù)的基礎(chǔ)上啼器，使得目標(biāo)函數(shù)最小的那棵CART樹(shù)旬渠，如下圖所示：

10.PNG

上圖中的constant就是前t-1棵樹(shù)的復(fù)雜度，再忍耐一會(huì)兒端壳，我們就會(huì)知道如何衡量樹(shù)的復(fù)雜度了告丢，暫時(shí)忽略它。

假如我們使用的損失函數(shù)是MSE损谦，那么上述表達(dá)式會(huì)變成這個(gè)樣子：

11.PNG

這個(gè)式子非常漂亮岖免，因?yàn)樗衒_t(x_i)的一次式和二次式岳颇，而且一次式項(xiàng)的系數(shù)是殘差。你可能好奇颅湘，為什么有一次式和二次式就漂亮话侧，因?yàn)樗鼤?huì)對(duì)我們后續(xù)的優(yōu)化提供很多方便，繼續(xù)前進(jìn)你就明白了闯参。
注意：f_t(x_i)是什么瞻鹏？它其實(shí)就是f_t的某個(gè)葉子節(jié)點(diǎn)的值。之前我們提到過(guò)鹿寨，葉子節(jié)點(diǎn)的值是可以作為模型的參數(shù)的新博。

但是對(duì)于其他的損失函數(shù)，我們未必能得出如此漂亮的式子脚草，所以叭披，對(duì)于一般的損失函數(shù)，我們需要將其作泰勒二階展開(kāi)玩讳，如下所示：

12.PNG

其中：

13.PNG

這里有必要再明確一下涩蜘，gi和hi的含義。gi怎么理解呢熏纯？現(xiàn)有t-1棵樹(shù)是不是同诫？這t-1棵樹(shù)組成的模型對(duì)第i個(gè)訓(xùn)練樣本有一個(gè)預(yù)測(cè)值y^i是不是？這個(gè)y^i與第i個(gè)樣本的真實(shí)標(biāo)簽yi肯定有差距是不是樟澜？這個(gè)差距可以用l(yi,y^i)這個(gè)損失函數(shù)來(lái)衡量是不是误窖？現(xiàn)在gi和hi的含義你已經(jīng)清楚了是不是？

如果你還是覺(jué)得抽象秩贰，我們來(lái)看一個(gè)具體的例子霹俺，假設(shè)我們正在優(yōu)化第11棵CART樹(shù)，也就是說(shuō)前10棵 CART樹(shù)已經(jīng)確定了毒费。這10棵樹(shù)對(duì)樣本(x_i,y_i=1)的預(yù)測(cè)值是y^i=-1丙唧，假設(shè)我們現(xiàn)在是做分類，我們的損失函數(shù)是

分類.PNG

在y_i=1時(shí)觅玻，損失函數(shù)變成了

image.png

我們可以求出這個(gè)損失函數(shù)對(duì)于y^i的梯度想际，如下所示：

image.png

將y^i =-1代入上面的式子，計(jì)算得到-0.27溪厘。這個(gè)-0.27就是g_i胡本。該值是負(fù)的，也就是說(shuō)畸悬，如果我們想要減小這10棵樹(shù)在該樣本點(diǎn)上的預(yù)測(cè)損失侧甫，我們應(yīng)該沿著梯度的反方向去走，也就是要增大y^i 的值,使其趨向于正，因?yàn)槲覀兊膟_i=1就是正的披粟。

來(lái)彩扔，答一個(gè)小問(wèn)題，在優(yōu)化第t棵樹(shù)時(shí)僻爽，有多少個(gè)gi和hi要計(jì)算？嗯贾惦，沒(méi)錯(cuò)就是各有N個(gè)胸梆，N是訓(xùn)練樣本的數(shù)量。如果有10萬(wàn)樣本须板，在優(yōu)化第t棵樹(shù)時(shí)碰镜，就需要計(jì)算出個(gè)10萬(wàn)個(gè)gi和hi蓬坡。感覺(jué)好像很麻煩是不是鞍泉？但是你再想一想，這10萬(wàn)個(gè)gi之間是不是沒(méi)有啥關(guān)系苏揣？是不是可以并行計(jì)算呢甜奄？聰明的你想必再一次感受到了柠横，為什么xgboost會(huì)辣么快！

好课兄，現(xiàn)在我們來(lái)審視下這個(gè)式子牍氛，哪些是常量，哪些是變量烟阐。式子最后有一個(gè)constant項(xiàng)搬俊，聰明如你，肯定猜到了蜒茄，它就是前t-1棵樹(shù)的正則化項(xiàng)唉擂。l(yi, yi^t-1)也是常數(shù)項(xiàng)。剩下的三個(gè)變量項(xiàng)分別是第t棵CART樹(shù)的一次式檀葛，二次式玩祟，和整棵樹(shù)的正則化項(xiàng)。再次提醒屿聋，這里所謂的樹(shù)的一次式卵凑，二次式，其實(shí)都是某個(gè)葉子節(jié)點(diǎn)的值的一次式胜臊，二次式勺卢。

我們的目標(biāo)是讓這個(gè)目標(biāo)函數(shù)最小化，常數(shù)項(xiàng)顯然沒(méi)有什么用象对，我們把它們?nèi)サ艉诔溃妥兂闪讼旅孢@樣：

14.PNG

好，現(xiàn)在我們可以回答之前的一個(gè)問(wèn)題了，為什么一次式和二次式顯得那么漂亮甫煞。因?yàn)檫@些一次式和二次式的系數(shù)是gi和hi菇曲，而gi和hi可以并行地求出來(lái)。而且抚吠，gi和hi是不依賴于損失函數(shù)的形式的常潮，只要這個(gè)損失函數(shù)二次可微就可以了。這有什么好處呢楷力？好處就是xgboost可以支持自定義損失函數(shù)喊式，只需滿足二次可微即可。強(qiáng)大了我的哥是不是萧朝？

5岔留、模型正則化項(xiàng)

上面的式子已然很漂亮，但是检柬，后面的Ω(ft)仍然是云遮霧罩献联，不清不楚。現(xiàn)在我們就來(lái)定義如何衡量一棵樹(shù)的正則化項(xiàng)何址。這個(gè)事兒并沒(méi)有一個(gè)客觀的標(biāo)準(zhǔn)里逆，可以見(jiàn)仁見(jiàn)智。為此用爪，我們先對(duì)CART樹(shù)作另一番定義运悲，如下所示：

16.PNG

需要解釋下這個(gè)定義，首先项钮，一棵樹(shù)有T個(gè)葉子節(jié)點(diǎn)班眯，這T個(gè)葉子節(jié)點(diǎn)的值組成了一個(gè)T維向量w，q(x)是一個(gè)映射烁巫，用來(lái)將樣本映射成1到T的某個(gè)值署隘，也就是把它分到某個(gè)葉子節(jié)點(diǎn)，q(x)其實(shí)就代表了CART樹(shù)的結(jié)構(gòu)亚隙。w_q(x)自然就是這棵樹(shù)對(duì)樣本x的預(yù)測(cè)值了磁餐。

有了這個(gè)定義，xgboost就使用了如下的正則化項(xiàng)：

17.PNG

注意：這里出現(xiàn)了γ和λ阿弃，這是xgboost自己定義的诊霹，在使用xgboost時(shí)，你可以設(shè)定它們的值渣淳，顯然脾还，γ越大，表示越希望獲得結(jié)構(gòu)簡(jiǎn)單的樹(shù)入愧，因?yàn)榇藭r(shí)對(duì)較多葉子節(jié)點(diǎn)的樹(shù)的懲罰越大鄙漏。λ越大也是越希望獲得結(jié)構(gòu)簡(jiǎn)單的樹(shù)嗤谚。

為什么xgboost要選擇這樣的正則化項(xiàng)？很簡(jiǎn)單怔蚌，好使巩步！效果好才是真的好。

6桦踊、見(jiàn)證奇跡的時(shí)刻

至此椅野，我們關(guān)于第t棵樹(shù)的優(yōu)化目標(biāo)已然很清晰，下面我們對(duì)它做如下變形籍胯，請(qǐng)睜大雙眼竟闪，集中精力：

18.PNG

這里需要停一停，認(rèn)真體會(huì)下芒炼。Ij代表什么？它代表一個(gè)集合术徊，集合中每個(gè)值代表一個(gè)訓(xùn)練樣本的序號(hào)本刽，整個(gè)集合就是被第t棵CART樹(shù)分到了第j個(gè)葉子節(jié)點(diǎn)上的訓(xùn)練樣本。理解了這一點(diǎn)赠涮，再看這步轉(zhuǎn)換子寓，其實(shí)就是內(nèi)外求和順序的改變。如果感覺(jué)還有困難笋除，歡迎評(píng)論留言斜友。

進(jìn)一步，我們可以做如下簡(jiǎn)化：

19.PNG

其中的Gj和Hj應(yīng)當(dāng)是不言自明了垃它。

對(duì)于第t棵CART樹(shù)的某一個(gè)確定的結(jié)構(gòu)（可用q(x)表示）鲜屏，所有的Gj和Hj都是確定的。而且上式中各個(gè)葉子節(jié)點(diǎn)的值wj之間是互相獨(dú)立的国拇。上式其實(shí)就是一個(gè)簡(jiǎn)單的二次式洛史，我們很容易求出各個(gè)葉子節(jié)點(diǎn)的最佳值以及此時(shí)目標(biāo)函數(shù)的值。如下所示：

20.PNG

obj*代表了什么呢酱吝？
它表示了這棵樹(shù)的結(jié)構(gòu)有多好也殖，值越小，代表這樣結(jié)構(gòu)越好务热！也就是說(shuō)忆嗜，它是衡量第t棵CART樹(shù)的結(jié)構(gòu)好壞的標(biāo)準(zhǔn)。注意~注意~注意~崎岂，這個(gè)值僅僅是用來(lái)衡量結(jié)構(gòu)的好壞的捆毫，與葉子節(jié)點(diǎn)的值可是無(wú)關(guān)的。為什么冲甘？請(qǐng)?jiān)僮屑?xì)看一下obj*的推導(dǎo)過(guò)程冻璃。obj*只和Gj和Hj和T有關(guān)响谓，而它們又只和樹(shù)的結(jié)構(gòu)(q(x))有關(guān)，與葉子節(jié)點(diǎn)的值可是半毛關(guān)系沒(méi)有省艳。如下圖所示：

23.PNG

Note：這里娘纷，我們對(duì)w*_j給出一個(gè)直覺(jué)的解釋，以便能獲得感性的認(rèn)識(shí)跋炕。我們假設(shè)分到j(luò)這個(gè)葉子節(jié)點(diǎn)上的樣本只有一個(gè)赖晶。那么，w*_j就變成如下這個(gè)樣子：

image.png

這個(gè)式子告訴我們辐烂，w*_j的最佳值就是負(fù)的梯度乘以一個(gè)權(quán)重系數(shù)遏插，該系數(shù)類似于隨機(jī)梯度下降中的學(xué)習(xí)率。觀察這個(gè)權(quán)重系數(shù)纠修，我們發(fā)現(xiàn)胳嘲，h_j越大，這個(gè)系數(shù)越小扣草，也就是學(xué)習(xí)率越小了牛。h_j越大代表什么意思呢？代表在該點(diǎn)附近梯度變化非常劇烈辰妙，可能只要一點(diǎn)點(diǎn)的改變鹰祸，梯度就從10000變到了1，所以密浑，此時(shí)蛙婴，我們?cè)谑褂梅聪蛱荻雀聲r(shí)步子就要小而又小，也就是權(quán)重系數(shù)要更小尔破。

7街图、找出最優(yōu)的樹(shù)結(jié)構(gòu)

好了，有了評(píng)判樹(shù)的結(jié)構(gòu)好壞的標(biāo)準(zhǔn)懒构，我們就可以先求最佳的樹(shù)結(jié)構(gòu)台夺，這個(gè)定出來(lái)后，最佳的葉子結(jié)點(diǎn)的值實(shí)際上在上面已經(jīng)求出來(lái)了痴脾。

問(wèn)題是：樹(shù)的結(jié)構(gòu)近乎無(wú)限多颤介，一個(gè)一個(gè)去測(cè)算它們的好壞程度，然后再取最好的顯然是不現(xiàn)實(shí)的赞赖。所以滚朵，我們?nèi)匀恍枰扇∫稽c(diǎn)策略，這就是逐步學(xué)習(xí)出最佳的樹(shù)結(jié)構(gòu)前域。這與我們將K棵樹(shù)的模型分解成一棵一棵樹(shù)來(lái)學(xué)習(xí)是一個(gè)道理辕近，只不過(guò)從一棵一棵樹(shù)變成了一層一層節(jié)點(diǎn)而已。如果此時(shí)你還是有點(diǎn)蒙匿垄，沒(méi)關(guān)系移宅，下面我們就來(lái)看一下具體的學(xué)習(xí)過(guò)程归粉。
我們以上文提到過(guò)的判斷一個(gè)人是否喜歡計(jì)算機(jī)游戲?yàn)槔印Ｗ詈?jiǎn)單的樹(shù)結(jié)構(gòu)就是一個(gè)節(jié)點(diǎn)的樹(shù)漏峰。我們可以算出這棵單節(jié)點(diǎn)的樹(shù)的好壞程度obj*糠悼。假設(shè)我們現(xiàn)在想按照年齡將這棵單節(jié)點(diǎn)樹(shù)進(jìn)行分叉，我們需要知道：
1浅乔、按照年齡分是否有效倔喂，也就是是否減少了obj的值
2、如果可分靖苇，那么以哪個(gè)年齡值來(lái)分席噩。

為了回答上面兩個(gè)問(wèn)題，我們可以將這一家五口人按照年齡做個(gè)排序贤壁。如下圖所示：

29.PNG

按照這個(gè)圖從左至右掃描悼枢，我們就可以找出所有的切分點(diǎn)。對(duì)每一個(gè)確定的切分點(diǎn)脾拆，我們衡量切分好壞的標(biāo)準(zhǔn)如下：

27.PNG

這個(gè)Gain實(shí)際上就是單節(jié)點(diǎn)的obj*減去切分后的兩個(gè)節(jié)點(diǎn)的樹(shù)obj*馒索，Gain如果是正的，并且值越大假丧，表示切分后obj*越小于單節(jié)點(diǎn)的obj*双揪，就越值得切分动羽。同時(shí)包帚，我們還可以觀察到，Gain的左半部分如果小于右側(cè)的γ运吓，則Gain就是負(fù)的渴邦，表明切分后obj反而變大了。γ在這里實(shí)際上是一個(gè)臨界值拘哨，它的值越大谋梭，表示我們對(duì)切分后obj下降幅度要求越嚴(yán)。這個(gè)值也是可以在xgboost中設(shè)定的倦青。

掃描結(jié)束后瓮床，我們就可以確定是否切分，如果切分产镐，對(duì)切分出來(lái)的兩個(gè)節(jié)點(diǎn)隘庄，遞歸地調(diào)用這個(gè)切分過(guò)程，我們就能獲得一個(gè)相對(duì)較好的樹(shù)結(jié)構(gòu)癣亚。

注意：xgboost的切分操作和普通的決策樹(shù)切分過(guò)程是不一樣的丑掺。普通的決策樹(shù)在切分的時(shí)候并不考慮樹(shù)的復(fù)雜度，而依賴后續(xù)的剪枝操作來(lái)控制述雾。xgboost在切分的時(shí)候就已經(jīng)考慮了樹(shù)的復(fù)雜度街州，就是那個(gè)γ參數(shù)兼丰。所以，它不需要進(jìn)行單獨(dú)的剪枝操作唆缴。

8鳍征、大功告成

最優(yōu)的樹(shù)結(jié)構(gòu)找到后，確定最優(yōu)的葉子節(jié)點(diǎn)就很容易了琐谤。我們成功地找出了第t棵樹(shù)蟆技！撒花！６芳伞质礼！