梯度提升技術

梯度提升，亦稱作梯度增強，是一種用於回歸和分類問題的機器學習技術。其產生的預測模型是弱預測模型的集成，如採用典型的決策樹作為弱預測模型，這時則為梯度提升樹（GBT或GBDT）。像其他提升方法一樣，它以分階段的方式構建模型，但它通過允許對任意可微分損失函數進行優化作為對一般提升方法的推廣。

梯度提升技術源自於Leo Breiman於1997年時將提升方法用於優化算法的觀察。隨後Jerome H. Friedman於1999年時提出了顯式回歸梯度增強算法。Llew Mason、Jonathan Baxter、Peter Bartlett和Marcus Frean則針對梯度提升在一般的函數空間的運用進行研究，並於1999年在研討會發表之後，同年正式發表了論文。該論文介紹了將提升算法看作「函數空間上的梯度下降迭代」算法的觀點。也就是將其視為通過迭代地選擇指向負梯度方向的函數（弱預測模型），來優化函數空間上的成本函數的算法。這種將提升視為函數梯度的觀點，導致了提升算法被運用於回歸和分類之外的其他機器學習和統計領域的後續發展。

非正式介紹

（本節遵循Li對梯度增強的說明。）

與其他增強方法一樣，梯度增強以迭代方式將弱的「學習器」組合為一個強學習器。最簡單的解釋是在最小二乘回歸中，通過最小化均方誤差 ${\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}$ ，「教」模型$F$預測實數值${\hat {y}}=F(x)$。

在梯度提升的每個階段 $m$, $1\leq m\leq M$, 假設已經有一個不太完美的模型 $F_{m}$ (最開始時只是一個預測輸出變量 y 均值的模型)。 梯度提升算法通過在當前模型 $F_{m}$ 增加一個新的估計量 h 得到一個更好的模型: $F_{m+1}(x)=F_{m}(x)+h(x)$. 為了求得 $h$, 梯度提升基於以下觀察：一個完美的 h 可以完美預測當前不完美模型$F_{m}$的殘差，即滿足，

$F_{m+1}(x)=F_{m}(x)+h(x)=y$

或者，等效地有，

$h(x)=y-F_{m}(x)$.

因此，梯度提升通過擬合殘差 $y-F_{m}(x)$得到 h 。和其他提升方法的變體一樣, $F_{m+1}$ 通過糾正 $F_{m}$的誤差變得更完美。 這個想法可以擴展到均方誤差損失之外的任意損失函數，甚至擴展到分類與排序問題，只要觀察到以下一點：模型的殘差 $y-F_{m}(x)$就是均方損失函數${\frac {1}{2}}(y-F(x))^{2}$關於$F(x)$的負梯度。因此，梯度提升其實是一種 梯度下降算法，可以代入除了均方損失之外的不同的損失函數，得到不同的梯度。

算法

在許多有監督學習問題中，一個輸出變量y和一個輸入變量x通過聯合概率分布$P(x,y)$描述 。給定訓練集$\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}$，目的是在所有具有給定形式的函數$F(x)$中找到一個${\hat {F}}(x)$使某些指定損失函數$L(y,F(x))$的期望值達到最小：

${\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]$.

梯度提升方法通過某一類${\mathcal {H}}$中弱學習器（或稱基學習器）$h_{i}(x)$帶權重和的形式來表示對實值變量y做出估計的${\hat {F}}(x)$:

${\hat {F}}(x)=\sum _{i=1}^{M}\gamma _{i}h_{i}(x)+{\mbox{const}}$.

根據經驗風險最小化原理，該方法試圖找到一個近似${\hat {F}}(x)$可以最大程度地減少訓練集上損失函數的平均值，即，最小化經驗風險。它是從一個由常數函數組成的模型$F_{0}(x)$開始 ，並以貪心的方式逐步擴展：

$F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}$,

$F_{m}(x)=F_{m-1}(x)+{\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\right]$,

