GBM算法的歷史和原理

編者按：DM Labs創(chuàng)始人、DIGINETICA首席數(shù)據(jù)官Alexey Natekin講解了梯度提升算法的原理。

大家好！目前為止，我們已經(jīng)介紹了從探索性分析到時序分析在內(nèi)的9個主題。今天我們將介紹最流行、最實(shí)用的機(jī)器學(xué)習(xí)算法之一：梯度提升。

概覽

導(dǎo)言和梯度提升的歷史

GBM算法

損失函數(shù)

相關(guān)資源

導(dǎo)言和梯度提升的歷史

在機(jī)器學(xué)習(xí)領(lǐng)域，梯度提升屬于人盡皆知的技術(shù)。許多數(shù)據(jù)科學(xué)家的工具箱中收錄了這一技術(shù)，因?yàn)樗谌魏谓o定的（未知）問題上都能得到很好的結(jié)果。

此外，XGBoost是ML競賽冠軍的常用配方。它是如此流行，以至于堆疊XGBoost的想法都成了meme。而且，梯度提升也是許多推薦系統(tǒng)的重要組成部分；有時它甚至成為了品牌。讓我們看下梯度提升的歷史和發(fā)展。

梯度提升源于這樣一個問題：能從大量相對弱小、簡單的模型得到一個強(qiáng)力模型嗎？這里“弱小模型”指的不是決策樹這樣簡單基本的模型，而是精確度表現(xiàn)糟糕的模型，糟糕到比隨機(jī)猜測好一點(diǎn)的程度。

研究發(fā)現(xiàn)，在數(shù)學(xué)上而言，這一問題的答案是肯定的，但開發(fā)實(shí)際可用的算法（例如，AdaBoost）花了好幾年。這些算法采用了貪婪的做法：首先，通過重新加權(quán)輸入數(shù)據(jù)創(chuàng)建簡單模型（基本算法）的線性組合；接著，基于之前錯誤預(yù)測的對象（給予更大權(quán)重）創(chuàng)建模型（通常是決策樹）。

很多機(jī)器學(xué)習(xí)課程討論了AdaBoost——GBM的祖先。然而，現(xiàn)在看來，AdaBoost不過是GBM的一個特定變體。

這一算法本身定義權(quán)重的直覺很清晰，通過可視化的方法很好解讀。讓我們查看下面的玩具分類問題，我們將在AdaBoost的每次迭代中在深度為1的樹間分割數(shù)據(jù)。

數(shù)據(jù)點(diǎn)的大小對應(yīng)其權(quán)重，為不正確的預(yù)測分配。在每次迭代中，我們看到因?yàn)槲茨苷_分類權(quán)重增加了。然而，如果我們進(jìn)行加權(quán)投票，就能得到正確的分類：

下面是一個更詳細(xì)的AdaBoost的例子，我們看到，隨著迭代的進(jìn)行，權(quán)重增加了，特別是在分類的邊界處。

AdaBoost效果不錯，但為何這一算法如此成功卻缺乏解釋，這正是一些疑惑產(chǎn)生的源頭。有些人認(rèn)為AdaBoost是一個超級算法，一枚銀彈，但另一些人顧慮重重，相信AdaBoost只不過是過擬合。

過擬合問題確實(shí)存在，特別是當(dāng)數(shù)據(jù)具有強(qiáng)離群值時。因此，AdaBoost在這類問題上的表現(xiàn)不穩(wěn)定。幸運(yùn)的是，一些斯坦福統(tǒng)計學(xué)教授開始研究這一算法（這些教授發(fā)明了Lasso、Elastic Net、隨機(jī)森林）。1999年，Jerome Friedman推廣了提升算法——梯度提升（機(jī)器），簡稱GBM。Friedman的這項(xiàng)工作為采用提升優(yōu)化這個一般方法的許多算法提供了統(tǒng)計學(xué)基礎(chǔ)。

