這篇文章打算介紹一下boosting 和xgboost漂羊，這兩天也看了好多文章稽寒，也感覺了解的不深，算是做個記錄磁椒。
Boost算法
先簡單提一下Bagging堤瘤， 原理是從現(xiàn)有數(shù)據(jù)中有放回的抽取若干個樣本構(gòu)建分類器，重復若干次建立若干個分類器進行投票浆熔。
而Boost（提升）是指每一步都產(chǎn)生一個弱預測模型本辐，然后加權(quán)累加到總模型中。每一步弱預測模型生成的依據(jù)都是損失函數(shù)的負梯度方向，若干步以后就可以達到逼近損失函數(shù)局部的最小值慎皱。
首先Boost是一個加法模型环葵，有若干個基函數(shù)及其權(quán)重乘積之和的累加。
其中b是基函數(shù)宝冕，beta是基函數(shù)的系數(shù)，這就是最終分類器的樣子邓萨。目標就是想辦法使損失函數(shù)的期望最小值地梨。
一步對m個分類起優(yōu)化太難，因此有一個稍微折中的辦法缔恳，因為是加法模型宝剖，每一步只對其中一個基函數(shù)及其系數(shù)進行求解，逐步逼近損失函數(shù)的最小值歉甚。
要使損失函數(shù)最小万细，那么新加的這一項剛好等于損失函數(shù)的負梯度。這樣一步一步就使得損失函數(shù)下降最快纸泄。
這里的lambda可以和beta合并表示步長赖钞。對于這個基函數(shù)而言，其實就是關于x和這個函數(shù)梯度的一個擬合聘裁，然后步長的選擇可以根據(jù)線性搜索雪营，即尋找在這個梯度上下降最小值的那個步長，盡快逼近損失函數(shù)的最小值衡便。
梯度提升完
GBDT
首先既然是樹献起，上一篇介紹過，基函數(shù)是決策樹镣陕，而損失函數(shù)則是根據(jù)具體問題具體分析谴餐，不過總體方法都是一樣，梯度下降呆抑。
比如到第m步岂嗓， 計算殘差。
有了殘差理肺，再用（xi摄闸， rim）去擬合第m個基函數(shù)。假設這顆樹把輸入空間劃分成j個空間R1m, R2m, ...., Rjm妹萨。假設在每個空間的輸出為bjm年枕。這樣，第m棵樹可以表示如下：
下一步乎完，對樹的每個區(qū)域分別用線性搜索的方法尋找最佳步長熏兄，然后與上面的區(qū)域預測值合并，最后可以得到第m步的目標函數(shù)。
對于GBDT容易出現(xiàn)過擬合摩桶，所以有必要增加一點正則項桥状，比如葉子節(jié)點數(shù)目或葉子節(jié)點預測值的平方和，限制模型復雜度的過度提升硝清。
XGBoost
之前用的梯度下降只考慮了一階信息辅斟，根據(jù)泰勒展開，把二階信息用上：
其中fm為參數(shù)的函數(shù)是正則項芦拿∈快可以表示如下：
對于決策樹而言，最重要的一共有多少個節(jié)點以及節(jié)點的權(quán)值蔗崎。所以決策樹可以表示為：
各種公式酵幕，最后得到
可以得到的結(jié)果是：把新一步函數(shù)的損失函數(shù)變成了只與上一步相關的一個新的損失函數(shù)。這樣可以遍歷數(shù)據(jù)中所有的分割點缓苛，尋找新的損失函數(shù)下降最多的分割點芳撒，重復上述操作。
相比于梯度下降提升未桥，XGBoost在劃分新的樹的時候還用到了二階信息笔刹，因此能夠更快的收斂；由于用c/c++寫的钢属，速度也快徘熔。在尋找最加分割點的時候，還可以引入并行計算淆党，因此速度進一步提高酷师。
參考文章：
XGBoost 與 Boosted Tree:多看幾遍
