前言
本文续接上文关于Adaboost的内容，继续记录 Boosting 算法族的其他算法。上一篇博客简单介绍了了加法模型和向前分布算法，以及 Adaboost 模型的原理和推导过程。本篇博客主要介绍 Boosted Decision Tree （提升树） 和 Bradient Boosting Decision Tree（GBDT）两种算法。其中 GDBT 可以理解为 BDT 的一种推广形式。
Boosted Decision Tree
算法
输入: \(D = \{(\boldsymbol{x}^{(1)}, y^{(1)}), (\boldsymbol{x}^{(2)}, y^{(2)}), ... , (\boldsymbol{x}^{(m)}, y^{(m)})\}\)
输出: 提升树 \(f_k(\boldsymbol{x})\)
(1) 初始化模型 \(f_0(\boldsymbol{x}) = 0\)
(2) for t in 1,2, ..., k; do
(a) 计算残差 \(r_t=y^{(t)} - f_{t-1}(\boldsymbol{x^{(i)}})\)
(b) 拟合残差 \(r_{t}\)，学习一个回归树，得到 \(T(\boldsymbol{x}; \theta_t)\)
(c) 更新 \(f_t(\boldsymbol{x})=f_{t-1}(\boldsymbol{x})+T(\boldsymbol{x}; \theta_t)\)
(3) 得到回归树 \(f_k(\boldsymbol{x})=\sum_{t=1}^KT(\boldsymbol{x};\theta_t)\)
简介
残差树是针对回归问题的一种提升方法。其基学习器是基于CART算法的回归树，模型依旧为加法模型、损失函数为平方函数、学习算法为前向分步算法。
其使用以下的前向分步算法：
\[ \begin{aligned} f_0(\boldsymbol{x})&=0 \\ f_k(\boldsymbol{x})&=f_{k-1}(\boldsymbol{x})+T(\boldsymbol{x};\theta_k) \\ f_k(\boldsymbol{x})&=\sum_{k=1}^KT(\boldsymbol{x}; \theta_k) \end{aligned} \]
在第 k 步，给定当前模型 \(f_{k-1}(\boldsymbol{x})\) 须求解
\[ \hat{\theta}_k=\arg\min_{\theta_k} \sum_{i=1}^M L(y^{(i)}, f_{k-1}(\boldsymbol{x}) + T(\boldsymbol{x}^{(i)};\theta_k)) \]
若采用平方误差损失函数
\[ L(y, f(\boldsymbol{x})) = (y-f(\boldsymbol{x}))^2 \]
\[ \begin{aligned} L(y, f_{k-1}(\boldsymbol{x})+ T(\boldsymbol{x}^{(i)};\theta_k)) &=[y - f_{k-1}(\boldsymbol{x})-T(\boldsymbol{x}^{(i)};\theta_k)]^2 \\ &=[r-T(\boldsymbol{x}^{(i)};\theta_k)]^2 \end{aligned} \]
其中 \(r=y-f_{k-1}(\boldsymbol{x})\) 即为残差
GBDT
Adaboost 算法使用指数损失函数，BDT 使用平方损失函数。这两类损失函数在平方算法中都是比较容易优化的。但是一般的损失函数可能就没有类似的性质。因此有人提出了梯度提升的概念，即利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中残差的近似。即为梯度提升树 (Gradient Boostes Decision Tree).
GDBT其基本原理和残差树类似，基学习器是基于CART算法的回归树，模型依旧为加法模型、学习算法为前向分步算法。不同的是，GDBT没有规定损失函数的类型，设损失函数为 \(L(y,f(x))\) 。前向加法算法的每一步都是拟合损失函数的负梯度。
\[ -[\frac{\partial L(y^{(i)},f(\boldsymbol{x}^{(i)}))}{\partial f(\boldsymbol{x}^{(i)})}]_{f(\boldsymbol{x})=f_{k-1}(\boldsymbol{x}) \approx r_{m,i}} \]
算法：
输入: 训练集 \(D = \{(\boldsymbol{x}^{(1)}, y^{(1)}), (\boldsymbol{x}^{(2)}, y^{(2)}), ... , (\boldsymbol{x}^{(m)}, y^{(m)})\}\)
损失函数 \(L(y, f(\boldsymbol{x}))\)
输出: 提升树 \(\hat{f}(\boldsymbol{x})\)
(1) 初始化模型 \(f_0(\boldsymbol{x})=\arg\min_c\sum_{i=1}^ML(y^{(i)},c)\)， \(c\)为常数
(2) 循环训练 k 个模型 k = 1, 2, 3,...,K
(a) 计算残差 i 对于 i=1, 2,... ,K
\[r_{k, j}=-[\frac{\partial L(y^{(i)},f(\boldsymbol{x}^{(i)}))}{\partial f(\boldsymbol{x}^{(i)})}]_{f(\boldsymbol{x})=f_{k-1}(\boldsymbol{x})}\]
(b) 拟合残差 \(r_{k, j}\) 学习一个回归树，得到第 k 颗树的叶节点区域 \(R_{k,j}\)，\(j=1,2,3,...,J\)
(c) 对 \(j=1,2,...,J\) 计算
\[c_{k,j}=\arg\min_c\sum_{ x^{(i)}\in R_{k,j}}L(y^{(i)},f_{k-1}(\boldsymbol{x}^{(i)})+c)\]
(d) 更新模型
\[f_k(\boldsymbol{x})=f_{k-1}(\boldsymbol{x})+\sum_{j=1}^JC_{k,j}\mathbb{I}(\boldsymbol{x} \in R_{k,j})\]
(3) 得到回归提升树
\[ \hat{f}(\boldsymbol{x})=f_K(\boldsymbol{x})=\sum_{k=1}^K\sum_{j=1}^J C_{k,j}\mathbb{I}(\boldsymbol{x} \in R_{k,j}) \]
当损失函数为 \(l(y,\hat{y})=\frac{1}{2}(y-\hat{y})^2\) 时，负梯度为 \(-[\frac{\partial L(y, \hat{y})}{\partial\hat{y}}]=(y-\hat{y})\)，即为残差。
如果一个函数到达极小值，那么其梯度值一定为零；当函数没有到达最小值的时候，我们每次都选择梯度的反方向走，这样可以最快的到达极小值。这也就是GDBT的思想。