> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/boosting.md).

# boosting

## 理解boosting

boosting假定模型为加性模型：$$F\_m(x) = \sum\_{m=1}^M \beta\_m f\_m(x;\gamma\_m)$$\
优化目标：$$\min\_{\beta\_m,\gamma\_m} \sum\_{i=1}^N L(y\_i, \sum\_{m=1}^M \beta\_m f\_m(x\_i;\gamma\_m))$$\
boosting过程：\
1\. initialise $$f\_0(x)=0$$\
2\. for m=1 to M

* compute $$(\beta\_m,\gamma\_m) = \arg \min \sum\_{i=1}^N L(y\_i, F\_{m-1}(x\_i) + \beta\_m f\_m(x\_i;\gamma\_m))$$
* set $$F\_m(x) = \sum\_{m=1}^M \beta\_m f\_m(x;\gamma\_m)$$

## AdaBoost

算法过程见《统计学习方法》p138，这里备注下细节。

* 分类错误：迭代到m时，算分类误差，算的仅仅是当前这步分类器分类错误的，而不是**前m步加权累加的分类错误**。
* 迭代终止条件：仅仅人为指定M（分类器数量）。（倘若第n步（$$n \lt M$$）时，分类准确率已经很高了。。。）

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F85ec9606a5d844b8eebb5fda1b3f19ab0f0e927d.png?generation=1589383939193183\&alt=media)

图来自<http://rob.schapire.net/papers/explaining-adaboost.pdf>

## AdaBoost解释

优化目标函数 $$E=\sum\_{n=1}^N \exp(-y\_n F\_m(X\_n))$$,n是样本数。

> 这个分类错误为什么不是0-1损失，而是指数形式？\
> 这个指数损失是0-1的凸上界。会有一些良好的性质，比如优化快。\
> 但是，对异常值敏感，鲁棒性差。可能一个噪音点能将分界面拉动很远。（所以后来有了 LogitBoost）

序列最小化指数函数$$F\_m(x) = \sum\_{m=1}^M \beta\_m f\_m(x)$$，\
所以

$$
\begin{align}
E &= \sum\_{n=1}^N \exp(-y\_n F\_m(X\_n)) \\
&=\sum\_{n=1}^N \exp(-y\_n F\_{m-1}(X\_n) - y\_n \beta\_m f\_m(X\_n) ) \\
&=\sum\_{n=1}^N w\_n^m \exp(-  y\_n \beta\_m f\_m(X\_n) ) \\
&= e^{- \beta\_m} \sum\_{n \in T\_m} w\_n^m + e^{\beta\_m} \sum\_{n \in M\_m} w\_n^m  \\
&= e^{- \beta\_m} \sum\_{n \in T\_m} w\_n^m + e^{- \beta\_m} \sum\_{n \in M\_m} w\_n^m - e^{- \beta\_m} \sum\_{n \in M\_m} w\_n^m + e^{\beta\_m} \sum\_{n \in M\_m} w\_n^m  \\
&= e^{- \beta\_m} \sum\_{n=1}^N w\_n^m + (e^{\beta\_m} - e^{- \beta\_m}) \sum\_{n=1}^N w\_n^m I(f\_m(X\_n) \neq y\_n) \\
&= e^{- \beta\_m} \sum\_{n=1}^N w\_n^m + (e^{\beta\_m} - e^{- \beta\_m}) \sum\_{n=1}^N w\_n^m I(f\_m(X\_n) \neq y\_n) \\
\end{align}
$$

其中

$$
w\_n^m = \exp(-y\_n F\_{m-1}(X\_n) ) \\
y\_n f\_m(X\_n) = 1 -2I(f\_m(X\_n) \neq y\_n) \quad \mbox{就是分对了为1，分错了为-1}
$$

然后通过$$\frac {\partial E}{\partial \beta\_m} = 0$$来求解E最小值。

$$
\frac {\partial E}{\partial \beta\_m} =0 \\
\Rightarrow \beta\_m = \frac 12 \ln (\frac {1-e\_m}{e\_m}) \qquad \text{这就是错误加权率} \\
e\_m = \frac {\sum\_{n=1}^N w\_n^m I(f\_m(X\_n) \neq y\_n)}{\sum\_{n=1}^N w\_n^m} \qquad \text{样本权重更新公式} \\
\= \frac {\sum\_{n=1}^N \exp(-y\_n F\_{m-1}(X\_n) ) I(f\_m(X\_n) \neq y\_n)}{\sum\_{n=1}^N w\_n^m} \\
\= \frac {\prod\_{n=1}^N \exp(-y\_n \beta\_m f\_m(X\_n) ) I(f\_m(X\_n) \neq y\_n)}{\sum\_{n=1}^N w\_n^m} \qquad \text{对照前面的权重更新公式，就是一直累乘起来} \\
$$

[AdaBoost算法](http://www.wengweitao.com/adaboostsuan-fa.html)

### AdaBoost变种

**Real Adaboost**\
adaboost要求输出必须是$${-1,1}$$,若不做此要求，然后相应的loss function改成$$E = \sum\_{n=1}^N \exp(-y\_n (F\_{m-1}(x\_n)+f\_m(x\_n)))$$,则得到了Real Adaboost。（基分类器$$f\_m(x)$$已经没有显式的再加权重了）\
![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F23ee9a89cfeca793ef0123637e6d52eb97ea0697.jpg?generation=1589383942744036\&alt=media)

**Gentle Adaboost**\
若在Real Adaboost基础上通过牛顿步来优化loss function，则得到了Gentle Adaboost。\
![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F5f6dfbfa3e3ca89e67ec93fbd26e5f6d869ece5a.jpg?generation=1589383939768787\&alt=media)

这些Adaboost都是指数损失。\
**指数损失的问题**：错分的outline会得到很高的权重，导致对噪声的鲁棒性能差\
![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F558dcbe3dc3591eefa1d74852fec98005b0a8fef.png?generation=1589383941707523\&alt=media)

### LogitBoost

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fdf9d61227d3e7ced7673f389b361a01715e228f6.jpg?generation=1589383940725336\&alt=media)

既然是logit损失，那么优化的就是负对数似然：$$l(y\_n,p(x\_n)) = -log(1+e^{-2 y\_n F\_m(x\_n)})$$ 。迭代时也用的是牛顿步。

## 误差分析

Bagging：样本分布的相似性$$E\[\frac{\sum^n x\_i}{n}]=E\[x\_i]$$，所以boostrap模型的bias与单个模型的bias差不多。各个boostrap模型之间有一定的相关性，但不完全相同，所以**Aggregating**之后降低了一定程度的variance。

Boosting : 有序的最小化损失函数，所以bias逐步下降

### 参考佳文

[AdaBoosting流程及数学证明](http://blog.csdn.net/lampqiu/article/details/39338277)