亚洲精品久久久久91,欧美色图综合

梯度提升（Gradient boosting）是一種用于回歸、分類和排序任務(wù)的技術(shù)，屬于Boosting算法族的一部分。Boosting是一族可將弱學(xué)習(xí)器提升為強(qiáng)學(xué)習(xí)器的算法，屬于集成學(xué)習(xí)（ensemble learning）的范疇。Boosting方法基于這樣一種思想：對于一個復(fù)雜任務(wù)來說，將多個專家的判斷進(jìn)行適當(dāng)?shù)木C合所得出的判斷，要比其中任何一個專家單獨(dú)的判斷要好。通俗地說，就是“三個臭皮匠頂個諸葛亮”的道理。梯度提升同其他boosting方法一樣，通過集成（ensemble）多個弱學(xué)習(xí)器，通常是決策樹，來構(gòu)建最終的預(yù)測模型。

Boosting、bagging和stacking是集成學(xué)習(xí)的三種主要方法。不同于bagging方法，boosting方法通過分步迭代（stage-wise）的方式來構(gòu)建模型，在迭代的每一步構(gòu)建的弱學(xué)習(xí)器都是為了彌補(bǔ)已有模型的不足。Boosting族算法的著名代表是AdaBoost，AdaBoost算法通過給已有模型預(yù)測錯誤的樣本更高的權(quán)重，使得先前的學(xué)習(xí)器做錯的訓(xùn)練樣本在后續(xù)受到更多的關(guān)注的方式來彌補(bǔ)已有模型的不足。與AdaBoost算法不同，梯度提升方法在迭代的每一步構(gòu)建一個能夠沿著梯度最陡的方向降低損失（steepest-descent）的學(xué)習(xí)器來彌補(bǔ)已有模型的不足。經(jīng)典的AdaBoost算法只能處理采用指數(shù)損失函數(shù)的二分類學(xué)習(xí)任務(wù)，而梯度提升方法通過設(shè)置不同的可微損失函數(shù)可以處理各類學(xué)習(xí)任務(wù)（多分類、回歸、Ranking等），應(yīng)用范圍大大擴(kuò)展。另一方面，AdaBoost算法對異常點(diǎn)（outlier）比較敏感，而梯度提升算法通過引入bagging思想、加入正則項等方法能夠有效地抵御訓(xùn)練數(shù)據(jù)中的噪音，具有更好的健壯性。這也是為什么梯度提升算法（尤其是采用決策樹作為弱學(xué)習(xí)器的GBDT算法）如此流行的原因。之前有種觀點(diǎn)認(rèn)為GBDT是性能最好的機(jī)器學(xué)習(xí) 算法，這當(dāng)然有點(diǎn)過于激進(jìn)又固步自封的味道，但通常各類機(jī)器學(xué)習(xí)算法比賽的贏家們都非常青睞GBDT算法，由此可見該算法的實(shí)力不可小覷。

