XGBoost算法背後的數學:儘可能簡單地解釋XGBoost算法背後的機制

2020-12-05 deephub

如果你想很好地理解某些內容，請嘗試簡單地給別人解釋出來。 ——費曼

XGBoost是一個很優美的算法，它的過程不乏啟發性。這些通常簡單而美麗的概念在數學術語中消失了。我在理解數學的過程中也遇到過同樣的挑戰，所以我寫這篇文章的目的是鞏固我的理解，同時幫助其他人完成類似的過程。

為了解XGBoost是什麼，我們首先要了解什麼是梯度提升機Gradient Boosting，以及梯度提升機背後的數學概念。請注意，這篇文章假設你對梯度提升機非常熟悉，並試圖觸及梯度提升機和XGBoost背後的直覺和數學。現在我們開始吧。

理解梯度提升機

第一步 - 初始函數

與往常一樣，讓我們從粗略的初始函數開始，類似於回歸時所有值的平均值。 它將為我們提供一些輸出，無論效果如何。

第二步 - 損失函數

下面我們計算損失函數。

那麼什麼是損失函數？它是一種度量預測值與真實值之間差異的算式，這裡有幾個例子：

從下表可以理解為什麼對異常值的魯棒性很重要：

其思想是，損失函數的值越低，我們的預測就越準確，所以獲取最佳的預測值等價為損失函數的最小化問題。

第三步 - 新的目標

到目前為止，我們已經建立了我們的初始模型，並進行了預測。接下來，我們應該在損失函數給出的殘差上擬合一個新模型，但有一個微妙的轉折：我們將擬合損失函數的負梯度，下面給出我們為什麼這樣做以及為什麼它們相似的直覺：

梯度可以解釋為函數的「最快增加的方向和速率」，因此負梯度告訴我們函數最小值的方向，在這種情況下為損失函數的最小值。

我們將遵循梯度下降法，逐步逼近損失函數的極小值，算法的學習速率將給出每一次更新的步長。在損失函數最小的情況下，我們的錯誤率也最低。

因此，我們將在損失函數的梯度處建立新模型。

第四步 - 累加

在梯度上迭代擬合模型的過程將繼續進行，直到我們達到給定的弱學習器數量的最小值或極限T為止，這稱為累加。

回想一下，在Adaboost中，模型的「缺點」是由高權重數據點確定的。在梯度提升機中，「缺點」是通過梯度來識別的。

簡單來說，這就是梯度提升機的工作機制。在回歸和分類任務中，唯一不同的是所使用的損失函數。

XGBoost

XGBoost和梯度提升機都遵循梯度提升決策樹的原理，但是XGBoost使用更加正則化的模型公式來控制擬合，這使它具有更好的性能，這就是為什麼它也被稱為「正則提升」技術。

牛頓法

那麼什麼是牛頓法呢？在隨機梯度下降中，我們用更少的數據點來計算梯度更新的方向，耗時也相對更少，但如果我們想要加速更新，就需要更多的數據點。而在牛頓法中，我們用來計算梯度更新的方向的耗時更多，但是需要的計算點也更少。

需要注意的重要一點是，即使梯度提升機在解決回歸問題時使用梯度下降法進行優化，在解決分類問題仍然使用牛頓方法來解決優化問題。 而XGBoost在分類和回歸的情況下都使用此方法。

牛頓法試圖通過構造一個序列來解決最小化問題，該序列從隨機起點開始，通過的二階泰勒展開序列收斂到的最小值。在附近的二階泰勒展開式是

二階導數對於加快梯度下降非常重要，因為在一個損失函數的山谷裡，如果算法的修正方向是鋸齒狀的下降，那麼您在沿著山谷的實際梯度上的進展就非常緩慢， 通過二階導數調整方向將使您的下降方向朝山谷的實際梯度方向傾斜，從而將緩慢的下降轉換為更快的下降。

損失函數

我們已經看到了平方損失函數在梯度提升機中的行為，讓我們快速看一下XGBoost中平方損失函數的作用：

均方誤差損失函數的形式是非常友好的，有一個一次項（通常稱為剩餘項）和一個二次項。對於其他值得注意的損失函數（例如logistic損失），要得到這樣一個好的形式並不容易。所以在一般情況下，我們把損失函數的泰勒展開式推廣到二階

這就成了我們對新樹的優化目標。該定義的一個重要優點是，目標函數的值僅依賴於和。這就是XGBoost支持自定義損失的方式。我們可以使用完全相同的以和作為輸入的求解器來優化每個損失函數，包括邏輯回歸和成對排序

正則化

