機(jī)器學(xué)習(xí)梯度提升算法的簡(jiǎn)單介紹
梯度提升是構(gòu)建預(yù)測(cè)模型最強(qiáng)大的技術(shù)之一。
今天您將了解梯度提升機(jī)器學(xué)習(xí)算法，并簡(jiǎn)要介紹它的來源和工作原理。
看完這篇文章，我們可以學(xué)習(xí)：
boosting 的起源來自學(xué)習(xí)理論和 AdaBoost。
梯度提升的工作原理包括損失函數(shù)、弱學(xué)習(xí)器和加法模型。
如何使用各種正則化方案提高基本算法的性能。
boosting 的想法來自于是否可以修改弱學(xué)習(xí)器以變得更好的想法。
Michael Kearns 將目標(biāo)闡述為“假設(shè)提升問題”，從實(shí)踐的角度將目標(biāo)陳述為：
... 一種將相對(duì)較差的假設(shè)轉(zhuǎn)換為非常好的假設(shè)的有效算法
—關(guān)于假設(shè)提升的思考?[PDF]，1988 年
弱假設(shè)或弱學(xué)習(xí)器被定義為性能至少略好于隨機(jī)機(jī)會(huì)的假設(shè)。
這些想法建立在 Leslie Valiant 在免費(fèi)分發(fā)或可能近似正確(PAC) 學(xué)習(xí)方面的工作之上，PAC 學(xué)習(xí)是一個(gè)用于調(diào)查機(jī)器學(xué)習(xí)問題復(fù)雜性的框架。
假設(shè)提升是過濾觀察的想法，留下弱學(xué)習(xí)器可以處理的那些觀察，并專注于開發(fā)新的弱學(xué)習(xí)來處理剩余的困難觀察。
這個(gè)想法是多次使用弱學(xué)習(xí)方法來獲得一系列假設(shè)，每個(gè)假設(shè)都重新關(guān)注前一個(gè)發(fā)現(xiàn)困難和錯(cuò)誤分類的例子?！?但是請(qǐng)注意，如何做到這一點(diǎn)并不明顯
—可能近似正確：在復(fù)雜世界中學(xué)習(xí)和繁榮的自然算法，第 152 頁，2013 年
AdaBoost 第一個(gè)提升算法
在應(yīng)用中取得巨大成功的第一個(gè) Boosting 實(shí)現(xiàn)是Adaptive Boosting 或簡(jiǎn)稱AdaBoost。
Boosting 指的是通過結(jié)合粗略和適度不準(zhǔn)確的經(jīng)驗(yàn)法則來產(chǎn)生非常準(zhǔn)確的預(yù)測(cè)規(guī)則的一般問題。
—在線學(xué)習(xí)的決策理論概括和對(duì) boosting 的應(yīng)用?[PDF]，1995
AdaBoost 中的弱學(xué)習(xí)器是具有單個(gè)分裂的決策樹，由于它們的短小，稱為決策樹樁。
AdaBoost 的工作原理是對(duì)觀察進(jìn)行加權(quán)，將更多的權(quán)重放在難以分類的實(shí)例上，而減少那些已經(jīng)處理得當(dāng)?shù)膶?shí)例。新的弱學(xué)習(xí)器按順序添加，將他們的訓(xùn)練集中在更困難的模式上。
這意味著難以分類的樣本會(huì)收到越來越大的權(quán)重，直到算法識(shí)別出正確分類這些樣本的模型
—應(yīng)用預(yù)測(cè)建模，2013 年
預(yù)測(cè)是通過弱學(xué)習(xí)者的預(yù)測(cè)的多數(shù)投票做出的，并由他們的個(gè)人準(zhǔn)確性加權(quán)。AdaBoost 算法最成功的形式是針對(duì)二元分類問題，稱為 AdaBoost.M1。
您可以在下面文章中了解有關(guān) AdaBoost 算法的更多信息：
用于機(jī)器學(xué)習(xí)的 Boosting 和 AdaBoost。
將 AdaBoost 推廣為梯度提升
AdaBoost 和相關(guān)算法首先由 Breiman 在統(tǒng)計(jì)框架中重鑄，稱它們?yōu)?ARCing 算法。
Arcing 是 Adaptive Reweighting and Combining 的首字母縮寫詞。Arcing 算法中的每一步都包含一個(gè)加權(quán)最小化，然后是 [分類器] 和 [加權(quán)輸入] 的重新計(jì)算。
—預(yù)測(cè)游戲和 Arching 算法?[PDF]，1997
這個(gè)框架由弗里德曼進(jìn)一步開發(fā)，稱為梯度提升機(jī)。后來稱為梯度提升或梯度樹提升。
統(tǒng)計(jì)框架將 boosting 視為數(shù)值優(yōu)化問題，其目標(biāo)是通過使用類似梯度下降的程序添加弱學(xué)習(xí)器來最小化模型的損失。
這類算法被描述為階段性加性模型。這是因?yàn)橐淮翁砑右粋€(gè)新的弱學(xué)習(xí)器，而模型中現(xiàn)有的弱學(xué)習(xí)器被凍結(jié)并保持不變。
請(qǐng)注意，此階段性策略不同于在添加新項(xiàng)時(shí)重新調(diào)整先前輸入項(xiàng)的逐步方法。
—貪婪函數(shù)逼近：梯度提升機(jī)?[PDF]，1999
泛化允許使用任意可微的損失函數(shù)，將技術(shù)擴(kuò)展到二元分類問題之外，以支持回歸、多類分類等。
梯度提升的工作原理
梯度提升涉及三個(gè)要素：
要優(yōu)化的損失函數(shù)。
進(jìn)行預(yù)測(cè)的弱學(xué)習(xí)器。
添加弱學(xué)習(xí)器以最小化損失函數(shù)的加法模型。
1. 損失函數(shù)
使用的損失函數(shù)取決于要解決的問題的類型。
它必須是可微的，但支持許多標(biāo)準(zhǔn)損失函數(shù)，您可以定義自己的損失函數(shù)。
例如，回歸可能使用平方誤差，分類可能使用對(duì)數(shù)損失。
梯度提升框架的一個(gè)好處是不必為每個(gè)可能想要使用的損失函數(shù)派生新的提升算法，相反，它是一個(gè)足夠通用的框架，可以使用任何可微的損失函數(shù)。
2. 弱學(xué)習(xí)者
決策樹用作梯度提升中的弱學(xué)習(xí)器。
具體來說，回歸樹用于輸出分割的真實(shí)值，其輸出可以加在一起，允許添加后續(xù)模型輸出并“校正”預(yù)測(cè)中的殘差。
樹以貪婪的方式構(gòu)建，根據(jù)基尼等純度分?jǐn)?shù)選擇最佳分割點(diǎn)或最小化損失。
最初，例如在 AdaBoost 的情況下，使用非常短的決策樹，只有一個(gè)分裂，稱為決策樹樁。較大的樹通?？梢允褂?4 到 8 層。
通常以特定方式約束弱學(xué)習(xí)器，例如最大數(shù)量的層、節(jié)點(diǎn)、分裂或葉節(jié)點(diǎn)。
這是為了確保學(xué)習(xí)器仍然很弱，但仍然可以以貪婪的方式構(gòu)造。
3. 加法模型
一次添加一棵樹，模型中現(xiàn)有的樹不會(huì)改變。
梯度下降程序用于在添加樹時(shí)最小化損失。
傳統(tǒng)上，梯度下降用于最小化一組參數(shù)，例如回歸方程中的系數(shù)或神經(jīng)網(wǎng)絡(luò)中的權(quán)重。在計(jì)算錯(cuò)誤或損失后，更新權(quán)重以最小化該錯(cuò)誤。
我們有弱學(xué)習(xí)器子模型或更具體地說是決策樹，而不是參數(shù)。計(jì)算損失后，要執(zhí)行梯度下降程序，我們必須向模型添加一棵樹以減少損失（即跟隨梯度）。我們通過參數(shù)化樹來做到這一點(diǎn)，然后修改樹的參數(shù)并通過（減少殘差損失）向正確的方向移動(dòng)。
通常這種方法稱為函數(shù)梯度下降或函數(shù)梯度下降。
產(chǎn)生優(yōu)化[成本]的分類器加權(quán)組合的一種方法是通過函數(shù)空間中的梯度下降
— 將算法提升為函數(shù)空間中的梯度下降?[PDF]，1999
然后將新樹的輸出添加到現(xiàn)有樹序列的輸出中，以努力糾正或改進(jìn)模型的最終輸出。
一旦損失達(dá)到可接受的水平或不再改進(jìn)外部驗(yàn)證數(shù)據(jù)集，就會(huì)添加固定數(shù)量的樹或停止訓(xùn)練。
對(duì)基本梯度提升的改進(jìn)
梯度提升是一種貪婪算法，可以快速過擬合訓(xùn)練數(shù)據(jù)集。
它可以受益于懲罰算法各個(gè)部分的正則化方法，并通過減少過度擬合來提高算法的性能。
在本節(jié)中，我們將了解基本梯度提升的 4 項(xiàng)增強(qiáng)功能：
樹約束
收縮率
隨機(jī)抽樣
懲罰學(xué)習(xí)
1. 樹約束
弱學(xué)習(xí)者有技能但仍然很弱是很重要的。
有多種方法可以約束樹。
一個(gè)很好的通用啟發(fā)式方法是，創(chuàng)建的約束樹越多，模型中需要的樹越多，反之，約束越少的單個(gè)樹，所需的樹就越少。
以下是一些可以強(qiáng)加給決策樹構(gòu)建的約束：
樹的數(shù)量，通常向模型中添加更多的樹可能會(huì)導(dǎo)致過擬合的速度非常慢。建議是繼續(xù)添加樹，直到觀察不到進(jìn)一步的改進(jìn)。
樹深度，更深的樹是更復(fù)雜的樹，更短的樹是首選。一般來說，4-8 級(jí)的效果會(huì)更好。
節(jié)點(diǎn)數(shù)或葉數(shù)，如深度，這可以約束樹的大小，但如果使用其他約束，則不受對(duì)稱結(jié)構(gòu)的約束。
在可以考慮拆分之前，每個(gè)拆分的觀察數(shù)對(duì)訓(xùn)練節(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)量施加了最小約束
對(duì)損失的最小改進(jìn)是對(duì)添加到樹的任何拆分的改進(jìn)的約束。
2. 加權(quán)更新
每棵樹的預(yù)測(cè)按順序加在一起。
每棵樹對(duì)這個(gè)總和的貢獻(xiàn)可以加權(quán)以減慢算法的學(xué)習(xí)速度。這種權(quán)重稱為收縮率或?qū)W習(xí)率。
每次更新都簡(jiǎn)單地按“學(xué)習(xí)率參數(shù) v”的值進(jìn)行縮放
—貪婪函數(shù)逼近：梯度提升機(jī)?[PDF]，1999
結(jié)果是學(xué)習(xí)速度變慢，反過來需要更多的樹添加到模型中，反過來需要更長(zhǎng)的時(shí)間來訓(xùn)練，提供了樹的數(shù)量和學(xué)習(xí)率之間的配置權(quán)衡。
降低 v [學(xué)習(xí)率] 的值會(huì)增加 M [樹的數(shù)量] 的最佳值。
—貪婪函數(shù)逼近：梯度提升機(jī)?[PDF]，1999
通常具有 0.1 到 0.3 范圍內(nèi)的小值以及小于 0.1 的值。
類似于隨機(jī)優(yōu)化中的學(xué)習(xí)率，收縮減少了每棵樹的影響，并為未來的樹留下空間以改進(jìn)模型。
—隨機(jī)梯度提升?[PDF]，1999
3. 隨機(jī)梯度提升
對(duì)裝袋集成和隨機(jī)森林的一個(gè)重要見解是允許從訓(xùn)練數(shù)據(jù)集的子樣本中貪婪地創(chuàng)建樹。
同樣的好處可用于減少梯度提升模型中序列中樹之間的相關(guān)性。
這種提升的變化稱為隨機(jī)梯度提升。
在每次迭代時(shí)，從完整的訓(xùn)練數(shù)據(jù)集中隨機(jī)（無替換）抽取訓(xùn)練數(shù)據(jù)的子樣本。然后使用隨機(jī)選擇的子樣本而不是完整樣本來擬合基礎(chǔ)學(xué)習(xí)器。
—隨機(jī)梯度提升?[PDF]，1999
可以使用的隨機(jī)提升的一些變體：
在創(chuàng)建每棵樹之前對(duì)行進(jìn)行子采樣。
創(chuàng)建每棵樹之前的子樣本列
在考慮每個(gè)拆分之前對(duì)列進(jìn)行子采樣。
通常，積極的子采樣（例如僅選擇 50% 的數(shù)據(jù)）已被證明是有益的。
根據(jù)用戶反饋，使用列子采樣比傳統(tǒng)的行子采樣更能防止過擬合
— XGBoost：可擴(kuò)展的樹提升系統(tǒng)，2016 年
4. 懲罰梯度提升
除了結(jié)構(gòu)之外，還可以對(duì)參數(shù)化樹施加額外的約束。
像 CART 這樣的經(jīng)典決策樹不用作弱學(xué)習(xí)器，而是使用一種稱為回歸樹的修改形式，它在葉節(jié)點(diǎn)（也稱為終端節(jié)點(diǎn)）中具有數(shù)值。在某些文獻(xiàn)中，樹的葉子中的值可以稱為權(quán)重。
因此，可以使用流行的正則化函數(shù)對(duì)樹的葉子權(quán)重值進(jìn)行正則化，例如：
權(quán)重的 L1 正則化。
權(quán)重的 L2 正則化。
額外的正則化項(xiàng)有助于平滑最終學(xué)習(xí)的權(quán)重以避免過度擬合。直觀地，正則化目標(biāo)將傾向于選擇采用簡(jiǎn)單和預(yù)測(cè)函數(shù)的模型。
— XGBoost：可擴(kuò)展的樹提升系統(tǒng)，2016 年
梯度提升資源
梯度提升是一種引人入勝的算法，我相信你想更深入。
本節(jié)列出了可用于了解有關(guān)梯度提升算法的更多信息的各種資源。
梯度提升視頻
梯度提升機(jī)器學(xué)習(xí)，Trevor Hastie，2014 年
梯度提升，Alexander Ihler，2012
GBM , 約翰·芒特, 2015
學(xué)習(xí)：提升，MIT 6.034 人工智能，2010
xgboost：用于快速準(zhǔn)確梯度提升的 R 包，2016
XGBoost：一種可擴(kuò)展的樹提升系統(tǒng)，Tianqi Chen，2016
教科書中的梯度提升
第 8.2.3 節(jié) Boosting，第 321 頁，統(tǒng)計(jì)學(xué)習(xí)簡(jiǎn)介：在 R 中的應(yīng)用。
第 8.6 節(jié) Boosting，第 203 頁，應(yīng)用預(yù)測(cè)建模。
第 14.5 節(jié)隨機(jī)梯度提升，第 390 頁，應(yīng)用預(yù)測(cè)建模。
第 16.4 節(jié) Boosting，第 556 頁，機(jī)器學(xué)習(xí)：概率視角
第 10 章提升樹和加法樹，第 337 頁，統(tǒng)計(jì)學(xué)習(xí)的要素：數(shù)據(jù)挖掘、推理和預(yù)測(cè)
梯度提升論文
關(guān)于假設(shè)提升的思考?[PDF]，邁克爾·卡恩斯，1988 年
在線學(xué)習(xí)的決策理論概括和對(duì)提升的應(yīng)用?[PDF], 1995
弧形邊緣?[PDF], 1998
隨機(jī)梯度提升?[PDF]，1999
提升算法作為函數(shù)空間中的梯度下降?[PDF]，1999
概括
在這篇文章中，您發(fā)現(xiàn)了用于機(jī)器學(xué)習(xí)中預(yù)測(cè)建模的梯度提升算法。
具體來說，你學(xué)到了：
boosting 學(xué)習(xí)理論和 AdaBoost 的歷史。
梯度提升算法如何與損失函數(shù)、弱學(xué)習(xí)器和加法模型配合使用。
如何通過正則化提高梯度提升的性能。