基于梯度提升算法的學(xué)習(xí)器叫做GBM(Gradient Boosting Machine)。理論上，GBM可以選擇各種不同的學(xué)習(xí)算法作為基學(xué)習(xí)器。現(xiàn)實(shí)中，用得最多的基學(xué)習(xí)器是決策樹。為什么梯度提升方法傾向于選擇決策樹（通常是CART樹）作為基學(xué)習(xí)器呢？這與決策樹算法自身的優(yōu)點(diǎn)有很大的關(guān)系。決策樹可以認(rèn)為是if-then規(guī)則的集合，易于理解，可解釋性強(qiáng)，預(yù)測速度快。同時，決策樹算法相比于其他的算法需要更少的特征工程，比如可以不用做特征標(biāo)準(zhǔn)化，可以很好的處理字段缺失的數(shù)據(jù)，也可以不用關(guān)心特征間是否相互依賴等。決策樹能夠自動組合多個特征，它可以毫無壓力地處理特征間的交互關(guān)系并且是非參數(shù)化的，因此你不必?fù)?dān)心異常值或者數(shù)據(jù)是否線性可分（舉個例子，決策樹能輕松處理好類別A在某個特征維度x的末端，類別B在中間，然后類別A又出現(xiàn)在特征維度x前端的情況）。不過，單獨(dú)使用決策樹算法時，有容易過擬合的缺點(diǎn)。所幸的是，通過各種方法，抑制決策樹的復(fù)雜性，降低單顆決策樹的擬合能力，再通過梯度提升的方法集成多個決策樹，最終能夠很好的解決過擬合的問題。由此可見，梯度提升方法和決策樹學(xué)習(xí)算法可以互相取長補(bǔ)短，是一對完美的搭檔。至于抑制單顆決策樹的復(fù)雜度的方法有很多，比如限制樹的最大深度、限制葉子節(jié)點(diǎn)的最少樣本數(shù)量、限制節(jié)點(diǎn)分裂時的最少樣本數(shù)量、吸收bagging的思想對訓(xùn)練樣本采樣（subsample），在學(xué)習(xí)單顆決策樹時只使用一部分訓(xùn)練樣本、借鑒隨機(jī)森林的思路在學(xué)習(xí)單顆決策樹時只采樣一部分特征、在目標(biāo)函數(shù)中添加正則項懲罰復(fù)雜的樹結(jié)構(gòu)等?，F(xiàn)在主流的GBDT算法實(shí)現(xiàn)中這些方法基本上都有實(shí)現(xiàn)，因此GBDT算法的超參數(shù)還是比較多的，應(yīng)用過程中需要精心調(diào)參，并用交叉驗證的方法選擇最佳參數(shù)。

本文對GBDT算法原理進(jìn)行介紹，從機(jī)器學(xué)習(xí)的關(guān)鍵元素出發(fā)，一步一步推導(dǎo)出GBDT算法背后的理論基礎(chǔ)，讀者可以從這個過程中了解到GBDT算法的來龍去脈。對于該算法的工程實(shí)現(xiàn)，本文也有較好的指導(dǎo)意義，實(shí)際上對機(jī)器學(xué)習(xí)關(guān)鍵概念元素的區(qū)分對應(yīng)了軟件工程中的“開放封閉原則”的思想，基于此思想的實(shí)現(xiàn)將會具有很好的模塊獨(dú)立性和擴(kuò)展性。

機(jī)器學(xué)習(xí)的關(guān)鍵元素

先復(fù)習(xí)下監(jiān)督學(xué)習(xí)的關(guān)鍵概念：模型（model）、參數(shù)（parameters）、目標(biāo)函數(shù)（objective function）。

模型就是所要學(xué)習(xí)的條件概率分布或者決策函數(shù)，它決定了在給定特征向量 $x$ 時如何預(yù)測出目標(biāo) $y$ 。定義 $x_i \in R^d$ 為訓(xùn)練集中的第 $i$ 個訓(xùn)練樣本，則線性模型（linear model）可以表示為： $\hat{y}_i = \sum_j{w_j x_{ij}}$ 。模型預(yù)測的分?jǐn)?shù) $\hat{y}_i$ 在不同的任務(wù)中有不同的解釋。例如在邏輯回歸任務(wù)中， $1/(1+exp(-\hat{y}_i))$ 表示模型預(yù)測為正例的概率；而在排序?qū)W習(xí)任務(wù)中， $\hat{y}_i$ 表示排序分。

參數(shù)就是我們要從數(shù)據(jù)中學(xué)習(xí)得到的內(nèi)容。模型通常是由一個參數(shù)向量決定的函數(shù)。例如，線性模型的參數(shù)可以表示為： $\Theta={w_j|j=1,\cdots,d}$ 。

目標(biāo)函數(shù)通常定義為如下形式： $Obj(\Theta)=L(\Theta)+\Omega(\Theta)$ 其中， $L(\Theta)$ 是損失函數(shù)，用來衡量模型擬合訓(xùn)練數(shù)據(jù)的好壞程度； $\Omega(\Theta)$ 稱之為正則項，用來衡量學(xué)習(xí)到的模型的復(fù)雜度。訓(xùn)練集上的損失（Loss）定義為： $L=\sum_{i=1}^n l(y_i, \hat{y}_i)$ 。

