xgboost是華盛頓大學博士陳天奇創(chuàng)造的一個梯度提升(Gradient Boosting)的開源框架。至今可以算是各種數據比賽中的大殺器,被大家廣泛地運用。 一、Xgboost和GBDT差異比較 1. 梯度下降在GBDT中,我們每次生成下一個弱學習器,都是把損失函數的梯度作為學習目標,相當于利用梯度下降法進行優(yōu)化來逼近損失函數的最小值,也就是使得損失函數為0,最終學習器盡可能接近真實結果。 ? 而xgboost中,我們則是把損失函數的二階泰勒展開的差值作為學習目標,相當于利用牛頓法進行優(yōu)化,來逼近損失函數的最小值,也就是使得損失函數為0。 那為什么可以這么逼近呢?這就涉及到泰勒展開: 梯度下降法就是用一階泰勒展開來近似函數: 而牛頓法則是用二階泰勒展開來近似函數: 之后具體的迭代收斂原理請看最優(yōu)化方法。 2. 正則項正則項是為了防止模型過擬合。于是,一般的損失函數L(x)就變成了目標函數 L(x)+O(x)。這樣,隨著樹的復雜度增大,對應的目標函數也就變大,這樣就有效防止了過擬合。葉子節(jié)點個數(T),葉節(jié)點分數(w) 對葉子節(jié)點個數進行懲罰,相當于在訓練過程中做了剪枝。 將xgboost的目標函數進行化簡 令 其導數為0,解得每個葉節(jié)點的最優(yōu)預測分數為: 代入目標函數,得到最小損失為: 3. 樹節(jié)點分裂方法精確算法:遍歷所有特征的所有可能分割點,來尋找使目標函數最小的分割點。 近似算法:對于每個特征,只考察分位點,減少計算復雜度。 而XGBoost不是簡單地按照樣本個數進行分位,而是以二階導數值作為權重(Weighted Quantile Sketch),比如: ![]() 4. 其他特征1.shrinkage(收縮)方法:相當于學習系數eta。對每顆子樹都要乘上該系數,防止過擬合。 2.列采樣:對特征進行降采樣,靈感來源于隨機森林,除了能降低計算量外,還能防止過擬合。 3.行采樣: 4.缺失值處理:通過枚舉所有缺失值在當前節(jié)點是進入左子樹,還是進入右子樹更優(yōu)來決定一個處理缺失值默認的方向。 5.xgboost工具支持并行。一般決策樹中,我們需要每次都對特征的值進行排序,來尋找分割點,極其費時。xgboost中,我們先對每個特征進行分塊(block)并排序,使得在尋找最佳分裂點的時候能夠并行化計算。這個結構加速了split finding的過程,只需要在建樹前排序一次,后面節(jié)點分裂時直接根據索引得到梯度信息。這是xgboost比一般GBDT更快的一個重要原因。 6.out-of-core, cache-aware優(yōu)化內存等方法來加速計算。 二、Xgboost原理 2.1 目標函數及其二階泰勒展開在Xgboost中,選擇樹模型為基學習器,我們需要正則的對象,或者說需要控制復雜度的對象就是這K顆樹,通常樹的參數有樹的深度,葉子節(jié)點的個數,葉子節(jié)點值的取值(Xgboost里稱為權重weight)。 所以,我們的目標函數形式如下: 其中第一部分是訓練損失,如上面所述的平方損失或者Logistic Loss等,第二部分是每棵樹的復雜度的和。因為現(xiàn)在我們的參數可以認為是在一個函數空間里面,我們不能采用傳統(tǒng)的如SGD之類的算法來學習我們的模型,因此我們會采用一種叫做additive training的方式。即每次迭代生成一棵新的回歸樹,從而使預測值不斷逼近真實值(即進一步最小化目標函數)。每一次保留原來的模型不變,加入一個新的函數f 到模型里面: 所以,對于第K次的目標函數為: 其中constant為前K?1顆樹的正則化項和,是一個常數。 根據公式(0),進一步為: 上面的式子意義很明顯,只需要尋找一顆合適的樹fK使得目標函數最小。然后不斷的迭代K 次就可以完成K 個學習器的訓練。 那么我們這顆樹到底怎么找呢? 在GBDT里面(當然GBDT沒有正則),我們的樹是通過擬合上一顆樹的負梯度值,建樹的時候采用的啟發(fā)式準則,如MSE等。 然而,在Xgboost里面,它是通過對損失函數進行二階泰勒展開: 對損失函數二階泰勒展開: 經過簡化得到: (8)式即為葉子結點取值的表達式。(9)式為目標函數的值。 2.2 分裂準則到這里,我們一直都是在圍繞目標函數進行分析,這個到底是為什么呢?這個主要是為了后面我們尋找f k ( x ),也就是建樹的過程。具體來說,我們回憶一下建樹的時候需要做什么,建樹的時候最關鍵的一步就是選擇一個分裂的準則,也就如何評價分裂的質量。比如在前面文章GBDT的介紹里,我們可以選擇MSE,MAE來評價我們的分裂的質量,但是,我們所選擇的分裂準則似乎不總是和我們的損失函數有關,因為這種選擇是啟發(fā)式的。比如,在分類任務里面,損失函數可以選擇logloss,分裂準確選擇MSE,這樣看來,似乎分裂的好壞和我們的損失并沒有直接掛鉤。 但是,在Xgboost里面,我們的分裂準則是直接與損失函數掛鉤的準則,這個也是Xgboost和GBDT一個很不一樣的地方。 三、手動計算還原Xgboost的過程 3.1 數據集,參數設置以及損失函數數據集的樣本條數只有15條,2個特征。具體如下: 這里為了簡單起見,樹的深度設置為3(max_depth=3),樹的顆數設置為2(num_boost_round=2),學習率為0.1(eta=0.1)。另外再設置兩個正則的參數,λ=1,γ=0。損失函數選擇logloss。由于后面需要用到logloss的一階導數以及二階導數,這里先簡單推導一下。 在一階導的基礎上再求一次有(其實就是sigmod函數求導) 所以樣本的一階導數值 樣本的二階導數值 3.2 建立第一顆樹(k=1)建樹的時候從根節(jié)點開始(Top-down greedy),在根節(jié)點上的樣本有ID1~ID15。那么回顧Xgboost的算法流程,我們需要在根節(jié)點處進行分裂,分裂的時候需要計算式子(10)。 那么式子(10)表達是:在結點處把樣本分成左子結點和右子結點兩個集合。分別求兩個集合的G L、H L、GR 、H R ,然后計算增益G a i n 。而這里,我其實可以先計算每個樣本的一階導數值和二階導數值,但是這里你可能碰到了一個問題,那就是第一顆樹的時候每個樣本的預測的概率yi,pred 是多少?這里和GBDT一樣,應該說和所有的Boosting算法一樣,都需要一個初始值。而在Xgboost里面,對于分類任務只需要初始化為(0,1)中的任意一個數都可以。具體來說就是參數base_score。(其默認值是0.5)(值得注意的是base_score是一個經過sigmod映射的值,可以理解為一個概率值,提這個原因是后面建第二顆樹會用到,需要注意這個細節(jié))這里我們也設base_score=0.5。然后我們就可以計算每個樣本的一階導數值和二階導數值了。具體如下表: 那么把樣本如何分成兩個集合呢?這里就是上面說到的選取一個最佳的特征以及分裂點使得Gain最大。 比如說對于特征x 1 x1x1,一共有[1,2,3,6,7,8,9,10]8種取值??梢缘玫揭韵逻@么多劃分方式。 以1為劃分時(x1<1): 左子節(jié)點包含的樣本IL =[] 右子節(jié)點包含的樣本IR=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] 那么左子節(jié)點為空,G L =0和HL=0 右子節(jié)點的一階導數和: 右子節(jié)點的二階導數和: 最后我們在計算一下增益Gain,可以得到Gain=0。計算出來發(fā)現(xiàn)Gain=0,不用驚訝,因為左子結點為空,也就是這次分裂把全部樣本都歸到右子結點,這個和沒分裂有啥區(qū)別?所以,分裂的時候每個結點至少有一個樣本。 下面,我再計算當以2劃分時的增益Gain。 下面,我再計算當以2劃分時的增益Gain。 以2為劃分時(x1<2): 左子結點包含的樣本I L =[1,4] 右子節(jié)點包含的樣本I R ==[2,3,5,6,7,8,9,10,11,12,13,14,15] 左子結點的一階導數和: 左子結點的二階導數和: 右子結點的一階導數和: 右子結點的二階導數和: 最后計算一下增益Gain: 其他的值[3,6,7,8,9,10]類似,計算歸總到下面表,供大家參考 從上表我們可以看到,如果特征x1以x1<10分裂時可以得到最大的增益0.615205。 按照算法的流程,這個時候需要遍歷下一個特征x2,對于特征x2也是重復上面這些步驟,可以得到類似的表如下,供大家參考。 可以看到,以x2特征來分裂時,最大的增益是0.2186<0.615205。所以在根節(jié)點處,我們以x1<10來進行分裂。由于我設置的最大深度是3,此時只有1層,所以還需要繼續(xù)往下分裂。 左子節(jié)點的樣本集合I L=[1,2,3,4,5,6,7,8,9,10,11,12,14,15] 右子節(jié)點的樣本集合I R =[13] 右子節(jié)點此時只剩一個樣本,不需要分裂了,也就是已經是葉子結點??梢杂嬎闫鋵娜~子結點值了,按照公式(8): 那么下面就是對左子結點I L進行分裂。分裂的時候把此時的結點看成根節(jié)點,其實就是循環(huán)上面的過程,同樣也是需要遍歷所有特征(x1,x2)的所有取值作為分裂點,選取增益最大的點。在此不展開敘述。 這里直接給出第一個樹的結構。 至此,我們學習完了第一顆樹。 3.3 建立第二顆樹(k=2)這里,我們開始擬合我們第二顆樹。其實過程和第一顆樹完全一樣。只不過對yi ,pred需要進行更新,也就是擬合第二顆樹是在第一顆樹預測的結果基礎上。這和GBDT一樣,因為大家都是Boosting思想的算法。 在第一顆樹里面由于前面沒有樹,所以初始yi ,pred= 0.5 假設此時,模型只有這一顆樹(K=1),那么模型對樣例x i 進行預測時,預測的結果表達是什么呢? 由加法模型 其中: 所以,我們可以得到第一棵樹預測的結果為下表(預測后將其映射成概率) 比如對于ID=1的樣本,其落在-0.04這個節(jié)點。那么經過sigmod映射后的值為 有了這個之后,根據公式(11)(12)我們就可以計算所有樣本新的一階導數和二階導數的值了。具體如下表: 之后,我們和第一顆樹建立的時候一樣以公式(10)去建樹。 擬合完后第二顆樹如下圖: 后面的所有過程都是重復這個過程,這里就不再啰嗦了。 至此,整個Xgboost的訓練過程已經完了。 原文鏈接:https://blog.csdn.net/anshuai_aw1/article/details/82970489 |
|
來自: NeighborMrSun > 《機器學習模型》