机器学习算法总结之XGBoost（上）
写在前面
wow将近看了一个礼拜终于走到XGBoost这一步。
还是跟前几个算法一样，首先从基本原理开始到最后的算法实战。
首先附上学习资料：
陈天奇论文XGBoost: A Scalable Tree Boosting System
Scalable and Flexible Gradient Boosting（类似官方文档）
1. XGBoost简介
XGBoost（eXtreme Gradient Boosting）是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包，比常见的工具包快10倍以上。在数据科学方面，有大量kaggle选手选用它进行数据挖掘比赛，如果你的算法预测结果不好，赶紧试试XGBoost吧。在工业界规模方面，xgboost的分布式版本有广泛的可移植性，支持在YARN, MPI, Sungrid Engine等各个平台上面运行，并且保留了单机并行版本的各种优化，使得它可以很好地解决于工业界规模的问题。
XGBoost其实是对前面所讲的GBDT算法的一种改良实现，主要包括了正则化、损失函数、学习策略、并行实现等一些方面。
2. XGBoost模型函数形式
给定数据集D，xgboost进行加法学习K棵树，采用以下函数对样本进行预测：
其中F是假设空间，f（x）是CART回归树：
q(x)表示将样本x分到了某个叶子节点上，w是叶子节点的分数（leaf score），所以 Wq( x)表示回归树对样本的预测值。
例如：预测一个人是否喜欢电脑游戏
回归树预测输出是实数分数可以用于回归、分类、排序等任务中。对于回归问题，可以直接作为目标值，对于分类问题，需要映
射成概率，比如采用逻辑函数（Sigmoid函数）等。
3.XGBoost模型目标函数
参数空间中的目标函数：
可以看出，目标函数包括了两个部分：误差函数（损失函数）和正则化。误差函数可以是square loss，logloss等，正则化包括前面学过的L1、L2正则等。优化损失函数有利于得到预测性更好的模型，优化正则化项有利于得到更简单的模型。
3.1 正则化项
正则化正是xgboost不同于GBDT的地方之一，它的作用可以从一下几个角度去解释：
- 通过偏差-方差分解
对于高偏差的情况，说明数据拟合情况不理想，可以通过减小正则化项的比重来解决；
对于高方差的情况，说明数据发生过拟合，泛化能力降低，可以通过增大正则化项的比重来解决。
- PAC-learning泛化界
在计算学习理论，probably approximately correct learning(PAC learning)是分析机器学习的一个数学框架。这里涉及较多的数学推导，课参考下面的两个链接。Anyway，主要就是说PAC-learning的泛化错误界与假设集合以及样本数量存在trade-off。（大概是这个意思吧。。。我其实也没怎么看懂。。。求指教）
- Bayes先验解释，把正则当成先验
最后贴一个知乎讨论：机器学习中使用正则化来防止过拟合是什么原理？
在陈天奇大牛的论文中给出XGBoost模型的正则化表达式：
其中T是树模型中叶子的数量，w是叶子的weights，这里正则化项对叶结点个数作了惩罚，相当于在训练过程中做了剪枝。
3.2 损失函数处理
上面式子中的损失函数不能通过传统的优化手段进行处理，在XGBoost中使用的是牛顿法进行二阶泰勒展开后进行优化。
在第t次迭代后，模型的预测等于前t-1次的模型预测加上第t棵树的预测：
此时目标函数就变成了：
此时为了优化目标函数，只需要找到合适的ft（x）
将误差函数进行二阶泰勒展开：
其中，
然后将公式中的常数项去掉，有：
现在定义每个叶结点j上的样本集合为，改写上式：
对其求导，可得最优叶结点weight：
带入目标函数后可得最小损失：
上面的推导完了，再贴上一个实例：
4. XGBoost学习策略/算法
当回归树的结构确定时，我们前面已经推导出其最优的叶节点分数以及对应的最小损失值，问题是怎么确定树的结构？
× 暴力枚举所有可能的树结构，选择损失值最小的 - NP难问题。
√ 贪心法，每次尝试分裂一个叶节点，计算分裂前后的增益，选择增益最大的。
分裂后增益计算公式如下：
Gain的值越大，分裂后 L 减小越多。所以当对一个叶节点分割时，计算所有候选(feature,value)对应的gain，选取gain最大的进行分割。
4.1 精确分裂算法（exact split finding）
遍历所有特征的所有可能的分割点，计算Gain值，选取最大的进行分支。
4.2 近似分类算法（approximate split finding）
对于每个特征只考察分位点，减少计算复杂度。
4.3 稀疏值处理
当特征出现缺失值时， XGBoost可以学习出默认的节点分支方向。
5. XGBoost的其他特性
- 缩减（Shrinkage），即类似于学习速率，shrinka减小了每棵单独树的影响并为未来加入的树提供可提高模型质量的空间。本质上是一种regularization的方式，可防止overfitting。
- 行、列抽样（raw/column subsampling），以前主要应用于随机森林，很少在Boosted trees里使用。但xgboost中应用可以加速并行算法的计算速度。
- 支持自定义损失函数，但必须要求二阶可导。
小结
结合大牛们的博文，总结xgboost算法如下：
- 基分类器：传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
- 二阶泰勒展开：传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
- 方差-方差权衡：XGBoost在目标函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出分数的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性。
- 缩减（Shrinkage）：相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
- 列抽样（column subsampling）：xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
- 对缺失值的处理：对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
- xgboost工具支持并行：boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
- 线程缓冲区存储：按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer（缓冲区），主要是结合多线程、数据压缩、分片的方法，然后再计算，提高算法的效率。
-
可并行的近似直方图算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
- 内置交叉验证：XGBoost允许在每一轮boosting迭代中使用交叉验证。因此，可以方便地获得最优boosting迭代次数。
而GBM使用网格搜索，只能检测有限个值。
接下来就是对XGBoost进行实战了~
以上~
2018.04.20