作者前言
在2020年還在整理XGB的算法，其實已經有點過時了。。不過，主要是為了學習算法嘛。現在的大資料競賽，XGB基本上已經全面被LGB模型取代了，這裡主要是學習一下Boost算法。之前已經在其他博文中介紹了Adaboost算法和Gradient-boost算法，這篇文章講解一下XGBoost。
Adaboost和XGBoost無關，但是Gradient-boost與XGBoost有一定關系。
一文搞懂：Adaboost及手推算法案例
一文讀懂：GBDT梯度提升
樹模型概述
XGB就是Extreme Gradient Boosting極限梯度提升模型。XGB簡單的說是一組分類和回歸樹（CART）的組合。跟GBDT和Adaboost都有異曲同工之處。
【CART=classification adn regression trees】
這裡對于一個決策樹，如何分裂，如何選擇最優的分割點，其實就是一個搜尋的過程。搜尋怎麼分裂，才能讓目标函數最小。目标函數如下：
\(Obj = Loss + \Omega\)
\(Obj\)就是我們要最小化的優化函數，\(Loss\)就是這個CART模型的預測結果和真實值得損失。\(\Omega\)就是這個CART模型的複雜度,類似神經網絡中的正則項。
【上面的公式就是一個抽象的概念。我們要知道的是：CART樹模型即要求預測盡可能準确，又要求樹模型不能過于複雜。】
對于回歸問題，我們可以用均方差來作為Loss：
\(Loss=\sum_i{(y_i-\hat{y_i})^2}\)
對于分類問題，用交叉熵是非常常見的,這裡用二值交叉熵作為例子：
\(Loss = \sum_i{(y_ilog(\hat{y_i})+(1-y_i)log(\hat{y_i}))}\)
總之，這個Loss就是衡量模型預測準确度的損失。
下面看一下如何計算這個模型複雜度\(\Omega\)吧。
\(\Omega = \gamma T+\frac{1}{2} \lambda \sum^T_j{w_j}^2\)
\(T\)表示葉子節點的數量，\(w_j\)表示每個葉子節點上的權重（與葉子節點的樣本數量成正比）。
【這裡有點麻煩的在于，\(w_j\)是與每個葉子節點的樣本數量成正比，但是并非是樣本數量。這個\(w_j\)的求取，要依靠與對整個目标函數求導數，然後找到每個葉子節點的權重值\(w_j\)。】
XGB vs GBDT
其實說了這麼多，感覺XGB和GDBT好像差別不大啊？下面整理一下網上有的說法，再加上自己的了解。有錯誤請指出評論，謝謝！
差別1：自帶正則項
GDBT中，隻是讓新的弱分類器來拟合負梯度，那拟合多少棵樹才算好呢？不知道。XGB的優化函數中，有一個\(\Omega\)複雜度。這個複雜度不是某一課CART的複雜度，而是XGB中所有CART的總複雜度。可想而知，每多一顆CART，這個複雜度就會增加他的懲罰力度，當損失下降小于複雜度上升的時候，XGB就停止了。
差別2：有二階導數資訊
GBDT中新的CART拟合的是負梯度，也就是一階導數。而在XGB會考慮二階導數的資訊。
這裡簡單推導一下XGB如何用上二階導數的資訊的：
-
之前我們得到了XGB的優化函數：
\(Obj = Loss + \Omega\)
-
然後我們把Loss和Omega寫的更具體一點：
\(Obj = \sum_i^n{Loss(y_i,\hat{y}_i^t)}+\sum_j^t{\Omega(cart_j)}\)
- \(\hat{y_i^t}\)表示總共有t個CART弱分類器，然後t個弱分類器給出樣本i的估計值就。
- \(y_i\)第i個樣本的真實值；
- \(\Omega(cart_j)\)第j個CART模型的複雜度。
-
我們現在要求取第t個CART模型的優化函數，是以目前我們隻是知道前面t-1的模型。是以我們得到：
\(\hat{y}_i^t = \hat{y}_i^{t-1}+f_t(x_i)\)
t個CART模型的預測，等于前面t-1個CART模型的預測加上第t個模型的預測。
-
是以可以得到：
\(\sum_i^n{Loss(y_i,\hat{y}_i^t)}=\sum_i^n{Loss(y_i,\hat{y}_i^{t-1}+f_t(x_i))}\)
這裡考慮一下特勒展開：
\(f(x+\Delta x)\approx f(x)+f\'(x)\Delta x + \frac{1}{2} f\'\'(x)\Delta x^2\)
-
如何把泰勒公式帶入呢？
\({Loss(y_i,\hat{y}_i^t)}\)中的\(y_i\)其實就是常數，不是變量
是以其實這個是可以看成\(Loss(\hat{y}_i^t)\),也就是:
\(Loss(\hat{y}_i^{t-1}+f_t(x_i))\)
-
帶入泰勒公式，把\(f_t(x_i)\)看成\(\Delta x\)：
\(Loss(\hat{y}_i^{t-1}+f_t(x_i))=Loss(\hat{y}_i^{t-1})+Loss\'(\hat{y}_i^{t-1})f_t(x_i)+\frac{1}{2}Loss\'\'(\hat{y}_i^{t-1})(f_t(x_i))^2\)
- 在很多的文章中，會用\(g_i=Loss\'(\hat{y}_i^{t-1})\),以及\(h_i=Loss\'\'(\hat{y}_i^{t-1})\)來表示函數的一階導數和二階導數。
-
把泰勒展開的東西帶回到最開始的優化函數中，删除掉常數項\(Loss(\hat{y}_i^{t-1})\)(這個與第t個CART模型無關呀)以及前面t-1個模型的複雜度，可以得到第t個CART的優化函數：
\(Obj^t \approx \sum_i^n{[g_i f_t(x_i)+\frac{1}{2}h_i(f_t(x_i))^2}]+{\Omega(cart_t)}\)
【是以XGB用到了二階導數的資訊，而GBDT隻用了一階的梯度】
差別3：列抽樣
XGB借鑒了随機森林的做法，不僅僅支援樣本抽樣，還支援特征抽樣（列抽樣），不僅可以降低過拟合，還可以減少計算。
差別4：缺失值
XGB可以自适應的處理樣本中的缺失值。如何處理的這裡就不再講述。
喜歡的話加個微信公衆号支援一下吧~目前主要再整理針對機器學習算法崗位的面試可能遇到的知識點。
公衆号回複【下載下傳】有精選的免費機器學習學習資料。 公衆号每天會更新一個機器學習、深度學習的小知識，都是面試官會問的知識點哦~
- 【機器學習的基礎數學(PDF)】
- 【競賽中的大資料處理流程(PDF)】
- 【如何做大資料的基礎特征工程(PDF)】
- 【自然語言處理NLP的應用實踐大合集(PDF)】
- 【python入門級教材(400頁PDF)】
公衆号每天會更新一個機器學習、深度學習的小知識，都是面試官會問的知識點哦~
