机器学习集成算法:XGBoost模型构造

《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,Kaggle 实战。期待您的到来!

01

回顾

昨天介绍了XGBoost的基本思想,说到新加入进来的决策树必须能使原已有的更好才行吧,那么将XGBoost这个提升的过程如何用数学模型来表达呢?

02

XGBoost整体模型

机器学习的有监督问题,通常可以分为两步走:模型建立(比如线性回归时选用线性模型),根据目标函数求出参数(比如球出线性回归的参数)。对于XGBoost,也是做有监督任务了,也可以按照这个过程去分析,它的模型表示为如下,k表示树的个数,f表示构建的每个数结构,xi表示第i个样本,xi在每个树上的得分值的和就是xi的预测值,

它的目标函数表示为如下,其中等号右侧第一项表示所有样本点的误差和,第二项表示对每棵树的惩罚项(我们知道,惩罚项是用来使得预测的模型不那么复杂的方法,这也是为了提高模型的泛化能力),原始目标函数形式如下:

其中上标 t 代表第 t 轮集成

总之,我们就是要让预测值接近真实值,同时要让树模型尽可能的简单。接下来,看看在集成的过程中,如何尽可能地使得目标函数尽可能地小。

03

如何集成

XGBoost是串行集成的,这是与随机森林的不同之处,详细看下这个过程,期初只有一棵树,后来yi2时,加入进来f2,依次递推,第 t轮的预测模型,等于保留前面 t-1 轮的模型预测,和新来的 ft,前面说过f可以看做一颗树的构造。

将上面的递推公式带入到初始目标函数后得到,第一次改进目标函数后得到:

上式中等号的第二项是正则化惩罚项,是为了限制树的叶子节点的个数,防止树变得过于庞大的,它等于:

上式怎么用呢?举个例子,如下图,一共3个叶子节点,则 T = 3,小男孩这个叶子节点的权重为+2,所以平方为4,因此惩罚项等于如下吧:

目标函数至此做了一步演化,下面进一步将等号右边第一项误差函数项,在此采用常用的平方误差项,进行目标函数的第二次演化,如下,

XGBoost模型还给出了一个更一般的误差模型,上面我们不是根据平方误差项吗,如果采取一个通用性更强的模型,应该怎么写的,可以看到 ft 相当于一个当前轮次的变化量,可以想到 f(x + dx) = f(x) + f(x)'dx + 0.5f(x)''dx + ... 这就是泰勒展开式,一般地取前三项就能保证问题的精度了,所以我们进行目标函数的第二次,更一般的演化,得到下式:

这是第一次演化后的公式,进行泰勒展开,关键要分清谁是 x , 谁是 dx 吧! 可以看到 与参数 t 相关的才是公式的变量,所以 x 为 y(t-1), dx 相当于 ft(xi) 吧,yi是给定样本编号 i的真实值吧,为常数,

所以,对其展开后为

其中,

在进行第 t 轮集成的时候,loss( yi, yi(t-1) )这项已经知道了吧,是个常数了,比如预测一个价格为每股2元的股票,在第 t-1 轮的时候我们就得出股票的价格为1.5元,所以在第 t 轮的时候,loss就等于0.5吧,因此 loss那项是可以拿掉的。

好了,至此,我们就把目标函数演化了一部分了,但是,XGBoost真正NB的地方,是下面这节,将对样本的遍历,转化为对叶子节点的遍历,这是巧妙的地方。

04

XGBoost最精彩的部分:转化的巧妙

首先,晒出两个映射,第一个映射是 q,在树结构 f 已知的情况下表,给出一个样本 xi ,通过 q 可以得出 xi 位于的叶子节点编号,如同下图,给出小女孩,通过 q 可以得出 leaf2,即属于叶子编号2,

晒出的第二个映射为 w ,这个不难理解,就像神经网络中神经元的权重参数,即 小女孩的权重参数为 +0.1,综合起来分析,

w ( q ( 小女孩 ) ) = +0.1

因此,可以将下式:

进行第三次演化后为下式:

这还不是最精彩的地方,因为上式还是对样本 i 从1到n的遍历,接下来,这个式子,将对样本的遍历转化为了对叶子节点的遍历,这是XGBoost的最重要的一步转化,进行第四次演化后为下式,

其中 ,

表示:第 j 个叶子中包括的所有样本, wj表示第 j 个叶子的权重。

综上所述,将

再由上带入进去,进一步化简为,

令,Gj, Hj 分别为:

目标函数经过第五次演化后为下式,

这就是目标函数的最终形式了。

05

求解目标函数

看到这个目标函数,就已经非常明了了,它是关于wj 的一维二次函数吧,所以对它求最小值,还是非常简单的吧,这个就不讲了,直接求出 wj 在取得什么值时,loss值会取到最小值,

我们费了这么多劲,至此终于推算出,在第 t 轮集成时,到底该选择哪个树结构 ft 的衡量标准了,哪个树结构 ft 能使得在t-1轮的目标函数上减少的最多,也就是 obj 越小越好吧,我们就选择它吧。

05

分割所得的信息增益

对于每次扩展,是要枚举所有可能的分割方案,比较分割后的信息增益,求出最大值对应的分割点。比如要枚举所有 x < constant 这样的条件,对于某个分割,要计算 constant 左边和右边,还有没有切分这个节点时的信息增益求出来,求解信息增益的公式如下:

如果,Gain 大于某个阈值,则这个分割是有必要的,然后根据枚举的结果,取出分割能获得的最大增益。

