1. 曆史及演進
提升學習算法，又常常被稱為Boosting，其主要思想是內建多個弱分類器，然後線性組合成為強分類器。為什麼弱分類算法可以通過線性組合形成強分類算法？其實這是有一定的理論基礎的。1988年，Kearns和Valiant首先提出了“強可學習”和“弱可學習”的概念，他們指出，在機率近似正确（Probably Approximately Correct, PAC）學習的架構中，一個概念，如果存在一個多項式的學習算法能夠學習它，并且正确率很高，那麼就稱這個概念是強可學習的；如果正确率隻是稍比随機猜測好，那麼就稱這個概念是弱可學習的。在兩年之後，Schapire證明了強可學習和弱可學習是等價的，也就是說，在PAC學習的架構下，一個概念的強可學習可以由弱可學習轉換得到。但在此後很長一段時間裡，都沒有人能設計一種算法驗證PAC理論。直到1996年，Schapire提出了AdaBoost算法才将這種僵局打破。AdaBoost算法将多個不同的決策樹用一種非随機的方式組合起來，比傳統決策樹精度更高也更加穩定。AdaBoost的出現不僅拯救了有些式微的決策樹算法，而且還開創了內建學習算法的先河。在AdaBoost的影響下，Friedman在1999年提出了梯度提升決策樹算法，這種算法完美地将梯度提升算法和CART算法結合起來，不僅可以用于回歸問題，同樣也可以應用于分類問題中。GBDT被很多人認為是傳統機器學習中位居Top3的算法。即使這樣，GBDT也并不完美，相比于AdaBoost，因為後一棵樹的訓練依賴于前一棵樹的殘差，是以其并不能進行并行訓練。XGBoost是近年來針對大規模機器學習需求對GBDT提出的改進方案。XGBoost是2016年由華盛頓大學在讀博士生陳天奇釋出的開源架構，相關論文 XGBoost: A Scalable Tree Boosting System 也發表在機器學習與資料挖掘***會議KDD2016上。XGBoost較傳統的GBDT算法，加入了正則項，能夠更好地防止模型過拟合，并且可以并行分布式計算，極大地提高了精度和訓練效率。
2. AdaBoost
AdaBoost的關鍵在于如何生成多個不同的弱分類器，其主要思想是在下一輪疊代中強化那些被誤分類的樣例，而弱化那些被正确分類的樣例。在實際設計時，通過調整每個樣例的權重來達到給予不同樣例不同關注程度的目的。每一輪的權重調整都是基于上一輪分類器對所有樣例分類情況的誤差評估，而每個分類器的權重則是由該分類器對樣例總體精度決定。
這裡我們以最簡單的二類分類問題為例對AdaBoost算法進行介紹，其他分類和回歸問題與此類似。假定二類分類問題的訓練資料集為：$(X,y)=\{(x_1,y_1), (x_2,y_2),...,(x_n,y_n)\}$。其中每個訓練樣本由特征向量和标記組成，特征向量$x_i \in \mathbb{R}^d, i=1,2,...,n$，$d$為特征向量的次元，标記$y_i \in \{\pm1\}, i=1,2,...,n$。下面将介紹AdaBoost的詳細算法流程。
1. 初始化訓練資料的權值：
$$W_1=(w_{1,1},w_{1,2},...,w_{1,i},...,w_{1,n}),w_{1,i}=\frac{1}{n},i=1,2,...,n$$
在最開始的時候，我們并不知道訓練資料的權值分布，隻能假定每個訓練樣例在初始的基本分類器中的作用相同，是以設定每個樣例的權重相同。
2. 對目前的權值分布$W_m$，使用訓練資料進行訓練，得到目前輪的基本分類器:
$$F_m(x):x\rightarrow \{\pm1\}$$
使用具有權重的訓練資料進行訓練，需要對訓練方法的公式稍加修改。
3. 計算$F_m(x)$在訓練資料集上的分類誤差率:
$$e_m=P\left(F_m(x)\neq y_i\right)=\sum_{i=1}^{n}w_{m,i}\,I\left(F_m(x_i)\neq y_i\right)$$
$$ I\left(F_m(x_i)\neq y_i\right)=\left\{
\begin{aligned}
1&& F_m(x_i)\neq y_i\\
0&& F_m(x_i)=y_i\\
\end{aligned}
\right.
$$
因為每個訓練樣例都有權重，是以我們隻需要将那些錯誤分類的樣例的權重全部相加即可計算得出基本分類器在訓練資料上的分類誤差率。
4. 計算目前分類器$F_m(x)$的權重：
$$\alpha_m=\frac{1}{2}\ln\left(\frac{1-e_m}{e_m}\right)$$
可以看出，當$e_m<\frac{1}{2}$時，$\alpha_m>0$，并且随着$e_m$的減小而增大。即，分類誤差率越大的權重應該越小，反而精度越高的權重應該越大。這其實很符合現實規律，比如三個人共同籌資建立一個公司，甲出資$30$萬元，乙出資$15$萬元，丙出資$5$萬元，按出資比例，甲占股$60\%$，乙占股$30\%$，丙占股$10\%$。在公司股東會表決某項決議的時候，甲擁有$60\%$的投票權，而乙和丙分别擁有$30\%$和$10\%$的投票權。
5. 使用$w_{m,i}$，$\alpha_m$，$F_m(x_i)$和$y_i$更新樣例$i$的權重：
$$w_{m+1,i}=\frac{w_{m,i}}{Z_m}exp\left(-\alpha_m \, y_i \,F_m\,(x_i)\right)$$
$Z_m$為規範化因子，使$W_{m+1}$稱為一個合理的機率分布：
$$Z_m=\sum_{i=1}^{n}w_{m,i}\,exp\left(-\alpha_m \, y_i \,F_m\,(x_i)\right)$$
更新樣本權重時，主要根據樣例在目前基本分類器中的分類情況，如果$y_i=1$，$F_m(x)$越趨近于$1$的時候，$exp\left(-\alpha_m \, y_i \,F_m\,(x_i)\right)$越小，反而如果越接近$-1$時越大。這也正符合目前輪分得越差的樣例在下一輪越受到重視的設計。
6. 對$m=1,2,...,M$（$M$是基本分類器的個數），重複步驟2~5；
7. 建構基本分類器的線性組合$f(x)$及其最終分類器$F(x)$：
$$f(x)=\sum_{m=1}^{M}\alpha_m\, F_m(x)$$
$$F(x)=sign(f(x))=sign\left(\sum_{m=1}^{M}\alpha_m \,F_m(x)\right)$$
$sign(x)$為符号函數，滿足以下性質：
$$ sign(x)=\left\{
\begin{aligned}
1&& x\geq 0\\
-1&& x<0\\
\end{aligned}
\right.
$$
你可能已經注意到，$F_m(x)$的系數計算及訓練資料的權值分布直接定義了兩個公式，并不能一眼看出其中的含義，那麼為什麼會想到這麼定義呢？其實AdaBoost算法還有另外一種解釋方法，即可以認為其是模型為加法模型、損失函數為指數函數、學習算法為前向分布算法時的二類分類學習方法。具體内容可參考李航的《統計機器學習》第$8$章 提升方法。
2. GBDT
GBDT是Gradient Boosting Decision Tree的簡稱，很多時候又稱為MART（Multiple Additive Regession Tree）。不同于經典的內建學習算法Adaboost利用前一輪學習器的誤差來更新下一輪學習的樣本權重，GBDT每次都拟合上一輪分類器産生的殘差。舉個例子便于了解，比如一個人的年齡是50歲，第一棵樹拟合的結果是35歲，第一輪的殘差為15歲；然後第二棵數拟合的結果是10歲，兩棵樹相加總的拟合結果是45歲，第二輪的殘差為5歲；第三棵數拟合的結果為2歲，三棵樹相加拟合的結果是47歲，第三輪的殘差是3歲......隻要如此不斷地進行下去，拟合結果就可以達到50歲，拟合殘差的過程就是訓練資料的過程。
對于一個給定的資料集$\{x_i,y_i\}, i=1,2,...,m$，其中特征向量$x_i \in \mathbb{R}^n$，标簽$y_i \in \mathbb{R}$，可以用$x_{ij}, j=1,2,...,d來表示x_i的第j個特征值$。對于一個典型的回歸決策樹問題，需要周遊所有特征$j$的全部門檻值$t$，找到最優的$j$和$t$使下面的等式最小化：
$$S_j=\sum_{i \in L}(y_i-\mu_L)^2+\sum_{i \in R}(y_i-\mu_R)^2$$
其中$x_{ij} \leq t$的所有樣本落入左子樹$L$中，其中$x_{ij} > t$的所有樣本落入右子樹$R$中，$\mu_L(\mu_R)$表示左子樹（右子樹）所有樣例标簽值的均值。如果這就是一棵最簡單的擁有一個根節點、兩個葉子節點的二叉回歸樹，那麼隻需要根據最優門檻值切分為左右子樹，并且分别計算左右子樹的值$\gamma_l,l=1,2$即可。如果将劃分子樹的過程繼續進行$L-1$次即可得到一棵包含$L$個葉子節點的回歸樹。
上面公式使用最小二乘法計算拟合誤差，是以通過上面方法得到的模型又稱為最小二乘回歸樹。其實不管誤差的計算方式如何，我們都可以拟合出相應的回歸樹，唯一的差別是梯度的計算不同而已。
GBDT使用線性組合的方式将拟合的樹結合起來，作為最後的輸出：
$$F_n(x)=\sum_{i=1}^{N}\alpha_if_i(x)$$
$f_i(x)$是單棵回歸樹函數，$\alpha_i$是第$i$棵回歸樹的權重，一般采用相等權重即可。
在這裡我們需要弄清楚為什麼拟合殘差就能不斷減少拟合誤差。假設拟合誤差$C$是拟合函數$F_n$的函數$C(F_n)$。那麼：
$$\delta C \approx \frac{\partial{C(F_n)}}{\partial{F_n}}\delta F_n$$
如果取$\delta F_n=-\eta \frac{\partial{C}}{\partial{F_n}}$，就可以得到$\delta C<0$。其中$\eta$是學習率，為正實數。是以隻要函數$F_n$拟合誤差函數的負梯度就可以不斷降低拟合誤差的值。
設标簽向量$y=[y_1,y_2,...,y_m]^T$，如果用最小二乘的方式表示拟合誤差，則：$$C=\frac{1}{2}(F_n-y)^2$$
那麼$\delta F_n=-\eta \frac{\partial{C}}{\partial{F_n}}=-\eta (F_n-y)$。$F_n-y$其實就是每一輪拟合後的殘差，是以拟合殘差就可以不斷減少拟合誤差。
3. XGBoost
XGBoost，全稱為eXtreme Gradient Boosting，是目前唯一能與LightGBM相媲美的提升樹算法。XGBoost的出現解決了傳統GBDT兩個很明顯的缺點：容易過拟合和對于大資料訓練效率低。既然在一定程度上解決了過拟合問題，模型的訓練精度也得到了很大的提升。在XGBoost剛分布的半年内，曾經一度包攬了Kaggle比賽的冠軍，實力可見一斑。那麼XGBoost是怎樣解決過拟合問題進而提升模型精度的呢？
我們先從一般的機器學習問題入手，然後再逐漸深入了解XGBoost的原理。定義機器學習問題的損失函數如下：
$$Obj(\Theta)=L(\Theta)+\Omega(\Theta)$$
其中的$L(\Theta)$表示訓練誤差，衡量目前機器學習模型與訓練資料的拟合程度，訓練誤差越低表示模型拟合得越好，但并不一定代表模型的泛化能力就強，因為很有可能是因為模型在訓練資料集上過拟合導緻的。$\Omega(\Theta)$表示模型正則化項，衡量了模型本身的複雜程度。在“以簡為美”的理念下，一般更傾向于選擇簡單的模型，認為越簡單的模型越可能是資料真正的規律。同時優化這兩項，就可以找到模型複雜度和模型對訓練資料拟合程度之間的一個tradeoff。
對于有$K$棵樹的GBDT模型來說，可以定義模型的損失函數如下：
$$Obj(\Theta)=\sum_{i=1}^{N}l(y_i,\hat{y_i})+\sum_{k=1}^{K}\Omega(f_k)$$
其中$\hat{y_i}=\sum_{k=1}^{K}f_k(x_i)$表示模型對樣例$i$的預測值，$y_i$則表示樣例$i$的标簽。$\Omega(f_k)$表示第$i$棵樹的複雜度。可以說以上的定義合乎情理，同時考慮了模型的拟合程度和樹模型的總複雜度。
如何定義每棵樹的拟合函數$f_k$呢？我們以陳天奇PPT裡的圖為例：
$f_k(x)=w_{q(x)}$，$w \in \mathbb{R}^T$，$T$為葉子節點個數，$q(x)$将樣例映射到葉子節點。$f_k(x)$将每個樣例映射到葉子節點，并且賦予一定的權重，但并沒有定義樹形結構，是以在後面優化時隻能采取啟發式的方法建構樹。
在XGBoost中，定義單棵樹的正則化項為：
$$\Omega(f_k)=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}$$
第一項為樹的葉子節點個數，第二項為所有葉子節點分數的$L2$正則化項。
很明顯，以上定義的損失函數并不能直接求導，是以也就不能直接使用SGD等梯度下降算法進行求解，GBDT是一種可行的解法。
實際上，可以将GBDT看成是一種加法訓練模型，在第$k$輪時，模型函數由第$k-1$輪和目前輪的拟合函數相加構成，也即:
$$\hat{y_i}^{(k)}=\hat{y_i}^{(k-1)}+f_k(x_i)$$
是以，可以改成損失函數為：
$$Obj^{(k)}=\sum_{i=1}^{N}l\left(y_i,\hat{y_i}^{(k)}\right)+\sum_{i=1}^{k}\Omega(f_i)=\sum_{i=1}^{N}l\left(y_i,\hat{y_i}^{(k-1)}+f_k(x_i)\right)+\Omega(f_k)+const$$
考慮最簡單的平方誤差，損失函數改寫為：
$$Obj^{(k)}=\sum_{i=1}^{N}\left[y_i-(\hat{y_i}^{(k-1)}+f_k(x_i))\right]^2+\Omega(f_k)+const=\sum_{i=1}^{N}\left[2(\hat{y_i}^{(k-1)}-y_i)f_k(x_i)+f_k(x_i)^2\right]+\Omega(f_k)+const$$
回憶一下泰勒展開公式，二階泰勒展開式為：
$$f(x+\Delta{x})\simeq f(x)+f'(x)\Delta{x}+\frac{1}{2}f''(x)\Delta{x}^2$$
那麼目标損失函數可以改寫為：
$$Obj^{(k)}\simeq \sum_{i=1}^{N}\left[l(y_i,\hat{y_i}^{(k-1)})+g_if_k(x_i)+\frac{1}{2}h_if_k^2(x_i)\right]+\Omega(f_k)+const$$
其中，
$$g_i=\frac{\partial l(y_i,\hat{y_i}^{(k-1)})}{\partial \hat{y_i}^{(k-1)}}$$
$$h_i=\frac{\partial^2 l(y_i,\hat{y_i}^{(k-1)})}{\partial (\hat{y_i}^{(k-1)})^2}$$
移除常數項，得到:
$$Obj^{(k)}=\sum_{i=1}^{N}\left[g_if_k(x_i)+\frac{1}{2}h_if_k^2(x_i)\right]+\Omega(f_k)$$
如果葉子節點$j$裡的樣例集合用$I_j$表示，可以改成損失函數如下所示：
$$Obj^{(k)}=\sum_{i=1}^{N}\left[g_if_k(x_i)+\frac{1}{2}h_if_k^2(x_i)\right]+\Omega(f_k)=\sum_{i=1}^{N}\left[g_iw_{q(x_i)}+\frac{1}{2}h_iw_{q(x_i)}^2\right]+\gamma T+\lambda \frac{1}{2}\sum_{j=1}^{T}w_j^2=\sum_{j=1}^{T}\left[(\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w_j^2\right]+\gamma T$$
令$G_j=\sum_{i\in I_j}g_i, H_j=\sum_{i \in I_j}h_i$，則：
$$Obj^{(k)}=\sum_{j=1}^{T}\left[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2\right]+\gamma T$$
如果上式中目前樹形結構已經确定，那麼可以在每個葉子節點優化權重，可以得到：
$$w_j^*=-\frac{G_j}{H_j+\lambda}$$
$$Obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T$$
$Obj$評價了一棵樹的好壞，值越小樹模型越好。但是問題來了，如果建構這棵樹呢？建構樹的方式似乎可以有很多很多種，周遊所有的樹形結構肯定是不可取的。回想一下在我們最開始學二叉樹的時候，知道樹是一層一層地建構出來的，這裡其實也可以定義一個切分規則，采用一種啟發式的方法，從上到下，一層層地将樹結構建構出來。
決策樹ID3采用資訊增益劃分節點，回歸樹使用基尼指數劃分節點，這裡可以根據損失函數來定義節點劃分标準：
$$Gain=\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{(H_L+H_R)+\lambda}-\gamma$$
第一項為左子樹的cost，第二項為右子樹的cost，第三項為劃分前的cost，最後一項定義為由于節點劃分帶給整棵樹的複雜度提升，可以作為是否切分節點的标準。有了節點劃分标準，就可以将樹結構疊代地建構出來。
XGBoost可以說完美地将正則化融入到GBDT模型中。