XGBoost,全称: Extreme Gradient Boosting
概述
- CART回归树是XGBoost的基分类器
XGBoost模型推导(假设回归树的结构确定)
模型\(F\)的加法定义：
$$
\begin{align}
F(x;w) = \sum_{k=0}^{K} f_{k}(x;w_{k})
\end{align}
$$
- 其中, \(x\)为输入样本, \(f_{k}\)为分类回归树,可以是分类回归树空间中的任意一棵树, \(w_{k}\)是树\(f_{k}\)的参数
定义损失函数
$$
\begin{align}
L^{t} &= \sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t}) + \Omega(f_{t}) \\
&= \sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t-1} + f_{t}(x_{i})) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
\end{align}
$$
- \(L^{t}\): 第 \(t\) 轮迭代的损失函数
- \(l(y_{i},\hat{y}_{i}^{t})\) 表示单个样本的损失函数定义
- \(\hat{y}_{i}^{t} = \hat{y}_{i}^{t-1} + f_{t}(x_{i})\) 表示第 \(t\) 轮 \(x_{i}\) 样本的预测值
- 加法模型: 第 \(t\) 轮预测值 = 第 \(t-1\) 轮预测值 + 第 \(t\) 棵(轮)决策树的预测值
- \(\Omega(f_{t})\) 表示正则项
- \(n\) 表示样本的个数
- \(T\) 表示叶子结点的个数
- \(w_{j}\) 表示叶节点分数, 即任意样本落到第 \(t\) 棵(轮)决策树的第 \(j\) 叶子结点时的预测值(可称为第 \(t\) 棵(轮)决策树的第 \(j\) 叶子结点的预测值)
- \(\gamma\)和\(\lambda\)都是正则项参数
第 \(t\) 轮训练的目标
- 找到一个最优的分类器 \(f_t^{\star}(x)\), 满足
$$
\begin{align}
f_t^{\star}(x) &= \arg\max_{f_t(x)}L^{t} \\
&= \arg\max_{f_t(x)}\left(\sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t}) + \Omega(f_{t})\right) \\
&= \arg\max_{f_t(x)}\left(\sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t-1} + f_{t}(x_{i})) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \right)
\end{align}
$$
最小化损失函数推导
损失函数二阶泰勒展开
回忆传统泰勒展开:
$$
\begin{aligned}
f(x) &= f(x_0) + f’(x_0)(x-x_0) + \frac{f’’(x_0)}{2!}(x-x_0)^2 + \cdots + \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n \\
& = \sum\limits_{n=0}^{\infty}\frac{f^{(n)}x_0}{n!}(x - x_0)^n
\end{aligned}
$$二阶泰勒展开公式
$$
\begin{align}
f(x+\Delta x) \approx f(x) + f’(x)\Delta x + \frac{1}{2}f’’(x)\Delta x^2
\end{align}
$$在我们的场景中,令
- \(x = \hat{y}_{i}^{t-1}\)
- \(\Delta x = f_{t}(x_{i})\)
则有对单个样本能得到
$$
\begin{align}
l(y_{i},\hat{y}_{i}^{t-1} + f_{t}(x_{i})) \approx l(y_i,\hat{y}_i^{t-1}) + l’(y_i,\hat{y}_i^{t-1})f_t(x_i) + \frac{1}{2}l’’(y_i,\hat{y}_i^{t-1})f_t^2(x_i)
\end{align}
$$- \(l’(y_i,\hat{y}_i^{t-1})\) 是 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的一阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值
- \(l’’(y_i,\hat{y}_i^{t-1})\) 是 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的二阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值
我们第 \(t\) 轮的目标是找到一个最优的分类器 \(f_t^{\star}(x)\)最小化损失函数 \(L^{t}\)
$$
\begin{align}
L^{t} \approx \sum_{i=1}^{n}\left(l(y_i,\hat{y}_i^{t-1}) + l’(y_i,\hat{y}_i^{t-1})f_t(x_i) + \frac{1}{2}l’’(y_i,\hat{y}_i^{t-1})f_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
\end{align}
$$显然上面式子中的 \(l(y_i,\hat{y}_i^{t-1})\) 与 \(f_t(x_i)\) 无关,可以移除,于是有
$$
\begin{align}
L^{t} \approx \sum_{i=1}^{n}\left(l’(y_i,\hat{y}_i^{t-1})f_t(x_i) + \frac{1}{2}l’’(y_i,\hat{y}_i^{t-1})f_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
\end{align}
$$令:
- \(g_i = l’(y_i,\hat{y}_i^{t-1})\) 为 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的一阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值
- \(h_i = l’’(y_i,\hat{y}_i^{t-1})\) 是 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的二阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值
则有:
$$
\begin{align}
L^{t} \approx \sum_{i=1}^{n}\left(g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
\end{align}
$$做一个重要的转换:
$$f_t(x_i) = w_j, \quad s.t. \ x_i \in I_j$$- 上面的式子前半部分成立的条件是 \(x_i\) 落在叶子结点 \(j\) 上
- 我们将条件\(x_i\) 落在叶子结点 \(j\) 上表示为 \(\ x_i \in I_j\)
于是: 我们可以将前面对样本的累加变成对叶子结点的累加
$$
\begin{align}
L^{t} &\approx \sum_{j=1}^{T}\left((\sum_{i \in I_j}g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i)w_j^2\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
&\approx \sum_{j=1}^{T}\left((\sum_{i \in I_j}g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i + \lambda)w_j^2\right) + \gamma T
\end{align}
$$令:
- \(G_j = \sum_{i \in I_j}g_i\)
- \(H_j = \sum_{i \in I_j}h_i\)
则有
$$
\begin{align}
L^{t} \approx \sum_{j=1}^{T}\left(G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2\right) + \gamma T
\end{align}
$$\(L^t\) 对 \(w_j\) 求偏导有
$$
\begin{align}
\frac{\partial L^{t}}{\partial w_j} = G_j + (H_j + \lambda)w_j
\end{align}
$$令导数 \(\frac{\partial L^{t}}{\partial w_j} = 0\) 可得
$$
\begin{align}
w_j^{\star} = -\frac{G_j}{H_j+\lambda}
\end{align}
$$同时
$$
\begin{align}
L^{\star^t} &\approx min(L^t) \\
&\approx \sum_{j=1}^{T}\left(G_j\cdot (-\frac{G_j}{H_j+\lambda}) + \frac{1}{2}(H_j + \lambda)\cdot(-\frac{G_j}{H_j+\lambda})^2\right) + \gamma T \\
&\approx -\frac{1}{2}\sum_{j=1}^{T}\left(\frac{G_j^2}{H_j+\lambda}\right) + \gamma T
\end{align}
$$目标函数的计算示例: 目标分数越小越好
结论
- 在第 \(t\) 轮回归树的结构确定后,我们得到的最优叶节点分数与结构无关 \(w_j^{\star} = -\frac{G_j}{H_j+\lambda}\)
- 最小损失与第 \(t\) 轮回归树的结构的复杂度(叶节点数量)相关
- 我们还需要确定第 \(t\) 轮回归树的结构
回归树的结构确定
普通决策树树结构的确定
- 详细情况可参考: ML——DT-决策树
ID3
- 最大化信息增益来选择分裂特征
C4.5
- 最大化信息增益比来选择分裂特征
CART
分类树
- 最小化基尼指数来选择分裂特征
回归树
- 最小化平方误差来选择分裂特征
XGBoost结点分裂前后的信息增益
- 信息增益应该与前面的损失函数相关, 损失越小越好
- 原始损失函数为
$$
\begin{align}
L^{\star^t} \approx -\frac{1}{2}\sum_{j=1}^{T}\left(\frac{G_j^2}{H_j+\lambda}\right) + \gamma T
\end{align}
$$ - 显然,要使得损失函数最小,我们需要使得下面的式子最大:
$$
\begin{align}
\frac{G_j^2}{H_j+\lambda}
\end{align}
$$ - 一个结点分裂后的信息为
$$
\begin{align}
\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}
\end{align}
$$- 左子树的信息 + 右子树的信息
- 一个结点分裂前信息为
$$
\begin{align}
\frac{(G_L + G_R)^2}{H_L+ H_R + \lambda}
\end{align}
$$ - 从而我们定义一个结点分列前后的信息增益为:
$$
\begin{align}
Gain = \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{align}
$$- Gain 越大说明当前结点的当前分裂方式越好
- 其中 \(\gamma\) 是一个超参数用于防止过拟合,可以理解为有两层含义:
- 用于对叶节点数目进行控制
- 用于增大分裂前后Gain的阈值
- 事实上 \(\gamma\) 不是凭空来的,开始的定义中 \(\gamma\) 就是L1正则化(叶节点数量)的系数, 这里分裂后叶节点数量多了1个, 我们希望树的叶节点越少越好(模型越简单越好),而这个的信息增益越大越好, 所以减去 \(\gamma\) 值,防止结点分裂得太多
- 对于每个特征的每个分裂点, \(\gamma\) 值都相同,所以 \(\gamma\) 值对特征和分裂点的选择没有影响,只是影响了某个结点是否能够被分裂(信息增益太小或者为负时我们可以选择不分裂)
XGBoost树节点分裂
精确分裂算法
- 单个叶节点精确计算信息增益分裂流程(特征和特征分裂取值的选择, 假设一共m个特征)
- 注意: 每次只对叶节点分裂,已经分裂了的就不是叶节点了,不能二次分裂
- 原图来自: https://www.cnblogs.com/massquantity/p/9794480.html
近似分裂算法
- 将每个特征的取值划分为多个分位点
- 每次考察特征时值考察分位点,减少计算复杂度
- 其他的步骤与前面的精确分裂算法相同,包括分数计算和选择最大分数等
分桶策略与GBDT的不同
- 传统的GBDT分桶时每个样本的权重都是相同的
- XGBoost中每个样本的权重为损失函数在该样本点的二阶导数(对不同的样本,计算得到的损失函数的二阶导数是不同的), 这里优点AdaBoost的思想,重点关注某些样本的感觉
- 这里影响的是划分点的位置(我们划分划分点[桶]时都是均匀划分样本到桶里面,当不同样本的权重不同时,每个桶里面的样本数量可能会不同)
- 下图是一个示例
- 详细推导解释,为什么选择损失函数在当前样本的二阶导数作为权重?
$$
\begin{align}
L^{t} &\approx \sum_{i=1}^{n}\left(g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
&\approx \sum_{i=1}^{n}\frac{1}{2}h_i\left(2\frac{g_i}{h_i}f_t(x_i) + f_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
&\approx \sum_{i=1}^{n}\frac{1}{2}h_i\left(f_t(x_i) - \frac{g_i}{h_i}\right)^2 + \sum_{i=1}^{n}\left ( \frac{g_i^2}{2h_i} - 2g_if_t(x_i) \right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
\end{align}
$$- 上面的式子中第二项在原文中用constant来表示,可以被看成某种正则项
- 第一项是一个平方误差表达式,样本 \(x_i\) 对应的输出值为 \(\frac{g_i}{h_i}\), 而样本权重就是 \(h_i\)
- 权重代表概率,概率越大说明该点出现的次数或者该点附近的值出现的次数就越多.
- XGBoost分桶流程
- [待更新]
XGBoost整棵树分裂流程
- 初始化\(f^0(x)\)
- for t=1 to M:
- 计算损失函数对每个训练样本点的一阶导数 \(g_i\) ,二阶导数 \(h_i\)
- 递归对叶子节点运用树分裂算法生成一颗决策树 \(f^t(x)\),
- (这一步包括叶子节点的分数 \(w_j\) 也都确定下来)
- (这一步可以使用近似分裂算法加快训练速度)
- 把新生成的决策树加入到模型中, \(\hat{y}^t = \hat{y}^{t-1} + f_m(x)\)
传统GDBT与XGBoost的比较
- 参考博客: ML——XGBoost-vs-传统GBDT