0 前言

xgboost一直在競(jìng)賽江湖里被傳為神器，比如時(shí)不時(shí)某個(gè)kaggle/天池比賽中，某人用xgboost于千軍萬馬中斬獲冠軍。

而我們的機(jī)器學(xué)習(xí)課程里也必講xgboost，如寒所說：“RF和GBDT是工業(yè)界大愛的模型，Xgboost 是大殺器包裹，Kaggle各種Top排行榜曾一度呈現(xiàn)Xgboost一統(tǒng)江湖的局面，另外某次滴滴比賽第一名的改進(jìn)也少不了Xgboost的功勞”。

此外，公司七月在線從2016年上半年起，就開始組織學(xué)員參加各種比賽，以在實(shí)際競(jìng)賽項(xiàng)目中成長(zhǎng)（畢竟，搞AI不可能沒實(shí)戰(zhàn)，而參加比賽歷經(jīng)數(shù)據(jù)處理、特征選擇、模型調(diào)優(yōu)、代碼調(diào)參，是一個(gè)極好的真刀真槍的實(shí)戰(zhàn)機(jī)會(huì)，對(duì)能力的提升和找/換工作的幫助都非常大）。

AI大潮之下，今年特別多從傳統(tǒng)IT轉(zhuǎn)行轉(zhuǎn)崗轉(zhuǎn)型AI的朋友，很多朋友都咨詢?nèi)绾无D(zhuǎn)行AI，我一般都會(huì)著重強(qiáng)調(diào)學(xué)習(xí)AI或找/換AI的四大金剛：課程 + 題庫 + OJ + kaggle/天池。包括集訓(xùn)營(yíng)的畢業(yè)考核更會(huì)融合kaggle或天池比賽。

考慮到kaggle/天池比賽對(duì)搞數(shù)學(xué)科學(xué)的重要性，特寫此文介紹xgboost，助力大家快速入門xgboost以及在比賽中獲得優(yōu)異成績(jī)。

最后，xgboost不是我July發(fā)明的，但我會(huì)確保本文對(duì)它的介紹是最通俗易懂的（且本文得到七月在線AI lab負(fù)責(zé)人陳博士審校）。另，感謝文末所列的全部參考文獻(xiàn)，有何問題，歡迎隨時(shí)留言評(píng)論，thanks。

1 決策樹

舉個(gè)例子，集訓(xùn)營(yíng)某一期有100多名學(xué)員，假定給你一個(gè)任務(wù)，要你統(tǒng)計(jì)男生女生各多少人，當(dāng)一個(gè)一個(gè)學(xué)員依次上臺(tái)站到你面前時(shí)，你會(huì)怎么區(qū)分誰是男誰是女呢？

很快，你考慮到男生的頭發(fā)一般很短，女生的頭發(fā)一般比較長(zhǎng)，所以你通過頭發(fā)的長(zhǎng)短將這個(gè)班的所有學(xué)員分為兩撥，長(zhǎng)發(fā)的為“女”，短發(fā)為“男”。

相當(dāng)于你依靠一個(gè)指標(biāo)“頭發(fā)長(zhǎng)短”將整個(gè)班的人進(jìn)行了劃分，于是形成了一個(gè)簡(jiǎn)單的決策樹，而劃分的依據(jù)是頭發(fā)長(zhǎng)短。 
這時(shí)，有的人可能有不同意見了：為什么要用“頭發(fā)長(zhǎng)短”劃分呀，我可不可以用“穿的鞋子是否是高跟鞋”，“有沒有喉結(jié)”等等這些來劃分呢，答案當(dāng)然是可以的。

但究竟根據(jù)哪個(gè)指標(biāo)劃分更好呢？很直接的判斷是哪個(gè)分類效果更好則優(yōu)先用哪個(gè)。所以，這時(shí)就需要一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)來量化分類效果了。 

怎么判斷“頭發(fā)長(zhǎng)短”或者“是否有喉結(jié)”是最好的劃分方式，效果怎么量化呢？直觀上來說，如果根據(jù)某個(gè)標(biāo)準(zhǔn)分類人群后，純度越高效果越好，比如說你分為兩群，“女”那一群都是女的，“男”那一群全是男的，那這個(gè)效果是最好的。但有時(shí)實(shí)際的分類情況不是那么理想，所以只能說越接近這種情況，我們則認(rèn)為效果越好。

量化分類效果的方式有很多，比如信息增益（ID3）、信息增益率（C4.5）、基尼系數(shù)（CART）等等。

信息增益的度量標(biāo)準(zhǔn)：熵

ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進(jìn)行分裂。

什么是信息增益呢？為了精確地定義信息增益，我們先定義信息論中廣泛使用的一個(gè)度量標(biāo)準(zhǔn)，稱為熵（entropy），它刻畫了任意樣例集的純度（purity）。給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為：

上述公式中，p+代表正樣例，比如在本文開頭第二個(gè)例子中p+則意味著去打羽毛球，而p-則代表反樣例，不去打球(在有關(guān)熵的所有計(jì)算中我們定義0log0為0)。

舉例來說，假設(shè)S是一個(gè)關(guān)于布爾概念的有14個(gè)樣例的集合，它包括9個(gè)正例和5個(gè)反例（我們采用記號(hào)[9+，5-]來概括這樣的數(shù)據(jù)樣例），那么S相對(duì)于這個(gè)布爾樣例的熵為：

Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。

So，根據(jù)上述這個(gè)公式，我們可以得到：

• 如果S的所有成員屬于同一類，則Entropy(S)=0；
• 如果S的正反樣例數(shù)量相等，則Entropy(S)=1；
• 如果S的正反樣例數(shù)量不等，則熵介于0，1之間

如下圖所示：

看到?jīng)]，通過Entropy的值，你就能評(píng)估當(dāng)前分類樹的分類效果好壞了。

更多細(xì)節(jié)如剪枝、過擬合、優(yōu)缺點(diǎn)、可以參考此文《決策樹學(xué)習(xí)》。

所以，現(xiàn)在決策樹的靈魂已經(jīng)有了，即依靠某種指標(biāo)進(jìn)行樹的分裂達(dá)到分類/回歸的目的，總是希望純度越高越好。

2.回歸樹與集成學(xué)習(xí)

如果用一句話定義xgboost，很簡(jiǎn)單：Xgboost就是由很多CART樹集成。但，什么是CART樹？

數(shù)據(jù)挖掘或機(jī)器學(xué)習(xí)中使用的決策樹有兩種主要類型：

