这部分主要介绍GBDT以及XGBOOST

这部分能学到的东西包括:
(1)无所不在的偏差-方差平衡
(2)目标函数:loss+正则的模式应用于回归树学习
(3)我们既要预测还要简单的模型
(4)定义了我们想要学习的(目标,模型)
(5)如何进行学习

我们如何学习
1、目标函数:loss+正则
2、我们不能用SGD,因为他们是树,不是多项式了
3、解决办法:叠加训练(boosting提升):从一个常数值开始,每次加一个新的函数。

叠加训练
1、我们怎么决定要加的函数呢?通过优化目标函数
2、展示在第t轮的预测
注意:在平方loss中的展开计算中,有一项残差的平方被加到const项中了。

泰勒展开拟合损失
1、除了平方误差的情况,目标函数仍然很复杂
2、用泰勒展开目标函数:
(1)泰勒公式
(2)含义:我现在要做的事情就是用f(t)去拟合残差:即l=(r+f(x))
3、拿MSE来进行计算演示一下
4、和之前的slice比较

新的目标函数
1、目标函数:把常数项去掉,现在的目标函数就比较清晰,它是一个关于f(x)的多项式,不管是MSE,还是logloss,都能通过开了展开的方式展成多项式
2、为什么我们要费力气进行推导呢,为什么不只增加树的数量呢?
(1)理论收益:知道我们正在学习的是什么,以及收敛性
(2)工程收益:召回监督学习的元素
---g和h来自于损失函数,是损失函数的求导
---学习仅仅通过依靠目标函数,目标函数和g和h有关
---如果要求通过MSE和逻辑loss两种方式来实现提升树,应该如何划分模型呢

重新定义树
现在我们用叶子分数作为一个向量来定义树,如图所示

定义树的复杂度
注意:不是唯一的定义形式哦~~
现在的定义是和叶子节点的数目以及叶子节点分数的L2正则相关

目标函数计算:将复杂度加进去,并且整理,是T个独立二次函数的和
i:有i个样本,每个人就是一个样本
j:叶子节点j

结构分数
1、对于单变量二次函数情况下,使式子最小的x值,已经将x带入求得的最小值
2、整理目标函数
3、按照上面的推导,也可以计算目标函数的最小值,以及使目标函数最小的w值
PS:此时Obj具有通用性,可用于自定义损失函数

结构分数的计算举例

单棵树的搜索算法
1、列举可能的树结构
2、运用下面计算分数的式子来计算结构分数
3.选择obj最小的作为最佳树结构,并且运用最优的权重
4.但是,树结构有很多很多可能
优化过程理解:假设我们有3个叶子节点,那么把这5个样本分到这3个叶子节点,有非常多的分法,我们需要一个一个的尝试,找到obj最小的,再求出最优的w,这样做很麻烦,计算量很大,需要很多尝试,还必须保证不能漏掉任何可能的结构。所以有下面的优化。

树贪婪学习
实践中,我们贪婪的增加树的数目:
(1)从深度为0的树开始
(2)对于这个树的每一个叶子节点,尝试去增加一个分割点,加入分隔点后的目标函数可见上图
(3)那么怎么找到最优的分裂点呢

高效的找出最优的分裂点
(1)首先我们选取一个特征,假如说:年龄,选取a为分裂点
(2)我们要做的就是左边和右边g和h的和,然后带入增益公式计算
(3)首先对实例点排序,对于不同的特征,从左到右线性扫描,最终决定最优的分裂点。

分裂点寻找的算法
1、对于每一个结点,对所有的特征穷举
(1)对于每个特征,通过特征值将实例进行排序
(2)沿着特征,运用线性扫描来找到最优的分裂点
(3)再遍历下一个特征,仍然用这种找分裂点的方法
2、深度为k的树的时间复杂度
(1)对于一层排序,需要时间nlog(n),由于有d个特征,k层,所以为ndklog(n)
(2)进一步优化(例如:运用近似或者将排序特征进行缓存)

对于离散变量呢
上面我们主要讨论的是连续变量,那么对于离散变量呢?
1、一些树的学习算法,是将连续变量和离散变量分开处理的,其实我们也可以用上面基于连续变量推导出来的分数计算方法
2、事实上,这里没有必要去单独的处理离散变量
(1)我们可以把离散的变量编码成数值向量,这里用的是one-hot编码。
(2)如果有很多很多类,这个向量是稀疏的,处理稀疏数据的算法优先

剪枝和正则化
1.分裂的增益,可能是负的。什么时候呢?当训练loss的减少比正则化力度还要小的时候。我们要找的是简单性和可预测性之间的平衡。
2、提前停止:
(1)如果最佳分裂点是负的,那么提前停止分裂
(2)但是也可能是一个分裂有益于后面的分裂
3、后剪枝
将一个树生长到它的最大深度,递归的剪枝,剪去叶子节点分裂是负增益的。

回顾
1、每个迭代过程增加一个树
2、每个迭代都需要计算一阶导和二阶导
3、对增长树f(x)进行贪婪统计
4、将f(x)加到模型:
(1)通常我们会加一个衰减因子,在0.1左右
(2)这就意味着我们并不是每一步都是做充分的优化,我们要为以后的迭代保留可能性,这有助于防止过拟合。
网友评论