Intro

Boosting can be interpreted as an optimization algorithm on a suitable cost function. The algorithms that optimize a cost function over function space by iteratively choosing a function(week hypothesis) that points in the negative gradient direction.

在分类问题中，提升(Boosting)思想，通过改变训练数据的概率分布（权重分布），针对不同的训练数据分布，学习多个弱分类器，将这些分类器线性组合，提高分类的性能。

围绕提升方法，有两个问题需要考虑：1.每一轮如何改变训练数据的概率或权值分布；2.如何将弱分类器组合成一个强分类器。

AdaBoost(Adaptive Boosting)

AdaBoost提高那些被前几轮弱分类器线性组成的分类器错误分类的样本权值，在下一轮的弱分类器中更加关注没有得到正确分类的数据；采用加权多数表决的方法，误差率小的弱分类器权值大，误差率大的弱 分类器权值小。

算法流程：（二分类问题）
输入：训练数据集\(T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}\)和弱分类器算法
输出：最终分类器\(G(x)\)

• 初始化训练样本的权值分布(均匀分布)
  $$D_1=(w_{11},…,w_{1i},…,w_{1N}), w_{1i}=\frac{1}{N}, i=1,2,…,N$$

• 对于\(m=1,2,…,M\)(迭代)

  • 使用具有权值分布\(D_m\)的训练数据集学习，得到基本分类器\(G_m(x)\)
  • 计算\(G_m(x)\)在权值分布\(D_m\)的训练数据集上的分类误差率 $$e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^N w_{mi}I(G_m(x_i) \neq y_i)$$
  • 计算\(G_m(x)\)的系数，即表决权 $$\alpha_{m} = \frac{1}{2} \log \frac{1-e_m}{e_m}$$
  • 更新训练数据集的权值分布 $$D_{m+1} = (w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N})$$ $$w_{m+1,i} = \frac{w_{mi}}{Z_m} \exp (-\alpha_m y_i G_m(x_i))$$ 其中\(Z_m\)是规范化因子,$$Z_m = \sum_{i=1}^N w_{mi} exp(-\alpha_m y_i G_m(x_i))$$

• 构建基本分类器的线性组合，得到最终的分类器 $$f(x) = \sum_{m=1}^M \alpha_m G_m(x)$$ $$G(x) = sign(f(x))$$

每轮迭代过程中，Adaboost会重点关注错误分类的样本，使得算法受噪声和离群点的影响较大。\(\alpha_m\)随着 \(e_m\) 的减小而增大，\(w_{mi}\) 也随着\(\alpha_m\) 而改变，不断增大误分类样本的权值，减小正确分类样本的权值。

AdaBoost的一个解释是，模型为加法模型，损失函数为指数函数，学习算法为前向分步算法的二分类学习方法。前向分步算法(forward stagewise algorithm)求解优化问题的思路是：从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，就可以简化优化的复杂度。

Boosting Tree(提升树)

采用加法模型(基函数的线性组合)与前向分步算法，以决策树为基函数的提升方法称为提升树，分类问题采用二叉分类树，回归问题采用二叉回归树。

提升树表示为决策树的加法模型: $$f_{M(x)} = \sum_{m=1}^M T(x; \Theta_m)$$ 其中，\(T(x;\Theta_m)\)表示决策树，\(\Theta_m\)为决策树的参数，M为树的个数

不同问题的提升树学习算法，主要区别在于使用的损失函数不同，包括用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。将Adaboost算法中的基本分类器限制为分类决策树，即为针对二分类问题的提升树算法。

提升树算法(回归问题):
输入:训练数据集\(T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}\)
输出:提升树\(f_M(x)\)

• 确定初始提升树\(f_0(x) = 0\)
• 对m = 1,2,…,M
  • 计算残差： \(r_{mi} = y_{i} - f_{m-1}(x_i), i=1,2,…,N\)
  • 拟合残差，学习一个回归树，得到\(T(x;\Theta_m)\)
  • 更新\(f_m(x)=f_{m-1}(x)+T(x;\Theta_m)\)
• 得到最终提升树：\(f_M(x)=\sum_{m=1}^M T(x;\Theta_m)\)

Gradient Boosting(梯度提升)

前向分布算法针对特殊的损失函数(平方和指数)，对于一般的损失函数，Freidman提出了梯度提升算法。它利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值最为回归问题提升树算法中的残差的近似值，拟合一个回归树。

梯度提升算法：
输入:训练数据集\(T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}\)，损失函数\(L(y,f(x))\)
输出:回归树\(\hat{f} (x)\)

1. 初始化，估计是损失函数极小化的常数值，即只有一个根节点的树 \(f_0(x) = arg\mathop{min}\limits_{c} \sum_{i=1}^{N} L(y_i,c)\)
2. 对m=1,2,…,M
   • 对i=1,2,…,N,计算 \(r_{mi} = - \{\left [\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]\}_{f(x)=f_{m-1}(x)}\)
   • 对于\(r_{mi}\)拟合一个回归树，得到第m棵树的叶节点区域\(R_{mj}$, j=1,2,…,J\)（对于平方损失函数，就是通常所说的残差，对于一般损失函数，即为残差的近似值）
   • 对于j=1,2,…,J,计算 $$c_{mj} = arg\mathop{min}\limits_{c} \sum_{x_i \in R_{mj}} L(y_i,f_{m-1}(x_i)+c)$$
   • 更新\(f_m(x) = f_{m-1}(x)+\sum_{j=1}^J c_{mj}I(x\in R_mj)\)
3. 得到回归树 $$\hat{f}(x) = f_M(x) = \sum_{m=1}^M \sum_{j=1}^J c_{mj} I(x \in R_{mj})$$