• 建樹過程中如何選擇使用哪個特征哪個值來進行分裂？
• 什么時候停止分裂？
• 如何計算葉節(jié)點的權(quán)值？
• 建完了第一棵樹之后如何建第二棵樹？
• 為防止過擬合，XGB做了哪些改進

樹的集成

本文主要針對xgboost的論文原文中的公式細節(jié)做了詳細的推導，對建樹過程進行詳細分析。

對于樣本個數(shù)為n特征個數(shù)為m的數(shù)據(jù)集 ，其中。

樹的集成學習方法使用K個增量函數(shù)來預測輸出：

為子模型的預測函數(shù)，每個即是一棵樹。

函數(shù)空間即樹的搜索空間。其中q為每棵樹的結(jié)構(gòu)，q將域中每個樣本對應到唯一的葉節(jié)點上，最終產(chǎn)生T個葉節(jié)點，則是該葉節(jié)點對應的權(quán)重，w即從節(jié)點到權(quán)重的映射（權(quán)重即葉節(jié)點的值）。每個對應一個獨立的樹結(jié)構(gòu)q和該樹每個葉節(jié)點的權(quán)重w。（這里樹結(jié)構(gòu)是指每個分裂點和對應的分裂值）。可以看做一個分段函數(shù)，q對應的不同的分段，w對應的為該分段的值，即分段到值的映射。

對我們的預測函數(shù)，目標函數(shù)為：

從公式1中可以看出，對于最終的預測函數(shù)，其參數(shù)為一個個的函數(shù)，因為參數(shù)為函數(shù)，所以無法使用傳統(tǒng)的優(yōu)化方法在歐氏空間中進行優(yōu)化，而是采用了加法模型來進行訓練。

boost的思想是將一系列弱分類器串行的組合起來，在前面的分類器的基礎(chǔ)上迭代的優(yōu)化新的分類器。

首先我們對所有的數(shù)據(jù)默認預測一個固定值(對應xgboost中參數(shù)base_score，注意并不等于base_score，而是經(jīng)過Sigmoid函數(shù)映射后的值)，在此基礎(chǔ)上根據(jù)該預測值與真實y值的損失 ，建立第一棵樹，之后每次迭代時都是根據(jù)其之前所有樹做出的預測之和與真實y值的損失來建立新樹。也就是每次迭代建樹時用新樹來優(yōu)化前一個樹的損失 。

為第t棵樹對第i個樣本做出的預測。我們每次添加新樹的時候，要優(yōu)化的目標函數(shù)為上一個樹產(chǎn)生的損失。

因此我們建立第t棵樹時有損失函數(shù)：

為新建的這棵樹做出的預測，為之前所有的樹預測值之和，即是新建了當前這棵樹后模型做出的預測值，求其與真實值之間的損失（注意這里是損失不是殘差，這里的可以是log_loss, mse等）。

泰勒展開

gbdt的目標函數(shù)與xgboost區(qū)別就是帶不帶正則項，也就是上面式子中的。gbdt對損失函數(shù)的優(yōu)化是直接使用了損失函數(shù)的負梯度，沿著梯度下降的方向來減小損失，其是也就是一階泰勒展開。而xgboost在這里使用了二階泰勒展開，因為包含了損失函數(shù)的二階信息，其優(yōu)化的速度大大加快。

下面來看一下泰勒展開的推導。首先我們來復習一下泰勒定理：

設n是一個正整數(shù)。如果定義在一個包含a的區(qū)間上的函數(shù)f在a點處n+1次可導，那么對于這個區(qū)間上的任意x，則有：其中的多項式稱為函數(shù)在a處的泰勒展開式，剩余的是泰勒公式的余項，是的高階無窮小。?

該公式經(jīng)過變換可以得到二階展開式：

對于式子：

可以這樣分析，為預測值和真實值之間的損失，為常量，因此是以預測值為自變量的函數(shù)，當建立新樹給出新的預測后，相當于在上一次的預測上增加了一個無窮小量

令

則有

其中真實標簽是常數(shù)，是上次迭代求出的值即這里的，為無窮小量。有了這個對應之后。

因此我們建立第t棵樹時有損失函數(shù)：

令損失函數(shù)的一階、二階偏導分別為，其中，

式中為常量，優(yōu)化的是損失函數(shù)的最小值，因此常量值可以從損失函數(shù)中去掉。上式可簡化為：

葉節(jié)點權(quán)重

式中正則項進行展開，得：

其中是新建的樹的值，對于每個樣本來說，就是對應的葉節(jié)點的權(quán)重。定義為分到葉節(jié)點的樣本(葉節(jié)點總數(shù)為T，樣本總數(shù)為n)

上式是對本次建樹時n個樣本的損失求和，下面分兩步：先對每個葉節(jié)點的樣本損失求和，再對所有葉節(jié)點求和，兩者結(jié)果一樣。

對于葉節(jié)點上的損失：

對于當前的樹結(jié)構(gòu)求使最小，顯然這是個一元二次方程求最小值問題。

可以得到葉節(jié)點權(quán)重的最優(yōu)值：

分裂準則

上面是對單個葉節(jié)點計算出了最優(yōu)權(quán)重，對于新建的這樹(樹結(jié)構(gòu))在此權(quán)重下對應的的最小損失為每個葉節(jié)點上樣本最小損失之和（將上式中的代入）:

在樹結(jié)構(gòu)下產(chǎn)生的最優(yōu)損失可以做為樹結(jié)構(gòu)的評價函數(shù)，也就是作為樹分裂時候的評價指標。

令為每次分裂時分到左子樹上的樣本，為每次分裂時分到右子樹上的樣本，有。則在該次分裂后損失的減小量為：

因此將分裂時增益定義為：

我們在建樹的過程（也就是求分段函數(shù)的過程）包括兩步：一是選擇分裂依據(jù)的特征和特征值（將自變量分段），二是確定葉節(jié)點的權(quán)重（確定每段對應的函數(shù)值）。劃分的依據(jù)準則是Gain，其實也就是損失函數(shù)的解析解，劃分后葉節(jié)點的權(quán)重是使函數(shù)達到解析解的權(quán)重。

從最優(yōu)化的角度來看：GBDT采用的是數(shù)值優(yōu)化的思維, 用的最速下降法去求解Loss Function的最優(yōu)解, 其中用CART決策樹去擬合負梯度, 用牛頓法求步長。XGboost用的解析的思維, 對Loss Function展開到二階近似, 求得解析解, 用解析解作為Gain來建立決策樹, 使得Loss Function最優(yōu).

除了對目標函數(shù)添加正則項外，為了減小過擬合，xgboost還使用了列采樣和縮減方法（Shrinkage，即Learning rate）。

損失函數(shù)計算

對于二分類問題常使用負log損失作為損失函數(shù)，下面推導一下log loss的一階梯度G和海森矩陣H。：

其中p為預測概率。若為預測值，則有：

因此：

即：

往期精彩回顧




適合初學者入門人工智能的路線及資料下載
機器學習及深度學習筆記等資料打印
機器學習在線手冊
深度學習筆記專輯
《統(tǒng)計學習方法》的代碼復現(xiàn)專輯
AI基礎(chǔ)下載
機器學習的數(shù)學基礎(chǔ)專輯
獲取本站知識星球優(yōu)惠券，復制鏈接直接打開：
https://t.zsxq.com/qFiUFMV
本站qq群704220115。
加入微信群請掃碼：