CART，bootstrap在內(nèi)的許多算法源自斯坦福統(tǒng)計學(xué)部門。這些算法的提出，為他們在未來的教科書中留下了位置。這些算法非常實(shí)用，而一些最近的工作尚未廣泛普及。例如，glinternet。

網(wǎng)上沒有太多Friedman的視頻，不過，有一個非常有趣的訪談，關(guān)于如何提出CART，以及CART如何解決統(tǒng)計學(xué)問題（很像今天的數(shù)據(jù)分析和數(shù)據(jù)科學(xué)）：https://youtu.be/8hupHmBVvb0 另外推薦Hastie的講座：https://youtu.be/zBk3PK3g-Fc，我們今天日常使用的很多方法的創(chuàng)造者對數(shù)據(jù)分析的回顧。

GBM的歷史

GBM從提出到成為數(shù)據(jù)科學(xué)工具箱的必備組件花了十多年。GBM的擴(kuò)展用于不同統(tǒng)計學(xué)問題：GBM模型加強(qiáng)版GLMboost、GAMboost，用于存活曲線的CoxBoost，用于排序的RankBoost和LambdaMART。

GBM的許多實(shí)現(xiàn)以不同的名字出現(xiàn)在不同的平臺上：隨機(jī)GBM，GBDT（梯度提升決策樹），GBRT（梯度提升回歸樹），MART（多重累加回歸樹）…… 此外，由于ML社區(qū)各自為營，很難追蹤梯度提升變得多么普及。

同時，梯度提升大量用于搜索排序。搜索排序問題可以基于懲罰輸出順序誤差的損失函數(shù)重新表述，從而便于直接插入GBM。AltaVista是第一個在搜索排序中引入梯度提升的公司之一。很快，Yahoo、Yandex、Bing等也采用了這一想法。自此之后，梯度提升不再僅僅用于研究之中，同時成為業(yè)界的核心技術(shù)之一。

ML競賽，特別是Kaggle，在梯度提升的流行中起到了主要作用。Kaggle為研究人員提供了一個可以和世紀(jì)各地大量參與者一起競爭數(shù)學(xué)科學(xué)問題的公共平臺。在Kaggle上，可以在真實(shí)數(shù)據(jù)上測試新算法，這就給了算法“閃耀”的機(jī)會。Kaggle提供了模型在不同競賽數(shù)據(jù)集上的表現(xiàn)的完整信息。這正是梯度提升用于Kaggle競賽后所發(fā)生的事（自2011年以來，Kaggle冠軍的訪談中大多提到自己使用了梯度提升）。XGBoost庫出現(xiàn)后迅速流行開來。XGBoost并不是一個新穎獨(dú)特的算法；它只是經(jīng)典GBM的一個極其高效的實(shí)現(xiàn)（加上了一些啟發(fā)式算法）。

GBM的經(jīng)歷也是今天許多ML算法的經(jīng)歷：初次出現(xiàn)之后，從數(shù)學(xué)問題和算法工藝到成功的實(shí)踐應(yīng)用和大規(guī)模使用花了許多年。

GBM算法

我們將求解一個一般的監(jiān)督學(xué)習(xí)設(shè)定下的函數(shù)逼近問題。特征集記為X，目標(biāo)變量記為y，我們需要重建y = f(x)這一依賴。我們通過逼近f(x)重建這一依賴，基于損失函數(shù)L(y, f)判斷哪個逼近較好：

在此階段，我們對f(x)的種類、逼近模型、目標(biāo)變量的分布不做任何假定。我們只期望L(y, f)是可微的。最小化數(shù)據(jù)損失（基于具體數(shù)據(jù)集的總體均值）的表達(dá)式為：

不幸的是，這樣的函數(shù)不僅數(shù)目很多，而且函數(shù)空間有著無窮維。因此，需要限制搜索空間至某些函數(shù)家族。這大大簡化了目標(biāo)，因?yàn)槲覀儸F(xiàn)在只需解決參數(shù)值的優(yōu)化問題。

