XGboost(理论篇)

集成学习

集成学习是将多个模型组合成一个模型的方法,一般是将学习到的多个弱学习器(基分类器)进行组合,构成一个强学习器,集诸子百家之大成。根据组合方式不同,又分为 BaggingBaggingBoostingBoosting ,前者代表算法是随机深林,后者代表是 AdaBoostAdaBoostGBDTGBDTXGBoostXGBoost

加法模型

加法模型是将多个基学习器通过相加,组合成强学习器。

F(x)=i=1mαif(x;θi)F(x) = \sum_{i=1}^{m} \alpha_i f(x;\theta_i)

其中 F(x)F(x) 是组合起来的强学习器,αi\alpha_i 是弱分类器的权重,θi\theta_i 是弱分类器的参数。若弱分类器是决策树,则参数为叶子节点的值、选择的特征等。

GBDTGBDT 为例,训练时采用逐步求解的方法,依次确定每个基分类器的参数,然后加入到强学习器中,使强学习器的精度不断提升。具体过程如下:

y^i0=0y^i1=f1(xi)=y^i0+f1(xi)y^i2=f1(xi)+f2(xi)=y^i1+f2(xi)y^it=k=1tfk(xi)=y^it1+ft(xi)\begin{aligned} \hat{y}_{i}^{0} &=0 \\ \hat{y}_{i}^{1} &=f_{1} \left(x_{i}\right)=\hat{y}_{i}^{0}+f_{1}\left(x_{i}\right) \\ \hat{y}_{i}^{2} &=f_{1} \left(x_{i}\right)+f_{2}\left(x_{i}\right)=\hat{y}_{i}^{1}+f_{2}\left(x_{i}\right) \\ & \cdots \\ \hat{y}_{i}^{t} &=\sum_{k=1}^{t} f_{k}\left(x_{i}\right)=\hat{y}_{i}^{t-1}+f_{t}\left(x_{i}\right) \end{aligned}

目标函数

以训练第 tt 个模型为例,模型对第 ii 个样本 xix_i 的预测过程为:

y^it=y^it1+ft(xi)\hat{y}_{i}^{t} = \hat{y}_{i}^{t-1}+f_{t}(x_i)

其中 ft(xi)f_{t}(x_i) 就是要训练的新模型,目标函数为:

Lt=i=1nl(yi,yi^t)+k=1tΩ(fk)L_t = \sum_{i=1}^{n} l(y_i, \hat{y_i}^t) + \sum_{k=1}^{t} \Omega(f_k)

其中第一部分是损失项,第二部分是正则化项。nn 为训练样本个数,yiy_i 为样本 xix_i 的真实标签,y^i\hat{y}_i 为样本 xix_i 的预测标签。正则化项表示模型的复杂度:

Ω(ft)=γT+12λk=1Tωk2\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{k=1}^{T} \omega _k^2

其中 TT 为叶子结点个数,该项体现了决策树结构的复杂程度; ωk\omega_k 为训练的第 kk 颗树叶子结点对应的值,体现了决策树的预测值复杂程度。

根据学过的高数可以知道,函数在 xx^* 处取得极值的必要条件是导数为 00 ,即:

f(x)=0\nabla f(x^*) = 0

因此,可以使用求导的方法找到函数的极值。但是如果函数非常复杂,该方法不易求解,所以采用迭代算法,从一个初始点 xix_i ,利用在该点的一阶导和二阶导,逐渐移动到极值点。

因此,当实际优化问题的目标函数往往比较复杂时,为了使问题简化,通常将目标函数在某点附近展开为泰勒多项式来逼近原函数。

根据泰勒公式,f(x)f(x)x0x_0 处展开二阶导:

f(x)f(x0)+f(x0)(xx0)+f(x0)2(xx0)2f(x) \approx f(x_0) + f'(x_0)(x - x_0) + \frac{f''(x_0)}{2}(x - x_0)^2

或者:

f(x+Δx)f(x)+f(x)Δx+f(x)2Δx2f(x + \Delta x) \approx f(x) + f'(x) \Delta x + \frac{f''(x)}{2} \Delta x^2

推导过程

目标函数:

Lt=i=1nl(yi,yi^t)+k=1tΩ(fk)=i=1nl(yi,yi^t1+ft(xi))+k=1tΩ(fk)\begin{aligned} L_t &= \sum_{i=1}^{n} l(y_i, \hat{y_i}^t) + \sum_{k=1}^{t} \Omega(f_k) \\ &= \sum_{i=1}^{n} l(y_i, \hat{y_i}^{t-1} + f_t(x_i)) + \sum_{k=1}^{t} \Omega(f_k) \\ \end{aligned}

ft(xi)f_t(x_i) 看作 Δx\Delta x ,目标函数可以写成:

Lt=i=1nl(yi,yi^t1+ft(xi))+k=1tΩ(fk)=i=1n[l(yi,yi^t1)+gift(xi)+12hift2(xi)]+k=1tΩ(fk)\begin{aligned} L_t &= \sum_{i=1}^{n} l(y_i, \hat{y_i}^{t-1} + f_t(x_i)) + \sum_{k=1}^{t} \Omega(f_k) \\ &= \sum_{i=1}^{n} [l(y_i, \hat{y_i}^{t-1}) + g_if_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)] + \sum_{k=1}^{t} \Omega(f_k) \end{aligned}