上式$h_{m}\in {\mathcal {H}}$是基學習器。

不幸的是，通常在每個步驟中為任意損失函數L選擇最佳函數h是計算上不可行的優化問題。因此，我們將方法局限於問題的簡化版本。

這個想法是對這個最小化問題（函數梯度下降）應用梯度下降步驟。如果我們考慮連續情況，即${\mathcal {H}}$是上的任意微分函數的集合$\mathbb {R}$ ，我們將根據以下方程式更新模型

$F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))},$

$\gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}},$

式子中，對於$i\in \{1,..,m\}$是關於函數$F_{i}$求導，$\gamma _{m}$是步長。 但是在離散情況下，即${\mathcal {H}}$如果是有限的，我們選擇最接近L梯度的候選函數h ，然後可以根據上述等式通過線搜索來計算係數γ。請注意，這種方法是一種啟發式方法，因此不能給出給定問題的精確解決方案，而是一種近似方法。 在偽代碼中，通用梯度增強方法是：

Input: training set $\{(x_{i},y_{i})\}_{i=1}^{n},$ a differentiable loss function $L(y,F(x)),$ number of iterations M.

Algorithm:

1. Initialize model with a constant value:

   $F_{0}(x)={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L(y_{i},\gamma ).$

2. For m = 1 to M:
   1. Compute so-called pseudo-residuals:

      $r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\mbox{for }}i=1,\ldots ,n.$

   2. Fit a base learner (or weak learner, e.g. tree) $h_{m}(x)$ to pseudo-residuals, i.e. train it using the training set $\{(x_{i},r_{im})\}_{i=1}^{n}$.
   3. Compute multiplier $\gamma _{m}$ by solving the following one-dimensional optimization problem:

      $\gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})\right).$

   4. Update the model:

      $F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).$

3. Output $F_{M}(x).$

梯度樹增強

梯度提升通常與固定大小的決策樹 （尤其是CART樹）一起用作基礎學習者。 對於這種特殊情況，Friedman提出了對梯度增強方法的改進，以提高每個基礎學習者的適應質量。

第m步的通用梯度提升將適合決策樹$h_{m}(x)$偽殘留物。 讓$J_{m}$是它的葉子數。 樹將輸入空間劃分為$J_{m}$不相交的區域$R_{1m},\ldots ,R_{J_{m}m}$並預測每個區域的恆定值。 使用指標符號 ，輸出$h_{m}(x)$輸入x可以寫為和：

$h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),$

這裡$b_{jm}$是該區域中預測的值$R_{jm}$。

然後係數$b_{jm}$乘以一些值$\gamma _{m}$ ，使用線搜索進行選擇，以最大程度地減少損失函數，並按以下方式更新模型：

$F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).$

弗里德曼（Friedman）建議修改此算法，以便選擇一個單獨的最佳值$\gamma _{jm}$每個樹的區域，而不是單個$\gamma _{m}$為整棵樹。 他稱修改後的算法為「 TreeBoost」。 係數$b_{jm}$然後可以簡單地丟棄樹擬合過程中的數據，模型更新規則變為：

$F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).$

樹木大小

$J$ （樹中終端節點的數量）是該方法的參數，可以針對手頭的數據集進行調整。 它控制模型中變量之間允許的最大交互級別。 用$J=2$ （ 決策樹樁 ），不允許變量之間進行交互。 用$J=3$該模型可能包括多達兩個變量之間的相互作用的影響，依此類推。

Hastie等人評論通常$4\leq J\leq 8$對於提升效果很好，結果對選擇$J$在這個範圍內$J=2$不足以用於許多應用程序，並且$J>10$不太可能是必需的。

正則化

過於緊密地擬合訓練集可能導致模型的泛化能力下降。 幾種所謂的正則化技術通過限制擬合過程來減少這種過度擬合的效果。