1. 分類樹分析是指預(yù)測(cè)結(jié)果是數(shù)據(jù)所屬的類（比如某個(gè)電影去看還是不看）
2. 回歸樹分析是指預(yù)測(cè)結(jié)果可以被認(rèn)為是實(shí)數(shù)（例如房屋的價(jià)格，或患者在醫(yī)院中的逗留時(shí)間）

而術(shù)語分類回歸樹（CART，Classification And Regression Tree）分析是用于指代上述兩種樹的總稱，由Breiman等人首先提出。

2.1 回歸樹
事實(shí)上，分類與回歸是兩個(gè)很接近的問題，分類的目標(biāo)是根據(jù)已知樣本的某些特征，判斷一個(gè)新的樣本屬于哪種已知的樣本類，它的結(jié)果是離散值。而回歸的結(jié)果是連續(xù)的值。當(dāng)然，本質(zhì)是一樣的，都是特征（feature）到結(jié)果/標(biāo)簽（label）之間的映射。

理清了什么是分類和回歸之后，理解分類樹和回歸樹就不難了。

分類樹的樣本輸出（即響應(yīng)值）是類的形式，比如判斷這個(gè)救命藥是真的還是假的，周末去看電影《風(fēng)語咒》還是不去。而回歸樹的樣本輸出是數(shù)值的形式，比如給某人發(fā)放房屋貸款的數(shù)額就是具體的數(shù)值，可以是0到300萬元之間的任意值。

所以，對(duì)于回歸樹，你沒法再用分類樹那套信息增益、信息增益率、基尼系數(shù)來判定樹的節(jié)點(diǎn)分裂了，你需要采取新的方式評(píng)估效果，包括預(yù)測(cè)誤差（常用的有均方誤差、對(duì)數(shù)誤差等）。而且節(jié)點(diǎn)不再是類別，是數(shù)值（預(yù)測(cè)值），那么怎么確定呢？有的是節(jié)點(diǎn)內(nèi)樣本均值，有的是最優(yōu)化算出來的比如Xgboost。

CART回歸樹是假設(shè)樹為二叉樹，通過不斷將特征進(jìn)行分裂。比如當(dāng)前樹結(jié)點(diǎn)是基于第j個(gè)特征值進(jìn)行分裂的，設(shè)該特征值小于s的樣本劃分為左子樹，大于s的樣本劃分為右子樹。

而CART回歸樹實(shí)質(zhì)上就是在該特征維度對(duì)樣本空間進(jìn)行劃分，而這種空間劃分的優(yōu)化是一種NP難問題，因此，在決策樹模型中是使用啟發(fā)式方法解決。典型CART回歸樹產(chǎn)生的目標(biāo)函數(shù)為：

因此，當(dāng)我們?yōu)榱饲蠼庾顑?yōu)的切分特征j和最優(yōu)的切分點(diǎn)s，就轉(zhuǎn)化為求解這么一個(gè)目標(biāo)函數(shù)：

所以我們只要遍歷所有特征的的所有切分點(diǎn)，就能找到最優(yōu)的切分特征和切分點(diǎn)。最終得到一棵回歸樹。

2.2 boosting集成學(xué)習(xí)

所謂集成學(xué)習(xí)，是指構(gòu)建多個(gè)分類器（弱分類器）對(duì)數(shù)據(jù)集進(jìn)行預(yù)測(cè)，然后用某種策略將多個(gè)分類器預(yù)測(cè)的結(jié)果集成起來，作為最終預(yù)測(cè)結(jié)果。通俗比喻就是“三個(gè)臭皮匠賽過諸葛亮”，或一個(gè)公司董事會(huì)上的各董事投票決策，它要求每個(gè)弱分類器具備一定的“準(zhǔn)確性”，分類器之間具備“差異性”。

集成學(xué)習(xí)根據(jù)各個(gè)弱分類器之間有無依賴關(guān)系，分為Boosting和Bagging兩大流派：

1. Boosting流派，各分類器之間有依賴關(guān)系，必須串行，比如Adaboost、GBDT(Gradient Boosting Decision Tree)、Xgboost
2. Bagging流派，各分類器之間沒有依賴關(guān)系，可各自并行，比如隨機(jī)森林（Random Forest）

而著名的Adaboost作為boosting流派中最具代表性的一種方法，本博客曾詳細(xì)介紹它。

AdaBoost，是英文"Adaptive Boosting"（自適應(yīng)增強(qiáng)）的縮寫，由Yoav Freund和Robert Schapire在1995年提出。它的自適應(yīng)在于：前一個(gè)基本分類器分錯(cuò)的樣本會(huì)得到加強(qiáng)，加權(quán)后的全體樣本再次被用來訓(xùn)練下一個(gè)基本分類器。同時(shí)，在每一輪中加入一個(gè)新的弱分類器，直到達(dá)到某個(gè)預(yù)定的足夠小的錯(cuò)誤率或達(dá)到預(yù)先指定的最大迭代次數(shù)。

    具體說來，整個(gè)Adaboost 迭代算法就3步：

1. 初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。如果有N個(gè)樣本，則每一個(gè)訓(xùn)練樣本最開始時(shí)都被賦予相同的權(quán)值：1/N。
2. 訓(xùn)練弱分類器。具體訓(xùn)練過程中，如果某個(gè)樣本點(diǎn)已經(jīng)被準(zhǔn)確地分類，那么在構(gòu)造下一個(gè)訓(xùn)練集中，它的權(quán)值就被降低；相反，如果某個(gè)樣本點(diǎn)沒有被準(zhǔn)確地分類，那么它的權(quán)值就得到提高。然后，權(quán)值更新過的樣本集被用于訓(xùn)練下一個(gè)分類器，整個(gè)訓(xùn)練過程如此迭代地進(jìn)行下去。
3. 將各個(gè)訓(xùn)練得到的弱分類器組合成強(qiáng)分類器。各個(gè)弱分類器的訓(xùn)練過程結(jié)束后，加大分類誤差率小的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較大的決定作用，而降低分類誤差率大的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較小的決定作用。換言之，誤差率低的弱分類器在最終分類器中占的權(quán)重較大，否則較小。

而另一種boosting方法GBDT（Gradient Boost Decision Tree)，則與AdaBoost不同，GBDT每一次的計(jì)算是都為了減少上一次的殘差，進(jìn)而在殘差減少（負(fù)梯度）的方向上建立一個(gè)新的模型。

