[TOC]

1. 提升方法AdaBoost算法
   1. 提升方法的基本思路
   2. AdaBoost算法
   3. AdaBoost的例子
2. AdaBoost算法的训练误差分析
3. AdaBoost算法的解释
   1. 前向分步算法
   2. 前向分布算法与AdaBoost
4. 提升树
   1. 提升树模型
   2. 提升树算法
   3. 梯度提升

书中在AdaBoost介绍之后，提到了下面

提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法

回顾这一章其实可以划分成三个部分：

1. 1️⃣加法模型 + 指数损失[特例,Adaboost又进一步是特例]
2. 2️⃣加法模型 + 平方损失[特例]
3. 3️⃣加法模型 + 一般损失

再复习下，之前李航老师讲到的：

统计学习方法之间的不同，主要来自器模型、策略、算法的不同。确定了模型、策略、算法，统计学习的方法也就确定了。这也就是将其称为统计学习三要素的原因。

再结构化一下这三个部分，好好理解：

• 模型：需要学习的条件概率分布或者决策函数
• 策略：按照什么样的准则学习或选择最优的模型。统计学习的目标在于从假设空间中选取最优模型。
  • 经验风险最小化($R_{emp}$)
  • 结构风险最小化($R_{srm}$)
• 算法：考虑用什么样的方法求解最优模型，这时统计学习问题归结为最优化问题，统计学习方法的算法称为求解最优化问题的算法。

Boosting方法是一种常用的统计学习方法，应用广泛且有效

• 【在分类问题中】改变训练样本权重，学习多个分类器
• 线性组合

书中在AdaBoost介绍之后，提到了下面

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法

概率近似正确(PAC, Probably approximately correct)

在PAC学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。 两个问题

1. 在每一轮如何改变训练数据的权值或者概率分布
2. 如何将弱分类器组合成一个强分类器

Adaboost解决方案：

1. 提高前一轮被分错的分类样本的权值，降低被正确分类的样本的权值
2. 加权多数表决的方法

• 输入：训练数据集T, 弱学习方法
• 输出：最终分类器G(x)

步骤

1. 初始化训练数据的权值分布 $D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N},w_{1i}=\frac{1}{N})$
2. m = 1,2, M
   1. $G_m(x):X->{-1,+1}$
   2. 求$G_m$在训练集上的分类误差率 $e_m=\sum_{i=1}^{N}P(G_m(x_i)\ne y_i)=\sum_{i=1}^{N}w_{mi}I(G_m(x_i)\ne y_i)$
   3. 计算$G_m(x)$的系数，$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}$，自然对数
   4. $w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i))$
   5. $Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$
3. $f(x)=\sum_{m=1}^M\alpha_mG_m(x)$
4. 最终分类器$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$

这里面有个描述

使用具有权值分布Dm的训练数据集

这个怎么理解，是改变了数据么？

• 这里不是的
• 弱分类器的分类准则是错误率$e_m=\sum_{i=1}^{N}P(G_m(x_i)\ne y_i)=\sum_{i=1}^{N}w_{mi}I(G_m(x_i)\ne y_i)$
• 每次学习用到的数据集没有变，划分方式也没有变（比如阈值分类器中的分类点的选取方式），变是评价每个划分错误的结果。
• 不同的权值分布上，不同样本错分对评价结果的贡献不同，分类器中分类错误的会被放大，分类正确的系数会减小，错误和正确的系数比值为$e^{2\alpha_m}=\frac{1-e_m}{e_m}$

弱分类器选为阈值分类器，通过阈值将数据划分成两部分，标准是分类误差率最低。

需要确定两个参数：

1. 阈值选在哪里
2. 划分的两部分类别指定方式

下面显示m=1，2，3时弱分类器的选择过程

m=1

m=2

m=3

数据显示了每一轮计算的结果

通过这个图来解释什么是加法模型

• 同样的数据集T，配合不同的权值分布，拿到不同的基分类器G
• 误差率的定义将权值系数分布与基分类器的结果联系在了一起
• 权值分布D的宽度代表分类器的误差率相对大小，D1➡️D3递减
• G的宽度代表最终模型中该分类器对应的系数大小，G1➡️G3递增
• 在模型的最终表示中有个$\sum$