常用的損失函數(shù)有:

平方損失（square loss）： $l(y_i, \hat{y}_i)=(y_i - \hat{y}_i)^2$ ；
Logistic損失： $l(y_i, \hat{y}_i)=y_i ln(1+e^{y_i}) + (1-y_i)ln(1+e^{\hat{y}_i})$ 。

常用的正則項有L1范數(shù) $\Omega(w)=\lambda \Vert w \Vert_1$ 和L2范數(shù) $\Omega(w)=\lambda \Vert w \Vert_2$ 。Ridge regression就是指使用平方損失和L2范數(shù)正則項的線性回歸模型；Lasso regression就是指使用平方損失和L1范數(shù)正則項的線性回歸模型；邏輯回歸（Logistic regression）指使用logistic損失和L2范數(shù)或L1范數(shù)正則項的線性模型。

目標(biāo)函數(shù)之所以定義為損失函數(shù)和正則項兩部分，是為了盡可能平衡模型的偏差和方差（Bias Variance Trade-off）。最小化目標(biāo)函數(shù)意味著同時最小化損失函數(shù)和正則項，損失函數(shù)最小化表明模型能夠較好的擬合訓(xùn)練數(shù)據(jù)，一般也預(yù)示著模型能夠較好地擬合真實(shí)數(shù)據(jù)（groud true）；另一方面，對正則項的優(yōu)化鼓勵算法學(xué)習(xí)到較簡單的模型，簡單模型一般在測試樣本上的預(yù)測結(jié)果比較穩(wěn)定、方差較小（奧坎姆剃刀原則）。也就是說，優(yōu)化損失函數(shù)盡量使模型走出欠擬合的狀態(tài)，優(yōu)化正則項盡量使模型避免過擬合。

從概念上區(qū)分模型、參數(shù)和目標(biāo)函數(shù)給學(xué)習(xí)算法的工程實(shí)現(xiàn)帶來了益處，使得機(jī)器學(xué)習(xí)的各個組成部分之間耦合盡量松散。

加法模型（additive model）

GBDT算法可以看成是由K棵樹組成的加法模型。一般我們使用CART（classification and regression tree）樹作為集成學(xué)習(xí)的基礎(chǔ)模塊，下圖是一顆用來預(yù)測某用戶是否喜歡電腦游戲X的例子，該例子中人群被劃分到不同的葉子節(jié)點(diǎn)，每個葉子節(jié)點(diǎn)被賦予一個分?jǐn)?shù)來表示其與目標(biāo)的關(guān)聯(lián)度。

cart.png

通常，一棵樹并不足以強(qiáng)大到能夠解決問題，我們使用基于多棵樹的集成模型來建模。在GBDT算法中，該集成模型即加法模型，它的形式化如下：

$\hat{y}_i=\sum_{k=1}^K f_k(x_i), f_k \in F \tag 0$

其中 $F$ 為所有樹組成的函數(shù)空間，以回歸任務(wù)為例，回歸樹可以看作為一個把特征向量映射為某個score的函數(shù)。該模型的參數(shù)為： $\Theta={f_1,f_2, \cdots, f_K }$ 。與一般的機(jī)器學(xué)習(xí)算法不同的是，加法模型不是學(xué)習(xí)d維空間中的權(quán)重，而是直接學(xué)習(xí)函數(shù)（決策樹）集合。

twocart.png

如上圖所示，每個樣本的最終得分是由每顆子樹的得分相加得到的。

上述加法模型的目標(biāo)函數(shù)定義為：

$Obj=\sum_{i=1}^n l(y_i, \hat{y}i) + \sum_{k=1}^K \Omega(f_k)，$

其中 $\Omega(\cdot)$ 是正則項，表示決策樹的復(fù)雜度，那么該如何定義樹的復(fù)雜度呢？比如，可以考慮樹的節(jié)點(diǎn)數(shù)量、樹的深度或者葉子節(jié)點(diǎn)所對應(yīng)的分?jǐn)?shù)的L2范數(shù)等等。