查找最佳參數(shù)經(jīng)常不存在簡單的解析解，我們通常迭代地逼近參數(shù)。我們在一開始寫下經(jīng)驗(yàn)損失函數(shù)，讓我們可以基于數(shù)據(jù)演算參數(shù)，并寫下M次迭代后的參數(shù)逼近之和：

接著，我們只需找到一個合適的最小化上式的迭代算法。梯度下降是最簡單、最常用的選項(xiàng)。我們定義損失函數(shù)在當(dāng)前逼近上的梯度，然后在迭代演算中減去梯度。最終我們只需初始化第一次逼近，并選擇迭代次數(shù)M。

函數(shù)梯度下降

讓我們想象一下，我們可以在函數(shù)空間中進(jìn)行優(yōu)化，迭代搜索函數(shù)逼近本身。我們將逼近表述為增量改進(jìn)之和，每個改進(jìn)都是一個函數(shù)。

目前為止沒有實(shí)際發(fā)生什么事；我們只是決定并不以具有大量參數(shù)的巨大模型（例如，神經(jīng)網(wǎng)絡(luò)）的方式搜索逼近，而是以函數(shù)之和的方式搜索逼近，假想我們在函數(shù)空間中移動。

為了完成這一任務(wù)，我們需要限制搜索空間至某個函數(shù)家族：

在迭代的每一步，我們需要選擇最優(yōu)參數(shù)ρ ∈ ?。第t步需要求解的問題如下：

這是關(guān)鍵之處。我們以一般形式定義了所有的目標(biāo)，假裝我們可以為任意種類的損失函數(shù)L(y, f(x, θ))定義任意種類的模型h(x, θ)。在實(shí)踐中，這極為困難。幸運(yùn)的是，有一種簡單方法可以解決這一任務(wù)。

一旦我們知道了損失函數(shù)的梯度表達(dá)式，我們就可以在數(shù)據(jù)上計算相應(yīng)的值。這樣，我們可以訓(xùn)練模型，使其預(yù)測和梯度（取反）更相關(guān)。換句話說，我們將基于預(yù)測和這些殘差的最小平方差糾正預(yù)測。因此，第t步最終轉(zhuǎn)化為以下問題：

Friedman的經(jīng)典GBM算法

下面我們講下Jerome Friedman在1999年提出的經(jīng)典GBM算法。它是一個具備以下要素的監(jiān)督算法：

數(shù)據(jù)集{(xi, yi)}i=1,…,n

迭代數(shù)M

梯度定義良好的損失函數(shù)L(y, f)

基礎(chǔ)算法對應(yīng)的函數(shù)家族h(x, θ)及其訓(xùn)練過程

h(x, θ)的其他超參數(shù)（例如，決策樹的深度）

還剩下初次逼近f0(x)沒講。出于簡單性，初次逼近使用一個常數(shù)γ。這個常數(shù)值γ和最優(yōu)參數(shù)ρ，均通過二元搜索或其他基于初始損失函數(shù)（非梯度）的線搜索算法得出。

GBM算法過程如下：

使用常數(shù)值初始化GBM：

每次迭代t = 1, …, M，重復(fù)以上逼近過程；

在i = 1, …, n上計算偽殘差rt：

以偽殘差{(xi, rit)}i=1,…,n上的回歸作為基礎(chǔ)算法ht(x)

據(jù)ht(x)的初始損失函數(shù)找出最優(yōu)參數(shù)ρt：

保存

更新當(dāng)前逼近：

組成最終GBM模型：

征服Kaggle和全世界

GBM如何工作

讓我們通過一個例子演示下GBM是如何工作的。在這個玩具示例中，我們需要重建以下函數(shù)：

這是一個實(shí)數(shù)值的回歸問題，所以我們將選擇均方誤差損失函數(shù)。我們將生成300對觀測，然后通過深度為2的決策樹逼近它們。羅列下使用GBM所需的要素：

玩具數(shù)據(jù) {(xi, yi)}i=1,…,300?

