参考:
- 陈天奇-"XGBoost: A Scalable Tree Boosting System" Paper地址: <https://arxiv.org/abs/1603.02754
- 文哲大佬全程手推
兄弟们,
再来手撸一波XGBoost, 这上半月目标算达成了.
感觉比上次撸 SVM 还是要难一些的. 但必须手撸, 因为, 近两年, 我已认识到, 很多梦魇, 只有从源头上彻底消灭后, 便不会时常萦绕心灵...
一边看原paper 和贪心地搬运大佬的知识,化为己有, 其乐无穷.
1. 目标函数
结合上篇的 XGBoost 的引入, 知道了该算法是 基于残差 来训练的, 也就是说, 最后的结果是要将前面的预测值都累加起来, 这点非常关键哦.
1.1 使用多棵树来预测
假设已经训练好了 K 棵树, 则对 第 i 个样本 的 最终预测值为:
\(\hat y = \sum \limits _{k}^K f_k(x_i)\)
1.2 目标函数抽象
\(Obj = \sum \limits_{i=1}^n l(y_i, \hat y_i) + \sum \limits_{k=1}^K \Omega(f_k)\)
现在,需要关注的是, 我在构造, 当前第k棵树的时候, 我的目标函数是怎样的, 然而到此为止只是泛泛地定义了一个问题, 甚至关键部分的定义都还是模糊的, 更别谈去参数化了.
1.3 树的复杂度
可以用如下的几个指标来衡量
- 叶节点的个数
- 树的深度
- 叶节点的值
1.4 累加树的训练
是基于残差的训练嘛, 因此咱可考虑用数学归纳法.
假设我们已经训练 k-1 棵树, 即: 1, 2, 3, 4, ....k-1, 则下一棵树 k 是多少呢? 也就是说在训练每棵树的时候, 都需要一个目标函数.
假设我们已经知道 前 k 棵树的预测值, 记为 \(\hat y_i\), 每棵树记为 \(f_i, \ 其中 i=0, 1, 2...k\)
对于给定一个 \(x_i\),
\(\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)} = 0 + f_1(x_i) + f_2(x_i) = \hat y_i^{(1)} + f_2(x_i)\)
\(\hat y_i^{(3)} = f_1(x_i) + f_2(x_i) + f_3(x_i) = \hat y_i^{(2)} + f_3(x_i)\)
\(\hat y_i^{(4)} = f_1(x_i) + f_2(x_i) + f_3(x_i) + f_4(x_i) = \hat y_i^{(3)} + f_4(x_i)\)
....
\(\hat y_i^{(k)} = f_1(x_i) + f_2(x_i) + ... f_{k-1}(x_i) + f_k(x_i) = \hat y_i^{(k-1)} + f_k(x_i)\)
$ = \sum \limits _{i=1}^k f_i(x_i) = y_i^{(k-1)} + f_k(x_i)$
即在有 k 棵树的情况下, 此时最终的预测值为: \(y_i^{(k-1)} + f_k(x_i)\) => 前 k-1 棵树的预测值之和+第k棵树的预测值
于是, 回顾一波目标函数:
\(Obj = \sum \limits_{i=1}^n l(y_i, \hat y_i) + \sum \limits_{k=1}^K \Omega(f_k)\)
首先来定义第一项, 即损失函数部分, 并将刚推导的 k-1 的思想来代入得:
\(loss = \sum \limits _{i=1}^n l(y_i, y_i^{(k-1)} + f_k(x_i))\)
同样, 对于第二项, 正则化 的部分, 也拆解为这种 k-1 与 k 的写法:
\(re = \sum \limits _{k=1}^{(K-1)} \Omega (f_{k}) + \Omega (f_k)\)
这样一来, 此时的目标函数就变成了:
\(\sum \limits _{i=1}^n l(y_i, \hat y_i^{(k-1)}+ f_k(x_i) + \sum \limits_{k=1}^{(K-1)} \Omega(f_k) + \Omega(f_k)\)
此时我们的假设是, 前 k-1 棵树是已知的, 于是再做进一步简化:
则, 第 k 棵 树的目标函数:
\(\sum \limits _{i=1}^n l(y_i, \hat y_i^{(k-1)}+f_k(x_i)) + \Omega(f_k)\)
因此, 优化的目标, 就是参数化 \(f_k(x_i)\) 和 \(\Omega (f_k)\) 使其 最小化
这里发现, 其实说到底, 还是要来整 \(f_K(x_i)\) 但其形式都是未知的, 更别说是优化了, 就有尴尬了, 怎么办呢, 不知道如描述一个函数, 可以用 其他函数去近似嘛, 函数近似?, 这不立马回想到 大一的高数课, "泰勒级数展开...
2. 用泰勒级数去近似目标函数
通俗点就是, 对于连续可导的函数 f(x), 具体形式不明确,
但是,
有要求 f(x) 在某点 \(x_0\) 的近似值
因此
可以在该点做一个幂级数展开, 一般展开到2阶就很精确了, 继续展开, 就越逼近呀.
在本例就是(就只写到2阶, 方便推导):
$f(x+ \triangle x) \simeq = f(x) + f'(x)\triangle x) + \frac {1}{2} f''(x)\triangle x^2 $
于是, 此时的问题变成了如何去定义 \(f(x) \ 和 \triangle x\) 依葫芦画瓢, 来整之前的这个:
\(\sum \limits _{i=1}^n l(y_i, \hat y_i^{(k-1)}+f_k(x_i)) + \Omega(f_k)\)
假设:
\(f(x) = l(y_i, \hat y_i^{(k-1)})\) , 如果将 \(f_k(x_i)\) 看作是 \(\triangle x\)
则: \(f(x + \triangle x) = l(y_i + f_k(x_i))\)
于是, 将 当前的目标函数代入到 泰勒展开式即:
\(\sum \limits _{i=1}^n l(y_i, \hat y_i^{(k-1)}+f_k(x_i)) + \Omega(f_k)\)
\(= [\sum \limits _{i=1}^n l(y_i, \hat y_i^{(k-1)}) + \partial _{\hat y_i^{(k-1)}} l(y_i, \hat y_i^{(k-1)}) * f_k(x_i) + 0.5 \partial ^2 _{\hat y_i^{(k-1)}} l(y_i, \hat y_i^{(k-1)})* f_k^2(x_i)] + \Omega(f_k)\)
注意因为 假设的前提是关于 k-1项的部分 ,其实我们是已知的, 为了简写, 用两个关于i 的变量代替即可
\(=\sum \limits _{i=1}^n g_i f_k(x_i) + 0.5h_i f_k^2(x_i)] + \Omega(f_k)\)
重要结论, 再写一遍!
目标函数为: \(\sum \limits _{i=1}^n g_i f_k(x_i) + \frac{1}{2} h_i f_k ^2(x_i) + \Omega(f_k)\)
3. 如何定义一棵树
目标函数已经化简差不多了, 现在就开始整, 如何定义 \(f_k(x_i)\) 对树的参数化, 包含3个方面:
- 样本的位置
- 样本的值
- 树的复杂度
我们知道, 诸如决策树, 回归树... 这些树结构, 都是二叉树的形式, 这里也一样. 每一个样本的输入训练后, 输出的值就分布在该树的某一个叶节点上(终端节点).
因为所所有假设的前提是 在训练第 K棵树的时, (K-1) 棵树的形状是已知的
3.1 样本的在树中的位置
(主观) 假设, 以树的节点, 从左到右依次编号作为树的叶节点的唯一编号, 则对于样本 \(x_i\) 在树中的位置可表示为(定义一个函数来整)
\(q(x_i)\) : 表示样本的位置. 参数为某个样本
\(q(x_1) = 1\): 表示 \(x_1\) 这个样本在树中的叶节点编号(id) 是1 (或树的第一个节点)
\(q(x_2) = 3\): 表示 \(x_2\) 这个样本在树中的叶节点编号(id) 是3
\(q(x_3) = 3\): 表示 \(x_3\) 这个样本在树中的叶节边编号(id) 是3
... 每个样本的位置就搞定了
3.2 参数化一棵树 \(f_k(x_i)\)
位置都确定了, 则值不就是该节点的权重参数嘛
\(f_k(x_i) = w_{q(x_i)}\)
于是在 k 这棵树下, 对于每个样本点:
\(f_k(x_1) = w_{q(x_1)} = 123\),
\(f_k(x_2) = w_{q_(x_2)} = 456\)
\(f_k(x_3) = w_{q(x_3)} = 456\)
....
这样对所有的样本 \(x_n\) 的预测结果,不都可以在这 第 k 棵树中表示出来了呀
然后再定义一个集合函数, 用来表示样本和叶子节点编号的 n:1 关系
\(I_j = \{ i|g(x_i) = j \}\)
"如上面的 \(q(x_2) = q(x_3) = 3\) 表示, 样本2, 样本3 都分布在树的 3号叶节点上"
则可表示为: \(I_3 = \{ 2, 3\}\)
3.3 如何参数化树的复杂度
重要结论再写一遍(目标函数):
\(\sum \limits [_{i=1}^n g_i f_k(x_i) + 0.5f_k ^2{x_i}] + \Omega (f_k)\)
关于loss 部分, 关键的 \(f_k(x_i) = w_ig(x_i)\) 已经搞定了, 现在就只剩下 后面的 树的复杂度. 因为树的复杂度如果非常高, 则越容易过拟合; 如果值很大则容易, 则太牛逼,不合适"集成", 不能搞个人崇拜嘛.
节点的个数, 不要太多
叶节点的值不大, 尽量小
\(\Omega (f_k) = T + \sum \limits _{j=1}^T w_j^2\)
然后为了更好控制这个约束, 再引入两个 超参数 来约束
\(\Omega (f_k) = \gamma T + 0.5 \lambda \sum \limits _{j=1}^Tw_j^2\)
4. 转为以节点为对象的目标树
回归一波推导的历史.
首先, 抽象概念定义出:
\(Obj = \sum \limits_{i=1}^n l(y_i, \hat y_i) + \sum \limits_{k=1}^K \Omega(f_k)\)
然后基于假设 k-1 已知下推出:
\(\sum \limits _{i=1}^n l(y_i, \hat y_i^{(k-1)}+ f_k(x_i) + \sum \limits_{k=1}^{(K-1)} \Omega(f_k) + \Omega(f_k)\)
然后用泰勒级数近似
\(\sum \limits _{i=1}^n g_i f_k(x_i) + \frac{1}{2} h_i f_k ^2(x_i) + \Omega(f_k)\)
最后再参数化树及其复杂度
\([\sum \limits _{i=1}^n g_i w_{q(x_i)} +0.5h_iw^2 _{q(x_i)}] + \gamma T + 0.5 \lambda \sum \limits_{j=1}^Tw_j^2\)
可以发现,
$\sum \limits {i=1}^n g_i w{q(x_i)} $
是按照样本来循环的, 是要先找到样本在树中的位置 \(q(x_i)\) , 然后再去其上的权重 \(w_i\) 之前也说了, 样本与w 是一个多对一的关系.
现在呢, 考虑另一种遍历, 按遍历节点,然后取出该节点的样本ID集合, 也就是前面定义的 \(I_j = \{i|g(x_i) = j\}\)
于是, 按照节点来遍历即可改写为:
\(\sum \limits _{j=1}^T [(\sum \limits _{i \in I_j}g_i)w_j + 0.5(\sum \limits _{i \in I_j}h_i) + \lambda) w_j^2] + \gamma T\)
目的是最小化:
\(\sum \limits _{j=1}^T [(\sum \limits _{i \in I_j}g_i)w_j + 0.5(\sum \limits _{i \in I_j}h_i) + \lambda) w_j^2] + \gamma T\)
而 \((\sum \limits _{i \in I_j}g_i)\) 是常量, 简记为 \(G_j\) , 同时\(0.5 \sum \limits _{i \in I_j} h_i\) 也是常量, 简记为 \(H_j\) (因为 k-1 棵树已知嘛)
这样一写出来, 大家都就豁然开朗了
\(\sum \limits _{j=1}^T[H_j w_j^2 + G_jw_j] + \gamma T\)
显然, 在 \(w* = -\frac {G_j}{H_i + \lambda}\) 处(代入) 取得最小值: $Obj = -\frac {1}{2} \sum \limits _{j=1}^T\frac {G_j^2}{H_j + \lambda} + \gamma T $
结论: 在已知一颗树的形状下, 直接可求解出, 每个叶节点的最优解, 以及这棵树的 目标函数值
so, 最后一步就是,如何来学习出一一棵新树的形状啦
是不是,
感觉
有点
像
在
递归地 倒推 哈哈哈
5. 如何训练一颗新树的形状
前面的一大通的推导, 就得出一个结论: 已知树的形状, 可直接求解其叶子节点的最优解和目标函数值
重要结论再写一遍:
\(\sum \limits _{j=1}^T[H_j w_j^2 + G_jw_j] + \gamma T\)
在叶节点为\(w* = -\frac {G_j}{H_i + \lambda}\) 取得目标函数最小值: $-\frac {1}{2} \sum \limits _{j=1}^T\frac {G_j^2}{H_j + \lambda} + \gamma T $
5.1 计算树的评估指标 (Score)
根据推论, 在已知一棵树的形状下, 可以直接求解出最优解. 即从理论上讲, 要训练新树, 枚举法, 直接训练出所有的树的形状 tree1, tree_2, tree_3...tree_n, 然后
\(min \ Obj (tree_1, tree_2...tree_n)\) 选择最小的即可.
但实际枚举上是不可能实现的, 于是, 我们可采用贪心算法的方式来寻找一个较好的树的形状.
\(obj = -0.5 \sum \limits _{j=1}^T \frac {G_j^2}{H_j + \lambda} + \gamma T\)
对于某个节点的是否分裂, 就是看 分裂前后的 目标函数值相差 如果很大, 则有分的价值.
5.2 根据 目标值 构建一新树
还是按文哲老师一样, 以形象一点的案例来整
分裂前obj = \(-0.5 [\frac {(G_5 +G_6)^2}{H_5 + H_6 +\lambda} +\frac {(G_1 + G_2 + ..G_4)^2}{H_1 + ...H_4 + \lambda} ] + \gamma * 2\)
....特征分割.... 分割后的叶节点分别为 {5,6}, L, R
分裂后obj = \(-0.5 [\frac {(G_5 +G_6)^2}{H_5 + H_6 +\lambda} +\frac {(G_L)^2}{H_L + \lambda} + \frac {(G_R)^2}{H_R + \lambda} ] + \gamma * 3\)
可将分裂前而obj 也可以写为 L, R 的形式即:
分裂前obj = \(-0.5 [\frac {(G_5 +G_6)^2}{H_5 + H_6 +\lambda} +\frac {(G_L+ G_R)^2}{H_L+ H_R + \lambda} ] + \gamma * 2\)
判断是否继续分裂, 其实即 |分裂前obj - 分解后obj | (相差) 很大则继续分裂呀
即: 此时的目标函数为:
前 - 后 = $ -0.5 [\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$
6. 总结XGBoost推导过程
总体上来认识 XGBoost, 是一种集成学习的 树结构算法. 是基于残差来训练的, 最终的预测值是每棵树的预测值的累加. 总体上跟决策树其实是有类似的, 用来做分类,回归均可, 网上一大把, 随便抄都是使用教程, 调参啥的. 主要回顾推导的思路.
总体推导,有点像 "递归或倒推"的感觉, 也是从概念到定义.
(1) 假设已经训练好了 K 棵树, 则对 第 i 个样本 的 最终预测值为:
\(\hat y = \sum \limits _{k}^K f_k(x_i)\)
(2) 抽象定义出 树的 损失 和 复杂度约束
\(Obj = \sum \limits_{i=1}^n l(y_i, \hat y_i) + \sum \limits_{k=1}^K \Omega(f_k)\)
(3) "叠加树思想, 引入全篇最重要假设: 假设要训练 第 k 棵树, 则对于 (k-1)棵树的形状是已知的.
\(\sum \limits _{i=1}^n l(y_i, \hat y_i^{(k-1)}+f_k(x_i)) + \Omega(f_k)\)
优化的目标, 就是参数化 \(f_k(x_i)\) 和 \(\Omega (f_k)\) 使其 最小化
(4) 用泰勒函数去对其二阶近似
\(\sum \limits _{i=1}^n g_i f_k(x_i) + \frac{1}{2} h_i f_k ^2(x_i) + \Omega(f_k)\)
其中 \(g_i, h_i\) 是关于 前 (k-1) 相关的已知量
(5) 定义一颗树的位置 和 值(权重)
\(f_k(x_i) = w_{q(x_i)}\)
(6) 定义集合函数, 用来表示样本和树的叶子节点编号的 n:1 关系
\(I_j = \{ i|g(x_i) = j \}\)
(7) 定义树的复杂度(节点个数 和 节点值大小约束), 并引入两个超参数
\(\Omega (f_k) = \gamma T + 0.5 \lambda \sum \limits _{j=1}^Tw_j^2\)
(8) 推导出较完整的目标函数 (树的定义, 和复杂度)
\([\sum \limits _{i=1}^n g_i w_{q(x_i)} +0.5h_iw^2 _{q(x_i)}] + \gamma T + 0.5 \lambda \sum \limits_{j=1}^Tw_j^2\)
(9) 最为关键一步: 根据 (8) 将树当前以 样本下标的形式 改为 以节点的方式 表示
原因在于
a. 样本的方式下, \(w_{q(x_i)}\) 一个变量的下标是函数, 这没法去处理
b. 改写后发现是关于 叶节点位置 \(w_j\) 的 二次函数 \(ax^2 + bx + c\)
\(\sum \limits _{j=1}^T [(\sum \limits _{i \in I_j}g_i)w_j + 0.5(\sum \limits _{i \in I_j}h_i) + \lambda) w_j^2] + \gamma T\)
(10) 得到全篇最重要的结论:
显然, 在 \(w* = -\frac {G_j}{H_i + \lambda}\) 处(代入) 取得最小值: $Obj = -\frac {1}{2} \sum \limits _{j=1}^T\frac {G_j^2}{H_j + \lambda} + \gamma T $
即: 在已知一颗树的形状下, 直接可求解出, 每个叶节点的最优解, 以及这棵树的 目标函数值
(11) 基于(10) 这个最重要结论, 采用 贪心算法, 训练一棵新的树
跟决策树其实类似的, 前者是以(特征) 最大熵 作为分割条件, XGBoost 是以 分裂节点前后的目标函数的差距 来作为是否分割的条件.
前-后= $ -0.5 [\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$
全篇推导的重点, 其实都是为了得出(10) , 而 最后训练新树, 则更适合用来代码来撸个直观.
代码实现, 有心情再用 Numpy 撸, 我还是想做一个自信的 C + V 调参侠.