boosting

• boost=加法模型(基函数的线性组合)+前向分布算法+损失函数
• adaboost=boost+损失函数是指数函数（基函数任意）
• 提升树=boost+基函数是决策树(损失函数任意)

boosting

• 每一步产生一个弱的预测模型（如决策树），并加权累加到总模型；
• 若每一步的弱预测模型生成都是依据损失函数的梯度方向，称为梯度提升（Gradient-boosting）
• 梯度提升：首先给一个目标损失函数，它的定义域是所有可行的弱函数集合( 基函数)；提升算法通过迭代的选择一个负梯度方向上的基函数来逐渐逼近局部极小值
• 提升的理论意义：一个问题存在若分类器，则可以通过提升的方法得到强分类器

1. 提升的基础

* 基本思路

• PAC框架下，弱可学习变为强可学习
• 提升：从弱分类器算法 出发，反复学习，得到一系列弱分类器，然后组合这些分类器，构成 强分类器
• 核心问题：每一轮如何改变训练数据的权重或概率分布；如何将弱分类器组合成强分类器；

2. adaboost

• 数据集：二分类数据集

$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$;

• x是实例空间；y是标记集合
• 从数据集中生成一系列弱分类器，并将它们组合成强分类器

2.1 算法

* 步骤1

• 初始化练集的权重分布$D_1=(w_{11},w_{12},...,w_{1N})$$w_{1i}=\frac{1}{N} \ \ \ \ \ i=1,2,...,N$

* 步骤2：对于$m=1,2,...,M$

• 使用具有权重分布$D_m$的训练数据集学习，得到基本分类器$G_m(x): \chi \rightarrow \{-1,+1\}$

• 计算$G_m(x)$在训练集上的分类误差率$e_m=P(G_m(x_i)\neq y_i)=\sum\limits_{i=1}^N$

• 计算$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)) \ \ \ \ i=1,2,...,N$

其中：$Z_m$是归一化因子

$Z_m=\sum\limits_{i=1}^Nw_{mi}exp(-\alpha_m y_i G_m(x_i))$

* 步骤3：

• 构建基本分类器的线性组合

$f(x)=\sum\limits_{m=1}^M\alpha_mG_m(x)$

• 得到最终分类器：

$G(x)=sign(f(x))=sign(\sum\limits_{m=1}^M\alpha_m G_m(x))$

* 例子： P141(李航)

2. Adaboost算法的训练误差分析

• adaboost可以在训练中不断减少训练误差
• adaboost的训练误差是以指数下降

* p143

3. adaboost的解释

• adaboost是模型为加法模型，损失函数是指数函数，学习算法是向前分步算法时的二类分类方法

3.1 前向分步算法

• 对于加法模型，从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，可以简化计算的复杂度

3.2 算法

* 输入：

• 训练数据集:$T=\{(x_1,y_1),...,(x_N,y_N)\}$；$y\in\{-1,1\}$
• 损失函数:$L(y,f(x))$
• 基函数集合:$\{b(x:\gamma)\}$

* 输出：加法模型f(x)

* 步骤1：

• 初始化$f_0(x)$

* 步骤2：

• 对$m=1,2,...,M$
• 极小化损失函数：

$(\beta_m,\gamma_m)=arg\min\limits_{\beta,\gamma}L(y_i,f_{m-1}(x_i)+\beta b(x_;\gamma))$

得到参数：$\beta_m, \gamma_m$

• 更新：$f_m(x)=f_{m-1}(x)+\beta_m b(x;\gamma_m)$

* 步骤3：

• 得到加法模型：

$f(x)=f_M(x)=\sum\limits_{m=1}^m\beta_m b(x;\gamma_m)$

* 结论

• 前向算法：将同时求解m=1到M所有参数$beta_m,\gamma_m$简化为逐次求解各个$\beta_m,\gamma_m$的过程

3.3 前向分步和adaboost算法的证明

• P145