闲来无事，想起不如来写篇博客吧。学术博文好久都没发过了，今天来写点Boosting的东西。这篇文章基本上是按着Robert E. Schapire在UAI 2002的文章Advances in Boosting来的，前不久看了看，现在想用自己的话复述一遍，备忘。
Boosting是个神奇的方法，据说是机器学习中最有名的先有理论再有方法的方法，其他的大多是先有模型或者方法，后来才有理论分析。典型的是神经网络，到现在连一层隐藏变量的神经网络的性质都没研究清楚，但其用途已经非常广泛了。不过话说回来，机器学习理论本身也非常乏力，发展这么多年可以提一提的成果也就只有boosting和SVM，而SVM的bound还相当loose，boosting为什么generalization好到现在也还说不清楚。
说回boosting，boosting是ensemble方法的一种。ensemble顾名思义就是用一堆东西来做一件事情。放到机器学习上来讲，就是用一堆分类器来做分类，其效果会比只用一个要好，人多力量大嘛。按照Robert Schapire在文章里说的，Leslie Valiant（2010年图灵奖获得者）在80年代研究PAC（probably approximately correct）learning的时候就提出了“弱”分类器能否被提升（boost）为“强”分类器的想法。Robert Schapire后来在1989年提出第一个有理论保障的boosting算法，但有不少实际缺陷。1995年Yoav Freud和Robert Schapire的文章提出了AdaBoost算法，克服了很多之前boosting的算法的缺陷，使得boosting被发扬光大。后来Boosting的理论吸引了好些搞统计的人，Stanford的Jerome Friedman就是其中一位，现在他也是搞boosting的大人物。去年他来演讲的时候讲的东西还是boosting。Robert Schapire也是一直在做boosting，好像也只做boosting，2010年他还得过NIPS的最佳论文奖，文章是multiclass boosting。但说实话，从九十年代AdaBoost一骑绝尘以后，boosting好像就没什么大的突破性进展了。
不知不觉又八卦了好些。开始正儿八经来点儿实际的吧，假设我们有一个数据集(x1, y1), (x2, y2), ..., (xm, ym)，其中xi是输入的feature，yi是类标，一般考虑二分类问题，y的取值可为+1或者-1。AdaBoost的算法有两个要素。一个基本的要求是要有一个基分类器（base learner）能够根据给定的数据集（一个数据分布）训练出一个分类器，这个分类器不需要很强，实际上是要求很低，只要比随机猜测好一点点就行。基分类器记为h(x)它是一个将x映射到{+1，-1}的函数。另一个要素是给每一个训练数据一个权重D(i)，可以理解为一个采样概率分布。基分类器需要能够根据给定的D来训练。给每个数据赋权重的意义在于，可以给特定数据高权重，特定数据低权重，使得基分类器能够关注一些特定的数据（或者说data space里的特定区域），这样一来，不同的D得到不同的h，每个h擅长分类不同的区域，也即成了“不同领域的专家”，把他们ensemble起来才有意义，就能获得比单个h更好的效果。
具体的算法是这样的，迭代T轮，记迭代轮次为t，从t=1开始，记D_t(i)为第 t 轮的数据权重或者说采样概率，h_t为第 t 轮得到的基分类器。初始化D_1(i)=1/m，也即每个数据实例的权重都相等。其后每一轮迭代中执行下面三步
（1）根据D_t训练基分类器h_t
（2）选定一个参数 \(\alpha_t\)，具体的选取方法有讲究，下面再介绍
（3）更新$$D_{t+1}(i)=\frac{D_t(i)\exp(-\alpha_t y_i h_t(x_i))}{Z_t}$$
这其中\(Z_t\)是一个归一化常数，目的是保证\(D_{t+1}\)仍然是一个概率分布（即所有i的\(D_{t+1}\)加起来是1）。
这样进行迭代完T轮后，最终的分类器为
$$H(x)=\mathrm{sign}\left(\sum_t \alpha_t h_t(x)\right)$$
sign为符号函数。
AdaBoost的这个算法中，第（3）步的解释很直观，如果\(y_i h_t(x_i)\)为正，也就是说基分类器分对了这个数据实例，那么\(\exp(-\alpha_t y_i h_t(x_i))\)就小于1（alpha总是为正），该实例的权重就下降；相应的，如果\(y_i h_t(x_i)\)为负，基分类器就分错了这个实例，相应的其权重就会提升。经过这样的权重调整，下一轮的分类器就会更加重视前一轮分类器分错的那些实例，而相应的忽视之前分对的那些。这样就可以做到各个基分类器的互补。
\(\alpha_t\)的选取是boosting的理论保障。下面这个性质非常关键：
$$\begin{array}{rcl}\mathrm{Err} & = & \frac{1}{m}|\{i:H(x_i)\neq y_i\}| \\ & \leq & \frac{1}{m}\sum_i \exp(-y_i f(x_i)) \\ & = & \prod_t Z_t \end{array}$$
这上面f定义为
$$f(x)=\sum_t \alpha_t h_t(x)$$
这里Err表示训练错误率。式子的第一行是错误率的定义。第二行的不等式可以这样证明：因为当H分类正确的时候，f 和 y同号，所以 exp小于1但大于0，当分错的时候，f 和 y异号，所以exp大于1。这样对于每个实例，其exp的值总是不小于其错误数（分对记0，分错记1），所以exp的和总是不小于分错的总数。第三行的等式可以根据算法中第三步的D更新公式得到。按照定义
$$\begin{array}{rcl}D_{t+1}(i)&=&\frac{D_t(i)\exp(-\alpha_t h_t(x_i)y_i)}{Z_t} \\ &=& \frac{D_{t-1}(i)\exp(-\alpha_{t-1}h_{t-1}(x_i)y_i - \alpha_t h_t(x_i)y_i)}{Z_{t-1}Z_t} \\ & & \cdots \\ &=&\frac{\exp\left(-y_i\sum_t \alpha_t h_t(x_i)\right)}{m\prod_t Z_t}\end{array}$$
又因为D_(t+1)是归一化的，也即所有D(i)的和为1，上式对 i 求和就可以得到第三行的等式。
这个性质给出了AdaBoost在训练集上的错误率bound，要减小这个bound，需要让Z_t的积尽量小。AdaBoost采用贪心的方法，每一步都让Z_t最小化。通过这个准则，可以求出每一步最优的\(\alpha_t\)，求的方法也很直接，就是求导。
$$Z_t=\sum_i D_t(i)\exp(-\alpha_t y_i h_t(x_i))$$
对\(\alpha_t\)求导，得到
$$\frac{\mathrm{d}Z_t}{\mathrm{d}\alpha_t} = -\sum_i D_t(i)y_i h_t(x_i)\exp(-\alpha_t y_i h_t(x)i))$$
这里有一个小trick，因为h_t把x映射到{+1, -1}，所以y_i 和 h_t的乘积只可能是+1或者-1。积为+1对应分对的情况，-1对应分错的情况。因此所有分对的 i，和式中的项可以简化为\(D_t(i)\exp(-\alpha_t)\)，而分错的项则为\(-D_t(i)\exp(\alpha_t)\)。令导数为零，则可得到
$$(1-\epsilon_t)\exp(-\alpha_t)=\epsilon_t\exp(\alpha_t)$$
这里\(\epsilon_t\)为使用 h_t 的分类错误率，注意每个数据样本都有权重，\(\epsilon_t\)的计算也是考虑权重的。稍变形一下，就可以得到AdaBoost中使用的\(\alpha_t\)公式
$$\alpha_t=\frac{1}{2}\ln\left(\frac{1-\epsilon_t}{\epsilon_t}\right)$$
有了这个\(\alpha_t\)的定义，Z_t便可以用\(\epsilon_t\)来表示。我们可以得到：
$$Z_t = (1-\epsilon_t)\exp(-\alpha_t) + \epsilon_t \exp(\alpha_t) = 2\sqrt{\epsilon_t(1-\epsilon_t)}=\sqrt{1-4\gamma_t^2}$$
其中\(\gamma_t = 1/2-\epsilon_t\)，表示h_t 比随机猜测好多少。利用不等式\(\sqrt{1-2x}\le \exp(-x)\)（这个不等式没什么蹊跷，纯粹是为了凑个指数形式凑出来的）可以进一步变形，并将训练误差Err写为
$$\mathrm{Err}=\prod_t Z_t \le \prod_t \exp(-2\gamma_t^2)=\exp\left(-2\sum_t \gamma_t^2\right)$$
如果基分类器能够保证稳定地优于随机猜测（哪怕只有一点点），\(\forall t, \gamma_t\ge \gamma\)，那么经过T轮迭代之后，
$$\mathrm{Err}\le \exp(-2T\gamma^2)$$
即训练错误率会随着T指数下降。这也就证明了AdaBoost能够将“弱”分类器boost为“强”分类器，而且是超强，因为只要迭代足够轮数，这个分类器可以达到任意精度。这里可以看到为什么基分类器的分类错误率需要小于1/2（或者稳定地高于1/2亦可）因为如果不这样的话，\(\gamma_t\)便为0，上面这个bound就无效了。
上面这些错误率bound都是针对训练错误率而言的。一般来说，AdaBoost在训练集上的错误率会非常快地降到0，测试集上的错误率也会下降，甚至在训练错误率到0之后，测试错误率还会继续下降一段时间。Boosting方法不容易过拟和，这个问题到现在都没研究清楚。也没有相应的bound能够说明boosting的generalization好。有研究说明过boosting的generalization和一种margin有着模模糊糊的关联，而boosting在训练的过程中可以增大那种margin，这貌似就是到目前为止对boosting的generalization可以讲的东西了。
到此为止是把AdaBoost的东西过了一遍，Robert Schapire文章里还提到了boosting实际上优化的exponential loss，以及boosting和logistic regression的关系，也是很有意思的话题，但这里就不提了。
上面说的东西除了没涉及到generalization bound以外，看上去都挺漂亮。但还有一个问题，也就是每一步的\(\alpha_t\)是通过“贪心”的方法选出来的。如果不贪心，是不是可以做得更好呢？有一种做法是在迭代生成各个基分类器的时候，不设定\(\alpha_t\)（D_t的更新通过别的方式），当得到所有基分类器之后，再做拟合找到最优的\(\alpha_t\)。这个拟合的过程其实是个logistic regression，基分类器的输出被当做feature向量，而\(\alpha_t\)就是各feature对应的系数。Jerome Friedman做了不少这方面的工作。
从这个观点再延伸一步，我们可以走另一个极端：所有基分类器我们都不学，而是用随机映射。由于给定的训练数据集数量有限，且计算机里用的都是伪随机数，我们其实无法得到真随机的 h_t （多多少少会和1/2的错误率差一点儿）。按照boosting的理论（应该就是Jerome Friedman的那些理论了，我不确定对不对），通过拟合\(\alpha_t\)我们依然可以将训练误差降到非常小！这也就可以解释为什么有的时候用random projection来抽取feature也可以做的很好了。random projection的另一种解释是这个projection可以看做是一个kernel。
好了，今天就到这里吧，写了这么多我也满足了。