迭代數(shù) M = 3 ?

均方誤差損失函數(shù) L(y,f) = (y-f)2?

L(y,f)（L2損失）的梯度不過是殘差r = (y-f) ?

基礎(chǔ)算法h(x)為決策樹 ?

決策樹的超參數(shù)：樹深等于2 ?

就均方誤差而言，γ和ρt的初始化很簡單。我們初始化GBM時將所有參數(shù)ρt設(shè)為1，γ據(jù)下式確定：

我們運(yùn)行GBM然后繪制兩種圖形：當(dāng)前逼近（藍(lán)色）和在偽殘差上構(gòu)建的每棵樹（綠色）。

從上圖我們可以看到，我們的決策樹在第二次迭代時恢復(fù)了函數(shù)的基本形式。然而，第一次迭代時算法只創(chuàng)建了函數(shù)的“最左部分”（x ∈ [-5, -4]）。這是因?yàn)槲覀兊臎Q策樹不具備足夠的深度一下子創(chuàng)建對稱分支，所以它首先關(guān)注誤差較大的最左部分。

剩下的過程不出我們的意料——每一步的偽殘差下降了，隨著迭代的進(jìn)行，GBM越來越好地逼近原函數(shù)。然而，決策樹的構(gòu)造決定了它無法逼近一個連續(xù)函數(shù)，這意味著在這個例子中GBM的效果不是很理想。如果你想以可視化的方式試驗(yàn)GBM函數(shù)逼近，可以使用Brilliantly wrong提供的工具：http://arogozhnikov.github.io/2016/06/24/gradient_boosting_explained.html

損失函數(shù)

如果我們想要求解一個分類問題，而不是回歸問題，那需要做什么變動？只需選擇一個合適的損失函數(shù)L(y,f)。正是這一最重要的高層的契機(jī)，決定了我們將如何優(yōu)化，以及我們期望最終的模型將具有哪些特性。

我們并不需要自行發(fā)明這些——研究人員已經(jīng)替我們做了?，F(xiàn)在我們將探索用于最常見的兩種目標(biāo)的損失函數(shù)：回歸和二元分類。

回歸損失函數(shù)

最常用的選項(xiàng)為：

L(y,f) = (y-f)2，即L2損失或高斯損失。這一經(jīng)典的條件平均數(shù)是最簡單也是最常見的情形。如果我們不具備額外信息，也不要求模型的魯棒性，那么可以使用高斯損失。

L(y,f) = |y-f|，即L1損失或拉普拉斯損失。事實(shí)上它定義了條件中位數(shù)。如我們所知，中位數(shù)對離群值的魯棒性更好，所以這一損失函數(shù)在某些情形下表現(xiàn)更好。對大偏差的懲罰不像L2那么大。

Lq損失或分位數(shù)損失：

其中α ∈ (0,1). Lq使用分位數(shù)而不是中位數(shù)，例如，α = 0.75. 如下圖所示，這一函數(shù)是不對稱的，對定義的分位數(shù)右側(cè)的觀測懲罰力度更大。

讓我們試驗(yàn)下Lq的效果。目標(biāo)是恢復(fù)余弦的條件75%分位數(shù)。列出GBM所需要素：

玩具數(shù)據(jù) {(xi, yi)}i=1,…,300 ?

迭代數(shù) M = 3 ?

損失函數(shù) L0.75(y,f) ?

L0.75(y,f)的梯度 ?

基礎(chǔ)算法h(x)為決策樹 ?

決策樹的超參數(shù)：樹深等于2 ?

初次逼近將使用所需的y的分位，但我們并不知道最佳參數(shù)該取什么值，所以我們將使用標(biāo)準(zhǔn)的線搜索。

結(jié)果等價于L2損失加上約0.135的偏置。但是如果我們使用的是90%分位數(shù)的話，那我們就不會有足夠的數(shù)據(jù)了（失衡分類）。當(dāng)我們處理非標(biāo)準(zhǔn)問題時，需要記住這一點(diǎn)。