boosting集成學(xué)習(xí)由多個(gè)相關(guān)聯(lián)的決策樹聯(lián)合決策，什么叫相關(guān)聯(lián)？舉個(gè)例子

1. 有一個(gè)樣本[數(shù)據(jù)->標(biāo)簽]是：[(2，4，5)-> 4]
2. 第一棵決策樹用這個(gè)樣本訓(xùn)練的預(yù)測(cè)為3.3
3. 那么第二棵決策樹訓(xùn)練時(shí)的輸入，這個(gè)樣本就變成了：[(2，4，5)-> 0.7]
4. 也就是說，下一棵決策樹輸入樣本會(huì)與前面決策樹的訓(xùn)練和預(yù)測(cè)相關(guān)

很快你會(huì)意識(shí)到，Xgboost為何也是一個(gè)boosting的集成學(xué)習(xí)了。

而一個(gè)回歸樹形成的關(guān)鍵點(diǎn)在于：

• 分裂點(diǎn)依據(jù)什么來劃分（如前面說的均方誤差最小，loss）；
• 分類后的節(jié)點(diǎn)預(yù)測(cè)值是多少（如前面說，有一種是將葉子節(jié)點(diǎn)下各樣本實(shí)際值得均值作為葉子節(jié)點(diǎn)預(yù)測(cè)誤差，或者計(jì)算所得）

至于另一類集成學(xué)習(xí)方法，比如Random Forest（隨機(jī)森林）算法，各個(gè)決策樹是獨(dú)立的、每個(gè)決策樹在樣本堆里隨機(jī)選一批樣本，隨機(jī)選一批特征進(jìn)行獨(dú)立訓(xùn)練，各個(gè)決策樹之間沒有啥關(guān)系。本文暫不展開介紹。

3.GBDT

說到Xgboost，不得不先從GBDT(Gradient Boosting Decision Tree)說起。因?yàn)閤gboost本質(zhì)上還是一個(gè)GBDT，但是力爭(zhēng)把速度和效率發(fā)揮到極致，所以叫X (Extreme) GBoosted。包括前面說過，兩者都是boosting方法。

GBDT的原理很簡(jiǎn)單，就是所有弱分類器的結(jié)果相加等于預(yù)測(cè)值，然后下一個(gè)弱分類器去擬合誤差函數(shù)對(duì)預(yù)測(cè)值的梯度/殘差(這個(gè)梯度/殘差就是預(yù)測(cè)值與真實(shí)值之間的誤差)。當(dāng)然了，它里面的弱分類器的表現(xiàn)形式就是各棵樹。如圖所示：Y = Y1 + Y2 + Y3。

舉一個(gè)非常簡(jiǎn)單的例子，比如我今年30歲了，但計(jì)算機(jī)或者模型GBDT并不知道我今年多少歲，那GBDT咋辦呢？

1. 它會(huì)在第一個(gè)弱分類器（或第一棵樹中）隨便用一個(gè)年齡比如20歲來擬合，然后發(fā)現(xiàn)誤差有10歲；
2. 接下來在第二棵樹中，用6歲去擬合剩下的損失，發(fā)現(xiàn)差距還有4歲；
3. 接著在第三棵樹中用3歲擬合剩下的差距，發(fā)現(xiàn)差距只有1歲了；
4. 最后在第四課樹中用1歲擬合剩下的殘差，完美。

最終，四棵樹的結(jié)論加起來，就是真實(shí)年齡30歲（實(shí)際工程中，用梯度近似殘差）。

在這里得啰嗦一下，上面預(yù)測(cè)年齡的第一個(gè)步驟中的“隨便”二字看似隨便，其實(shí)深入思考一下一點(diǎn)都不隨便，你會(huì)發(fā)現(xiàn)大部分做預(yù)測(cè)的模型，基本都是這么個(gè)常規(guī)套路，先隨便用一個(gè)值去預(yù)測(cè)，然后對(duì)比預(yù)測(cè)值與真實(shí)值的差距，最后不斷調(diào)整 縮小差距。所以會(huì)出來一系列目標(biāo)函數(shù)：確定目標(biāo)，和損失函數(shù)：縮小誤差。

再進(jìn)一步思考，你會(huì)發(fā)現(xiàn)這完全符合人類做預(yù)測(cè)的普遍常識(shí)、普遍做法，當(dāng)對(duì)一個(gè)事物不太了解時(shí)，一開始也是根據(jù)經(jīng)驗(yàn)嘗試、初探，直到逼近某種意義上的接近或者完全吻合。

還是年齡預(yù)測(cè)的例子。

簡(jiǎn)單起見，假定訓(xùn)練集只有4個(gè)人：A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學(xué)生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。

所以，現(xiàn)在的問題就是我們要預(yù)測(cè)這4個(gè)人的年齡，咋下手？很簡(jiǎn)單，先隨便用一個(gè)年齡比如20歲去擬合他們，然后根據(jù)實(shí)際情況不斷調(diào)整。

如果是用一棵傳統(tǒng)的回歸決策樹來訓(xùn)練，會(huì)得到如下圖所示結(jié)果：

現(xiàn)在我們使用GBDT來做這件事，由于數(shù)據(jù)太少，我們限定葉子節(jié)點(diǎn)做多有兩個(gè)，即每棵樹都只有一個(gè)分枝，并且限定只學(xué)兩棵樹。

我們會(huì)得到如下圖所示結(jié)果：

在第一棵樹分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為左右兩撥，每撥用平均年齡作為預(yù)測(cè)值。

• 此時(shí)計(jì)算殘差（殘差的意思就是：A的實(shí)際值 - A的預(yù)測(cè)值 = A的殘差），所以A的殘差就是實(shí)際值14 - 預(yù)測(cè)值15 = 殘差值-1。
• 注意，A的預(yù)測(cè)值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預(yù)測(cè)值。

殘差在數(shù)理統(tǒng)計(jì)中是指實(shí)際觀察值與估計(jì)值（擬合值）之間的差?！皻埐睢碧N(yùn)含了有關(guān)模型基本假設(shè)的重要信息。如果回歸模型正確的話， 我們可以將殘差看作誤差的觀測(cè)值。

進(jìn)而得到A,B,C,D的殘差分別為-1,1，-1,1。

然后拿它們的殘差-1、1、-1、1代替A B C D的原值，到第二棵樹去學(xué)習(xí)，第二棵樹只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)，即A和C分在左邊，B和D分在右邊，經(jīng)過計(jì)算（比如A，實(shí)際值-1 - 預(yù)測(cè)值-1 = 殘差0，比如C，實(shí)際值-1 - 預(yù)測(cè)值-1 = 0），此時(shí)所有人的殘差都是0。

