編者按：說到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的正則項會懲罰具有多個葉子節點的樹結構。
- 關於選擇分叉標準，強烈建議閱讀論文。
閱讀更多 論智 的文章
