機器學習演算法中GBDT與Adaboost的區別與聯繫是什麼？

01-01

GBDT可用於classification與regression，我的理解是classification是Log Loss, regreesion是平方Loss,採用回歸樹去擬合殘差或者Loss Fuction的導數，AdaBoost是向前加項模型，採用指數損失，是分類樹做基分類器，調整錯分類的點的observation probability,不知理解是否正確，求大神進一步從深層次分析一下兩者的區別和聯繫
另外，GBDT做分類與邏輯回歸的區別是什麼？是否可以理解為尋找的是非線性分界面？為什麼會比lr效果好？

謝邀，試答一下。

Boosting演算法

Boosting演算法特徵如下：通過將一些表現效果一般（可能僅僅優於隨機猜測）的模型通過特定方法進行組合來獲得一個表現效果較好的模型。從抽象的角度來看，Boosting演算法是藉助convex loss function在函數空間進行梯度下降的一類演算法。Gradient Boost和Adaboost就是其中比較常見的兩種。

AdaBoost（Adaptive Boosting)

由Yoav Freund和Robert Schapire提出，兩人因此獲得了哥德爾獎。

為了比較好地理解AdaBoost，先來看下下面這些圖。

二元分類問題，如何劃分紅球和籃球。顯然這個問題用一個線性分類器的話很難取得最好的效果。有沒有辦法通過組合一系列和正方形平行的線（每條線都相當於一個線性分類器）來獲得一個比較好的分類效果呢？

第一步：先矮子里拔將軍，選擇一條平行於四邊且最不壞的線段。下圖第一排中間的小圖裡，直線把圖分為左邊（紅點）和右邊（藍點）兩類，被錯分的點只有3個，這似乎是能得到的最好的結果了。然後我們想去找第二條線（第二個線性分類器）。如果只是基於現有的這些點的話那麼說不定得到的線段還是和之前那條差不多，那多個線段（線性分類器）就沒有意義了。所以我們要稍微調整一下某些點在分類結果里的重要性，提升他們的權重。我們在這裡提升了那三個被錯分的點的權重。

第二步：我們找到了一條新的線段，因為之前提升了把藍點和藍點分在一起的重要性，所以這條線段沒有選擇平行於上下兩邊把上面4個點（1紅3藍）和下面7個點（5紅2藍）分開，而是選擇儘可能多地把藍點歸在一起。然而這次不同的是我們分錯的是右邊那4個紅點，於是我們放大那4個紅點，提升他們的權重。

不斷重複這一過程。

最終我們得到了多個線性分類器，把這些線性分類器的結果做一個線性組合，我們就得到了整個集成模型的結果。每個線性分類器的結果的係數（權重）取決於它的表現，表現越好，權重越高。比如第一條線段的分類錯誤就優於第二條線段，那麼它獲得的權重也就會更大。集成模型的效果非常好。

順帶一提，第一條線段的分類正確率是8/11，第二條線段的分類正確率是7/11，第三條線段的分類正確率是8/11，確實要好於隨機猜測（以1/2為界）。

圖片來源： Mehryar Mohris Foundations of Machine Learning的上課講義http://www.cs.nyu.edu/~mohri/mls/ml_boosting.pdf

把AdaBoost和一開始對Boosting演算法的定義比較看看，我們確實通過組合一系列表現一般的模型獲得了一個表現優秀的模型。另外值得注意的是在訓練過程中，每個新的模型都會基於前一個模型的表現結果進行調整，這也就是為什麼AdaBoost是自適應（adaptive）的原因。

演算法如下：

圖片來源：同上。

AdaBoost確實採用的是指數損失，基分類器最常見的是決策樹（在很多情況下是決策樹樁，深度為1的決策樹）。在每一輪提升相應錯分類點的權重可以被理解為調整錯分類點的observation probability。

Gradient Boosting

在AdaBoost發表後不久，Breiman等人發表了Formulate AdaBoost as gradient descent with a special loss function。隨後Friedman等人發表了Generalize AdaBoost to Gradient Boosting in order to handle a variety of loss functions。可以說AdaBoost是Gradient Boosting的一個特例或者Gradient Boosting是對AdaBoost進行推廣。

Gradient Boosting和其它Boosting演算法一樣，通過將表現一般的數個模型（通常是深度固定的決策樹）組合在一起來集成一個表現較好的模型。抽象地說，模型的訓練過程是對一任意可導目標函數的優化過程。通過反覆地選擇一個指向負梯度方向的函數，該演算法可被看做在函數空間里對目標函數進行優化。因此可以說Gradient Boosting = Gradient Descent + Boosting。

和AdaBoost一樣，Gradient Boosting也是重複選擇一個表現一般的模型並且每次基於先前模型的表現進行調整。不同的是，AdaBoost是通過提升錯分數據點的權重來定位模型的不足而Gradient Boosting是通過算梯度（gradient）來定位模型的不足。因此相比AdaBoost, Gradient Boosting可以使用更多種類的目標函數。

Gradient Boosting for Regression

