boosting

理解boosting

boosting假定模型为加性模型：Fm(x)=∑m=1Mβmfm(x;γm)F_m(x) = \sum_{m=1}^M \beta_m f_m(x;\gamma_m) 优化目标：min⁡βm,γm∑i=1NL(yi,∑m=1Mβmfm(xi;γ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 f0(x)=0f_0(x)=0 2. for m=1 to M

  • compute (βm,γm)=arg⁡min⁡∑i=1NL(yi,Fm−1(xi)+βmfm(xi;γm))(\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 Fm(x)=∑m=1Mβmfm(x;γm)F_m(x) = \sum_{m=1}^M \beta_m f_m(x;\gamma_m)

AdaBoost

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

  • 分类错误：迭代到m时，算分类误差，算的仅仅是当前这步分类器分类错误的，而不是前m步加权累加的分类错误。

  • 迭代终止条件：仅仅人为指定M（分类器数量）。（倘若第n步（n<Mn \lt M）时，分类准确率已经很高了。。。）

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

AdaBoost解释

优化目标函数 E=∑n=1Nexp⁡(−ynFm(Xn))E=\sum_{n=1}^N \exp(-y_n F_m(X_n)),n是样本数。

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

序列最小化指数函数Fm(x)=∑m=1Mβmfm(x)F_m(x) = \sum_{m=1}^M \beta_m f_m(x)， 所以

E=∑n=1Nexp⁡(−ynFm(Xn))=∑n=1Nexp⁡(−ynFm−1(Xn)−ynβmfm(Xn))=∑n=1Nwnmexp⁡(−ynβmfm(Xn))=e−βm∑n∈Tmwnm+eβm∑n∈Mmwnm=e−βm∑n∈Tmwnm+e−βm∑n∈Mmwnm−e−βm∑n∈Mmwnm+eβm∑n∈Mmwnm=e−βm∑n=1Nwnm+(eβm−e−βm)∑n=1NwnmI(fm(Xn)≠yn)=e−βm∑n=1Nwnm+(eβm−e−βm)∑n=1NwnmI(fm(Xn)≠yn)\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}

其中

然后通过∂E∂βm=0\frac {\partial E}{\partial \beta_m} = 0来求解E最小值。

∂E∂βm=0⇒βm=12ln⁡(1−emem)这就是错误加权率em=∑n=1NwnmI(fm(Xn)≠yn)∑n=1Nwnm样本权重更新公式=∑n=1Nexp⁡(−ynFm−1(Xn))I(fm(Xn)≠yn)∑n=1Nwnm=∏n=1Nexp⁡(−ynβmfm(Xn))I(fm(Xn)≠yn)∑n=1Nwnm对照前面的权重更新公式，就是一直累乘起来\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}\{-1,1\},若不做此要求，然后相应的loss function改成E=∑n=1Nexp⁡(−yn(Fm−1(xn)+fm(xn)))E = \sum_{n=1}^N \exp(-y_n (F_{m-1}(x_n)+f_m(x_n))),则得到了Real Adaboost。（基分类器fm(x)f_m(x)已经没有显式的再加权重了）

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

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

LogitBoost

既然是logit损失，那么优化的就是负对数似然：l(yn,p(xn))=−log(1+e−2ynFm(xn))l(y_n,p(x_n)) = -log(1+e^{-2 y_n F_m(x_n)}) 。迭代时也用的是牛顿步。

误差分析

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

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

参考佳文

AdaBoosting流程及数学证明

Previousrandom forestNextcatboost

Last updated

Was this helpful?