AdaBoosting流程及数学证明

基本思想：通过级联弱分类器（分类能力较弱的分类器）来构造一个强分类器。

训练准备：为了描述简洁，用典型的二分类问题进行阐述。

   训练集：   N个多维的特征向量

   分类器池：L个弱分类器

    m个分类器判别结果的线性组合：

                                                             （1）

   其中代表第t个弱分类器的权值，且始终大于0，直觉上，这个权值对于错分率较低的线性分类器必须给予较高的权值；

   表示输入为多维特征向量（多维空间中的一个点）时第t个弱分类器的判断结果。对于二分类问题，值域为

     有了公式（1）对于特征向量，级联判断器的分类结果为。

 训练步骤

       1、从分类器中选择一个分类器，使得能通过分类器的样本数量尽可能多。

       数学表达：假设当前已有m-1个分类器被选入级联分类器中，对于特征向量，当前级联分类器的线性组合是

                                                        （2）

      现在我们希望从分类器池中再选出一个分类器作为第m个分类器，加入到级联组中，数学表达如下

                                        （3）

       并根据分类器的错分率，自动调整相应的权值，使得错分率大的分类器权值小（这就是Adaptive Boosting中Adaptive自适应的含义吧）。

       为了解决如何选择第m个分类器的问题，对于训练集，我们引入如下分类损失函数

                                                    （4）

 其中yi为训练样本人工分类的结果，值域也为                            

              可以看到由于前m-1个分类器和相应的权值都以确定，故必定是一个常数，因此公式（4）可以化简为

                                                             （5）

  其中            是一个常数

   根据人工标注的结果和线性分类器判别的结果可以对（5）继续分解

                            （6）

   可以看到，对于错分的样本，对E的贡献要大，对于正确分类的样本，对E的贡献要小

       由于是常数，我们可以写出如下表达式

                                                                      （7）

        其中（）表示当前第m个分类器错分(正确分类)时，前m-1个分类器对错分（正确分类）样本的权重系数之和。为一个常数W。我们必须选错分权重系数之和最小的分类器作为第m个分类器。

       2.确定权重系数

        然后对

  求取偏导，使得损失最小

          

         令偏导数=0求得

       

         其中

        可以看到对于错分率低的分类器，权值会是最大，加强了这个分类器的分类影响。

        3.迭代运行算法，直到达到级联器中分类器的上限

参考资料：AdaBoost and the Super Bowl of Classi ers A Tutorial Introduction to Adaptive Boosting

                 http://summerbell.iteye.com/blog/532376