1、基本知识点简介
-
在集成学习的Boosting提升算法中，有两大家族：第一是AdaBoost提升学习方法，另一种是GBDT梯度提升树。
-
传统的AdaBoost算法：利用前一轮迭代弱学习器的误差来更新训练集的权重，一轮轮迭代下去。
-
梯度提升树GBDT：也是通过迭代的算法，使用前向分布算法，但是其弱分类器限定了只能使用CART回归树模型。
-
GBDT算法原理：指通过在残差减小的梯度方向建立boosting tree（提升树），即gradient boosting tree（梯度提升树）。每次建立新模型都是为了使之前模型的残差往梯度方向下降。
2、梯度提升树GBDT算法
2.1 思路和原理
- 基本思路：假设前一轮迭代得到的强学习器是(f_{t-1}(x))，损失函数是(L(y, f_{t-1}(x)))，则本轮迭代的目标是找到一个CART回归树模型的弱学习器(h_{t}(x))，让本轮的损失函数(L(y,f_{t}(x)) = L(y,f_{t-1}(x)) - h_{t}(x))最小。即本轮迭代找到的损失函数要使样本的损失比上一轮更小。
- 大牛Freidman提出用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树，第 t 轮的第 i 个样本的损失函数的负梯度表示为：
[r_{ti} = - [frac{partial L(y_{i}, f(x_{i})) }{partial f(x_{i}) }]_{f(x)=f_{t-1}(x)}
]
2.2 梯度代替残差建立CART回归树
利用((x_{i}, r_{ti}), (i=1,2,...,m))（此处损失函数的负梯度代替了一般提升树的残差），我们可以拟合一棵CART回归树，得到第 t 棵回归树，其对应的叶结点区域(R_{tj}, j=1,2,...,J)。其中J为叶子结点的个数。
- 对于每一个叶子结点的样本，通过使平方误差损失函数最小，输出拟合叶子结点最好的输出值(C_{tj})（CART回归树中采取的公式是每一个样本的划分单元上的所有实例(x_{i})的所有输入实例对应的输出平均值，即(hat{c}_{m} = ave(y_{i} | x_{i} in R_{m}))），此处输出值为：
[c_{tj} = arg minlimits_{c} sumlimits_{x_{i} in R_{tj}} L(y_{i}, f_{t-1}(x_{i}) + c)
]
因此本轮决策树的拟合函数为：
[h_{t}(x) = sumlimits_{j=1}^{J} c_{tj} I(x in R_{tj})
]
从而得到本轮的强学习器表达式为：
[f_{t}(x) = f_{t-1}(x) + sumlimits_{j=1}^{J} c_{tj} I(x in R_{tj})
]
- 如果是GBDT分类算法，则需要改变损失函数为指数损失函数（类似为AdaBoost算法），或者对数似然损失函数（逻辑回归）。——暂时不作分析。
- 指数损失函数：(L(y, f(x)) = exp(-Y(f(x))))
- 对数损失函数：(L(Y,P(Y|X)) = -log P(Y|X))