如何來學(xué)習(xí)加法模型呢？

解這一優(yōu)化問題，可以用前向分布算法（forward stagewise algorithm）。因為學(xué)習(xí)的是加法模型，如果能夠從前往后，每一步只學(xué)習(xí)一個基函數(shù)及其系數(shù)（在GBDT算法中即為樹的結(jié)構(gòu)和葉子節(jié)點(diǎn)的分?jǐn)?shù)），逐步逼近優(yōu)化目標(biāo)函數(shù)，那么就可以簡化復(fù)雜度。這一學(xué)習(xí)過程稱之為Boosting。具體地，我們從一個常量預(yù)測開始，每次學(xué)習(xí)一個新的函數(shù)，過程如下：

$\begin{split} \hat{y}_i^0 &= 0 \\ \hat{y}_i^1 &= f_1(x_i) = \hat{y}_i^0 + f_1(x_i) \\ \hat{y}_i^2 &= f_1(x_i) + f_2(x_i) = \hat{y}_i^1 + f_2(x_i) \\ & \cdots \\ \hat{y}_i^t &= \sum_{k=1}^t f_k(x_i) = \hat{y}_i^{t-1} + f_t(x_i) \ \end{split}$

那么，在每一步如何決定哪一個函數(shù) $f$ 被加入呢？指導(dǎo)原則還是最小化目標(biāo)函數(shù)。在第 $t$ 步，模型對 $x_i$ 的預(yù)測為： $\hat{y}_i^t= \hat{y}_i^{t-1} + f_t(x_i)$ ，其中 $f_t(x_i)$ 為這一輪我們要學(xué)習(xí)的函數(shù)（決策樹）。這個時候目標(biāo)函數(shù)可以寫為：

$\begin{split} Obj^{(t)} &= \sum_{i=1}^nl(y_i, \hat{y}_i^t) + \sum_{i=i}^t \Omega(f_i) \\ &= \sum_{i=1}^n l\left(y_i, \hat{y}_i^{t-1} + f_t(x_i) \right) + \Omega(f_t) + constant \end{split}\tag{1}$

舉例說明，假設(shè)損失函數(shù)為平均平方損失（mean square loss），則目標(biāo)函數(shù)為：

$\begin{split} Obj^{(t)} &= \sum_{i=1}^n \left(y_i - (\hat{y}_i^{t-1} + f_t(x_i)) \right)^2 + \Omega(f_t) + constant \\ &= \sum_{i=1}^n \left[2(\hat{y}_i^{t-1} - y_i)f_t(x_i) + f_t(x_i)^2 \right] + \Omega(f_t) + constant \end{split}\tag{2}$

其中， $(\hat{y}_i^{t-1} - y_i)$ 稱之為殘差（residual）。因此，在使用平方損失函數(shù)時，GBDT算法的每一步在生成決策樹時只需要擬合前面的模型的殘差。

在使用其他損失函數(shù)時，如logistic loss，就很難得到如MSE損失那樣簡潔的解析表達(dá)式。因此，Xgboost使用泰勒公式的二階展開式來近似目標(biāo)函數(shù)，詳細(xì)過程如下：

泰勒公式：設(shè) $n$ 是一個正整數(shù)，如果定義在一個包含 $a$ 的區(qū)間上的函數(shù) $f$ 在 $a$ 點(diǎn)處 $n+1$ 次可導(dǎo)，那么對于這個區(qū)間上的任意 $x$ 都有： $\displaystyle f(x)=\sum_{n=0}^{N}\frac{f^{(n)}(a)}{n!}(x-a)^ n+R_n(x)$ ，其中的多項式稱為函數(shù)在 $a$ 處的泰勒展開式， $R_n(x)$ 是泰勒公式的余項且是 $(x-a)^ n$ 的高階無窮小。
其中，零階導(dǎo)數(shù)理解為本身，常數(shù)0階導(dǎo)數(shù)仍為本身，函數(shù)的0階導(dǎo)數(shù)為函數(shù)本身；并且規(guī)定0!=1。