其中,gig_i 为目标函数一阶导,hih_i 为目标函数二阶导。注意 :这里的求导是对 y^it1\hat y_i^{t-1} 导的。

假设损失函数 l(yi,yi^t1)l(y_i, \hat{y_i}^{t-1}) 为均方误差损失函数,则 l(yi,yi^t1)=(yiyi^t1)2l(y_i, \hat{y_i}^{t-1}) = (y_i- \hat{y_i}^{t-1})^2 ,其中 yiyi^y_i- \hat{y_i} 称为残差。

所以:

gi=l(yi,yi^t1)yi^t1=2(yiyi^t1)hi=2l(yi,yi^t1)2yi^t1=2\begin{aligned} g_i &= \frac{\partial l(y_i, \hat{y_i}^{t-1})}{\partial \hat{y_i}^{t-1}} = -2(y_i- \hat{y_i}^{t-1}) \\ h_i &= \frac{\partial ^2 l(y_i, \hat{y_i}^{t-1})}{\partial ^2 \hat{y_i}^{t-1}} = -2 \end{aligned}

训练第 tt 个模型时,y^it1\hat y_i^{t-1} 是上一个模型对 xix_i 的预测值,是已知的,所以 l(yi,yi^t1)l(y_i, \hat{y_i}^{t-1}) 是一个常数。因此,目标函数可以简化为:

Lt=i=1n[gift(xi)+12hift2(xi)]+k=1tΩ(fk)\begin{aligned} L_t = \sum_{i=1}^{n} [g_if_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)] + \sum_{k=1}^{t} \Omega(f_k) \end{aligned}

假设训练好了一颗决策树拟合当前的残差数据,决策树的叶子结点数为 TT ,第 jj 个叶子结点的值为 wjw_j 。定义函数 q(xi)=jq(x_i) = j 表示数据 xx 属于被分到第 jj 个叶子结点里的数据。

定义集合:

Ij={iq(xi)=j}I_j = \{i | q(x_i) = j\}

表示第 jj 个叶子结点的训练样本集合。

因为每个训练样本只属于一个叶子结点,所以目标函数可以转化为对每一个叶子结点里的样本集合求损失函数,然后累加:

Lt=i=1n[gift(xi)+12hift2(xi)]+k=1tΩ(fk)=i=1n[gift(xi)+12hift2(xi)]+γT+12λk=1Tωk2=k=1T[(iIkgi)ωk+12(iIkhi+λ)ωk2]+γT\begin{aligned} L_t &= \sum_{i=1}^{n} [g_if_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)] + \sum_{k=1}^{t} \Omega(f_k) \\ &= \sum_{i=1}^{n} [g_if_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)] + \gamma T + \frac{1}{2} \lambda \sum_{k=1}^{T} \omega _k^2 \\ &= \sum_{k=1}^{T} [ (\sum_{i \in I_k} g_i) \omega_k + \frac{1}{2}(\sum_{i \in I_k} h_i + \lambda) \omega_k^2 ] + \gamma T \end{aligned}

令:

Gk=iIkgiHk=iIkhi\begin{aligned} G_k = \sum_{i \in I_k} g_i, H_k = \sum_{i \in I_k} h_i \end{aligned}

则目标函数可写成:

Lt=k=1T[Gkωk+12(Hk+λ)ωk2]+γT\begin{aligned} L_t = \sum_{k=1}^{T} [G_k \omega_k + \frac{1}{2}( H_k + \lambda) \omega_k^2 ] + \gamma T \end{aligned}

目标函数对 ωk\omega _k 求导,可以得到叶子结点 kk 的最优值:

ωk=GkHk+λ\omega_k^* = -\frac{G_k}{H_k + \lambda}

带入目标函数:

Lt=12k=1TGk2Hk+λ+γT\begin{aligned} L_t = - \frac{1}{2} \sum_{k=1}^{T} \frac{G_k^2}{H_k + \lambda} + \gamma T \end{aligned}

经过推导后的目标函数作为选择最优分裂特征的标准。

假设某结点分裂前训练样本数为 II ,分裂后左结点的训练样本数为 ILI_L ,右结点样本数为 IRI_R

则分裂前的目标函数为:

Lt=12(GL+GR)2HL+HR+λ+γ\begin{aligned} L_t = - \frac{1}{2} \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} + \gamma \end{aligned}

分裂后的目标函数为:

Lt=12[GL2HL+λ+GR2HR+λ]+2γ\begin{aligned} L_t = - \frac{1}{2} [\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda}] + 2\gamma \end{aligned}

分裂后的信息增益为:

Gain=12[GL2HL+λ+GR2HR+λ(GL+GR)2HL+HR+λ]γ\begin{aligned} Gain = - \frac{1}{2} [\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}] -\gamma \end{aligned}

对于每一个特征,选取信息增益最大的作为分裂特征。

Reference

理解XGBoost