基于 Boosting 框架的主流集成算法介紹（上）

本文是決策樹的第三篇，主要介紹基于 Boosting 框架的主流集成算法，包括 XGBoost 和 LightGBM。

XGBoost

XGBoost 是大規(guī)模并行 boosting tree 的工具，它是目前最快最好的開(kāi)源 boosting tree 工具包，比常見(jiàn)的工具包快 10 倍以上。Xgboost 和 GBDT 兩者都是 boosting 方法，除了工程實(shí)現(xiàn)、解決問(wèn)題上的一些差異外，最大的不同就是目標(biāo)函數(shù)的定義。故本文將從數(shù)學(xué)原理和工程實(shí)現(xiàn)上進(jìn)行介紹，并在最后介紹下 Xgboost 的優(yōu)點(diǎn)。

1.1 數(shù)學(xué)原理

1.1.1 目標(biāo)函數(shù)

我們知道 XGBoost 是由 k 個(gè)基模型組成的一個(gè)加法運(yùn)算式：

其中 為第 k 個(gè)基模型， 為第 i 個(gè)樣本的預(yù)測(cè)值。

損失函數(shù)可由預(yù)測(cè)值 與真實(shí)值 進(jìn)行表示：

其中 n 為樣本數(shù)量。

我們知道模型的預(yù)測(cè)精度由模型的偏差和方差共同決定，損失函數(shù)代表了模型的偏差，想要方差小則需要簡(jiǎn)單的模型，所以目標(biāo)函數(shù)由模型的損失函數(shù) L 與抑制模型復(fù)雜度的正則項(xiàng) 組成，所以我們有：

為模型的正則項(xiàng)，由于 XGBoost 支持決策樹也支持線性模型，所以這里不再展開(kāi)描述。

我們知道 boosting 模型是前向加法，以第 t 步的模型為例，模型對(duì)第 i 個(gè)樣本 的預(yù)測(cè)為：

其中 由第 t-1 步的模型給出的預(yù)測(cè)值，是已知常數(shù)， 是我們這次需要加入的新模型的預(yù)測(cè)值，此時(shí)，目標(biāo)函數(shù)就可以寫成：

求此時(shí)最優(yōu)化目標(biāo)函數(shù)，就相當(dāng)于求解 。

泰勒公式是將一個(gè)在 處具有 n 階導(dǎo)數(shù)的函數(shù) f(x) 利用關(guān)于 的 n 次多項(xiàng)式來(lái)逼近函數(shù)的方法，若函數(shù) f(x) 在包含 的某個(gè)閉區(qū)間 上具有 n 階導(dǎo)數(shù)，且在開(kāi)區(qū)間 (a,b) 上具有 n+1 階導(dǎo)數(shù)，則對(duì)閉區(qū)間 上任意一點(diǎn) x 有 其中的多項(xiàng)式稱為函數(shù)在 處的泰勒展開(kāi)式， 是泰勒公式的余項(xiàng)且是 的高階無(wú)窮小。

根據(jù)泰勒公式我們把函數(shù) 在點(diǎn) x 處進(jìn)行泰勒的二階展開(kāi)，可得到如下等式：

我們把 視為 視為 ，故可以將目標(biāo)函數(shù)寫為：

其中 為損失函數(shù)的一階導(dǎo)， 為損失函數(shù)的二階導(dǎo)，注意這里的求導(dǎo)是對(duì) 求導(dǎo)。

我們以平方損失函數(shù)為例：

則：

由于在第 t 步時(shí) 其實(shí)是一個(gè)已知的值，所以 是一個(gè)常數(shù)，其對(duì)函數(shù)的優(yōu)化不會(huì)產(chǎn)生影響，因此目標(biāo)函數(shù)可以寫成：

所以我們只需要求出每一步損失函數(shù)的一階導(dǎo)和二階導(dǎo)的值（由于前一步的 是已知的，所以這兩個(gè)值就是常數(shù)），然后最優(yōu)化目標(biāo)函數(shù)，就可以得到每一步的 f(x) ，最后根據(jù)加法模型得到一個(gè)整體模型。

1.1.2 基于決策樹的目標(biāo)函數(shù)

