1. 什么是XGBoost
XGBoost是陳天奇等人開發(fā)的一個開源機器學習項目苹支，高效地實現(xiàn)了GBDT算法并進行了算法和工程上的許多改進愁铺，被廣泛應用在Kaggle競賽及其他許多機器學習競賽中并取得了不錯的成績遏佣。
說到XGBoost嗡害，不得不提GBDT(Gradient Boosting Decision Tree)炉奴。因為XGBoost本質(zhì)上還是一個GBDT佛吓，但是力爭把速度和效率發(fā)揮到極致，所以叫X (Extreme) GBoosted俱诸。包括前面說過菠劝，兩者都是boosting方法。
關于GBDT睁搭，這里不再提赶诊，可以查看我前一篇的介紹，點此跳轉(zhuǎn)园骆。
1.1 XGBoost樹的定義
先來舉個例子舔痪，我們要預測一家人對電子游戲的喜好程度，考慮到年輕和年老相比锌唾，年輕更可能喜歡電子游戲锄码，以及男性和女性相比，男性更喜歡電子游戲，故先根據(jù)年齡大小區(qū)分小孩和大人巍耗，然后再通過性別區(qū)分開是男是女，逐一給各人在電子游戲喜好程度上打分渐排，如下圖所示炬太。
就這樣，訓練出了2棵樹tree1和tree2驯耻，類似之前gbdt的原理亲族，兩棵樹的結論累加起來便是最終的結論，所以小孩的預測分數(shù)就是兩棵樹中小孩所落到的結點的分數(shù)相加：2 + 0.9 = 2.9可缚。爺爺?shù)念A測分數(shù)同理：-1 + （-0.9）= -1.9霎迫。具體如下圖所示：
恩，你可能要拍案而起了帘靡，驚呼知给，這不是跟上文介紹的GBDT乃異曲同工么？
事實上描姚，如果不考慮工程實現(xiàn)涩赢、解決問題上的一些差異，XGBoost與GBDT比較大的不同就是目標函數(shù)的定義轩勘。XGBoost的目標函數(shù)如下圖所示：
其中：
- 紅色箭頭所指向的L 即為損失函數(shù)（比如平方損失函數(shù)：
)
- 紅色方框所框起來的是正則項（包括L1正則筒扒、L2正則）
- 紅色圓圈所圈起來的為常數(shù)項
- 對于f(x)，XGBoost利用泰勒展開三項绊寻，做一個近似花墩。f(x)表示的是其中一顆回歸樹。
看到這里可能有些讀者會頭暈了澄步，這么多公式冰蘑，我在這里只做一個簡要式的講解，具體的算法細節(jié)和公式求解請查看這篇博文驮俗，講得很仔細：通俗理解kaggle比賽大殺器xgboost
XGBoost的核心算法思想不難懂缕，基本就是：
- 不斷地添加樹，不斷地進行特征分裂來生長一棵樹王凑，每次添加一個樹搪柑，其實是學習一個新函數(shù)f(x)，去擬合上次預測的殘差索烹。
- 當我們訓練完成得到k棵樹工碾，我們要預測一個樣本的分數(shù)，其實就是根據(jù)這個樣本的特征百姓，在每棵樹中會落到對應的一個葉子節(jié)點渊额，每個葉子節(jié)點就對應一個分數(shù)
- 最后只需要將每棵樹對應的分數(shù)加起來就是該樣本的預測值。
顯然，我們的目標是要使得樹群的預測值盡量接近真實值
旬迹，而且有盡量大的泛化能力火惊。類似之前GBDT的套路，XGBoost也是需要將多棵樹的得分累加得到最終的預測得分（每一次迭代奔垦，都在現(xiàn)有樹的基礎上屹耐，增加一棵樹去擬合前面樹的預測結果與真實值之間的殘差）。
那接下來椿猎，我們?nèi)绾芜x擇每一輪加入什么 f 呢惶岭？答案是非常直接的，選取一個 f 來使得我們的目標函數(shù)盡量最大地降低犯眠。這里 f 可以使用泰勒展開公式近似按灶。
實質(zhì)是把樣本分配到葉子結點會對應一個obj，優(yōu)化過程就是obj優(yōu)化筐咧。也就是分裂節(jié)點到葉子不同的組合鸯旁，不同的組合對應不同obj，所有的優(yōu)化圍繞這個思想展開嗜浮。到目前為止我們討論了目標函數(shù)中的第一個部分：訓練誤差羡亩。接下來我們討論目標函數(shù)的第二個部分：正則項，即如何定義樹的復雜度危融。
1.2 正則項：樹的復雜度
XGBoost對樹的復雜度包含了兩個部分：
- 一個是樹里面葉子節(jié)點的個數(shù)T
- 一個是樹上葉子節(jié)點的得分w的L2模平方（對w進行L2正則化畏铆，相當于針對每個葉結點的得分增加L2平滑，目的是為了避免過擬合）
我們再來看一下XGBoost的目標函數(shù)（損失函數(shù)揭示訓練誤差 + 正則化定義復雜度）：
正則化公式也就是目標函數(shù)的后半部分吉殃，對于上式而言辞居，是整個累加模型的輸出，正則化項∑kΩ(ft)是則表示樹的復雜度的函數(shù)蛋勺，值越小復雜度越低瓦灶，泛化能力越強。
1.3 樹該怎么長
很有意思的一個事是抱完，我們從頭到尾了解了xgboost如何優(yōu)化贼陶、如何計算，但樹到底長啥樣巧娱，我們卻一直沒看到碉怔。很顯然，一棵樹的生成是由一個節(jié)點一分為二禁添，然后不斷分裂最終形成為整棵樹撮胧。那么樹怎么分裂的就成為了接下來我們要探討的關鍵。對于一個葉子節(jié)點如何進行分裂老翘，XGBoost作者在其原始論文中給出了一種分裂節(jié)點的方法：枚舉所有不同樹結構的貪心法
不斷地枚舉不同樹的結構芹啥，然后利用打分函數(shù)來尋找出一個最優(yōu)結構的樹锻离，接著加入到模型中，不斷重復這樣的操作墓怀。這個尋找的過程使用的就是貪心算法汽纠。選擇一個feature分裂，計算loss function最小值傀履，然后再選一個feature分裂疏虫，又得到一個loss function最小值，你枚舉完啤呼，找一個效果最好的，把樹給分裂呢袱，就得到了小樹苗官扣。
總而言之，XGBoost使用了和CART回歸樹一樣的想法羞福，利用貪婪算法惕蹄，遍歷所有特征的所有特征劃分點，不同的是使用的目標函數(shù)不一樣治专。具體做法就是分裂后的目標函數(shù)值比單子葉子節(jié)點的目標函數(shù)的增益卖陵，同時為了限制樹生長過深，還加了個閾值张峰，只有當增益大于該閾值才進行分裂泪蔫。從而繼續(xù)分裂，形成一棵樹喘批，再形成一棵樹撩荣，每次在上一次的預測基礎上取最優(yōu)進一步分裂/建樹。
1.4 如何停止樹的循環(huán)生成
凡是這種循環(huán)迭代的方式必定有停止條件饶深，什么時候停止呢餐曹？簡言之，設置樹的最大深度敌厘、當樣本權重和小于設定閾值時停止生長以防止過擬合台猴。具體而言，則
- 當引入的分裂帶來的增益小于設定閥值的時候俱两，我們可以忽略掉這個分裂饱狂，所以并不是每一次分裂loss function整體都會增加的，有點預剪枝的意思锋华，閾值參數(shù)為（即正則項里葉子節(jié)點數(shù)T的系數(shù)）嗡官；
- 當樹達到最大深度時則停止建立決策樹，設置一個超參數(shù)max_depth毯焕，避免樹太深導致學習局部樣本衍腥，從而過擬合磺樱；
- 樣本權重和小于設定閾值時則停止建樹。什么意思呢婆咸，即涉及到一個超參數(shù)-最小的樣本權重和min_child_weight竹捉，和GBM的 min_child_leaf 參數(shù)類似，但不完全一樣尚骄。大意就是一個葉子節(jié)點樣本太少了块差，也終止同樣是防止過擬合；
2. XGBoost與GBDT有什么不同
除了算法上與傳統(tǒng)的GBDT有一些不同外倔丈，XGBoost還在工程實現(xiàn)上做了大量的優(yōu)化憨闰。總的來說需五，兩者之間的區(qū)別和聯(lián)系可以總結成以下幾個方面鹉动。
- GBDT是機器學習算法，XGBoost是該算法的工程實現(xiàn)宏邮。
- 在使用CART作為基分類器時泽示，XGBoost顯式地加入了正則項來控制模 型的復雜度，有利于防止過擬合蜜氨，從而提高模型的泛化能力械筛。
- GBDT在模型訓練時只使用了代價函數(shù)的一階導數(shù)信息，XGBoost對代 價函數(shù)進行二階泰勒展開飒炎，可以同時使用一階和二階導數(shù)埋哟。
- 傳統(tǒng)的GBDT采用CART作為基分類器，XGBoost支持多種類型的基分類 器郎汪，比如線性分類器定欧。
- 傳統(tǒng)的GBDT在每輪迭代時使用全部的數(shù)據(jù)，XGBoost則采用了與隨機 森林相似的策略怒竿，支持對數(shù)據(jù)進行采樣砍鸠。
- 傳統(tǒng)的GBDT沒有設計對缺失值進行處理，XGBoost能夠自動學習出缺 失值的處理策略耕驰。
3. 為什么XGBoost要用泰勒展開爷辱，優(yōu)勢在哪里？
XGBoost使用了一階和二階偏導, 二階導數(shù)有利于梯度下降的更快更準. 使用泰勒展開取得函數(shù)做自變量的二階導數(shù)形式, 可以在不選定損失函數(shù)具體形式的情況下, 僅僅依靠輸入數(shù)據(jù)的值就可以進行葉子分裂優(yōu)化計算, 本質(zhì)上也就把損失函數(shù)的選取和模型算法優(yōu)化/參數(shù)選擇分開了. 這種去耦合增加了XGBoost的適用性, 使得它按需選取損失函數(shù), 可以用于分類, 也可以用于回歸朦肘。
4. 代碼實現(xiàn)
GitHub：點擊進入
5. 參考文獻
作者：@mantchs
GitHub：https://github.com/NLP-LOVE/ML-NLP
歡迎大家加入討論饭弓！共同完善此項目！群號：【541954936】點擊加入