接下來，我們將處理正則化項，但在此之前，我們需要了解如何以數學方式定義決策樹。 直觀來說，決策樹主要是葉節點、數據點和將數據點分配給這些葉節點的函數的組合。 數學上它寫為：

其中JT是葉數。此定義將樹上的預測過程描述為：

將數據點賦給一片葉子將相應分數分配給第個數據點在XGBoost中，複雜度定義為：

XGBoost中的超參數描述如下：

當然，定義複雜度的方法不止一種，但這一種方法在實踐中效果很好。正則化是大多數基於樹的方法處理得不太仔細或忽略掉的一部分。這是因為傳統的樹學習方法只強調提升純度，而複雜度的控制則只能基於試探。通過正式定義它，我們可以更好地了解我們的模型正在學習的內容，並獲得泛化能力良好的模型

最後一個方程衡量的是樹的結構的優劣。

如果聽起來有些複雜，讓我們看一下圖片，看看如何計算分數。

基本上，對於給定的樹結構，我們將統計信息和推入它們所屬的葉節點，將統計信息求和，然後使用這一公式計算樹的質量。 該分數類似於決策樹中的純度度量，不同之處在於它還考慮了模型的複雜性

學習樹的結構

現在，我們有了一種方法來衡量一棵樹的質量。理想情況下，我們將枚舉所有可能的樹並選擇最佳的樹，但實際上這是非常棘手的，因此我們將嘗試一次優化一個樹的部分。 具體來說，我們嘗試將一片葉子分成兩片葉子，其得分為

該公式可分解為: 1）新左葉上的分數；2）新右葉上的分數；3）原始葉上的分數；4）附加葉上的正則化。 我們在這裡可以看到一個重要的事實：如果增益小於，我們最好不要添加該分支，這正是基於樹的模型中的修剪技術！ 通過使用監督學習的原理，我們自然可以得出這些技術起作用的原因

很好，現在希望我們對XGBoost有一個初步的了解，以及為什麼它會這樣工作。下次見！

作者：Dip Ranjan Chatterjee

deephub翻譯組：Alexander Zhao