有一組數據 $(x_1,y_1),...,(x_m,y_m)$ 和一個基礎模型 $F$ 就像你說的我們想要最小化預測值 $F(x_i)$ 和真實值 $y_i$ 之間的square loss。對於任意 $i$ ，使得 $1le i le m$ ，我們稱 $h_i=y_i-F(x_i)$ 為關於 $x_i$ 的殘差。我們可以訓練一個回歸樹 $h$ 來擬合數據組 $(x_1, y_1-F(x_1)),...,(x_m, y_m-F(x_m))$ 。這樣我們就得到了一個更好的模型 $F+h$ ，重複這一過程，我們最終得到了一個讓人滿意的模型。

用回歸樹去擬合殘差其實就是用回歸樹去擬合目標方程關於 $F(x_i)$ 的梯度。

對於任意 $i$ ，使得 $1 le i le m$ ，預測值和真實值之間的square loss為 $(y_i-F(x_i))^2$ ，我們注意到 $underset{F}{mathrm{argmin}} (y-F(x))^2\ = underset{F}{mathrm{argmin}} (y-F(x))^2/2$ , 令 $L(y_i, F(x_i)) = (y_i-F(x_i))^2/2$ , 目標函數 $J = sum_i L(y_i, F(x_i))$ , $J$ 關於 $F(x_i)$ 的偏導數由鏈式法則可得正好是 $F(x_i)-y_i$ ，則 $y_i-F(x_i)$ 恰好是 $y_i-F(x_i) = -frac{partial J}{partial F(x_i)}$ 。因此在這裡用回歸樹擬合殘差實際上就是用回歸樹擬合負梯度（當損失函數不為square loss時殘差並不一定等於負梯度！）。我們實際上是在通過梯度下降法對模型參數進行更新。這樣理解的好處在於我們可以把這一演算法推廣到其它的損失函數上。

圖片來源：Li, Cheng. http://www.chengli.io/tutorials/gradient_boosting.pdf

要注意regression並不一定會用square loss。square loss的優點是便於理解和實現，缺點在於對於異常值它的魯棒性較差，如下圖：

圖片來源：同上。

一個異常值造成的損失由於二次冪而被過分放大，會影響到最後得到模型在測試集上的表現。

因此我們有時候會選擇其它的損失函數，如absolute loss或Huber loss（標紅色星號的數據為異常值）:

圖片來源：同上。

梯度下降法的思想使得我們可以非常輕易地改用不同的損失函數設計Gradient Boosting演算法。另外在使用某些其它損失函數時（如Huber loss），殘差相比負梯度更容易受到異常值的影響。

Gradient Boosting for Classification

基於回歸樹的Gradient Boosting除了回歸問題外還可以做分類問題、排序問題等。

對於分類問題，很多時候我們是要去獲得一個概率分布去逼近真正的概率分布，因此很多時候就會基於log loss來構建目標函數，如KL-divergence或cross entropy。但有時候也可能使用其它損失函數，可以參考一下Loss functions for classification 。

除了損失函數的區別外，分類問題和回歸問題的區別還在於當我有多個類的時候，我可能會訓練多個分類器。比如如果要去識別手寫字母的話，我可能會訓26個分類器來分別去求該手寫字母為A/.../Z的概率。

由於決策樹是非線性的（並且隨著深度的加深非線性越來越強），基於決策樹的GBDT也是非線性的。

AdaBoost V.S. GBDT

最主要的區別在於兩者如何識別模型的問題。AdaBoost用錯分數據點來識別問題，通過調整錯分數據點的權重來改進模型。Gradient Boosting通過負梯度來識別問題，通過計算負梯度來改進模型。

GBDT V.S. LR(Linear Regression? Logistic Regression?)

從決策邊界來說，線性回歸的決策邊界是一條直線，邏輯回歸的決策邊界是一條曲線，而GBDT的決策邊界可能是很多條線。

邏輯回歸演算法在某一數據集上得到的決策邊界。
來源：Andrew Ng在Coursera上機器學習的講義。

GBDT並不一定總是好於線性回歸或邏輯回歸。根據沒有免費的午餐原則，沒有一個演算法是在所有問題上都能好於另一個演算法的。根據奧卡姆剃刀原則，如果GBDT和線性回歸或邏輯回歸在某個問題上表現接近，那麼我們應該選擇相對比較簡單的線性回歸或邏輯回歸。具體選擇哪一個演算法還是要根據實際問題來決定。

參考：

http://www.cs.nyu.edu/~mohri/mls/ml_boosting.pdf
http://www.chengli.io/tutorials/gradient_boosting.pdf

Adaboost is a kind of GBDT

這篇文章講述了boost的發展：

The Evolution of Boosting Algorithms From Machine Learning to Statistical Modelling

https://arxiv.org/pdf/1403.1452.pdf

統計學習方法147倒數第二段（提升樹那一章8.4.2正數第四段），提升樹在處理分類問題的時候，實際上就是AdaBoost的基函數變成普通決策樹；然後，提升樹在處理回歸問題的時候，實際上是擬合上一次模型訓練的一個殘差再訓練一棵樹出來進行Boosting集成；隨後在統計學習方法後面，在梯度提升樹中，實際上提升樹的殘差，是損失函數為平方損失MSE下的特例，這個時候MSE的負梯度就是yi -f(xi)，這一點最高票回答裡面有推。整個過程如果按照統計學習方法的描述裡面就是這樣子的，當然高票回答推公式、推理論，水平更高。