对于这次特定的分割,

GL = g1 + g4

HL = h1 + h4

GR = g2 + g5 + g3

HR = h2 + h5 + h3

然后带入信息增益的公式,求出本次分割获得信息增益,然后枚举所有可能的分割得到的信息增益,选取最大值,假定得出如下所示的最佳分割点,此时 constant = 0.9,则可以得到 x < 0.9时,左子树只含有一个节点,右子树含有剩余节点,这种 ft 树结构。

总结下,以上介绍了XGBoost的目标函数原理推导,进一步得出了某个分割的信息增益,进而得出构造 ft 的过程。明天根据XGBoost的开源库,实战演练下XGBoost做分类和回归的过程。

算法channel已推送的更多文章:

1 机器学习:不得不知的概念(1)

2 机器学习:不得不知的概念(2)

3 机器学习:不得不知的概念(3)

4 回归分析简介

5 最小二乘法:背后的假设和原理(前篇)

6 最小二乘法原理(后):梯度下降求权重参数

7 机器学习之线性回归:算法兑现为python代码

8 机器学习之线性回归:OLS 无偏估计及相关性python分析

9 机器学习线性回归:谈谈多重共线性问题及相关算法

10 机器学习:说说L1和L2正则化

11 机器学习逻辑回归:原理解析及代码实现

12 机器学习逻辑回归:算法兑现为python代码

13 机器学习:谈谈决策树

14 机器学习:对决策树剪枝

15 机器学习决策树:sklearn分类和回归

16 机器学习决策树:提炼出分类器算法

17 机器学习:说说贝叶斯分类

18 朴素贝叶斯分类器:例子解释

19 朴素贝叶斯分类:拉普拉斯修正

20 机器学习:单词拼写纠正器python实现

21 机器学习:半朴素贝叶斯分类器

22 机器学习期望最大算法:实例解析

23 机器学习高斯混合模型(前篇):聚类原理分析

24 机器学习高斯混合模型(中篇):聚类求解

25 机器学习高斯混合模型(后篇):GMM求解完整代码实现

26 高斯混合模型:不掉包实现多维数据聚类分析

27 高斯混合模型:GMM求解完整代码实现

28 数据降维处理:背景及基本概念

29 数据降维处理:PCA之特征值分解法例子解析

30 数据降维处理:PCA之奇异值分解(SVD)介绍

31 数据降维处理:特征值分解和奇异值分解的实战分析

32 机器学习集成算法:XGBoost思想

本文分享自微信公众号 - 算法channel(alg-channel)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-12-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

【干货】机器学习工程师必须知道的十个算法

【新智元导读】机器学习算法可以分为三个大类:监督学习、无监督学习、强化学习。监督学习对于有属性(标记)的特定数据集(训练集)是非常有效的。无监督学习对于在给定未...

32160
来自专栏量子位

“每天AI资讯这么多!该看哪些?”推荐一份优质资料清单

原作 BAILOOL & meetshah1995 Root 编译自 GitHub 量子位 出品 | 公众号 QbitAI 人工智能最近火到炸裂,不看吧担心和时...

33960
来自专栏量子位

干货分享 | 自然语言处理及词向量模型介绍(附PPT)

云脑科技机器学习训练营第二期,对自然语言处理及词向量模型进行了详细介绍,量子位作为合作媒体为大家带来本期干货分享~ 本期讲师简介 ? 樊向军 云脑科技核心算法工...

53470
来自专栏人称T客

报告 | 机器学习:竞争优势的新探索

T客汇官网:tikehui 撰文 |卿云 最近,MIT技术评论定制和Google Cloud完成了一项名为《机器学习:竞争优势的新探索》调查,发现: ●201...

37370
来自专栏新智元

【干货】机器学习常用 35 大算法盘点(附思维导图)

【新智元导读】本文将带你遍历机器学习领域最受欢迎的算法。系统地了解这些算法有助于进一步掌握机器学习。当然,本文收录的算法并不完全,分类的方式也不唯一。不过,看完...

54870
来自专栏量子位

不再需要词典了,现在,AI通过无监督学习学会了双语翻译

维金 编译 Science 量子位 出品 | 公众号 QbitAI ? 由于神经网络技术的发展,翻译自动化已经取得了长足的进步。然而传统上,训练这样的神经网络...

23330
来自专栏量子位

我在Google用AI研究基因,入门从吴恩达的课程开始

允中 编译 Google博客 量子位 出品 | 公众号 QbitAI ? Google AI入驻计划,是一项为期12个月的研究培训项目,希望帮助不同领域的科学...

383100
来自专栏量子位

用机器学习拯救“智障”聊天机器人,谷歌开放分析平台Chatbase

李杉 李林 编译整理 量子位 出品 | 公众号 QbitAI 当你做了一个网站、App、游戏,肯定会马上想到要加上统计分析功能,这早就成了互联网产品的标配组件,...

451100
来自专栏量子位

亚马逊全面发力AI,推机器学习托管服务、四项新工具,还有AI硬件

Root 假装发自 拉斯维加斯 量子位 出品 | 公众号 QbitAI 机器学习现在已经在多个领域爆发出惊人的能量,企业通过获取有效的用户数据,可以高效锁定用户...

32870
来自专栏新智元

【干货】关于机器学习你需要知道的一切(附中英论文下载)

【新智元导读】《主算法》作者、华盛顿大学教授 Pedro Domingos 写了文章“A Few Useful Things to Know about Mac...

425100

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励