根據(jù)泰勒公式把函數(shù) $f(x+\Delta x)$ 在點(diǎn) $x$ 處二階展開，可得到如下等式： $f(x+\Delta x) \approx f(x) + f'(x)\Delta x + \frac12 f''(x)\Delta x^2 \tag 3$
（即用 $x+\Delta x$ 代替泰勒公式中的 $x$ ，并且用 $x$ 代替泰勒公式中的 $a$ ）

由等式(1)可知，目標(biāo)函數(shù)是關(guān)于變量 $\hat{y}_i^{t-1} + f_t(x_i)$ 的函數(shù)，若把變量 $\hat{y}_i^{t-1}$ 看成是等式(3)中的 $x$ ，把變量 $f_t(x_i)$ 看成是等式(3)中的 $\Delta x$ ，則等式(1)可轉(zhuǎn)化為：

$Obj^{(t)} = \sum_{i=1}^n \left[ l(y_i, \hat{y}_i^{t-1}) + g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) + constant \tag 4$

其中， $g_i$ 定義為損失函數(shù)的一階導(dǎo)數(shù)，即 $g_i=\partial_{\hat{y}_i^{t-1}}l(y_i,\hat{y}_i^{t-1})$ ； $h_i$ 定義為損失函數(shù)的二階導(dǎo)數(shù)，即 $h_i=\partial_{\hat{y}_i^{t-1}}^2l(y_i,\hat{y}_i^{t-1})$ 。這里需要注意的是，損失函數(shù)是對前一步的預(yù)測結(jié)果 $\hat{y}_i^{t-1}$ 求導(dǎo)。

假設(shè)損失函數(shù)為平方損失函數(shù)，則 $g_i=\partial_{\hat{y}^{t-1}}(\hat{y}^{t-1} - y_i)^2 = 2(\hat{y}^{t-1} - y_i)$ ， $h_i=\partial_{\hat{y}^{t-1}}^2(\hat{y}^{t-1} - y_i)^2 = 2$ ，把 $g_i$ 和 $h_i$ 代入等式(4)即得等式(2)。

由于函數(shù)中的常量在函數(shù)最小化的過程中不起作用，因此我們可以從等式(4)中移除掉常量項，得：
$Obj^{(t)} \approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) \tag 5$

由于要學(xué)習(xí)的函數(shù)僅僅依賴于目標(biāo)函數(shù)，從等式(5)可以看出只需為學(xué)習(xí)任務(wù)定義好損失函數(shù)，并為每個訓(xùn)練樣本計算出損失函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，通過在訓(xùn)練樣本集上最小化等式(5)即可求得每步要學(xué)習(xí)的函數(shù) $f(x)$ ，從而根據(jù)加法模型等式(0)可得最終要學(xué)習(xí)的模型。

GBDT算法

一顆生成好的決策樹，假設(shè)其葉子節(jié)點(diǎn)個數(shù)為 $T$ ，該決策樹是由所有葉子節(jié)點(diǎn)對應(yīng)的值組成的向量 $w \in R^T$ ，以及一個把特征向量映射到葉子節(jié)點(diǎn)索引（Index）的函數(shù) $q:R^d \to {1,2,\cdots,T}$ 組成的。因此，策樹可以定義為 $f_t(x)=w_{q(x)}$ 。

決策樹的復(fù)雜度可以由正則項 $\Omega(f_t)=\gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2$ 來定義，即決策樹模型的復(fù)雜度由生成的樹的葉子節(jié)點(diǎn)數(shù)量和葉子節(jié)點(diǎn)對應(yīng)的值向量的L2范數(shù)決定。

