Xgboost 是一套提升树可扩展性的机器学习系统，它的算法原理就是将多棵树的预测结果相加得到最终预测结果。之前看了一些博客和视频教程，看完还是一头雾水，最后还是看了原论文才终于有了点头绪。
正则化目标函数
首先，给定一个数据集 包含
个数据，其中每个数据有
个特征，即
Xgboost 是一个树集成模型，它将 个树的预测结果进行求和得到最终预测值。即每一个样本的预测值为
其中，
-
是回归树（CART 树）的空间；
-
代表每棵树的结构，它把样本映射到树中对应的叶子节点，比如一个样本
被树划分到一个叶子节点，这个叶子节点的编号为
。
（所以
就是样本
-
是树的叶子节点个数。
-
每一个
对应一个独立的树结构
。
这里的树是回归树，也就是树的每个叶子节点都包含一个权重 （第
个叶子节点的权重）。对于每一个样本，我们根据每一棵回归树把它划分到每棵树的叶子节点中，然后对这些叶子节点的权重求和得到该样本的预测结果。
于是我们的目标就是最小化 目标函数：
其中
-
（
）
-
是 损失函数，表示预测值
和真实值
之间的误差。
-
用来控制（回归树）模型的复杂度，避免过拟合。
中目标函数的优化参数是模型（即
）。因为整个 Xgboost 模型是以求和回归树的方式训练的，所以相当于训练中每一轮都加入一个回归树模型，即
-
一开始，预测值
-
之后每一轮都是前一轮的预测值加上一个新的回归树模型，即在第
轮，模型的预测值为
于是目标函数变为
为了能快速优化目标函数，我们将目标函数进行二阶泰勒展开，得到近似目标函数（也就是说这个展开后的函数近似原来的目标函数，但并不完全相等）：
其中 ，
分别是损失函数的一阶和二阶偏导。
然后，我们可以移除目标函数中的常量，得到
令 为叶子节点
中样本的集合（即被划分到该叶子节点的所有样本），我们可以将
写为
求这个目标函数的最优解
带入 得到最优目标函数
可以用来衡量一个树结构
的好坏（类似决策树中的纯度），
越小，树结构越好。
贪婪算法
通常我们无法枚举所有树结构，所以我们用一种贪婪算法：从单个叶节点开始，迭代地给树添加分支。
假设 和
是节点分裂后的左节点的样本集和右节点的样本集，令
，节点切分后的损失函数为
我们的目标是找到一个特征，使切分后的损失减少最大。 除了控制树的复杂度，也作为阈值，当分裂后增益大于
时才分裂，起到了预剪枝作用。
缩减和列采样
缩减和列采样也用来防止过拟合。
- 缩减是在每一步 tree boosting （增加树）后引入缩减系数
，对新增加的权重进行收缩，减少每棵树的影响，为以后加入的树留下改进模型的空间。
- 列采样通常用在随机森林中，它有时比传统的行采样更能防止过拟合，它也加速了并行计算。
之后还有一部分算法，比如寻找最佳分割点等，下次补充。
参考：
XGBoost: A Scalable Tree Boosting System（这是 Xgboost 的论文）
XGBoost 原理（这篇基本是翻译了 Xgboost 的论文，有些英文看不明白的可以看看中文，不过我看到一半发现一处翻译错误，已在我的这篇订正）