人們?yōu)榛貧w任務(wù)開發(fā)了許多損失函數(shù)。例如，Huber損失函數(shù)，離群值較少時，和L2類似，但超出定義的閾值后，轉(zhuǎn)變?yōu)長1，從而降低離群值的影響。

下面是一個例子，數(shù)據(jù)生成自函數(shù)y = sin(x) / x，加上噪聲（正態(tài)分布和伯努利分布的混合分布）。

在這個例子中，我們使用樣條作為基礎(chǔ)算法。你看，梯度提升并不總是需要使用決策樹的。

上圖很清楚地顯示了L2、L1、Huber損失的區(qū)別。如果我們?yōu)镠uber損失選擇最優(yōu)的參數(shù)，可以得到最佳的逼近。

不幸的是，流行的庫/軟件包中，只有很少支持Huber損失；h2o支持，XGBoost不支持。Huber損失和條件expectiles有關(guān)——相對而言更奇異，但仍然值得了解的知識。

分類損失函數(shù)

現(xiàn)在讓我們看下二元分類問題。技術(shù)上說，我們有可能基于L2回歸解決這一問題，但這不是正規(guī)做法。

目標(biāo)變量的分布（y ∈ {?1,1}）需要我們使用對數(shù)似然，所以我們需要不同的損失函數(shù)。最常見的選擇為：

L(y,f) = log(1 + exp(?2yf))，即邏輯損失或伯努利損失。這個損失函數(shù)有一個有趣的性質(zhì)，它甚至?xí)土P正確預(yù)測的分類——不僅優(yōu)化損失，同時使分類分得更開。

L(y,f) = exp(-yf)，即AdaBoost損失。使用該損失函數(shù)的AdaBoost等價于GBM。從概念上講，這個函數(shù)和邏輯損失很相似，但對錯誤預(yù)測有更重的指數(shù)懲罰。

讓我們生成新的分類問題的玩具數(shù)據(jù)。我們將使用前面提到的加噪余弦作為基礎(chǔ)，并使用符號函數(shù)得到目標(biāo)變量的分類。我們的玩具數(shù)據(jù)如下圖所示（加入了抖動噪聲）：

我們將使用邏輯損失。讓我們再一次羅列GBM的要素：

玩具數(shù)據(jù) {(xi, yi)}i=1,…,300, y ∈ {?1,1} ?

迭代數(shù) M = 3 ?

損失函數(shù)為邏輯損失，梯度計算方法見下 ?

基礎(chǔ)算法h(x)為決策樹 ?

決策樹的超參數(shù)：樹深等于2 ?

邏輯損失梯度計算

這次，算法的初始化要困難一點(diǎn)。首先，我們的分類并不均衡（63%對37%）。其次，損失函數(shù)的初始化沒有已知的解析公式，所以我們需要通過搜索解決：

我們的最優(yōu)初始逼近在-0.273左右。你可能猜想過它應(yīng)該是負(fù)值，因?yàn)轭A(yù)測所有項(xiàng)為最流行的分類是最有利的，但沒有求出精確值的公式?，F(xiàn)在我們終于可以開始GBM過程了：

算法成功恢復(fù)了分類的分隔。你可以看到“低部”是如何分開的，因?yàn)闆Q策樹對負(fù)分類（-1）的正確預(yù)測更有信心，也可以看到模型如何擬合混合分類。很明顯，我們得到了大量正確分類的觀測，一些誤差較大的觀測則是數(shù)據(jù)中的噪聲所致。

權(quán)重

有時候，我們會碰到想要使用更特定的損失函數(shù)的情形。例如，在財經(jīng)時序數(shù)據(jù)上，我們可能需要給時序中的大變動更大的權(quán)重；在離網(wǎng)率預(yù)測問題中，預(yù)測高LTV（客戶未來會帶來多少利潤）的客戶的離網(wǎng)率更有用。