殘差值都為0，相當(dāng)于第二棵樹的預(yù)測(cè)值和它們的實(shí)際值相等，則只需把第二棵樹的結(jié)論累加到第一棵樹上就能得到真實(shí)年齡了，即每個(gè)人都得到了真實(shí)的預(yù)測(cè)值。

換句話說，現(xiàn)在A,B,C,D的預(yù)測(cè)值都和真實(shí)年齡一致了。Perfect！
A: 14歲高一學(xué)生，購物較少，經(jīng)常問學(xué)長(zhǎng)問題，預(yù)測(cè)年齡A = 15 – 1 = 14
B: 16歲高三學(xué)生，購物較少，經(jīng)常被學(xué)弟問問題，預(yù)測(cè)年齡B = 15 + 1 = 16

C: 24歲應(yīng)屆畢業(yè)生，購物較多，經(jīng)常問師兄問題，預(yù)測(cè)年齡C = 25 – 1 = 24
D: 26歲工作兩年員工，購物較多，經(jīng)常被師弟問問題，預(yù)測(cè)年齡D = 25 + 1 = 26

所以，GBDT需要將多棵樹的得分累加得到最終的預(yù)測(cè)得分，且每一次迭代，都在現(xiàn)有樹的基礎(chǔ)上，增加一棵樹去擬合前面樹的預(yù)測(cè)結(jié)果與真實(shí)值之間的殘差。

4.Xgboost

4.1 xgboost樹的定義

本節(jié)的示意圖基本引用自xgboost原作者陳天奇的講義PPT中。

舉個(gè)例子，我們要預(yù)測(cè)一家人對(duì)電子游戲的喜好程度，考慮到年輕和年老相比，年輕更可能喜歡電子游戲，以及男性和女性相比，男性更喜歡電子游戲，故先根據(jù)年齡大小區(qū)分小孩和大人，然后再通過性別區(qū)分開是男是女，逐一給各人在電子游戲喜好程度上打分，如下圖所示。

就這樣，訓(xùn)練出了2棵樹tree1和tree2，類似之前gbdt的原理，兩棵樹的結(jié)論累加起來便是最終的結(jié)論，所以小孩的預(yù)測(cè)分?jǐn)?shù)就是兩棵樹中小孩所落到的結(jié)點(diǎn)的分?jǐn)?shù)相加：2 + 0.9 = 2.9。爺爺?shù)念A(yù)測(cè)分?jǐn)?shù)同理：-1 + （-0.9）= -1.9。具體如下圖所示

恩，你可能要拍案而起了，驚呼，這不是跟上文介紹的gbdt乃異曲同工么？

事實(shí)上，如果不考慮工程實(shí)現(xiàn)、解決問題上的一些差異，xgboost與gbdt比較大的不同就是目標(biāo)函數(shù)的定義。xgboost的目標(biāo)函數(shù)如下圖所示：

其中

• 紅色箭頭所指向的L 即為損失函數(shù)（比如平方損失函數(shù)：，或logistic損失函數(shù)：）
• 紅色方框所框起來的是正則項(xiàng)（包括L1正則、L2正則）
• 紅色圓圈所圈起來的為常數(shù)項(xiàng)
• 對(duì)于，xgboost利用泰勒展開三項(xiàng)，做一個(gè)近似

我們可以很清晰地看到，最終的目標(biāo)函數(shù)只依賴于每個(gè)數(shù)據(jù)點(diǎn)在誤差函數(shù)上的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)。

額，峰回路轉(zhuǎn)，突然丟這么大一個(gè)公式，不少人可能瞬間就懵了。沒事，下面咱們來拆解下這個(gè)目標(biāo)函數(shù)，并一一剖析每個(gè)公式、每個(gè)符號(hào)、每個(gè)下標(biāo)的含義。

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

xgboost的核心算法思想不難，基本就是

1. 不斷地添加樹，不斷地進(jìn)行特征分裂來生長(zhǎng)一棵樹，每次添加一個(gè)樹，其實(shí)是學(xué)習(xí)一個(gè)新函數(shù)，去擬合上次預(yù)測(cè)的殘差。

   

   注：w_q(x)為葉子節(jié)點(diǎn)q的分?jǐn)?shù)，對(duì)應(yīng)了所有K棵回歸樹（regression tree）的集合，而f(x)為其中一棵回歸樹。

2. 當(dāng)我們訓(xùn)練完成得到k棵樹，我們要預(yù)測(cè)一個(gè)樣本的分?jǐn)?shù)，其實(shí)就是根據(jù)這個(gè)樣本的特征，在每棵樹中會(huì)落到對(duì)應(yīng)的一個(gè)葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)就對(duì)應(yīng)一個(gè)分?jǐn)?shù)
3. 最后只需要將每棵樹對(duì)應(yīng)的分?jǐn)?shù)加起來就是該樣本的預(yù)測(cè)值。

顯然，我們的目標(biāo)是要使得樹群的預(yù)測(cè)值盡量接近真實(shí)值，而且有盡量大的泛化能力。

所以，從數(shù)學(xué)角度看這是一個(gè)泛函最優(yōu)化問題，故把目標(biāo)函數(shù)簡(jiǎn)化如下：

如你所見，這個(gè)目標(biāo)函數(shù)分為兩部分：損失函數(shù)和正則化項(xiàng)。且損失函數(shù)揭示訓(xùn)練誤差（即預(yù)測(cè)分?jǐn)?shù)和真實(shí)分?jǐn)?shù)的差距），正則化定義復(fù)雜度。

對(duì)于上式而言，是整個(gè)累加模型的輸出，正則化項(xiàng)∑kΩ()是則表示樹的復(fù)雜度的函數(shù)，值越小復(fù)雜度越低，泛化能力越強(qiáng)，其表達(dá)式為

T表示葉子節(jié)點(diǎn)的個(gè)數(shù)，w表示葉子節(jié)點(diǎn)的分?jǐn)?shù)。直觀上看，目標(biāo)要求預(yù)測(cè)誤差盡量小，且葉子節(jié)點(diǎn)T盡量少（γ控制葉子結(jié)點(diǎn)的個(gè)數(shù)），節(jié)點(diǎn)數(shù)值w盡量不極端（λ控制葉子節(jié)點(diǎn)的分?jǐn)?shù)不會(huì)過大），防止過擬合。

