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$）时，分类准确率已经很高了。。。）

图来自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算法

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)$已经没有显式的再加权重了）

Gentle Adaboost 若在Real Adaboost基础上通过牛顿步来优化loss function，则得到了Gentle Adaboost。

这些Adaboost都是指数损失。 指数损失的问题：错分的outline会得到很高的权重，导致对噪声的鲁棒性能差

LogitBoost

既然是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流程及数学证明