集成学习：AdaBoost

0 简介

Boosting的一种 关注于之前错分的样本
对样本赋予权重 弱分类器也有权重
强分类器由若干个弱分类器乘各自的权重组成
弱分类器为决策树

$$sgn(F(x))$$

$$F(x)=\sum _{i=1}^M{\beta }_{i}f(x;\gamma )$$

1 目标优化函数

采用指标损失函数 $e^{?yF(x)}$
需要求解的参数：

1. 弱分类器的权重 $\beta$
2. 弱分类器的参数 $\gamma$
   用 $F_{j?1}$代表上一个强分类器 $F_j$代表新的强分类器：
   $$F_j=F_{j?1}+\beta f(x)$$
   所以目标优化函数为
   $$min\sum _{i=1}^l{e}^{?y_i[F_{j?1}+\beta f(x_i)]}$$
   $$min\sum _{i=1}^l{w}_i^{j?1}?e^{?y_i\beta f(x_i)}$$
   其中$w_i^{j?1}=e^{?y_i{F}_{j?1}}$
   代表 (j-1) 的强分类器对样本 i 的损失 或者说样本 i 在 (j-1) 时的权重

2 求解目标优化函数

2.1 把β看做常数

$y_i\beta f(x_i)$ 只能取1或-1 f最优解的参数是使得下式最小：
$$min\sum _{i=1}^l{w}_i^{j?1}I(y_i?=f(x_i))$$
（这里求决策树f参数时其实我没太明白 为什么忽略了yi=f(xi)时的β ）
（是因为为了求目标函数最小 都使得yi=f(xi)）

2.2 求解β

目标优化函数变为最小化以下：
$$\begin{gathered} L(\beta )=e^{?\beta }\times \sum _{y_i=f(x_i)}{w}_i^{j?1}+e^{\beta }\times \sum _{y_i?=f(x_i)}{w}_i^{j?1} \\ =e^{?\beta }\times \sum _{i=1}^l{w}_i^{j?1}+(e^{\beta }?e^{?\beta })\times \sum _{y_i?=f(x_i)}{w}_i^{j?1} \end{gathered}$$
解得β（当前弱分类器权重）
$$er{r}_j=\frac{{\sum }_{y_i?=f(x_i)}{w}_i^{j?1}}{{\sum }_{i=1}^l{w}_i^{j?1}}=\frac{上一个强分类器错分样本权重（损失）之和}{上一个强分类器所有样本权重（损失）之和}$$
$$\beta =\frac{1}{2}\ln \frac{1?er{r}_j}{errj}$$

3 训练流程

流程
（1） 样本初始化权重为$\frac{1}{l}$
（2） 对于t=1,2,3…T个训练好的弱分类器 做以下：

• ①得到$f_t(x)$的加权错误率 $e_t$
• ②计算弱分类器权重 ${\beta }_t=\frac{1}{2}\ln \frac{1?er{r}_j}{errj}$
• ③更新样本权重
  $$\begin{gathered} w_i^t=w_i^{t?1}?e^{?y_i{f}_t(x_i){\beta }_t} \\ {w}_i^t=\frac{w_i^t}{{\sum }_{i=1}^l{w}_i^t}（归一化） \end{gathered}$$

4 训练弱分类器

$$min\sum _{i=1}^l{w}_i^{j?1}I(y_i?=f(x_i))$$
Gini纯度公式为：

$$G=\frac{\sum _i(\sum _{j,y_j=i}{w}_{L,j}{)}^2}{{\sum }_i{w}_{L,i}}+\frac{\sum _i(\sum _{j,y_j=i}{w}_{R,j}{)}^2}{{\sum }_i{w}_{R,i}}$$

5 强分类器的误差

每增加一个弱分类器(保证加权错误率小于1/2) 误差上限会减小
误差上界会乘一个小于1的数 证明公式太长了 先略掉

6 其他类型的AdaBoost

• 上述是离散型的AdaBoost
• 实数型Adaboost
• LogitBoost
• Gentle型AdaBoost

7 实现细节

• 弱分类器一般选择深度很小的决策树
• 弱分类器应选择非线性的
• 弱分类器个数：训练时增加弱分类器 当训练误差或测试误差达到阈值 终止训练
• 样本权重削减：样本权重趋于0的样本在后面的训练中可以剔除掉