插一句，一般的目標(biāo)函數(shù)都包含下面兩項(xiàng)

其中，誤差/損失函數(shù)鼓勵(lì)我們的模型盡量去擬合訓(xùn)練數(shù)據(jù)，使得最后的模型會(huì)有比較少的 bias。而正則化項(xiàng)則鼓勵(lì)更加簡(jiǎn)單的模型。因?yàn)楫?dāng)模型簡(jiǎn)單之后，有限數(shù)據(jù)擬合出來結(jié)果的隨機(jī)性比較小，不容易過擬合，使得最后模型的預(yù)測(cè)更加穩(wěn)定。

4.2.1 模型學(xué)習(xí)與訓(xùn)練誤差

具體來說，目標(biāo)函數(shù)第一部分中的  表示第個(gè)樣本， ( ? ) 表示第  個(gè)樣本的預(yù)測(cè)誤差，我們的目標(biāo)當(dāng)然是誤差越小越好。

類似之前GBDT的套路，xgboost也是需要將多棵樹的得分累加得到最終的預(yù)測(cè)得分（每一次迭代，都在現(xiàn)有樹的基礎(chǔ)上，增加一棵樹去擬合前面樹的預(yù)測(cè)結(jié)果與真實(shí)值之間的殘差）。

但，我們?nèi)绾芜x擇每一輪加入什么呢？答案是非常直接的，選取一個(gè) 來使得我們的目標(biāo)函數(shù)盡量最大地降低。

再強(qiáng)調(diào)一下，考慮到第t輪的模型預(yù)測(cè)值  =  前t-1輪的模型預(yù)測(cè)  +  ，因此誤差函數(shù)記為： ( ,  +  )，后面一項(xiàng)為正則化項(xiàng)。

對(duì)于這個(gè)誤差函數(shù)的式子而言，在第t步，是真實(shí)值，即已知，可由上一步第t-1步中的yi^(t-2)加上計(jì)算所得，某種意義上也算已知值，故模型學(xué)習(xí)的是。

上面那個(gè)Obj的公式表達(dá)的可能有些過于抽象，我們可以考慮當(dāng) 是平方誤差的情況（相當(dāng)于），這個(gè)時(shí)候我們的目標(biāo)可以被寫成下面這樣的二次函數(shù)（圖中畫圈的部分表示的就是預(yù)測(cè)值和真實(shí)值之間的殘差）：

更加一般的，損失函數(shù)不是二次函數(shù)咋辦？利用泰勒展開，不是二次的想辦法近似為二次（如你所見，定義了一階導(dǎo)和二階導(dǎo)）。

恩恩，注意了！不少人可能就會(huì)在這里卡殼，網(wǎng)上也很少有文章解釋清楚，在和七月在線AI lab陳博士討論之后，發(fā)現(xiàn)這里面最關(guān)鍵的其實(shí)就是把泰勒二階展開各項(xiàng)和xgboost 目標(biāo)函數(shù)的對(duì)應(yīng)關(guān)系搞清楚，相當(dāng)于我們可以利用泰勒二階展開去做目標(biāo)函數(shù)的近似。

首先，這是泰勒二階展開

對(duì)應(yīng)到xgboost的目標(biāo)函數(shù)里頭

忽略損失函數(shù) 中的（別忘了上面說的“ 在第t步，是真實(shí)值，即已知 ”）：

就是x，就是，從而對(duì)f 求導(dǎo)數(shù)時(shí)，即對(duì)求偏導(dǎo)，得到：

其中，，

嗚呼，透了！不過，這個(gè)轉(zhuǎn)化過程中的關(guān)鍵泰勒二次展開到底是哪來的呢？

在數(shù)學(xué)中，泰勒公式（英語：Taylor's Formula）是一個(gè)用函數(shù)在某點(diǎn)的信息描述其附近取值的公式。這個(gè)公式來自于微積分的泰勒定理（Taylor's theorem），泰勒定理描述了一個(gè)可微函數(shù)，如果函數(shù)足夠光滑的話，在已知函數(shù)在某一點(diǎn)的各階導(dǎo)數(shù)值的情況之下，泰勒公式可以用這些導(dǎo)數(shù)值做系數(shù)構(gòu)建一個(gè)多項(xiàng)式來近似函數(shù)在這一點(diǎn)的鄰域中的值，這個(gè)多項(xiàng)式稱為泰勒多項(xiàng)式（Taylor polynomial）。

相當(dāng)于告訴我們可由利用泰勒多項(xiàng)式的某些次項(xiàng)做原函數(shù)的近似。

泰勒定理：
設(shè) n 是一個(gè)正整數(shù)。如果定義在一個(gè)包含 a 的區(qū)間上的函數(shù) f 在 a 點(diǎn)處 n+1 次可導(dǎo)，那么對(duì)于這個(gè)區(qū)間上的任意 x，都有：

其中的多項(xiàng)式稱為函數(shù)在a 處的泰勒展開式，剩余的是泰勒公式的余項(xiàng)，是的高階無窮小。

接下來，考慮到我們的第t 顆回歸樹是根據(jù)前面的t-1顆回歸樹的殘差得來的，相當(dāng)于t-1顆樹的值是已知的。換句話說，對(duì)目標(biāo)函數(shù)的優(yōu)化不影響，可以直接去掉，且常數(shù)項(xiàng)也可以移除，從而得到如下一個(gè)比較統(tǒng)一的目標(biāo)函數(shù)。

這時(shí)，目標(biāo)函數(shù)只依賴于每個(gè)數(shù)據(jù)點(diǎn)的在誤差函數(shù)上的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)（相信你已經(jīng)看出xgboost和gbdt的不同了，目標(biāo)函數(shù)保留了泰勒展開的二次項(xiàng)）。

總的指導(dǎo)原則如就職Google的讀者crab6789所說：

實(shí)質(zhì)是把樣本分配到葉子結(jié)點(diǎn)會(huì)對(duì)應(yīng)一個(gè)obj，優(yōu)化過程就是obj優(yōu)化。也就是分裂節(jié)點(diǎn)到葉子不同的組合，不同的組合對(duì)應(yīng)不同obj，所有的優(yōu)化圍繞這個(gè)思想展開。

到目前為止我們討論了目標(biāo)函數(shù)中的第一個(gè)部分：訓(xùn)練誤差。接下來我們討論目標(biāo)函數(shù)的第二個(gè)部分：正則項(xiàng)，即如何定義樹的復(fù)雜度。

