转载自：https://medium.com/@cwchang/gradient-boosting-%E7%B0%A1%E4%BB%8B-f3a578ae7205

在 Boosting 類型的學習演算法裡，Gradient Boosting 是諸多比賽中的常勝軍，這篇文章嘗試簡述其背後的想法，希望能在不涉及過多數學的情況下介紹這個模型。受限於才疏學淺，若有敘述不準確的地方請不吝指正。 

Linear Regression v.s. Gradient Boosting (PC: Ref. [1])

什麼是 Boosting

在機器學習中，Boosting 是一種透過組合一群 Weak Learners、嘗試改進每一次的錯誤、從而獲得一個 Strong Learner 的方法，大致上的核心思想就是「知錯能改的三個臭皮匠勝過一個諸葛亮」。

Weak Learner 指的是「比亂猜好一點」的模型，這種模型的好性質包含：複雜度低、訓練的成本低、不容易 Overfitting，例如 Decision Stump（決策樹墩？），這個模型其實就是把 Decision Tree 的深度限制在一層，可想而知，只能切一刀的 Decision Tree 大概不會太好用，但是它卻滿足 Weak Learner 的性質，能夠快速的訓練、並且做出的預測能夠比亂猜好一些。

當使用 Weak Learner 作為 Boosting 的 Base Learner，我們除了能夠快速的訓練出許多模型來組合外，Weak Learner 的低複雜度也為我們帶來一個好性質：最終組合出的 Strong Learner 能夠對 Overfitting 有良好的抵抗性。

Gradient Boosting

這篇要介紹的 Gradient Boosting 除了 Boosting 一般擁有的性質外，還具備一些好處：

1. Gradient Boosting 可以應用在許多不同的（可微分）Loss Function 上
2. 利用不同的 Loss Function，我們可以處理 Regression / Classification / Ranking 等不同的問題

我們接著先以一個簡單的 Regression 問題作為例子介紹 Gradient Boosting，同樣的概念並不局限於 Regression、可以輕易地推廣到不同的 Loss 及不同的任務上。

以 Regression 為例

假設我們有個任務：在給定的訓練資料上，利用特徵 x 來預測目標值 y。同時，我們手上已有一個基於 Regression Tree 的預測模型 F(x)，我們刻意地限制了它的複雜度以使其能夠扮演一個 Weak Learner 的角色（例如像上述所說的 Decision Stump，限制這棵樹的最大深度為一層），如下表所示：

 

接下來我們想做的事情，是利用這個已知的 F(x)，訓練出一個更好的預測模型，但在這個過程中，我們必須遵守下面兩條遊戲規則：

1. 我們不能對這個模型做出更動，也就是把 F(x) 當做一個黑盒子，只使用它的輸出值而不對其內部的演算法或參數做任何修改。
2. 我們可以另外利用 Regression Tree 再訓練一個模型 h(x)，加在原先的 F(x) 上，並期望 F(x)+h(x) 能比原本的模型 F(x) 更好。

為了做出「更好的預測」，我們首先利用 Mean Squared Errors (MSE) 來量化模型的優劣，在這個例子中，F(x) 的 MSE 是 62.74。

接著，我們還可以計算 F(x) 跟真實資料之間的差距 — Residual。而「更好的預測」除了代表更小的 MSE 外，在某種程度上也是希望新的模型在每一個不同 x 上的犯的錯（Residual）能夠變小 — 在哪裡跌倒就在哪裡爬起來！下面的表格把 F(x) 在每一個 x 上的預測以及其 Residual 列了出來：

根據上述的兩條規則，在計算出 Residual 之後，一個直覺的做法是利用 Regression Tree 來訓練一個能夠預測 Residual 的 h(x)，也就是使
h(x)≈y−F(x)；假使我們的 Regression Tree 能夠把這個任務做得還不錯，那麼根據我們給 h(x) 設定的目標，我們應該能夠得到 F(x)+h(x)≈y。我們繼續使用上述的例子驗證一下：

而在 MSE 上，新的模型 F(x)+h(x) 的 MSE 是 32.82，相較於原先的 62.74， 的確是一個更好的結果；同時，我們也能看到在大部分的 x 上，F(x)+h(x) 所犯的錯確實變小了。

至此，Gradient Boosting 背後的「直觀想法」已經差不多了：

1. 利用 F(x) 的 Residual 作為目標，訓練 h(x)
2. 利用 F(x)+h(x) 的 Residual 作為目標，訓練出 m(x)
3. 利用 F(x)+h(x)+m(x) 的 Residual 作為目標，再訓練出新的 n(x)
4. …重複多次…
5. 最後 F(x)+h(x)+m(x)+n(x)+… 就是我們的最終模型

此外，我們可以輕易地把上述的例子拓展至多維度 Features 的 Data 上、或是我們也能抽換掉 Regression Tree 改用其他的 Base Learner。

