XGBoost算法原理

前言：有监督算法的组成：模型，参数和目标函数
（1）模型：给入指定的Xi如何去预测Yi，姑且认为是一个Y关于X的函数吧,如线性回归Y=∑Wi*Xi
（2）参数：就是指系数W
（3）目标函数（损失+正则）：目标函数的作用是找到比较好的参数W，来更好地预测，基本形式如下：

常见的误差函数有：
（1）平方误差：

（2）logistic误差函数：

正则化有L2和L1正则化（其区别可以看我另一篇博客）
XGBoost基本原理
Boosted Tree
（1）基学习器：分类和回归树（CART）
举个经典的例子：

CART会把输入根据属性分配到各个叶子结点，每个叶子结点都会对应一个分数（具体分数怎么得到的暂时不管），上面的例子分数理解为多可能这个人喜欢电脑游戏（输入为人的年龄，性别），得到这些分数之后，我们就可以概率预测，排序等
（2）Tree Ensemble：单个CART可能过于简单，无法有效预测，所以构建一个Tree Ensemble（树的集合）

一棵树预测不准，我们使用两棵树。对于每个样本的预测就是每棵树的预测的和（是不是想起了随机森林）。在这，参数对于了树的结构（分裂值该怎么设置），以及每个叶子结点的分数
我们现在的任务就是构建合理的目标函数去学习这些参数。Tree Ensemble模型可以写成以下形式：

f是每一棵树的函数模型，F则是整个树的集合，f(x)得到的是分数
设计的目标函数形式为（loss+正则项）：

（3）模型学习：additive training
其中一部分是训练误差，就是真实值减去预测值（有平方误差，logisticloss）
另一部分是每棵树的复杂度的和。每次保留原来的模型不变，加入一个新的函数到模型中（加的函数实际上就是树）

还有一个问题，我们怎么加入f，以什么样的标准呢？我们的准则就是：选取一个f使得目标函数尽量最大的降低

可以把上面的公式写的具体一点：实际上就是把公式拆开，很简单

注：残差实际上就是每一轮的预测值和真实值的差，残差的使用面挺广的，也很有效，如ResNet在2015年就火了一把
有时候使用的不是平方误差，我们就用泰勒展开来近似目标函数，方便计算:

不考虑常数项，仔细看公式发现，中括号里面的表示误差函数，我们发现，好像就是在前一个误差函数下加上了一个一阶导数和二阶导数（实际上这就是泰勒公式的妙处）

这样可以得到什么呢？是不是意味着，我们前面得到了t-1个函数模型（树），我们要构建第t个模型(树)时，是不是只要求前t-1函数的一阶和二阶导数和前t-1的函数模型的乘积即可。这样是不是意味着我们不仅可以用这个模型来做分类，还可以回归等，增强了泛化性。
（4）树的复杂度：
前面我们讨论了目标函数的训练误差部分，接下来讨论如何定义树的复杂度。我们先对f的定义做一下细化，把树拆分成结构部分q和叶子权重部分w。结构函数q把输入映射到叶子的索引号上去，而w给定了每个索引号对应的叶子分数

我们定义一棵树的复杂度：这个复杂度包含了一棵树的节点数和每个叶子节点输出分数的模的平方（L2）。当然，不止这一种定义，如下：

看这个图应该还是比较好理解的
（5）关键步骤
我们可以对目标函数进行如下改写，其中I被定义为每个叶子节点上样本集合：

注：i代表第i个样本，j代表第j个叶子节点，整个代表在所有叶子节点上的样本的集合，集合的元素是单个叶子节点的样本的集合

上式包含了T（模型/树的个数）个相互独立的单变量二次函数，我们可以定义

那么目标函数又可以改写：只把w看成未知变量，假设树的结构我们知道

有了这个目标函数，我们可以很容易求w的最优解，直接对w求导

（6）打分函数举例（具体的表述待以后更新，楼主也不是很明白）
Obj代表了当我们指定一个树的结构的时候，我们在目标上面最多减少多少，

注：因为目标函数实际上是loss function，目的是为了逼近真实值，这里的分数就是Obj，实际上就是loss，当然是越小越好，这里的分数实际上每个树的评分
（7）枚举所有不同树结构的贪心算法
我们不断枚举树的结构，利用这个打分函数来寻找最优树，加入到我们的模型中，不断重复这个操作。不过这种枚举操作不太可行，所以常用贪心算法。每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算

对于每次扩展，我们还是要枚举所有可能的分割方案，如何高效地枚举所有的分割呢？我假设我们要枚举所有 x