定義集合 $I_j=\{ i \vert q(x_i)=j \}$ 為所有被劃分到葉子節(jié)點(diǎn) $j$ 的訓(xùn)練樣本的集合。等式(5)可以根據(jù)樹的葉子節(jié)點(diǎn)重新組織為T個獨(dú)立的二次函數(shù)的和：
$\begin{split} Obj^{(t)} &\approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) \\ &= \sum_{i=1}^n \left[ g_iw_{q(x_i)} + \frac12h_iw_{q(x_i)}^2 \right] + \gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2 \\ &= \sum_{j=1}^T \left[(\sum_{i \in I_j}g_i)w_j + \frac12(\sum_{i \in I_j}h_i + \lambda)w_j^2 \right] + \gamma T \end{split}\tag 6$

定義 $G_j=\sum_{i \in I_j}g_i$ ， $H_j=\sum_{i \in I_j}h_i$ ，則等式(6)可寫為：
$Obj^{(t)} = \sum_{j=1}^T \left[G_iw_j + \frac12(H_i + \lambda)w_j^2 \right] + \gamma T$

假設(shè)樹的結(jié)構(gòu)是固定的，即由函數(shù) $q(x)$ 確定，令函數(shù) $Obj^{(t)}$ 對參數(shù) $w_j$ 的一階導(dǎo)數(shù)等于0，即可求得葉子節(jié)點(diǎn) $j$ 對應(yīng)的值為： $w_j^*=-\frac{G_j}{H_j+\lambda} \tag 7$

此時，目標(biāo)函數(shù)的值為
$Obj^* = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T \tag 8$
該函數(shù)度量了一顆樹結(jié)構(gòu)的好壞程度，其類似于決策樹算法中的不純度度量（impurity measure），只是額外考慮了正則項。

struct_score.png

綜上，為了便于理解，單顆決策樹的學(xué)習(xí)過程可以大致描述為：

枚舉所有可能的樹結(jié)構(gòu) $q$
用等式(8)為每個 $q$ 計算其對應(yīng)的分?jǐn)?shù) $Obj$ ，分?jǐn)?shù)越小說明對應(yīng)的樹結(jié)構(gòu)越好
根據(jù)上一步的結(jié)果，找到最佳的樹結(jié)構(gòu)，用等式(7)為樹的每個葉子節(jié)點(diǎn)計算預(yù)測值

然而，可能的樹結(jié)構(gòu)數(shù)量是無窮的，所以實(shí)際上我們不可能枚舉所有可能的樹結(jié)構(gòu)。通常情況下，我們采用貪心策略來生成決策樹的每個節(jié)點(diǎn)。

從深度為0的樹開始，對每個葉節(jié)點(diǎn)枚舉所有的可用特征
針對每個特征，把屬于該節(jié)點(diǎn)的訓(xùn)練樣本根據(jù)該特征值升序排列，通過線性掃描的方式來決定該特征的最佳分裂點(diǎn)，并記錄該特征的最大收益（采用最佳分裂點(diǎn)時的收益）；這里假設(shè)類別型特征已經(jīng)做了one-hot編碼
選擇收益最大的特征作為分裂特征，用該特征的最佳分裂點(diǎn)作為分裂位置，把該節(jié)點(diǎn)生長出左右兩個新的葉節(jié)點(diǎn)，并為每個新節(jié)點(diǎn)關(guān)聯(lián)對應(yīng)的樣本集
回到第1步，遞歸執(zhí)行到滿足特定條件為止

在上述算法的第二步，樣本排序的時間復(fù)雜度為 $O(n \log n)$ ，假設(shè)共有 K 個特征，那么生成一顆深度為 d 的樹的時間復(fù)雜度為 $O(dKn\log n)$ 。具體實(shí)現(xiàn)可以進(jìn)一步優(yōu)化計算復(fù)雜度，比如可以緩存每個特征的排序結(jié)果等。

