集成学习

简单来说，集成学习就是将一组个体学习器结合起来，通过某种策略，将其结合成一个总学习器来完成相应任务；集成学习是为了得到比单一学习器更好的泛化性能。主要分为两种类型：若每个个体学习器是通过同一算法得到，则称为同质，每个各体学习器称为基学习器；若每个个体学习器是由不同算法得到，则称为异质，个体学习器也可称为组件学习器。
集成学习的一个核心是：如何产生并结合“好而不同”的个体学习器。下面是西瓜书里，一个关于集成学习的直观举例，像下面有三种集成学习的情况，前两种情况的个体学习器都是66%的准确率，可是第一种情况个体学习器之前存在差距，因此集成后效果得到提高；而第二种情况，个体学习器由于之间没有差距，因此集成后效果没有提高；而第三种因为个体学习器不够好，因此集成后反而没有提高。

“好而不同”

集成学习的简单数学解释

下面是关于集成学习的一个简单分析：一个二分类问题 $y \in \{ -1, 1 \}$ 和其实际对应函数 $f(x)$ ；假设每个基分类器 $h_i(x)$ 的错误率为 $\epsilon_i$ ，即：
$P(h_i(x) \neq f(x)) = \epsilon$ 通过投票法集成T个基本分类器，即：
$H(x) = \sum _{i=1} ^{T} {h_i(x)}$ 假设每个基分类器 $h_i(x)$ 错误率相互独立，那么：
$\begin{aligned} P(H(x) \neq f(x)) &= \sum _{k=0} ^{ \lfloor {T \over 2} \rfloor } {T \choose K} {(1 - \epsilon)}^k {\epsilon}^{{T \over 2} - k} \\ & \leq e^{-{1 \over 2} T {(1 - 2 \epsilon)}^2 } \end{aligned}$ 上述公式的第一行可通过排列组合知识来解释；第二行的不等式是利用Hoeffding不等式所推出得知。上述公式随着T的增加，其错误率则不断的下降；这意味着当个体分类数目越多，其集成后分类错误率则越低。
集成学习的方法主要分为两大类：第一类是串行序列化方法，先从初始训练集得到一个基学习器，然后再调整训练样本分布，再训练下一个基学习器，学习器之间存在较强的依赖关系；第二类是并行化方法。第一类的代表是boosting，第二类是bagging和随机森林。

boosting

boosting是一种串行序列化方法，先从初始训练集得到一个基学习器，然后再调整训练样本分布，再训练下一个基学习器，学习器之间存在较强的依赖关系；其中AdaBoost就是其中的代表算法。下面是AdaBoost算法的整体流程：

Adaboost(训练集D, 基学习算法b, 迭代次数T){
      初始化训练集D的权重分布D_1(x) = 1 / m
      
      for t = 1 to T {
          ht = b(D, D_t)    #根据数据集D与数据的权重分布D_t生成基学习器ht
          计算h_t的错误率p
          
          if p > 0.5
             break
         
         更新当前基学习器ht的权重a_t
         更新训练集D的权重分布D_t+1
      }

     返回基学习器的加权和：H(x)
}

AdaBoost的优化目标

可以看到AdaBoost算法是一个迭代优化算法，该算法的优化目标是最小化指数损失函数的期望，假设问题是解决一个二分类问题。
$\begin{aligned} loss(H | D) &= E[ e^{ -f(x)H(x) } ] \\ &= e^{-H(x)} P(f(x) = 1) + e^{H(x)} P(f(x) = -1) \end{aligned}$ 然后损失函数对 $H$ 进行求导可得：
${ {\partial loss} \over {\partial H} } = -e^{-H(x)} P(f(x) = 1) + e^{H(x)} P(f(x) = -1)$ 令上式取零解后，可得：
$H(x) = {1 \over 2} ln{ P(f(x) = 1) \over P(f(x) = -1) }$ 进一步可得到：
$\begin{aligned} sign( H(x) ) &= sign( {1 \over 2} ln{ P(f(x) = 1) \over P(f(x) = -1) } ) \\ &= \begin{cases} 1, &P(f(x) = 1) > P(f(x) = -1) \\ -1, &P(f(x) = 1) > P(f(x) = -1) \end{cases} \end{aligned}$ 上述过程说明 $sign( H(x) )$ 达到贝叶斯最优错误率，即最小化上述指数损失函数的期望，也可将错误率最小化；并且该损失函数更具比较好的数学性质。因此AdaBoost的优化目标是：最小化指数损失函数的期望。