相關焦點

  • 資料| 陳天奇介紹Xgboost原理的PPT
    https://xgboost.apachecn.org/  所有者：https://xgboost.apachecn.org/ 】內容簡介陳天奇介紹Xgboost原理的PPT，用於學習它在 Gradient Boosting 框架下實現機器學習算法。XGBoost提供並行樹提升（也稱為GBDT，GBM），可以快速準確地解決許多數據科學問題。相同的代碼在主要的分布式環境（Hadoop，SGE，MPI）上運行，並且可以解決數十億個示例之外的問題。
  • XGboost算法在不同作業系統中安裝方法乾貨分享
    安裝Xgboost方法最近小編想安裝一下xgboost軟體包，用pip install xgboost 安裝有問題，今天將對主流作業系統下的安裝方法進行了匯總，用到的時候拿來即用，省事省力，內容包括三大主流作業系統的，其他系統的沒有環境，暫時不列舉。
  • 大戰三回合:XGBoost、LightGBM和Catboost一決高低
    但在大訓練樣本和高維度特徵的數據環境下，GBDT 算法的性能以及準確性卻面臨了極大的挑戰，隨後，2017 年 LightGBM 應勢而生，由微軟開源的一個機器學習框架；同年，俄羅斯的搜索巨頭 Yandex 開源 Catboost 框架。
  • XGBoost算法
    XGBoost（eXtreme Gradient Boosting）算法近年來在各種比賽中可謂是「香餑餑」，預測性能很好。下面我們就來介紹它的原理。 原理 首先，我們要了解的是，XGBoost是GBDT算法的一種改進。
  • 中信建投證券:xgboost中證500指數增強7月持倉組合發布
    xgboost模型是一種強學習模型，其是由眾多弱學習模型集成，其採用弱學習模型為CART，即分類與回歸樹。該模型重在擬合特徵和標籤間的非線性關係。組成該模型的眾多弱學習器之間的關係是補充彌補的關係，弱學習器的訓練有先後，每個新的弱學習器的學習目標都是之前已訓練好的弱學習器的殘差。
  • 機器學習算法的新女王——XGBoost
    決策樹，在其最簡單的形式，是易於可視化和相當可解釋的算法，但為下一代基於樹的算法建立直覺可能有點棘手。下面是一個簡單的類比，可以更好地理解基於樹的算法的發展。  XGBoost如何優化標準GBM算法並行化：XGBoost使用並行化實現序列樹的構建過程。
  • 從結構到性能,一文概述XGBoost、Light GBM和CatBoost的同與不同
    >選取所有特徵分割結果中最好的一個簡單說，直方圖算法在某個特徵上將所有數據點劃分到離散區域，並通過使用這些離散區域來確定直方圖的分割值。雖然在計算速度上，和需要在預分類特徵值上遍歷所有可能的分割點的預分類算法相比，直方圖算法的效率更高，但和 GOSS 算法相比，其速度仍然更慢。為什麼 GOSS 方法如此高效？在 Adaboost 中，樣本權重是展示樣本重要性的很好的指標。
  • 以XGBoost為代表的集成算法體現的哲學思想與數學技巧
    為什麼要看待機器學習中某些問題要從哲學思想與數學思想技巧的高度呢?一是，增加學習的樂趣，降低理解的難度，揭開其神秘的面紗，也就是以簡馭繁。二是能夠追根溯源，知其然並知其所以然，不僅幫助我們理解，同時給我們提供更多的創新出發點，是大有裨益的。
  • XGBoost之切分點算法
    前言上文介紹了XGBoost的算法原理並引出了衡量樹結構好壞的打分函數（目標函數），根據特徵切分點前後的打分函數選擇最佳切分點，但並未對節點的切分算法作詳細的介紹。本文詳細的介紹了XGBoost的切分點算法，內容參考陳天奇博士《XGBoost ：A scalable Tree Boosting System》。
  • 數據挖掘中的利器——XGBoost理論篇
    XGBoost是各種數據挖掘或機器學習算法類比賽中每個團隊都會使用且精度相對最好的算法之一（Deep Learning算法除外）。也就是說，對於剛轉向機器學習領域的同胞們，在掌握數據挖掘的基本常識概念之後，要想在比賽中有所收穫，掌握XGBoost算法也是當務之急。
  • XGBoost 重要關鍵參數及調優步驟
    本篇對XGBoost主要參數進行解釋，方括號內是對應scikit-learn中XGBoost算法模塊的叫法。提升參數雖然有兩種類型的booster，但是我們這裡只介紹tree。因為tree的性能比線性回歸好得多，因此我們很少用線性回歸。
  • 斯坦福發表NGBoost算法
    Stanford ML Group 最近在他們的論文中發表了一個新算法，其實現被稱為 NGBoost。該算法利用自然梯度將不確定性估計引入到梯度增強中。本文試圖了解這個新算法，並與其他流行的 boosting 算法 LightGBM 和 XGboost 進行比較，以了解它在實踐中是如何工作的。
  • XGBoost算法原理小結
    前言XGBoost（eXtreme Gradient Boosting）全名叫極端梯度提升，XGBoost是集成學習方法的王牌，在Kaggle數據挖掘比賽中，大部分獲勝者用了XGBoost，XGBoost在絕大多數的回歸和分類問題上表現的十分頂尖，本文較詳細的介紹了XGBoost的算法原理。
  • 10大機器學習算法,看懂你就是數據科學家
    很明顯，你可以使用這種算法擬合簡單曲線/回歸。K-均值聚類 這是所有人都喜歡的非監督學習聚類算法。給定一組矢量形式的數據點，我們可以基於它們之間的距離生成數據點群。它是一種期望最大化的算法，反覆地移動群組的中心，然後聚集每個群組中心點。此算法所採用的輸入是生成群組的數量，並且它將嘗試匯集群組的迭代次數。
  • 機器學習算法基礎(使用Python代碼)
    3.強化學習：工作原理：使用這種算法，機器經過培訓，可以做出具體決策。它的工作原理是這樣的：機器暴露在一個環境中，在這個環境中，它通過反覆試驗不斷地訓練自己。機器從過去的經驗中學習，並嘗試獲取儘可能好的知識，以做出準確的業務決策。
  • XGBoost缺失值引發的問題及其深度分析|CSDN博文精選
    然而，在XGBoost on Spark的官方實現中，卻存在一個因XGBoost缺失值和Spark稀疏表示機制而帶來的不穩定問題。事情起源於美團內部某機器學習平臺使用方同學的反饋，在該平臺上訓練出的XGBoost模型，使用同一個模型、同一份測試數據，在本地調用（Java引擎）與平臺（Spark引擎）計算的結果不一致。
  • 陳天奇做的XGBoost為什麼能橫掃機器學習競賽平臺?
    XGBoost選用了CART樹，數學公式表達XGBoost模型如下：K是樹的數量，F表示所有可能的CART樹，f表示一棵具體的CART樹。這個模型由K棵CART樹組成。可以與Flink、Spark和其他雲數據流系統集成下圖顯示了基於樹的算法的發展歷程：決策樹：由一個決策圖和可能的結果（包括資源成本和風險）組成， 用來創建到達目標的規劃。