Foundations of Machine Learning: Boosting
Boosting是属于自适应基函数(Adaptive basis-function Model(ABM))中的一种模型。自适应基函数可以表示成：
$$f(x)=w_0+sum_{m=1}^Mw_mphi_m(x).$$
其中基函数$phi_m$在Boosting里面叫做weak learner。Boosting会不断学习出weak learner,然后通过权重向量将这些weak learner组合成一个stronger learner。 并且可以证明只要weak learner 比随机learner好，那么Boosting总可以以很高的概率组合成一个性能任意好的stronger learner。
Boosting 在每一次迭代都会产生一个weak learner，而这个weak learner 与其他的机器学习算法一样，都是通过训练集学习出来的，现在假如我们每一步学习用到的训练集都一样的话，那么每一步学习出来的weak learner可能都差不多，甚至一样，这样组合起来的最终结果并没有什么意义。所以Boosting在每一步都会根据上一步的结果来产生一个新的训练集。
一、二分类下的AdaBoost算法。
AdaBoost的特点：
- 每次迭代中的训练集因分布$D_t$不同而不同，而$D_{t+1}$根据$D_t$产生。
- 每次迭代产生的$epsilon_t$称为该weak learner的错误率。由于$epsilon_t<1/2$,故$alpha_t>0$，而$alpha_t$最后作为组合weak learner的权重，显然$epsilon_t$越小，$alpha_t$越大，也即好的weak learner的权重越大。
- $D_t$作为每个样本的权重分布，当第$t$步产生的$h_t$使样本$x_i$发生错误则，$D_{t+1}(i)=frac{D_{t}(i)exp(alpha_t)}{z_t}$，使第i个样本权重增大；当$h_t$使样本$x_i$不发生错误时，$D_{t+1}(i)=frac{D_{t}(i)exp(-alpha_t)}{z_t}$，使样本i的权重减小。也就是说，在下一步总是更关心上一步被分错的那些点。
- 除以$z_t$是为了使$D_{t+1}$成为一个分布，即保证$sum_{i=1}^mD_{t+1}(i)=1$。故
egin{align*}Z_t &=sum _{i=1} ^mD_t(i)e^{-alpha_ty_ih_t(x_i)} \& =sum _{i:y_ih_t(x_i)=1}D_t(i)e^{-alpha_t}+sum _{i:y_ih_t(x_i)=-1}D_t(i)e^{alpha_t} \&=(1-varepsilon_t)e^{-alpha_t}+varepsilon_te^{alpha_t} \&=(1-varepsilon_t)sqrt{frac{varepsilon_t}{1-varepsilon_t}}+varepsilon_tsqrt{frac{1-varepsilon_t}{varepsilon_t}} \&=2sqrt{varepsilon_t(1-varepsilon_t)}end{align*}
二、经验错误的界。
定理 3.1 AdaBoost算法返回的分类器所产生的经验错误满足如下的界：
$$widehat{mathcal{R}}(h)leq exp[-2sum_{t=1}^T(frac{1}{2}-epsilon _t)^2],$$
更进一步说，如果对所有的$tin [1,T],gammaleq (frac{1}{2}-epsilon _t)$，那么
$$widehat{mathcal{R}}(h)leq exp(-2gamma^2T).$$
证明：由$mathbb{I}((uleq 0))leq exp(-u)$得：
egin{align*}widehat{mathcal{R}}(h) &=frac{1}{m}sum{i=1}^mmathbb{I}((y_ig_T(x_i))leq 0) \&leq frac{1}{m}sum _{i=1} ^me^{-y_ig_T(x_i)}end{align*}
根据$D_t$的定义有：
egin{align*}D_1(i) &=frac{1}{m} \D_2(i) &=frac{exp(-alpha_1 y_i h_1 (x_i))}{mz_1} \ D_3(i) &=frac{exp(-alpha_1 y_i h_1 (x_i))}{mz_1}cdotfrac{exp(-alpha_2 y_i h_2 (x_i))}{z_2} \ ... & ... \D_t(i) &=frac{exp(-alpha_1 y_i h_1 (x_i))cdot exp(-alpha_2 y_i h_2 (x_i))...exp(-alpha_{t-1} y_i h_{t-1} (x_i))}{mz_1cdot ...cdot z_{t-1}}end{align*}
$$Longrightarrow D_{t+1}(i)=frac{e^{-y_ig_t(x_t)}}{mPi_{s=1}^{t}z_s} Rightarrow e^{-y_ig_T(x_i)}=mPi_{s=1}^Tz_scdot D_{T+1}(i)$$
代入上式：
egin{align*}widehat{mathcal{R}}(h) &leq frac{1}{m} sum _{i=0} ^mmPi_{s=1}^Tz_sD_{T+1}(i) \&=Pi_{s=1}^T z_s \&=Pi_{t=1}^T 2sqrt{epsilon_t(1-epsilon_t)} \ &leq Pi_{t=1}^T exp[-2(frac{1}{2}-epsilon)^2)] \ &= exp[-2sum _{t=1}^T(frac{1}{2}-epsilon_t)^2] end{align*}
注意点：
- $alpha_t=1/2logfrac{1-epsilon_t}{epsilon_t}$的原因：要使得$z_t=(1-varepsilon_t)e^{-alpha_t}+varepsilon_te^{alpha_t}$最小,令其导数等于0即可求得。即令$frac{dZ_t(alpha_t)}{dalpha_t}=-(1-epsilon_t)e^{alpha_t}+epsilon_t e^{alpha_t}=0$
$$Longleftrightarrow (1-epsilon_t)e^{-alpha_t}=epsilon_te^{alpha_t}Longleftrightarrow alpha_t=frac{1}{2}logfrac{1-epsilon_t}{epsilon_t} $$
$alpha_t$是根据最小化$Z_t$来选取，即每次选得$alpha_t$都使$widehat{mathcal{R}}(h)$的上界变小。 - 其中的$gamma$叫做edge。
三、使用VC理论去界定泛化界。
像上面章节一样，假设集H为所有可选择的基本假设$h_t$的集合，$C_T$为用T个基本假设线性组合的组合假设。对二分类来说：$C_T={H(x)=sign(sum _{t=1} ^Talpha_th_t(x)),h_tin H,alpha_tin R}$。定义一个函数$sigma:R^T ightharpoonup{-1,+1}$,且$sigma(x)=sign(wcdot x)$,令$sum_T$表示所有这样的$sigma$函数，即$sum_T={sigma(x)=sign(wcdot x);win mathbb{R}^T}$。所以$H(x)=sign(sum _{t=1}^Talpha_t h_t(x))$就可以表示成$H(x)=sigma(h_1(x),h_2(x),...,h_T(x))$。而
$$C_T={x ightarrowsigma(h_1(x),h_2(x),...h_T(x)):sigma inSigma_T;h_1,...,h_Tin H}.$$
引理 3.1 在$R^n$中的线性阈值函数空间$sum_n$的VC维为$n$。
证明：
1：证明存在n个点可以被打散。
令$e_i$为n维空间的基向量，即
egin{equation*}e_i(j)=egin{cases} 1 &mbox{$j=i$}\ 0 & mbox{$j
eq i$} end{cases} end{equation*}
则只需证明$e_1,e_2,...,e_n$可以被$sum_n$打散。
首先，对于任何一种二分结果，我们都可以将其表示成$(y_1,y_2,...,y_n)$，其中$y_i in{-1,+1}$。所以当我们令$w=(y_1,y_2,...,y_n)$时，由$sign(wcdot e_i)=y_i$可知，该二分结果总可以被实现。故$e_1,e_2,...,e_n$可以被$sum_n$打散。
所以$sum_n$的VC维至少为n。
2： 证明所有n+1个点都不可以被打散。
假设存在n+1个点$x_1,...,x_{n+1}inmathbb{R}^n$可以被$sum_n$打散。那么，必定存在不全为0的$eta_1,eta_2,....,eta_{n+1}$使$sum _{i=1} ^{n+1}eta_ix_i=0$。
不失一般性，我们假设$eta_{n+1}>0$，由于这些点可以被$sum_n$打散，故一定存在一个$omega in R^n$使分类的结果为
egin{equation*}y_i= egin{cases} +1 & if eta_i>0 \ -1 & if eta_ileq0 end{cases} end{equation*}
即$omega$满足$sign(omegacdot x_{n+1})=+1$,
egin{equation*}sign(omegacdot x_i)= egin{cases} +1 & if eta_i>0 \ -1 & if eta_ileq0 end{cases} end{equation*}
即$eta_{n+1}cdot omega cdot x_{n+1}>0,eta_icdot omega cdot x_i>0$。
而且
egin{align*} 0=omegacdot 0 &=omega cdot sum _{i=1} ^{n+1}eta_icdot x_i \ &=sum _{i=1} ^{n+1}eta_icdotomegacdot x_i>0 end{align*}
所以矛盾。
引理 3.2 假设H是有限的。令$mgeq Tgeq 1$，那么对任意的有$m$个点的集合$S$，由$C_T$所实现的划分的数量的界为：
$$mid Pi_{C_T}(S)midleq Pi _{C_T}(m)leq(frac{em}{T})^Tmid Hmid^T$$
证明：令$S=(x_1,x_2,...,x_m)$。考虑到固定序列的基本假设$h_1,h_2,...,h_T in H$，相对这些基本假设，我们得到一个新的样本$S'=(x_1',x_2',...,x_m')$，其中$x_i'=(h_1(x_i),...,h_T(x_i))$,即每一个样本$x_i$在每一步中得到的结果组成的向量。
由于$sum_T$的VC维为T，所以根据推论2.3有：
$$|Pi_{sum_T}(S')|leq (frac{em}{T})^T$$
由于选择$h_1,...,h_T$的方式有$|H|^T$种，所以可以得到
$$|Pi_{C_T}(S)|leq Pi_{C_T}(m)leq(frac{em}{d})^T|H|^T$$
如何理解上述引理？首先我们得先明确，Boosting的假设集$C_T$ 由两部分结合而成（或者说是由两种函数复合而成）。第一个选基函数，即选$h_1,h_2,...,h_T$；第二个选线性函数，即选择系数将$h_1,h_2,...,h_T$线性组合起来。
第一种的选择方式有$mid Hmid^T$ 种可能，第二种的选择方式有无穷多种，但有效的选择方式只有$midPi_{sum_T}(S')$种。
或者可以这样理解：先选择$h_1,h_2,...,h_T$，然后由这些$h_1,h_2,...,h_T$ 组成一个新的坐标系，把原来的样本转换到这个新坐标系中得到新样本，然后用一个线性分类器对这个新样本分类。
引理3.3 假设H拥有有限的VC维$dgeq 1$。令$mgeqmax{d,T}$。对任意的m个点的集合S，由$C_T$所实现的划分的数量的界为：
$$mid Pi_{C_T}(S)midleq Pi _{C_T}(m)leq(frac{em}{T})^T(frac{em}{d})^{dT}$$
证明：
令任意大小为 m 的样本 $S={x_1,x_2,...,x_m}$, 则用假设集H中的每一个元素预测样本S最多可以实现的“二分”结果个数为$mid Pi_H(S)mid$。 现在我们对每一个“二分”结果只取一个假设$h'$ 构成一个新的假设集$H'$,则 $mid H'mid=midPi_H(S）mid$且根据 推论2.3 可知： $|H'|=|Pi_H(S)|leq (frac{em}{d})^d$.
由于每一个$hin H$在样本S上产生的二分结果在$H'$中都存在着唯一一个$h'in H'$与之相对应。所以在H上选择T个$hin H$与在$H'$上选择T个$h'in H'$是等价的。即根据 引理3.1 有：
egin{align*}|Pi_{C_T}(S)| &leq (frac{em}{T})^T|H'|^T \ &leq (frac{em}{T})^T(frac{em}{d})^dT end{align*}
有了这个界后，我们可以将 推论2.2 拿过来产生Boosting的 generalization error的界，即：
egin{align}mathcal{R}(h) &leq widehat{mathcal{R}}(h) + sqrt{frac{2logPi_{C_T}(m)}{m}} + sqrt{frac{logfrac{1}{delta}}{2m}} \ &leq widehat{mathcal{R}}(h) + sqrt{frac{2Tlogfrac{em}{T}+2dTlogfrac{em}{d}}{m}} + sqrt{frac{logfrac{1}{delta}}{2m}}end{align}
从上面的不等式可以看出，当T越来越大时$mathcal{R}$的上界会不断增大，似乎当T很大时会产生 overfit 的情况。但在实际情况下，Boosting 很少会产生overfit的情况，既然在$widehat{mathcal{R}}(h)=0$ 情况增加T也不会产生 overfit。 而这种情况就需要用新的理论来解释，即 Margin 理论：当T不断增加时，Margin 会越来越大，即可置信的程度越来越高。