4.2.2 正則項(xiàng)：樹的復(fù)雜度

首先，梳理下幾個(gè)規(guī)則

• 用葉子節(jié)點(diǎn)集合以及葉子節(jié)點(diǎn)得分表示 
• 每個(gè)樣本都落在一個(gè)葉子節(jié)點(diǎn)上 
• q(x)表示樣本x在某個(gè)葉子節(jié)點(diǎn)上，wq(x)是該節(jié)點(diǎn)的打分，即該樣本的模型預(yù)測(cè)值

所以當(dāng)我們把樹成結(jié)構(gòu)部分q和葉子權(quán)重部分w后，結(jié)構(gòu)函數(shù)q把輸入映射到葉子的索引號(hào)上面去，而w給定了每個(gè)索引號(hào)對(duì)應(yīng)的葉子分?jǐn)?shù)是什么。

另外，如下圖所示，xgboost對(duì)樹的復(fù)雜度包含了兩個(gè)部分：

1. 一個(gè)是樹里面葉子節(jié)點(diǎn)的個(gè)數(shù)T
2. 一個(gè)是樹上葉子節(jié)點(diǎn)的得分w的L2模平方（對(duì)w進(jìn)行L2正則化，相當(dāng)于針對(duì)每個(gè)葉結(jié)點(diǎn)的得分增加L2平滑，目的是為了避免過擬合）

在這種新的定義下，我們可以把之前的目標(biāo)函數(shù)進(jìn)行如下變形（另，別忘了：）

其中被定義為每個(gè)葉節(jié)點(diǎn) j 上面樣本下標(biāo)的集合 ，g是一階導(dǎo)數(shù)，h是二階導(dǎo)數(shù)。這一步是由于xgboost目標(biāo)函數(shù)第二部分加了兩個(gè)正則項(xiàng)，一個(gè)是葉子節(jié)點(diǎn)個(gè)數(shù)(T),一個(gè)是葉子節(jié)點(diǎn)的分?jǐn)?shù)(w)。

從而，加了正則項(xiàng)的目標(biāo)函數(shù)里就出現(xiàn)了兩種累加

• 一種是 - > n（樣本數(shù)）
• 一種是 -> T（葉子節(jié)點(diǎn)數(shù)）

這一個(gè)目標(biāo)包含了T個(gè)相互獨(dú)立的單變量二次函數(shù)。

理解這個(gè)推導(dǎo)的關(guān)鍵在哪呢？在和AI lab陳博士討論之后，其實(shí)就在于理解這個(gè)定義：被定義為每個(gè)葉節(jié)點(diǎn) j 上面樣本下標(biāo)的集合 ，這個(gè)定義里的q(xi)要表達(dá)的是：每個(gè)樣本值xi 都能通過函數(shù)q(xi)映射到樹上的某個(gè)葉子節(jié)點(diǎn)，從而通過這個(gè)定義把兩種累加統(tǒng)一到了一起。

接著，我們可以定義

最終公式可以化簡(jiǎn)為

通過對(duì)求導(dǎo)等于0，可以得到

然后把最優(yōu)解代入得到：

4.3 打分函數(shù)計(jì)算

Obj代表了當(dāng)我們指定一個(gè)樹的結(jié)構(gòu)的時(shí)候，我們?cè)谀繕?biāo)上面最多減少多少。我們可以把它叫做結(jié)構(gòu)分?jǐn)?shù)(structure score)

4.3.1 分裂節(jié)點(diǎn)

很有意思的一個(gè)事是，我們從頭到尾了解了xgboost如何優(yōu)化、如何計(jì)算，但樹到底長(zhǎng)啥樣，我們卻一直沒看到。很顯然，一棵樹的生成是由一個(gè)節(jié)點(diǎn)一分為二，然后不斷分裂最終形成為整棵樹。那么樹怎么分裂的就成為了接下來我們要探討的關(guān)鍵。

對(duì)于一個(gè)葉子節(jié)點(diǎn)如何進(jìn)行分裂，xgboost作者在其原始論文中給出了兩種分裂節(jié)點(diǎn)的方法

（1）枚舉所有不同樹結(jié)構(gòu)的貪心法

現(xiàn)在的情況是只要知道樹的結(jié)構(gòu)，就能得到一個(gè)該結(jié)構(gòu)下的最好分?jǐn)?shù)，那如何確定樹的結(jié)構(gòu)呢？

一個(gè)想當(dāng)然的方法是：不斷地枚舉不同樹的結(jié)構(gòu)，然后利用打分函數(shù)來尋找出一個(gè)最優(yōu)結(jié)構(gòu)的樹，接著加入到模型中，不斷重復(fù)這樣的操作。而再一想，你會(huì)意識(shí)到要枚舉的狀態(tài)太多了，基本屬于無窮種，那咋辦呢？

我們?cè)囅仑澬姆ǎ瑥臉渖疃?開始，每一節(jié)點(diǎn)都遍歷所有的特征，比如年齡、性別等等，然后對(duì)于某個(gè)特征，先按照該特征里的值進(jìn)行排序，然后線性掃描該特征進(jìn)而確定最好的分割點(diǎn)，最后對(duì)所有特征進(jìn)行分割后，我們選擇所謂的增益Gain最高的那個(gè)特征，而Gain如何計(jì)算呢？

還記得4.2節(jié)最后，我們得到的計(jì)算式子吧？

換句話說，目標(biāo)函數(shù)中的G/(H+λ)部分，表示著每一個(gè)葉子節(jié)點(diǎn)對(duì)當(dāng)前模型損失的貢獻(xiàn)程度，融合一下，得到Gain的計(jì)算表達(dá)式，如下所示：

第一個(gè)值得注意的事情是“對(duì)于某個(gè)特征，先按照該特征里的值進(jìn)行排序”，這里舉個(gè)例子。

比如設(shè)置一個(gè)值a，然后枚舉所有x < a、a  < x這樣的條件（x代表某個(gè)特征比如年齡age，把a(bǔ)ge從小到大排序：假定從左至右依次增大，則比a小的放在左邊，比a大的放在右邊），對(duì)于某個(gè)特定的分割a，我們要計(jì)算a左邊和右邊的導(dǎo)數(shù)和。

比如總共五個(gè)人，按年齡排好序后，一開始我們總共有如下4種劃分方法：