一個自然的正則化參數是梯度提升迭代的次數M（即，當基礎學習者是決策樹時，模型中的樹的數量）。M的增加會減少訓練集上的誤差，但將其設置得過高可能會導致過度擬合。 通常通過監視單獨的驗證數據集上的預測誤差來選擇M的最佳值。 除了控制M外，還使用其他幾種正則化技術。

另一個正則化參數是樹的深度。 該值越高，模型越可能適合訓練數據。

收縮率

梯度增強方法的一個重要部分是通過收縮進行正則化，它包括如下修改更新規則：

$F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,$

哪裡參數 $\nu$被稱為「學習率」。

根據經驗發現，使用較小的學習率 （例如$\nu <0.1$ ）在不縮小（而不縮小）的情況下，極大地提高了模型的泛化能力$\nu =1$ ）。然而，這是以在訓練和查詢期間增加計算時間為代價的：較低的學習率需要更多的迭代。

隨機梯度增強

引入梯度增強後不久，Friedman在Breiman的bootstrap聚合 （「裝袋」）方法的啟發下 ，對該算法進行了較小的修改。具體來說，他提出在算法的每次迭代中，基礎學習者都應適合隨機抽取的訓練集的子樣本，而無需替換。弗里德曼（Friedman）觀察到，通過這種修改，梯度增強的精度有了顯着提高。

子樣本大小是某個常數$f$訓練集的大小。 什麼時候$f=1$ ，該算法是確定性的，並且與上述算法相同。 較小的值$f$將隨機性引入算法中，並防止過度擬合 ，作為一種正則化 。 該算法也變得更快，因為回歸樹必須在每次迭代時都適合較小的數據集。弗里德曼獲得了$0.5\leq f\leq 0.8$在中小型訓練集上可獲得良好的結果。 因此， $f$通常將其設置為0.5，這意味着訓練集的一半用於構建每個基礎學習者。

同樣，像在裝袋中一樣，子採樣允許通過評估那些在下一個基礎學習者的構建中未使用的觀察值的預測來定義預測性能改進的袋外誤差 。 預算外的估計有助於避免需要獨立的驗證數據集，但通常會低估實際性能的提高和最佳迭代次數。

葉子中的觀察數

梯度樹增強實現通常還通過限制樹的終端節點中的最小觀察次數來使用正則化（此參數在R gbm軟件包中命名為n.minobsinnode）。通過忽略導致導致節點包含少於此訓練集實例數量的節點的任何拆分，在樹構建過程中使用它。

施加此限制有助於減少葉子預測的差異。

懲罰樹木的複雜性

用於梯度增強樹的另一種有用的正則化技術是懲罰學習模型的模型複雜性。 模型複雜度可以定義為學習樹中葉子的比例。 損失和模型複雜性的聯合優化對應於後修剪算法，該算法可刪除未能將損失降低閾值的分支。 其他種類的正規化，例如$\ell _{2}$還可以添加對葉子值的懲罰以避免過度擬合 。

用法

梯度提升可以用於學習排名 。 商業網絡搜索引擎Yahoo 和Yandex 在其機器學習的排名引擎中使用了梯度增強的變體。

名字

該方法有多種名稱。弗里德曼（Friedman）將他的回歸技術稱為「梯度提升機」（GBM）。 梅森，巴克斯特等。將廣義的算法抽象類描述為「功能梯度提升」。弗里德曼（Friedman）等人。將梯度提升模型的進展描述為多重可加回歸樹（MART）；Elith等。將這種方法描述為「增強回歸樹」（BRT）。

R的一種流行的開源實現將其稱為「通用提升模型」。但是，使用BRT擴展這項工作的軟件包。 Salford Systems的商業實現使用名稱「 Multiple Additive Regression Trees」（MART）和TreeNet，兩者均為商標。  

參見

• AdaBoost
• 隨機森林
• XGBoost
• CatBoost
• 決策樹學習

外部連結

• 如何解釋梯度提升 （頁面存檔備份，存於網際網路檔案館）
• 梯度增強回歸樹 （頁面存檔備份，存於網際網路檔案館）