如何計算每次分裂的收益呢？假設(shè)當(dāng)前節(jié)點(diǎn)記為 $C$ ,分裂之后左孩子節(jié)點(diǎn)記為 $L$ ，右孩子節(jié)點(diǎn)記為 $R$ ，則該分裂獲得的收益定義為當(dāng)前節(jié)點(diǎn)的目標(biāo)函數(shù)值減去左右兩個孩子節(jié)點(diǎn)的目標(biāo)函數(shù)值之和： $Gain=Obj_C-Obj_L-Obj_R$ ，具體地，根據(jù)等式(8)可得： $Gain=\frac12 \left[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma$ 其中， $-\gamma$ 項表示因為增加了樹的復(fù)雜性（該分裂增加了一個葉子節(jié)點(diǎn)）帶來的懲罰。當(dāng)節(jié)點(diǎn)的最佳分裂收益小于0時（也就是不考慮增加樹的復(fù)雜性懲罰時的收益小于 $\gamma$ 時），意味著此時最好不要分裂該節(jié)點(diǎn)。這也就是決策樹剪枝算法的原理。搜索某特征最佳分裂點(diǎn)的過程可參考下面的例子。

split_find.png

A left to right scan is sufficient to calculate the structure score of all possible split solutions, and we can find the best split efficiently.

關(guān)于如何計算特征的重要度，請參考《Tree ensemble算法的特征重要度計算》。

最后，總結(jié)一下GBDT的學(xué)習(xí)算法：

算法每次迭代生成一顆新的決策樹
在每次迭代開始之前，計算損失函數(shù)在每個訓(xùn)練樣本點(diǎn)的一階導(dǎo)數(shù) $g_i$ 和二階導(dǎo)數(shù) $h_i$
通過貪心策略生成新的決策樹，通過等式(7)計算每個葉節(jié)點(diǎn)對應(yīng)的預(yù)測值
把新生成的決策樹 $f_t(x)$ 添加到模型中： $\hat{y}_i^t = \hat{y}_i^{t-1} + f_t(x_i)$

通常在第四步，我們把模型更新公式替換為： $\hat{y}_i^t = \hat{y}_i^{t-1} + \epsilon f_t(x_i)$ ，其中 $\epsilon$ 稱之為步長或者學(xué)習(xí)率。增加 $\epsilon$ 因子的目的是為了避免模型過擬合。

參考資料

[1] Gradient Boosting 的更多內(nèi)容
[2] XGBoost 是一個優(yōu)秀的GBDT開源軟件庫，有多種語言接口
[3] Pyramid 是一個基于Java語言的機(jī)器學(xué)習(xí)庫，里面也有GBDT算法的介紹和實(shí)現(xiàn)
[4] Friedman的論文《Greedy function approximation: a gradient boosting machine》是比較早的GBDT算法文獻(xiàn)，但是比較晦澀難懂，不適合初學(xué)者，高階選手可以進(jìn)一步學(xué)習(xí)
[5] "A Gentle Introduction to Gradient Boosting"是關(guān)于Gradient Boosting的一個通俗易懂的解釋，比較適合初學(xué)者或者是已經(jīng)對GBDT算法原理印象不深的從業(yè)者
[6] 關(guān)于GBDT算法調(diào)參的經(jīng)驗和技巧可以參考這兩篇博文：《GBM調(diào)參指南》、《XGBoost調(diào)參指南》，作者使用的算法實(shí)現(xiàn)工具來自于著名的Python機(jī)器學(xué)習(xí)工具scikit-learn
[7] GBDT算法在搜索引擎排序中的應(yīng)用可以查看這篇論文《Web-Search Ranking with Initialized Gradient Boosted Regression Trees 》，這篇論文提出了一個非常有意思的方法，用一個已經(jīng)訓(xùn)練好的隨機(jī)森林模型作為GBDT算法的初始化，再用GBDT算法優(yōu)化最終的模型，取得了很好的效果

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

全網(wǎng)最淺顯易懂的GBDT(xgboost)算法原理深入剖析

全網(wǎng)最淺顯易懂的GBDT(xgboost)算法原理深入剖析

機(jī)器學(xué)習(xí)的關(guān)鍵元素

加法模型（additive model）

GBDT算法

參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

全網(wǎng)最淺顯易懂的GBDT(xgboost)算法原理深入剖析

機(jī)器學(xué)習(xí)的關(guān)鍵元素

加法模型（additive model）

GBDT算法

參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av