AdaBoost的参数更新

   损失函数 $loss(H|D)$ 中，其中 $H$ 的定义是：
$H(x) = \sum _{t=1} ^{T} {\alpha_t h_t(x)}$ 而基分类器 $h_t(x)$ 是由关于数据集的权重 $D_t(x)$ 与数据集 $D$ 共同生成，因此AdaBoost算法中，需要更新的参数为： $\alpha_t$ 和 $D_t(x)$ 。
   关于 $\alpha_t$ ，将t时刻的分类器代入损失函数中可得：
$\begin{aligned} loss(\alpha_t h_t | D_t) &= E[ e^{-f(x) \alpha_t h_t(x)} ] \\ &= E [ e^{- \alpha_t } bool(f(x) = h_t(x)) + e^{\alpha_t} bool(f(x) \neq h_t(x)) ] \\ &= e^{- \alpha_t } E[ bool(f(x) = h_t(x)) ] + e^{\alpha_t} E[ bool(f(x) \neq h_t(x)) ] \\ &= e^{- \alpha_t } P( f(x) = h_t(x) ) + e^{\alpha_t} P( f(x) \neq h_t(x) ) \\ &= e^{- \alpha_t } (1 - \epsilon_t) + e^{\alpha_t} \epsilon_t \end{aligned}$ 求上述式子关于 $\alpha_t$ 的偏导，可得：
${\partial loss \over \partial {\alpha_t}} = -e^{- \alpha_t } (1 - \epsilon_t) + e^{\alpha_t} \epsilon_t$ 取上式的零解，可得：
$\alpha_t = {1 \over 2} ln ( {{1 - \epsilon_t} \over {\epsilon_t}} )$ 这就是 $\alpha_t$ 的更新公式。
    下面是关于AdaBoost算法中， $h_t$ 是对 $H_{t-1}$ 错判的数据极可能的关注的一个证明，使得基学习器 $h_t$ 尽可能的纠正 $H_{t-1}$ 的错误，即最小化：
$\begin{aligned} loss(H_{t-1} + h_t | D) &= E[ e^{-f(x)(H_{t-1}(x) + h_t(x) )} ] \\ &= E[ e^{-f(x) H_{t-1}(x)} e^{-f(x) h_t(x)}] \end{aligned}$ 对上述式子后半部分进行泰勒展开，可得：
$\begin{aligned} loss(H_{t-1} + h_t | D) & \approx E[ e^{-f(x) H_{t-1}(x)} (1 - f(x) h_t(x) + { f^2(x) {h_t}^2(x) \over 2}) ] \\ & = E[ e^{-f(x) H_{t-1}(x)} (1 - f(x) h_t(x) + {1 \over 2} ) ] \end{aligned}$ 那么想 $h_t$ 可以纠正更多错误，则可以最小化损失函数，即：
$\begin{aligned} arg min_h loss(H_{t-1} + h | D) \\ &= arg min_h E[ e^{-f(x) H_{t-1}(x)} (1 - f(x) h(x) + {1 \over 2} ) ] \\ &= arg max_h E[ e^{-f(x) H_{t-1}(x)} f(x) h(x) ] \\ &= arg max_h E[ {e^{-f(x) H_{t-1}(x)} \over E[e^{-f(x) H_{t-1}(x)}] } f(x) h(x) ] \end{aligned}$ 设分布 $D_t(x)$ 为：
$D_t(x) = { { D(x) e^{-f(x) H_{t-1}(x) } } \over E[ e^{-f(x) H_{t-1}(x)} ] }$ 由数学期望定义，上式等价于：
$\begin{aligned} arg max_h E _{x \sim D} [ {e^{-f(x) H_{t-1}(x)} \over E[e^{-f(x) H_{t-1}(x)}] } f(x) h(x) ] &= arg max_h E _{x \sim D_t} [f(x)h(x)] \\ &= arg max_h E _{x \sim D_t} [1 - 2*bool(f(x) \neq h(x) )] \\ &= arg min_h E _{x \sim D_t} [bool(f(x) \neq h(x) )] \end{aligned}$ 个人对于上式第一行的理解是，左半部分是计算一个基于分布D的一个数学期望，简单来写就是：分布D $\times$ 取值，而再结合分布 $D_t(x)$ 的定义，就变成右半部的随机变量f(x)h(x)关于分布 $D_t(x)$ 的数学期望。
   上面的过程是关于基分类器 $h_t(x)$ 是对之前分布错误的一个调整后的分类器，使得 $h_t(x)$ 将在分布 $D_t$ 下最小化误差。
   关于分布 $D_t$ 的更新，则可从式子出发：
