梯度提升树/GBDT（Gradient Descent Deci

2018-08-29 本文已影响96人大雄的学习人生

梯度提升树被认为是统计学习算法中性能最好的算法之一

算法释义

梯度提升树是以 CART 作为基函数，采用加法模型和前向分步算法的一种梯度提升方法。

梯度提升树（GBDT）

GBDT 采用前向分步算法，初始提升树 f₀(x) = 0，第 t 步的模型：
$f_t(x) = f_{t-1}(x) + T(x;γ_t)$

利用损失函数最小化求解，即：
$γ_t = arg\min_{γ_t} \sum_{i=1}^N L(y_i, f_{t-1}(x_i) + T(x_i;γ_t))$

当基函数是二叉回归树时，损失函数使用平方损失函数，即：
$\begin{align} & γ_t = arg\min_{γ_t} \sum_{i=1}^N (y_i - f_{t-1}(x_i) - T(x_i;γ_t))^2\\ & 令残差\, r_{t,i} = y_i - f_{t-1}(x_i)\\ & 则\, γ_t = arg\min_{γ_t} \sum_{i=1}^N (r_{t,i} - T(x_i;γ_t))^2\\ \end{align}$

这就相当于对当前模拟数据的残差训练一个回归树 T(x; γ_t)，显然这样的子问题比较简单。

梯度提升回归树算法步骤

输入：训练集 D
输出：回归提升树 f_T(x)
(1) 初始化提升树：f₀(x) = 0
(2) 迭代训练：t = 1,2,...,T
a. 计算当前模拟数据的残差：
$r_{t,i} = y_i - f_{t-1}(x_i), i =1,2,...,N$

b. 对当前残差训练一个回归树：
$γ_t = arg\min_{γ_t} \sum_{i=1}^N (r_{t,i} - T(x_i;γ_t))^2$

c. 更新提升树：
$f_t(x) = f_{t-1}(x) + T(x;γ_t)$

(3) 返回最终提升树：f_T(x)

梯度提升

梯度提升树采用前向分步算法，当损失函数是平方损失函数或指数损失函数时，每一步优化相对简单，但对一般损失函数而言，优化过程可能变得比较困难，针对这一问题，Freidman 提出了梯度提升(Gradient Boosting)算法，该方法类似权重学习中的梯度下降方法，其关键是利用损失函数在当前模型下的负梯度作为回归问题提升树中的残差的近似值，拟合一个回归树：
$r_{t,i} = - \nabla_{f_{t-1}(x_i)} L(y_i, f_{t-1}(x_i))$

参考资料

《机器学习技法》，林轩田
《统计学习方法》，李航