我們知道 Xgboost 的基模型不僅支持決策樹，還支持線性模型，這里我們主要介紹基于決策樹的目標(biāo)函數(shù)。

我們可以將決策樹定義為 ，x 為某一樣本，這里的 q(x) 代表了該樣本在哪個(gè)葉子結(jié)點(diǎn)上，而 w_q 則代表了葉子結(jié)點(diǎn)取值 w ，所以 就代表了每個(gè)樣本的取值 w （即預(yù)測(cè)值）。

決策樹的復(fù)雜度可由葉子數(shù) T 組成，葉子節(jié)點(diǎn)越少模型越簡(jiǎn)單，此外葉子節(jié)點(diǎn)也不應(yīng)該含有過(guò)高的權(quán)重 w （類比 LR 的每個(gè)變量的權(quán)重），所以目標(biāo)函數(shù)的正則項(xiàng)可以定義為：

即決策樹模型的復(fù)雜度由生成的所有決策樹的葉子節(jié)點(diǎn)數(shù)量，和所有節(jié)點(diǎn)權(quán)重所組成的向量的 范式共同決定。

這張圖給出了基于決策樹的 XGBoost 的正則項(xiàng)的求解方式。

我們?cè)O(shè) 為第 j 個(gè)葉子節(jié)點(diǎn)的樣本集合，故我們的目標(biāo)函數(shù)可以寫成：

第二步到第三步可能看的不是特別明白，這邊做些解釋：第二步是遍歷所有的樣本后求每個(gè)樣本的損失函數(shù)，但樣本最終會(huì)落在葉子節(jié)點(diǎn)上，所以我們也可以遍歷葉子節(jié)點(diǎn)，然后獲取葉子節(jié)點(diǎn)上的樣本集合，最后在求損失函數(shù)。即我們之前樣本的集合，現(xiàn)在都改寫成葉子結(jié)點(diǎn)的集合，由于一個(gè)葉子結(jié)點(diǎn)有多個(gè)樣本存在，因此才有了 和 這兩項(xiàng)， 為第 j 個(gè)葉子節(jié)點(diǎn)取值。

為簡(jiǎn)化表達(dá)式，我們定義 ，則目標(biāo)函數(shù)為：

這里我們要注意 和 是前 t-1 步得到的結(jié)果，其值已知可視為常數(shù)，只有最后一棵樹的葉子節(jié)點(diǎn) 不確定，那么將目標(biāo)函數(shù)對(duì) 求一階導(dǎo)，并令其等于 0 ，則可以求得葉子結(jié)點(diǎn) j 對(duì)應(yīng)的權(quán)值：

所以目標(biāo)函數(shù)可以化簡(jiǎn)為：

上圖給出目標(biāo)函數(shù)計(jì)算的例子，求每個(gè)節(jié)點(diǎn)每個(gè)樣本的一階導(dǎo)數(shù) 和二階導(dǎo)數(shù) ，然后針對(duì)每個(gè)節(jié)點(diǎn)對(duì)所含樣本求和得到的 和 ，最后遍歷決策樹的節(jié)點(diǎn)即可得到目標(biāo)函數(shù)。

1.1.3 最優(yōu)切分點(diǎn)劃分算法

在決策樹的生長(zhǎng)過(guò)程中，一個(gè)非常關(guān)鍵的問(wèn)題是如何找到葉子的節(jié)點(diǎn)的最優(yōu)切分點(diǎn)，Xgboost 支持兩種分裂節(jié)點(diǎn)的方法——貪心算法和近似算法。

1）貪心算法

1. 從深度為 0 的樹開(kāi)始，對(duì)每個(gè)葉節(jié)點(diǎn)枚舉所有的可用特征；
2. 針對(duì)每個(gè)特征，把屬于該節(jié)點(diǎn)的訓(xùn)練樣本根據(jù)該特征值進(jìn)行升序排列，通過(guò)線性掃描的方式來(lái)決定該特征的最佳分裂點(diǎn)，并記錄該特征的分裂收益；
3. 選擇收益最大的特征作為分裂特征，用該特征的最佳分裂點(diǎn)作為分裂位置，在該節(jié)點(diǎn)上分裂出左右兩個(gè)新的葉節(jié)點(diǎn)，并為每個(gè)新節(jié)點(diǎn)關(guān)聯(lián)對(duì)應(yīng)的樣本集
4. 回到第 1 步，遞歸執(zhí)行到滿足特定條件為止