Residual 和 Squared Error 的關係

上述的例子雖然展示了 Gradient Boosting 的簡易做法，卻沒有把兩件事情說清楚：

1. 為什麼我們明明想優化的是 MSE 卻著手於 Residual，除了「知錯能改」這樣的直覺外，有沒有能數學化的理由？
2. 既然我們用的是 Residual，為什麼不叫 Residual Boosting 而要叫 Gradient Boosting，說好的 Gradient 呢？

在回答這兩個問題前，我們先對要優化的 MSE Loss 稍做手腳，首先把 Squared Error 除以二：

L(y, F(x))= (y−F(x))²/2

接著對 L(y, F(x)) 中的 F(x) 做偏微分，得到

∂L/∂F = −(y−F)

也就是說，在使用 MSE Loss 的情況下，Residual 正是 Loss 對 F 的 Gradient 取負號（在 x 處取值）。

在繼續說下去之前，我們稍微岔開話題介紹一下 Gradient Descent。

Gradient Descent 101

Gradient Descent 是一個在最佳化領域相當常見的迭代方法，用於尋找「可微分函數」的局部最小值，它的做法是這樣的：

1. 假設我們要最佳化的目標函數是 L(x)，例如要找 L(x) 的最小值
2. 隨機選取一個起始點，例如從 a 出發
3. 從 a 沿著 −∇L(a)走一小步，即 a−γ∇L(a)
   此處的 ∇L(a) 代表的是 L 在 a 上的 Gradient
   那麼對於一個夠小的 γ，此處的函數值將小於等於 L(a)
4. 換句話說，對於一個夠小的 γ，我們有
   L(a)≥L(a−γ∇L(a))
5. 令 a−γ∇L(a) 為新的出發點，重複 3–4
6. 根據這樣的方法，從 a 開始一步一步走（迭代），在 γ 選取適當的情況下，我們可以找到 L(x) 的局部最小值

在許多機器學習的演算法中，Gradient Descent 扮演的角色是迭代地找到最好的參數：假設需要優化損失函數 L(θ) 是參數 θ 的函數，那麼對於某些品性良好的 L(θ)，我們只需要隨機地找一個出發點 θ，並沿著 Gradient 的方向持續更新 θ，便能降低損失函數的值。而這個「沿著 Gradient 的方向更新 θ 」的過程，其實也就是我們常說的 Training。

Gradient Descent 與 Gradient Boosting

了解 Gradient Descent 可以用於「優化」目標函數的值之後，我們就可以嘗試回答先前提到的問題：「為何用 Residual 來優化 MSE？」、「Gradient Boosting 的 Gradient 是從哪來的？」。

前面提到，Residual 正是 Loss 對 F 的 Gradient 取負號：

y−F=−∂L/∂F

如果我們把 H(x)=F(x)+h(x) 視作對 F(x) 的「更新」，那麼根據 h(x)≈y−F(x)=−∂L/∂F，其實我們做的正是上述 Gradient Descent 中的第三步：

H(x)=F(x)−γ∂L/∂F,
where γ=1

這就回答了為什麼我們能夠透過 Fit Residual 來優化 MSE：因為從 F(x) 沿著這個方向走得到的 H(x) 能夠降低損失函數 MSE 的值。

在一般的機器學習演算法中，我們透過對演算法的參數 θ 做 Gradient Descent 以學出能使「損失函數」達到局部最小值的參數。而在 Gradient Boosting 中，我們的參數其實就是模型的預測值 F(x)，並且我們透過 Base Learner 來學出近似的−∂L/∂F。

當我們從 Gradient Descent 的角度來看 Residual 之後，事情就變得有趣一些了：我們知道 Residual 是 Squared Loss 的 Gradient，那麼如果衡量模型優劣的損失函數被換掉了，只要它還是滿足 Gradient Descent 需要的好性質，那麼我們一樣可以計算這個 Loss 對 F(x) 的 Gradient，並讓這個 Gradient 作為 Base Learner 的學習目標。這也是為什麼不叫 Residual Boosting 而叫 Gradient Boosting — 只是在 MSE 的情況下，負 Gradient 剛好是 Residual 而已。

寫在後面

1. 在第一個例子中的 F(x)+h(x)+m(x)+… 這樣能夠加在一起的模型，一般我們稱之 Additive Models
2. Gradient Descent 中控制步伐大小的 γ 稱作 Learning Rate，不見得要用 1 來 Update，只是在我們的例子中用 1 比較方便而已
3. 上述的 Gradient Boosting 只是一個雛形，實際上我們還能透過使用 Adaptive Learning Rate、或是類似 Random Forest 使用的 Data Subsampling 來進一步優化這個演算法。

---

參考資料

1. A Gentle Introduction to Gradient Boosting
2. A Kaggle Master Explains Gradient Boosting
3. Machine Learning Techniques. Lecture 11: Gradient Boosted Decision Tree