$\begin{aligned} D_{t+1}(x) &= { { D(x) e^{-f(x) H_{t}(x) } } \over E[ e^{-f(x) H_{t}(x)} ] } \\ &= { { D(x) e^{-f(x) H_{t-1}(x) } e^{-f(x) \alpha_t h_t(x) } } \over E[ e^{-f(x) H_{t-1}(x)} ] } \\ &= D_t(x) \cdot e ^{-f(x) \alpha_t h_t(x)} { E[ e^{-f(x) H_{t-1}(x) } ] \over E[ e^{-f(x) H_{t}(x) } ] } \end{aligned}$
   总的来说，AdaBoost算法最主要的是下面两个式子：
$\begin{aligned} \alpha_t &= {1 \over 2} ln( { {1 - \epsilon_i} \over \epsilon_i } ) \\ D_{t + 1}(x) &= {D_t(x) e^{- \alpha_t f(x) h_t(x) } \over z_t } \end{aligned}$

AdaBoost的实现

这里关于AdatBoost的实现，是参考《机器学习实战》里面的实现。该实现中使用的弱分类器是决策树桩(decision stump)，其是单层决策树，既只通过某个特征的某个特征值的大于小于来进行分类。
下面这段代码是关于决策树桩的分类，其实只是根据某个特征的某个值进行二分：

def stumpClassify(dataset, index, value, ops):
    
    m, n = dataset.shape
    res = np.ones((m))
    
    #lt代表小于value值的为负类，gt代表大于value值的为负类
    if ops == 'lt':
        res[ np.where( dataset[:, index] <= value )[0] ] = -1.0
    elif ops== 'gt':
        res[ np.where( dataset[:, index] > value )[0] ] = -1.0
        
    return res

这一段是关于如何建立一个决策树桩，通过遍历所有特征的特征值，选择其中带权误差率(分布D的作用主要是计算误差率)最小的作为建立的决策树桩。：

def buildStump(dataset, D):
    
    m, n = dataset.shape
    bestStump = {}
    bestClassEst = np.zeros(m)
    numSteps = 10.0
    min_err = np.inf
    
    for i in range( n - 1 ):
        
        #将值范围分成numSteps等份，再以该等份的值作为分类的值
        min_value = np.min( dataset[:, i] ); max_value =  np.max( dataset[:, i] )
        step_size = (max_value - min_value) / numSteps
        
        for j in range(-1, int(numSteps) + 1):
            for o in ['lt', 'gt']:
                value = min_value + float(j) * step_size
                predictions = stumpClassify(dataset, i, value, o)
                mistake = (predictions != dataset[:, -1] )
                weight_err = np.dot(D, mistake)
                
                if weight_err < min_err:
                    min_err = weight_err
                    bestClassEst = predictions.copy()
                    bestStump['idx'] = i
                    bestStump['val'] = value
                    bestStump['ops'] = o
                    
    return bestStump, min_err, bestClassEst

下面这段代码是AdaBoost的主体：

def AdaBoot(dataset, numIter=40):
    
    bases = []
    m, n = dataset.shape
    
    D = np.ones( m ) / m
    acc_res = np.zeros( m )
    
    for i in range( numIter ):
        #根据分布D和数据集，建立基分类器
        stump, err_rate, classEnt = buildStump(dataset, D)
        
        #若单个基分类器错误率大于0.5抛弃并退出循环
        if err_rate > 0.5:
            break
        
        #更新基分类器权重
        alpha = np.log( (1.0 - err_rate) / np.maximum(err_rate, 1e-6) ) * 0.5
        stump['alpha'] = alpha
        bases.append( stump )
        
        #更新下一次的权重分布D
        D = D * np.exp( -1.0 * classEnt * dataset[:, -1] * alpha ) / np.sum( D )
        
        #计算当前集成后的分类器的错误率
        acc_res += alpha * classEnt
        acc_err = np.mean(np.sign( acc_res ) != dataset[:, -1])
ji        
        #若集成后的分类器已经达到零差错，则无需继续进行下去
        if acc_err == 0.0:
            break
            
    return bases

而到实际用于分类时，只需遍历base中的分类器，将分类结果加权求和即可。

sklearn中的AdaBoost

在sklearn中，AdaBoost的使用与其他模型类似；其默认的base_estimator是一层的决策树，而具体的实现算法有：SAMME和SAMME.R，SAMME是以分类的类别作为调整权值分布，而SAMME.R是以分类的类别概率来调整权值分布。

集成学习——AdaBoost