1. 把第一個(gè)人和后面四個(gè)人劃分開
2. 把前兩個(gè)人和后面三個(gè)人劃分開
3. 把前三個(gè)人和后面兩個(gè)人劃分開
4. 把前面四個(gè)人和后面一個(gè)人劃分開

接下來，把上面4種劃分方法全都各自計(jì)算一下Gain，看哪種劃分方法得到的Gain值最大則選取哪種劃分方法，經(jīng)過計(jì)算，發(fā)現(xiàn)把第2種劃分方法“前面兩個(gè)人和后面三個(gè)人劃分開”得到的Gain值最大，意味著在一分為二這個(gè)第一層層面上這種劃分方法是最合適的。

換句話說，對(duì)于所有的特征x，我們只要做一遍從左到右的掃描就可以枚舉出所有分割的梯度和GL和GR。然后用計(jì)算Gain的公式計(jì)算每個(gè)分割方案的分?jǐn)?shù)就可以了。

然后后續(xù)則依然按照這種劃分方法繼續(xù)第二層、第三層、第四層、第N層的分裂。

第二個(gè)值得注意的事情就是引入分割不一定會(huì)使得情況變好，所以我們有一個(gè)引入新葉子的懲罰項(xiàng)。優(yōu)化這個(gè)目標(biāo)對(duì)應(yīng)了樹的剪枝， 當(dāng)引入的分割帶來的增益小于一個(gè)閥值γ 的時(shí)候，則忽略這個(gè)分割。相當(dāng)于在我們發(fā)現(xiàn)“分”還不如“不分”的情況下后（得到的增益太小，小到小于閾值γ），會(huì)有2個(gè)葉子節(jié)點(diǎn)存在同一棵子樹上的情況。

下面是論文中的算法

（2）近似算法

主要針對(duì)數(shù)據(jù)太大，不能直接進(jìn)行計(jì)算

就職于Google的讀者crab6789點(diǎn)評(píng)：

把樣本從根分配到葉子結(jié)點(diǎn)，就是個(gè)排列組合。不同的組合對(duì)應(yīng)的cost不同。求最好的組合你就要try，一味窮舉是不可能的，所以才出來貪婪法。不看從頭到尾 就看當(dāng)下節(jié)點(diǎn)怎么分配最好。這才有了那個(gè)exact greddy方法，后來還想加速才有了histogram的做法。

4.4 小結(jié)：Boosted Tree Algorithm 

總結(jié)一下，如圖所示

咱們來再次回顧整個(gè)過程。

如果某個(gè)樣本label數(shù)值為4，那么第一個(gè)回歸樹預(yù)測(cè)3，第二個(gè)預(yù)測(cè)為1； 另外一組回歸樹，一個(gè)預(yù)測(cè)2，一個(gè)預(yù)測(cè)2，那么傾向后一種，為什么呢？前一種情況，第一棵樹學(xué)的太多，太接近4，也就意味著有較大的過擬合的風(fēng)險(xiǎn)。

OK，聽起來很美好，可是怎么實(shí)現(xiàn)呢，上面這個(gè)目標(biāo)函數(shù)跟實(shí)際的參數(shù)怎么聯(lián)系起來，記得我們說過，回歸樹的參數(shù)：

1. 選取哪個(gè)feature分裂節(jié)點(diǎn)呢
2. 節(jié)點(diǎn)的預(yù)測(cè)值（總不能靠取平均值這么粗暴不講道理的方式吧，好歹高級(jí)一點(diǎn)）

最終的策略就是：貪心 + 最優(yōu)化（對(duì)的，二次最優(yōu)化） 。

通俗解釋貪心策略：就是決策時(shí)刻按照當(dāng)前目標(biāo)最優(yōu)化決定，說白了就是眼前利益最大化決定，“目光短淺”策略。

這里是怎么用貪心策略的呢，剛開始你有一群樣本，放在第一個(gè)節(jié)點(diǎn)，這時(shí)候T=1，w多少呢，不知道，是求出來的，這時(shí)候所有樣本的預(yù)測(cè)值都是w,帶入樣本的label數(shù)值，此時(shí)loss function變?yōu)?/p>

• 如果這里的l(w?yi)誤差表示用的是平方誤差，那么上述函數(shù)就是一個(gè)關(guān)于w的二次函數(shù)求最小值，取最小值的點(diǎn)就是這個(gè)節(jié)點(diǎn)的預(yù)測(cè)值，最小的函數(shù)值為最小損失函數(shù)。
• 本質(zhì)上來講，這就是一個(gè)二次函數(shù)最優(yōu)化問題！但要是損失函數(shù)不是二次函數(shù)咋辦？泰勒展開，不是二次的想辦法近似為二次。

接著來，接下來要選個(gè)feature分裂成兩個(gè)節(jié)點(diǎn)，變成一棵弱小的樹苗，那么需要：

1. 確定分裂用的feature，how？最簡(jiǎn)單的是粗暴的枚舉/窮舉（嗯，夠粗暴），然后選擇loss function效果最好的那個(gè)；
2. 如何確立節(jié)點(diǎn)的w以及最小的loss function，大聲告訴我怎么做？對(duì)，二次函數(shù)的求最值（計(jì)算二次的最值一般都有固定套路，即導(dǎo)數(shù)等于0的點(diǎn)） 。所以，選擇一個(gè)feature分裂，計(jì)算loss function最小值，然后再選一個(gè)feature分裂，又得到一個(gè)loss function最小值，你枚舉完，找一個(gè)效果最好的，把樹給分裂，就得到了小樹苗。

在分裂的時(shí)候，你可以注意到，每次節(jié)點(diǎn)分裂，loss function被影響的只有這個(gè)節(jié)點(diǎn)的樣本，因而每次分裂，計(jì)算分裂的增益（loss function的降低量）只需要關(guān)注打算分裂的那個(gè)節(jié)點(diǎn)的樣本。

總而言之，XGBoost使用了和CART回歸樹一樣的想法，利用貪婪算法，遍歷所有特征的所有特征劃分點(diǎn)，不同的是使用的目標(biāo)函數(shù)不一樣。具體做法就是分裂后的目標(biāo)函數(shù)值比單子葉子節(jié)點(diǎn)的目標(biāo)函數(shù)的增益，同時(shí)為了限制樹生長(zhǎng)過深，還加了個(gè)閾值，只有當(dāng)增益大于該閾值才進(jìn)行分裂。

以下便為設(shè)定的閾值

從而繼續(xù)分裂，形成一棵樹，再形成一棵樹，每次在上一次的預(yù)測(cè)基礎(chǔ)上取最優(yōu)進(jìn)一步分裂/建樹，是不是貪心策略？

