梯度提升(Gradient Boosting)是一種boosting的演算法，最早的論文是「Greedy Function Approximation: A Gradient Boosting Machine」，目前已被引用約15,000次，此種演算法可以應用到很多模型上，但是最常見的是用到決策樹(Decision tree)上，也就是GBDT(Gradient Boosting Decision Tree)。
機器學習領域在做演算法的訓練目標通常是為了優化或最小化損失函數(loss Function)，Gradient boosting的核心精神是迭代出多個（M個）弱的演算法，然後將M個弱模型的預測結果相加，後面的模型Fm+1(x)基於前面學習模型的Fm(x)的效果生成的，關係如下：
Gradient boosting(GB)計算流程:假設Input為ｘ、Output為y
當我們有了GB的概念後，XGboost演算法的基本想法與GBDT (Regression Decistion Tree (DT)+Gradient Boosting (GB))類似，經過產生許多顆決策樹，每一輪學習一棵樹，去擬合上一輪模型的預測值與實際值之間的殘差。當我們訓練完成得到k棵樹時，我們要預測一個樣本的分數，其實就是根據這個樣本的特徵，在每棵樹中會落到對應的一個葉子節點，每個葉子節點就對應一個分數，最後只需將每棵樹對應的分數加起來就是最終的預測結果(bagging的概念)，如下圖所示。
XGboost的目標函數＝損失函數＋正則項，左邊是損失函數，右邊則是正則項，損失函數是用來衡量預測值與實際值的誤差，正則項包含兩部分，T表示葉子結點的個數，w表示葉子節點的分數。γ可以控制葉子結點的個數，λ可以控制葉子節點的分數不會過大，可以用來防止模型過擬合(Over-fitting)。
XGboost的演變過程: BaggingàBoostingàGradient boosting(GB)àGradient Boosting Decision Tree(GBDT)à eXtreme Gradient Boosting(XGboost)
XGboost的特性:
1.Parallelization：訓練時可以用所有的CPU來進行平行運算(類似bagging的方式)
2.Distributed Computing ：用分散式運算來訓練非常複雜的模型
3.Out-of-Core Computing：對於非常大的資料集還可以進行單機的批次處理
4.Cache Optimization of data structures and algorithms：更好地利用硬體
XGboost在模型的準確性以及運算時間上做了許多優化，因此在Kaggle的比賽中，凡是非結構化資料相關的競賽，例如:語音、影像，基本都是深度學習獲勝，但凡是結構化資料上的競賽，基本都是XGboost 獲勝，可見XGboost真的是相當厲害的演算法。
XGboost的優點:
1.將樹模型的複雜度加入到正則項中，來避免過擬合(over-fitting)的問題，因此外推性會優於GBDT的方法
2.損失函數用泰勒展開式展開，同時用到了一階和二階導數(推導過程可參考參考資料2)，可以加快優化速度
3.GBDT只支持Classification And Regression Tree (CART)作為基學習器，XGBoost還支援線性分類器(例如: LDA、Bayes..)作為基學習器
4.引進了特徵子採樣(不需要使用全部的特徵做訓練)，像隨機森林那樣，能避免過擬合，又能減少計算時間
5.在尋找最佳分割點時，考慮到傳統的貪婪演算法效率較低，實現了一種近似貪婪演算法，用來加速和減少記憶體使用，除此之外，還考慮了稀疏資料集合缺失值的處理
關於理論的部分就講到這裡，筆者之後的文章會再針對XGboost在R語言上面進行實做與示範。
參考資料:
留言列表
{{ article.title }}