XGBoost
Objective Function： Training1 Loss + Regularization
目标函数分为Training Loss和Regularization term两项。
通常损失函数L的选择是mean square error函数：
在用于Logistic Regression时，会使用Logistic Loss：
正则项常常是用来控制模型复杂度的。用来保证bias-variance tradeoff。
bias 度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力；
variance度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力.
high bias low variance是欠拟合； low bias high variance是过拟合.
目标函数可以优化为：
其中K是树的数量，f是函数空间F中的f，并且F是所有可能CART中的集合。
Additive Training
我们使用加法策略表示迭代过程中，树的学习过程：
在t步的目标函数用t-1步展开：
假设我们这里使用Mean Square Error(MSE)作为损失函数，目标函数变为：
若使用MSE作为损失函数，使用1阶展开和2阶展开是十分友好的。但用于其他的损失函数时，是得不到这样一个友好的损失函数。所以普遍来说，我们是将损失函数展开至2阶：
具体泰勒展开推导过程如下：
标准二阶泰勒展开如下：
假设：
然后带入进去即可得到如上最终表达式：
然后移除所有常数，在t步的具体目标函数变成：
Model Complexity
定义树f(x)如下：
其中w是叶子结点的得分向量值，q是将数据点对应到对应叶子的函数，T是叶子树木。在XGBoost中，我们定义复杂度为：
The Structure Score
在此，我们重新写出在t棵树上的目标值为：
再对此式进行压缩更改为：
其中
在此式子中，Wj是相互独立的，故在式子是二次项式并且最佳Wj对于给定结构q(x)，可以得到客观上最优值，最优结点weight和最优目标函数：
这里出现了 γ，λ，在使用xgboost时，可以设定它们的值。
γ越大，表示获得结构越简单的树，因为此时对较多叶子节点的树的惩罚越大。λ 越大也是获得结构越简单的树。
Tree Structure
-
枚举所有可能的树结构，选择loss最小的。这是NP hard问题，代价过大。
-
根据贪心策略，每次分裂叶节点时，选择前后增益最大的。
分裂后的增益计算公式为：
Advantage&Disadvantages
-
能达到bais-variance tradeoff
-
可以通过乘上一个learning rate来控制收缩速率
-
对于缺失值可以自动分裂出树节点的分裂方向