凡是這種循環(huán)迭代的方式必定有停止條件，什么時(shí)候停止呢？簡(jiǎn)言之，設(shè)置樹的最大深度、當(dāng)樣本權(quán)重和小于設(shè)定閾值時(shí)停止生長(zhǎng)以防止過擬合。具體而言，則

1. 當(dāng)引入的分裂帶來的增益小于設(shè)定閥值的時(shí)候，我們可以忽略掉這個(gè)分裂，所以并不是每一次分裂loss function整體都會(huì)增加的，有點(diǎn)預(yù)剪枝的意思，閾值參數(shù)為（即正則項(xiàng)里葉子節(jié)點(diǎn)數(shù)T的系數(shù)）； 
2. 當(dāng)樹達(dá)到最大深度時(shí)則停止建立決策樹，設(shè)置一個(gè)超參數(shù)max_depth，避免樹太深導(dǎo)致學(xué)習(xí)局部樣本，從而過擬合； 
3. 當(dāng)樣本權(quán)重和小于設(shè)定閾值時(shí)則停止建樹。什么意思呢，即涉及到一個(gè)超參數(shù)-最小的樣本權(quán)重和min_child_weight，和GBM的 min_child_leaf 參數(shù)類似，但不完全一樣。大意就是一個(gè)葉子節(jié)點(diǎn)樣本太少了，也終止同樣是防止過擬合； 
4. 貌似看到過有樹的最大數(shù)量的…

6 參考文獻(xiàn)與推薦閱讀

1. xgboost原始論文：https:///pdf/1603.02754v1.pdf
2. xgboost作者講義PPT：https://homes.cs./~tqchen/pdf/BoostedTree.pdf
3. XGBoost 與 Boosted Tree
4. xgboost原理：https://blog.csdn.net/a819825294/article/details/51206410
5. xgboost入門與實(shí)戰(zhàn)（原理篇）：https://blog.csdn.net/sb19931201/article/details/52557382
6. CART的Wikipedia
7. 集成學(xué)習(xí)（Ensemble Learning)
8. 淺談集成學(xué)習(xí)：Boosting與隨機(jī)森林
9. 從決策樹學(xué)習(xí)談到貝葉斯分類算法
10. 決策樹（三）--完整總結(jié)（ID3，C4.5，CART,剪枝，替代）兼源碼剖析
11. 一文讀懂機(jī)器學(xué)習(xí)大殺器XGBoost原理
12. 為什么在實(shí)際的 kaggle 比賽中 gbdt 和 random forest 效果非常好？
13. 通俗、有邏輯的寫一篇說下Xgboost的原理，供討論參考
14. 七月在線機(jī)器學(xué)習(xí)第8期第4課 決策樹、隨機(jī)森林、GBDT、xgboost
15. xgboost的一些核心參數(shù)
16. 怎樣通俗的理解泰勒級(jí)數(shù)？：https://www.zhihu.com/question/21149770
17. xgboost 為何需要泰勒二階展開：https://www./question/big/kp_id/23/ques_id/990
18. 最通俗的梯度提升樹(GBDT)原理
19. ID3、C4.5、CART、隨機(jī)森林、bagging、boosting、Adaboost、GBDT、xgboost算法總結(jié)
20. XGBoost二階泰勒展開公式推導(dǎo)
21. 泰勒公司W(wǎng)ikipedia
22. 七月在線集6學(xué)員超級(jí)瑪麗寫的xgboost筆記：一文帶你讀懂xgboost原理
23. 在線編輯LaTeX公式：http://www./latex/eqneditor.php?lang=zh-cn

后記

終于大致搞懂了這個(gè)經(jīng)常刷屏的xgboost，再次印證我之前說過的一句話：當(dāng)你學(xué)習(xí)某個(gè)知識(shí)點(diǎn)感覺學(xué)不懂時(shí)，十有八九不是你不夠聰明，十有八九是你所看的資料不夠通俗、不夠易懂（如果還是不行，問人）。

希望閱讀此文的你，也有同樣的感受。

以下的本文的改進(jìn)過程，供理解上參考：

1. 8.4上午第一版，通過一個(gè)通俗易懂的年齡預(yù)測(cè)例子介紹gbdt，因?yàn)間bdt是理解xgboost的基礎(chǔ)；
2. 8.4下午第二版，xgboost的推導(dǎo)里公式很多，初學(xué)者很容易陷進(jìn)去，后通過抓住xgboost的核心：目標(biāo)函數(shù)，梳理清晰xgboost的脈絡(luò)框架；
3. 8.5上午第三版，優(yōu)化了決策樹的介紹部分，比如增加對(duì)信息增益的介紹；
4. 8.5下午第四版，優(yōu)化大部分公式的顯示，比如之前是純文本顯示，現(xiàn)改成LaTeX圖片顯示；
5. 8.6上午第五版，優(yōu)化對(duì)booting集成學(xué)習(xí)的介紹，已讓全文更循序漸進(jìn)；
6. 8.6晚上第六版，規(guī)范xgboost目標(biāo)函數(shù)的公式表示，并梳理全文多處細(xì)節(jié)、公式；
7. 9.1上午第七版，完善4.3.1節(jié)中xgboost樹的分裂劃分方式，以更清晰；
8. 19年1.9第八版，完善4.3.1節(jié)中關(guān)于分裂節(jié)點(diǎn)的描述，以讓邏輯更清晰、行文更通俗；
9. 19年1.10第九版，第3部分增加一個(gè)預(yù)測(cè)年齡的例子，以更通俗化解釋GBDT；
10. 19年1.14第十版，把泰勒二階展開和xgboost 目標(biāo)函數(shù)的對(duì)應(yīng)關(guān)系寫清楚，從而理解更順暢。

看完全文后，你會(huì)發(fā)現(xiàn)理解xgboost有三個(gè)關(guān)鍵點(diǎn)：①4.2.1節(jié)中，理清楚xgboost目標(biāo)函數(shù)各項(xiàng)和泰勒展開二項(xiàng)的一一對(duì)應(yīng)關(guān)系，②4.2.2節(jié)中對(duì)計(jì)算數(shù)的得分w時(shí)使用的一個(gè)數(shù)學(xué)技巧，③4.3.1節(jié)中所示的樹的分裂算法。理清了這三點(diǎn)，則理解xgboost不再有障礙。

July、二零一八年八月六日晚上~二零一九年一月十四日晚上。