在最近的 Kaggle 竞赛中,利使用 Xgboost 的队伍经常能问鼎冠军,那么问题来了,Xgboost 为什么这么强呢?
算法释义
Xgboost 是一种带有正则化项,并利使用损失函数泰勒开展式中二阶导数信息优化求解并添加少量计算优化的梯度提升树。Xgboost 的目标函数定义为:
其中 l 为损失函数, Ω(ft(x)) 是使用于惩罚 ft(x) 模型复杂度的正则化项。根据上述目标函数可以得到 Xgboost 在每一轮前向分步算法中的目标函数为:
从而每一步的目标函数可以使用损失函数的一阶导数和二阶导数来表示,这样每一轮需要求解的 ft(x) 为:
那么如何使目标函数最小化呢?
算法求解
Xgboost 每生成一颗树的方式和其余决策树的方式相似,采使用一种贪心策略。
我们知道一颗决策树可以表示为:
其中 q(x) 把 x 映射到决策树中的一个节点,wq 把每一个结点映射一个值,即 ft(x) 的取值。
我们知道上述目标函数中有权重 w 以及树的节点数量 T 两组变量,首先上式可以拆分为 T 个独立的二次函数最小化问题,每个子问题中只有 w 权重这一组变量,首先求解权重 w。
权重求解
由于二次函数最小化问题有解析解,所以直接求解:
树的生成
处理了权重求解的问题,如何处理结点数量问题呢?也就是说怎样样对结点进行划分呢?这里一般在每个节点上采使用贪心策略进行划分。通过比较划分前和划分后目标函数的减一些来选择最优划分属性和划分点,具体地:
减少树的权重
用 Xgboost 没生成一棵决策树时,升级 y(t)(x) 时:
一般采使用较小的 ε 值,例如 0.1,这样可以防止在某一轮“学得太好”,并且为未来的迭代提供“学习空间”,可以有效地防止过拟合。
参考资料
《Xgboost PPT》,陈天奇
上一篇 目录 下一篇