那么如何計(jì)算每個(gè)特征的分裂收益呢？

假設(shè)我們?cè)谀骋还?jié)點(diǎn)完成特征分裂，則分列前的目標(biāo)函數(shù)可以寫為：

分裂后的目標(biāo)函數(shù)為：

則對(duì)于目標(biāo)函數(shù)來(lái)說(shuō)，分裂后的收益為：

注意該特征收益也可作為特征重要性輸出的重要依據(jù)。

對(duì)于每次分裂，我們都需要枚舉所有特征可能的分割方案，如何高效地枚舉所有的分割呢？

我假設(shè)我們要枚舉所有 x < a 這樣的條件，對(duì)于某個(gè)特定的分割點(diǎn) a 我們要計(jì)算 a 左邊和右邊的導(dǎo)數(shù)和。

我們可以發(fā)現(xiàn)對(duì)于所有的分裂點(diǎn) a，我們只要做一遍從左到右的掃描就可以枚舉出所有分割的梯度和 和 。然后用上面的公式計(jì)算每個(gè)分割方案的分?jǐn)?shù)就可以了。

2）近似算法

貪婪算法可以的到最優(yōu)解，但當(dāng)數(shù)據(jù)量太大時(shí)則無(wú)法讀入內(nèi)存進(jìn)行計(jì)算，近似算法主要針對(duì)貪婪算法這一缺點(diǎn)給出了近似最優(yōu)解。

對(duì)于每個(gè)特征，只考察分位點(diǎn)可以減少計(jì)算復(fù)雜度。

該算法會(huì)首先根據(jù)特征分布的分位數(shù)提出候選劃分點(diǎn)，然后將連續(xù)型特征映射到由這些候選點(diǎn)劃分的桶中，然后聚合統(tǒng)計(jì)信息找到所有區(qū)間的最佳分裂點(diǎn)。

在提出候選切分點(diǎn)時(shí)有兩種策略：

• Global：學(xué)習(xí)每棵樹前就提出候選切分點(diǎn)，并在每次分裂時(shí)都采用這種分割；
• Local：每次分裂前將重新提出候選切分點(diǎn)。

直觀上來(lái)看，Local 策略需要更多的計(jì)算步驟，而 Global 策略因?yàn)楣?jié)點(diǎn)沒(méi)有劃分所以需要更多的候選點(diǎn)。

下圖給出不同種分裂策略的 AUC 變換曲線，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為測(cè)試集 AUC，eps 為近似算法的精度，其倒數(shù)為桶的數(shù)量。

我們可以看到 Global 策略在候選點(diǎn)數(shù)多時(shí)（eps 小）可以和 Local 策略在候選點(diǎn)少時(shí)（eps 大）具有相似的精度。此外我們還發(fā)現(xiàn)，在 eps 取值合理的情況下，分位數(shù)策略可以獲得與貪婪算法相同的精度。

• 第一個(gè) for 循環(huán)：對(duì)特征 k 根據(jù)該特征分布的分位數(shù)找到切割點(diǎn)的候選集合 。XGBoost 支持 Global 策略和 Local 策略。
• 第二個(gè) for 循環(huán)：針對(duì)每個(gè)特征的候選集合，將樣本映射到由該特征對(duì)應(yīng)的候選點(diǎn)集構(gòu)成的分桶區(qū)間中，即 ，對(duì)每個(gè)桶統(tǒng)計(jì) G,H 值，最后在這些統(tǒng)計(jì)量上尋找最佳分裂點(diǎn)。

下圖給出近似算法的具體例子，以三分位為例：

根據(jù)樣本特征進(jìn)行排序，然后基于分位數(shù)進(jìn)行劃分，并統(tǒng)計(jì)三個(gè)桶內(nèi)的 G,H 值，最終求解節(jié)點(diǎn)劃分的增益。