机器学习本质是空间搜索和函数的泛化。现在企业主要是基于样本的有监督学习。现实中，逻辑回归(LogisticRegression, LR)的训练速度很快，可解释性强，但是拟合精度不够，然而向量机(SupportVectorMachine，SVM)的预测精度很高，但是特征选取和参数调优非常困难。很多时候鱼与熊掌不可兼得。由于XGBoost算法具有自动特征(Feature)选取、计算复杂度不高，泛化效果好等优势，这个方法已经被很多数据挖掘专家所采用。
今天小盾带大家再探索一遍XGBoost算法，让各位弄清XGBoost是什么鬼。XGBoos是在AdaBoost和GBDT等提升算法基础上进行了优化的算法，一般来说，算法都是由模型、参数和目标函数三部分组成。模型可以理解为基函数(一个函数的固定形式，也就是函数只会在这个函数的基础上变化而不会丢掉的函数)和权重的组合即一类问题的算法。参数就是算法学习的结果，就像决策树学习产生的从根节点通往叶节点的路径q和每个叶节点上面的期望权重w，改变参数（q，w）就是改变已有模型。优化目标函数需要实现两个目的：第一：尽量让预测值接近真实值；第二：保证模型的泛化能力（GeneralizationAbility）。为达到第一点，我们可以最小化损失函数，对于第二点，我们可以最小化损失函数过程中加上控制模型复杂度的惩罚项，也可称为正则化项，如L1，L2损失。我们优化目标函数以达到误差和复杂度综合最优。
目标函数Obj(θ)两部分组成:误差函数L(θ)和复杂度函数O(θ)。我们学习的目标肯定是损失偏差尽量小，函数尽量不复杂。复杂度高意味模型过拟合风险高。其实最终我们关注的是泛化误差(TotalError)大小，即偏差(Bias)和方差(Variance)之间的平衡点。偏差(Bias)度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力；方差度量了同样数量的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。
上图可以看出泛化误差(TotalError)最低点是模型最优点，意味模型的泛化能力最好。在泛化误差最低点之前我们称模型为欠拟合(Underfit)，泛化误差最低点之后我们称模型为过拟合(Overfit)。
下面我们来看XGBoost是如何具体实现的。首先是我们的基学习器。基学习器可以选择决策树或者逻辑回归等这类弱分类器(WeakClassifier)作为基础分类器。XGBoost的思想是每次迭代学习之前学习后的损失值，用基分类器预测值相加，来预测结果。分类器越弱偏差越大，因为每次学习就是减少偏差，判断的时候就会有更多模型参与，其实设置更小的步长（Shrinkage）是换来更多的模型数量。提升算法的背后思想就如同：弱分类器就像偏科的同学，分类器学习的时候会选择该科目里面能力最强的学生，最后就是一群偏科学生一起答完了一张考卷。
弱分类器只有组合才能实现比较好的分类，这和传统的SGD(Stochastic Gradient Descent)算法的模型是有区别的，传统的SGD算法是寻找这样的函数f∈F ,能够在训练集中最小化平方损失函数。我们称通过弱分类器迭加来预测结果我们称为加性模型
我们基函数选择回归树(RegressionTree)，也叫做CART树，即回归问题的决策树，为什么选择CART树，是基于先验给出。
CART其实很多时候也当强分类器，只要树的深度够大，对于样本的分类性也很好，但是有过拟合问题。所以用CART学习XGBoost模型的时候必须控制树深度，因为我们需要弱分类器。随机森林是从SGD和BootStrap角度实现的组合决策树(TreeEnsemble)，随机森林解决了大部分样本特征选择和过拟合的问题。其实XGBoost从加性模型的角度实现了功能更强大的一个分类器。
基函数选择CART，假定CART的第m次预测结果为
基函数确定我们的损失函数也可以确定，函数T表示决策树，m表示决策树个数或者弱分类器个数，theta表示决策树的区域划分(可以理解为：决策树的划分路径)和各区域的常数。我们最终的预测结果是f(m-1)+T(m)，这里f(m-1)是前m-1次预测的累加结果，而最终的误差项为
CART通过优化GINI指数、剪枝、控制树的深度分类。其实背后原理是控制模型的复杂度和正则化的极大似然估计类似。我们设计复杂函数其实也是这个思想。叶子节点数目T 和LeafScore的L2模的平方来定义结构复杂度函数：
上式中：γ（gamma）即阈值，是叶子节点数T的系数 ，类似XGBoost做了前剪枝，系数λ（lambda），是正则项里LeafScore的L2模平方的系数，对LeafScore做了平滑，也起到了防止过拟合的作用。
综合误差函数和复杂度函数可以表达成如下：
传统的GBDT算法（不考虑惩罚项Ω(θ)）是计算损失函数每次迭代使其误差减少最大，就是我们说的梯度下降算法，只要沿着负梯度方向我们可以保证每次减少最大即算法最优，这样把每一次迭代的弱分类器相加，就能使我们的加性模型（GeneralizedAdditiveModels）结果尽量最优。
对损失函数求导后，CART的区域划分和各区域的常数都已知了，所以每个CART都可以确定。
但是梯度算法只是一个抽象，弱分类器会有很多。所以我们必须要给出通用算法：
泰勒展开是具有更一般性的近似算法，而且可以直接源码实现。
目标函数：
n表示样本数量，m表第几次迭代，f(m)表示第m次迭代误差
用泰勒展开：
定义：
代入计算：
具体公式推导见原作者《XGBoost: A Scalable Tree Boosting System》
你肯定迷糊，问推这些公式干什么用呢？其实很非常简单，目的就一个找到最低复杂度的最优特征分裂点，和没有复杂度的GBDT思想类似。基学习器分类指标也可以类比CART树，就是增加了复杂度的基尼指数GiniIndex。排列特征后就可以通过以下计算公式遍历每一维特征每一个分裂点的值，来断定最优分裂点。
至此公式来源和XGBoost学习原理已经讲完。