经典机器学习系列(六)【集成学习】之周志华西瓜书-AdaBoost算法证明解析

本节证明并未从集成学习源头开始，如若对集成学习还不是很清楚的同学，参考文章：  

• 经典机器学习系列之【集成学习】

AdaBoost算法证明

  本文以周志华西瓜书推导过程为例，以“加性模型”（additive model）进行解析：   将基学习器ht​(x)线性组合，则基学习器的线性组合表示为如下$H(\mathbf{x})$形式：  
  定义整个学习器的损失函数为指数损失函数(exponential loss function)，期望指数损失函数最小化：  
  其中$f$是真实函数，yi​∈{−1,+1}，D 表示样本的权值分布(对于错误的样本权重要高一点，正确的样本权重要低一点，所有的样本组合起来就相当于有一个分布)。   若基学习器的线性组合$H(\mathbf{x})$能够使得指数损失函数最小化，一般的做法就是求偏导数，令其等于零，求解。由于f ( x ) 取值只有两种，所以其求偏导数之后的结果如下所示：  
  这意味着若指数损失函数最小化，则分类错误率也将最小化。说明指数损失函数是原任务的替代函数，但由于其连续可微，所以用它替代0/1损失函数作为优化目标。上面这么多就是说接下来用这个连续的指数损失函数做进一步的处理。   在AdaBoost算法中，第一个基分类器h1​通过直接将基学习算法用于初始数据分布而得到；之后的ht​和α t 是通过迭代生成得到的。当基分类器ht​基于分布Dt​产生之后，基分类器的权重αt​应该使得αt​ht​最小化指数损失函数，只有αt​在判断错误的基分类器给予较小权值，判断正确的基分类器给予较大权值，才能使得$H(\mathbf{x})$具有较准确的判断，从而最小化指数损失函数  
 
其实就是误判率。为了求得基分类器的权重，对其求导：  
  到这里相当于自适应做完了，在这里，AdaBoost自适应的思想采取的是加权多数表决的方法，上述公式体现出来的就是加大分类器误差率小的弱分类器的权值，使其在表决中起较大作用。误差率较大的则相反。   现在要回到Boost的原理中对样本的处理，在改变这个样本的权值，或者说概率分布的时候，我们要实现的直观想法是：提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值。接下来我们去把这个公式证出来：   这里通过基学习器开始证明，看基学习器在什么样本分布下能够学出来最小化分类误差。   AdaBoost在得到Ht−1​之后，调整样本分布，使得ht​能学出来之前的基学习器无法学习到的东西，能纠正Ht−1​的一些错误，那这个ht​就能够最小化：  
  于是理想的基学习器：  
  依据数学期望的定义，等价于令:  
  则理想的基学习器：  
  由此可见，理想的ht​将在分布Dt​下最小化分类误差。Dt​和Dt+1​的关系有：  
  上述公式就是下图AdaBoost的第7步更新公式，整个的AdaBoost算法如下图所示：  
  AdaBoost 算法第五行检查当前基分类器是否比随机猜测好，一旦不满足条件，当前基学习器即被抛弃，且学习过程停止。在这个请款下就有可能导致集成中包含基学习器数量过少，导致整体性能不佳。采用“重采样法”（re-sampling）来处理，即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样而得到的样本集对基学习器进行训练，则可获得重启动。