从GBDT到Xgboost

GBDT

---

GBDT= gradient boosting + decision tree + shrinkage
GBDT是指基学习器为决策树的gradient boosting。以下是gradient boosting的代码，参见wiki。

1. 首先初始化，探索 γ 值，使得loss最小，得到 F0(x) 。
2. For m = 1 to M：
(1) 计算残差r1m, r2m, r3m, …, rnm，一共n个。
(2) 使用(x1,r1m), (x2,r2m), …, (xn,rnm)训练基础学习器hm(x)。
(3) 经过上一步计算，yi的估计值为 Fm−1(xi)+γhm(xi) ， 计算最小误差γm。
(4)更新模型。
3. 输出FM(x)

gradient boosting中的残差学习器 hm(x) 通常使用固定大小的决策树（特别是CART树）。设Jm为叶子节点的数目。这棵树将输入分为Jm个不相交的区域R1m,...,RJmm， 并在每个区域预测一个值。对于输入x，hm(x)的输出可以写作：

hm(x)=∑Jmj=1γjmI(x∈Rjm)
γjm=argminγ∑xi∈RjmL(yi,Fm−1(xi)+γ)
其中 γjm 是区域 Rjm 的预测值。

注：
1. J控制模型变量的影响程度。如果J=2，变量之间没有相互影响。通常取值为4≤J≤8。
2. regularization（正则化）。一个重要的参数就是gradient boosting循环次数M，也就是树的个数。M太大可能导致过拟合。通常通过验证集来选择M的大小。
3. shrinkage（缩减）。在更新的时候添加一个学习率ν。

Fm(x)=Fm−1(xi)+ν⋅γmhm(xi)
通常使用较小的学习率（ν<0.1）能使模型性能得到较好的提升，但是计算量也会随之增大，因为低学习率需要更多的迭代次数。
4. GBDT是回归树，适用于回归和分类。对于分类问题，损失函数L通常要做一些处理，比如做一下logistic变换等等。
5. 优点：可以灵活地处理离散值和连续值，泛化能力强，对异常值鲁棒性强；非线性变换比较多，表达能力强，而且不需要做复杂的特征工程和特征变换。
6. 缺点：由于弱学习器之间存在依赖关系，难以并行训练数据。计算复杂度高，不太适合高维洗漱特征。

Xgboost

---

xgboost地址：https://github.com/dmlc/xgboost
xgboost全称：extreme gradient boost
目标函数包括两部分：
(1) 训练误差 L （衡量how well model fit on training data，目标是predictive）。训练误差可以选择均方误差、logistic误差等。
(2) 正则化 Ω（衡量模型的复杂度，目标是simple，stable）
假设有K棵树：

y^i=∑Kk=1fk(xi),fk∈F
F是包含所有回归树的函数空间，回归树将属性映射为叶节点的分数值。
目标函数为：Obj=∑ni=1l(yi,y^i)+∑Kk=1Ω(fk)
怎么优化目标函数呢？由于此时f是树，而非向量，因此不能使用SGD之类的方法来找合适的f。选用gradient boosting方法。

在回合t的预测值是y^(t)i，因此我们要首先决定ft(xi)的值。每次怎么找到合适的 ft(xi) 呢？——最优化回合t的目标函数：
Obj(t)=∑ni=1l(yi,y^(t−1)i+ft(xi))+Ω(ft)+constant
由泰勒公式f(x+Δx)≈f(x)+f′(x)Δx+12f′′(x)Δx2得：
Obj(t)≈∑ni=1[l(yi,y^(t−1)i)+gift(xi)+12hif2t(xi)]+Ω(ft)+constant
其中gi=∂y^(t−1)l(yi,y^(t−1))，hi=∂2y^(t−1)l(yi,y^(t−1))
将常量移去，得到：
Obj(t)≈∑ni=1[gift(xi)+12hif2t(xi)]+Ω(ft)
我们通过叶子节点的分数值和叶子索引函数（映射一个instance到叶子节点）向量定义树：
ft(x)=wq(x),w∈RT,q:Rd→{1,2,...,T}
其中 RT 表示树的叶子权重，q 表示树的结构，T表示节点的数目。
定义复杂度（以下不是唯一的定义）：Ω(ft)=γT+12λ∑Tj=1w2j后一项是L2正则化的叶子节点分数。
定义Ij={i|q(xi)}为分配给第j个叶子节点的数据集的索引集合。

令Gj=∑i∈Ijgi， Hj=∑i∈Ijhi，则：
Obj(t)=∑Tj=1[Gjwj+12(Hj+λ)w2j]+γT
将wj当做变量，则方括号里面是一个格式为ax2+bx且向上凹的一元二次方程。当目标函数最优（取最小值）时，
w∗j=−GjHj+λ，Obj∗=−12∑Tj=1G2jHj+λ+γT
当我们可以判断树好坏时，理想情况下，我们枚举所有可能的树，然后选择最优。但这是不可能的，因此我们尽量最优化一棵树。当我们试图将一个叶节点分为两个叶节点时，它获得的分数值是：
Gain=12[G2LHL+λ+G2RHR+λ−(GL+GR)2HL+HR+λ]−γ
也就是左边新节点的分数、右边新节点的分数、原始节点的分数、新的节点的正则化。这个分数值可以决定是否切分该节点。扫描排序过的所有特征实例的分数，寻找最优切分点。

最后总结以下Xgboost的算法：

1. 每个迭代（each iteration）添加一棵树
2. 每个迭代的开始阶段，计算gi=∂y^(t−1)l(yi,y^(t−1))，hi=∂2y^(t−1)l(yi,y^(t−1))
3. 用贪心算法寻找切分点，生产一棵树ft(x)，目标函数为：
   Obj=−12∑Tj=1G2jHj+λ+γT
4. 将ft(x)添加到模型y^(t)i=y^(t−1)i+ft(xi)。通常我们会添加一个 ϵ ，称为缩减量(shrinkage)或者步长(step_size)，通常设为0.1。
   y^(t)i=y^(t−1)i+ϵft(xi)
   这意味着在每个回合我们并不完全最优化，而是为后面的回合保留机会，这可以避免过拟合。

Xgboost的优点：对输入的尺度不敏感，不用标准化特征；能够学习到特征之间的高度联系；可扩展性，可用于工业。和GBDT相比，除了用tree，还可以使用线性分类器，用到了二阶导数信息，而普通的GBDT只用到一阶，支持并行。

参考：
GBDT维基百科：
https://en.wikipedia.org/wiki/Gradient_boosting#cite_note-6
GBDT：http://www.cnblogs.com/pinard/p/6140514.html
GBDT调参：http://www.cnblogs.com/DjangoBlog/p/6201663.html
xgboost：http://blog.csdn.net/sb19931201/article/details/52557382
xgboost tutorial：http://xgboost.readthedocs.io/en/latest/model.html