讲稿
页码
内容
XGBoost的作者是曾在华盛顿大学研究机器学习的大牛陈天齐，XGBoost全称是eXtreme Gradient Boosting，从名称看XGBoost仍然是GBDT，在GBDT基础上优化和增强。XGBoost以出众的效率和较高的预测准确率在各大算法比赛中被广泛使用。这篇文章介绍了XGBoost这种可扩展、端到端的Boosting Tree的新算法。
论文分为如下几个部分，第一部分是简介，然后是主要的算法，接下来是分割算法，然后系统设计，端到端评估。
为什么选择这个主题呢，因为我个人比较喜欢传统的机器学习
极限提升树XGBoost(Extreme Gradient Boosting，XGB，发音/æks-g-boost/)是基于梯度提升树GBDT全面升级的新一代提升算法，也是提升家族中最富盛名、最灵活、最被机器学习竞赛所青睐的算法。
树的集成模型是机器学习中最为强大的学习器之一，这一族学习器的特点是精确性好、适用于各种场景，但运行缓慢、且过拟合风险很高，因此从学习单一决策树时起，我们就持续为大家提供丰富的剪枝策略，目的就是为了降低各种树模型的模型复杂度，从而控制住过拟合。
论文中的数学推导特别多，对此我把它的符号全都整理了出来
XGBoost使用的都是回归树。我们先来看作者在论文中举的这个例子：按照是否喜欢电脑游戏对一个家庭的5个人进行分类，第一个节点是年龄是否小于15，第二个是是否为男性。最后就得到我们的节点，非常简单对吧。
作者使用的符号比较多，让我们来开始讲解符号。
这里展示的是我们XGB的建树过程，它是一个加法模型，从0开始迭代，每轮新建的书都加到原有的模型上。迭代到第t轮停止。
根据这个设定，我们把目标函数写成损失函数的形式。
当然，除了平方损失，也可以使用其他的方式，比如交叉熵。
使用了岭回归或者拉索回归，表达式就会变成上面的样子，这些我们应该都非常熟悉了。
定义完了整个目标函数，我们来看这个。
这个式子并不好化简，就需要回到作者在论文中的定义
我们把每颗树分出来的不同类别集合叫做I
为了书写方便，我们再定义大G 和大H
然后我们到了第三章，树结构的生成
这里又到了我们信息增益的环节了，大家很熟悉了吧
刚才的这个，使用的是论文中的算法1：
另外，在分割的时候，这个系统还能感知稀疏值，咱们给每一个树的结点都加了一个默认方向，当一个值是缺失值时，咱们就把他分类到默认方向，每一个分支有两个选择，具体应该选哪一个？这里提出一个算法，枚举向左和向右的状况，哪一个gain大选哪一个：
做一个小的总结，可以看下我们算法的迭代过程
第四章开始，讲的是底层的优化了，也阐述了为什么XGB可以这么快，适应这么大规模的数据
以压缩形式分别存到block里，不一样的block能够分布式存储，甚至存到硬盘里。在特征选择的时候，能够并行的处理这些列数据，XGB就是在这实现的并行化，用多线程来实现加速。同时这里陈博士还用cache加了一个底层优化
当数据排序后，索引值是乱序的，可能指向了不一样的内存地址，找的时候数据是不连续的，这里加了个缓存，让之后找的时候能找到小批量的连续地址，以实现加速！这里是在每一个线程里申请了一个internal buffer来实现的！这个优化在小数据下看不出来，数据越多越明显。
当使用近似算法时，block结构也非常有用。在这种情况下，可以使用多个block，每个block对应于数据集中的不同的行子集。不同的block可以分布在机器上，或者在非核心设置中存储在磁盘上。使用排序结构，分位数查找步骤在完成排序的列上就变成了线性扫描。这对于在每个分支中频繁更新候选分割点的本地优先算法非常有价值。直方图聚合中的二分搜索也变成了线性时间合并样式算法。