編者按：說到Kaggle神器，不少人會想到XGBoost。一周前，我們曾在“從Kaggle歷史數據看機器學習競賽趨勢”介紹過它的“霸主地位”：自提出后，這種算法在機器學習競賽中被迅速普及，并被多數奪冠模型視為訓練速度、最終性能提升的利器。那么，你知道XGBoost背后的數學原理是什么嗎？

好奇的李雷和韓梅梅

李雷和韓梅梅是形影不離的好朋友，一天，他們一起去山里摘蘋果。按照計劃，他們打算去摘山谷底部的那棵大蘋果樹。雖然韓梅梅聰明而富有冒險精神，而李雷有些謹慎和遲鈍，但他們中會爬樹的只有李雷。那么他們的路徑是什么呢？

如上圖所示，李雷和韓梅梅所在的位置是a點，他們的目標蘋果樹位于g點。山里環境復雜，要怎么做才能確定自己到了山谷底部呢？他們有兩種方法。

1.由韓梅梅計算“a”點的斜率，如果斜率為正，則繼續朝這個方向前進；如果為負，朝反方向前進。

斜率給出了前進的方向，但沒有說明他們需要朝這個方向移動多少。為此，韓梅梅決定走幾步臺階，算一下斜率，確保自己不會到達錯誤位置，最終錯過大蘋果樹。但是這種方法有風險，控制臺階多少的是學習率，這是個需要人為把控的值：如果學習率過大，李雷和韓梅梅很可能會在g點兩側來回奔走；如果學習率過小，可能天黑了他們都未必摘得到蘋果。

聽到可能會走錯路，李雷不樂意了，他不想繞遠路，也不愿意錯過回家吃飯的時間。看到好友這么為難，韓梅梅提出了第二種方法。

2.在第一種方法的基礎上，每走過特定數量的臺階，都由韓梅梅去計算每一個臺階的損失函數值，并從中找出局部最小值，以免錯過全局最小值。每次韓梅梅找到局部最小值，她就發個信號，這樣李雷就永遠不會走錯路了。但這種方法對女孩子不公平，可憐的韓梅梅需要探索她附近的所有點并計算所有這些點的函數值。

XGBoost的優點在于它能同時解決以上兩種方案的缺陷。

梯度提升（Gradient Boosting）

很多梯度提升實現都會采用方法1來計算目標函數的最小值。在每次迭代中，我們利用損失函數的梯度訓練基學習器，然后用預測結果乘上一個常數，將其與前一次迭代的值相加，更新模型。

它背后的思路就是在損失函數上執行梯度下降，然后用基學習器對其進行擬合。當梯度為負時，我們稱它為偽殘差，因為它們依然能間接幫助我們最小化目標函數。

XGBoost

XGBoost是陳天奇在華盛頓大學求學期間提出的成果。它是一個整體加法模型，由幾個基學習器共同構成。

那么，我們該如何在每次迭代中選擇一個函數？這里可以用一種最小化整體損失的方法。

在上述梯度提升算法中，我們通過將基學習器擬合到相對于先前迭代值的損失函數的負梯度，在每次迭代時獲得ft(xi)。而在XGBoost中，我們只探索幾個基學習器或函數，選擇其中一個計算最小值，也就是韓梅梅的方法2。

如前所述，這種方法有兩個問題：

探索不同的基學習器；

計算所有基學習器的損失函數值。

XGBoost在計算基學習器ft(xi)最小值的，使用的方法是泰勒級數逼近。比起計算精確值，計算近似值可以大大減輕韓梅梅的工作量。

雖然上面只展開到二階導數，但這種近似程度就足夠了。對于任意ft(xi)，第一項C都是常數。gi是前一次迭代中損失的一階導數，hi是其二階導數。韓梅梅可以在探索其他基學習器前直接計算gi和hi，這就成了一個簡單的乘法問題，計算負擔大大減輕了，不是嗎？

解決了損失函數值的問題，我們還要探索不同的基學習器。

假設韓梅梅更新了一個具有K個葉子節點的基學習器ft。設Ij是屬于節點j的實例集合，wj是該節點的預測。因此，對于Ij中的實例i，我們有ft(xi)=wj。所以我們在上式中用代入法更新了L(t)的表達式。更新后，我們就能針對每個葉子節點的權重采用損失函數的導數，以獲得最優權重。

以上就是對于具有K個葉子節點的基學習器的最佳損失。考慮到這樣的節點會有上百個，一個個探索它們是不現實的。

所以讓我們來看韓梅梅的情況。她現在已經知道如何使用泰勒展開來降低損失計算量，也知道了什么是葉子節點中的最佳權重。唯一值得關注的是如何探索所有不同的樹結構。

XGBoost不會探索所有可能的樹結構，它只是貪婪地構建一棵樹，選擇導致最大損失的方法，減少分叉。在上圖中，樹從節點I開始，根據標準，節點分為左右分叉。所以我們的實例一部分被放進了左側的葉子節點，剩下的則去了右側的葉子節點。現在，我們就可以計算損失值并選擇導致損失減少最大的分叉。

解決了上述問題后，現在韓梅梅就只剩下一個問題：如何選擇分叉標準？XGBoost使用不同的技巧來提出不同的分割點，比如直方圖。對于這部分，建議去看論文，本文不再作解釋。

XGBoost要點

雖然梯度提升遵循負梯度來優化損失函數，但XGBoost計算每個基學習器損失函數值用的是泰勒展開。

XGBoost不會探索所有可能的樹結構，而是貪婪地構建一棵樹。

XGBoost的正則項會懲罰具有多個葉子節點的樹結構。

關于選擇分叉標準，強烈建議閱讀論文：arxiv.org/pdf/1603.02754.pdf