統(tǒng)計學(xué)戰(zhàn)士可能想要自己發(fā)明損失函數(shù)，寫下它的梯度（包括海森矩陣），并仔細(xì)檢查這一函數(shù)是否滿足需要具備的性質(zhì)。然而，有很大的幾率會在某處犯下錯誤，導(dǎo)致計算困難，花費(fèi)過量時間排錯。

有鑒于此，人們提出了一種非常簡單的做法（實(shí)踐中很少有人記得）：使用權(quán)重分配函數(shù)加權(quán)觀測。最簡單的一個例子是為了平衡分類加上的權(quán)重。一般來說，如果我們知道數(shù)據(jù)的某個子集（輸入變量和目標(biāo)變量）對我們的模型更重要，那么我們可以直接給它們分配較大的權(quán)重w(x, y)。

權(quán)重需滿足以下條件：

權(quán)重能夠顯著降低花在為當(dāng)前任務(wù)調(diào)整損失函數(shù)上的時間，并鼓勵你試驗(yàn)?zāi)繕?biāo)模型的性質(zhì)。權(quán)重分配可以充分發(fā)揮你的創(chuàng)造性。比如，簡單地加上標(biāo)量權(quán)重：

對任意權(quán)重而言，我們未必知道模型的統(tǒng)計學(xué)性質(zhì)。將權(quán)重與y值相聯(lián)系經(jīng)常會變得太復(fù)雜。例如，使用正比于|y|的權(quán)重在L1損失和L2損失中是不等價的（梯度不考慮預(yù)測值本身）。

現(xiàn)在，為我們的玩具數(shù)據(jù)創(chuàng)建一些非常奇異的權(quán)重。我們將定義一個強(qiáng)力的非對稱加權(quán)函數(shù)：

基于這樣的權(quán)重，我們期望得到兩個屬性：X的負(fù)值細(xì)節(jié)更少，形成類似初始余弦的函數(shù)。我們采用了上一個例子中的GBM，加以調(diào)整，最終得到：

我們?nèi)〉昧艘饬现械慕Y(jié)果。首先，我們可以看到，第一次迭代上的偽殘差有著很大的差距，看起來幾乎是原本的余弦函數(shù)。其次，函數(shù)左半部分的圖形常常被忽略，函數(shù)更偏向具有更大權(quán)重的有半部分。第三，第3次迭代得到的函數(shù)看起來和原本的余弦函數(shù)類似（同時開始稍微有點(diǎn)過擬合了）。

權(quán)重是一個高風(fēng)險的強(qiáng)力工具，可用于控制模型的性質(zhì)。如果你打算優(yōu)化損失函數(shù)，值得首先嘗試下給觀測加上權(quán)重這一更簡單的問題。

結(jié)語

今天，我們學(xué)習(xí)了梯度提升背后的理論。GBM不是一個特定的算法，而是創(chuàng)建模型集成的一種常見方法。這一方法具有足夠的靈活性和擴(kuò)展性——可以訓(xùn)練大量模型，使用不同的損失函數(shù)和加權(quán)函數(shù)。

實(shí)際項(xiàng)目和ML競賽表明，在標(biāo)準(zhǔn)問題上（圖像、音頻、非常稀疏的數(shù)據(jù)除外），GBM經(jīng)常是最有效的算法（更別說在堆疊和高層集成中，GBM幾乎總是其中的一部分）。同時，強(qiáng)化學(xué)習(xí)中GBM也用得不少（Minecraft, ICML 2016）。順便提下，計算機(jī)視覺領(lǐng)域，現(xiàn)在還使用基于AdaBoost的維奧拉-瓊斯算法。

在這篇文章中，我們有意省略了關(guān)于GBM的正則化、隨機(jī)性、超參數(shù)的問題。我們一直使用很小的迭代數(shù)M = 3并非出于偶然。如果我們使用30棵樹訓(xùn)練GBM的話，結(jié)果的預(yù)測性不會那么好：

良好的擬合

過擬合

圖片來源： arogozhnikov.github.io