0 写在前面

机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理；“广”在分析多个机器学习模型：决策树、支持向量机、贝叶斯与马尔科夫决策、强化学习等。强基计划实现从理论到实践的全面覆盖，由本人亲自从底层编写、测试与文章配套的各个经典算法，不依赖于现有库，可以大大加深对算法的理解。

?详情：机器学习强基计划(附几十种经典模型源码)

1 串行集成学习

串行集成学习是一种机器学习的技术，旨在通过将多个基学习器按顺序组合起来，以提高整体学习性能。在串行集成学习中，基学习器按照一定的顺序进行训练和集成，每个基学习器都依赖于前一个学习器的输出。

Boosting是一族将弱学习器提升为强学习器的串行集成算法，这族算法核心原理为：先从初始训练集训练出一个基学习器；再根据基学习器的表现对训练样本分布进行调整，实现不同学习器的差异性，同时使先前基学习器的误分类样本在后续受到更多关注；然后基于调整后的样本分布训练下一个基学习器；重复进行直至基学习器数目达到事先指定值$T$，最终将这$T$个基学习器进行集成输出。

Boosting族的著名算法是自适应提升(Adaptive Boosting, AdaBoost)，其采用指数损失函数，具体原理参见第二节

2 AdaBoost原理推导

AdaBoost具体而言，分为两个步骤：

• 从样本分布${\mathcal{D}}_t$中训练分类器$h_t$，使$H_{t-1}$的误分类样本在$h_t$作用下误分类概率下降
• 生成$h_t$后计算其权重${\alpha }_t$使总体损失最小

注意，标准AdaBoost算法只用于二分类问题。

具体原理推导如下：首先考察$h_t$的产生，理想的$h_t$能纠正$H_{t-1}$的所有错误，使损失最小

$$\begin{array}{rl}{h}_t& =\underset{h\in \mathcal{H}}{\mathrm{argmin}}\sum _{\mathbf{x}}{e}^{-f\left(\mathbf{x}\right)\left[H_{t-1}\left(\mathbf{x}\right)+{\alpha }_{t}h\left(\mathbf{x}\right)\right]}\\ & =\underset{h\in \mathcal{H}}{\mathrm{argmin}}\sum _{\mathbf{x}:h\left(\mathbf{x}\right)=f\left(\mathbf{x}\right)}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}{e}^{-{\alpha }_t}+\sum _{\mathbf{x}:h\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}{e}^{{\alpha }_t}\\ & =\underset{h\in \mathcal{H}}{\mathrm{argmin}}\sum _{\mathbf{x}}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}{e}^{-{\alpha }_t}+\sum _{\mathbf{x}:h\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}\left(e^{{\alpha }_t}-e^{-{\alpha }_t}\right)\\ & =\underset{h\in \mathcal{H}}{\mathrm{argmin}}\sum _{\mathbf{x}:h\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}\\ & =\underset{h\in \mathcal{H}}{\mathrm{argmin}}\sum _{\mathbf{x}:h\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)}\frac{e^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}{{\sum }_{\mathbf{x}}^{}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}\end{array}$$

其中$f$为训练集$D$中样本$\mathbf{x}$到其标签$y$的映射。若设分布

$${\mathcal{D}}_t\left(\mathbf{x}\right)=\frac{e^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}{{\sum }_{\mathbf{x}}^{}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}$$

其中误分类样本$f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)<0$权重升高，正确分类样本权重降低，则

$$h_t=\underset{h\in \mathcal{H}}{\mathrm{argmin}}\sum _{\mathbf{x}:h\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)}{\mathcal{D}}_t\left(\mathbf{x}\right)=\underset{h\in \mathcal{H}}{\mathrm{argmin}}{P}_{\mathbf{x}{\mathcal{D}}_t}\left(h\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)\right)$$

换言之，只要根据$H_{t-1}$调整下一轮迭代时的样本分布${\mathcal{D}}_t\left(\mathbf{x}\right)$，就能降低$H_{t-1}$中误分类样本再次被误分类的概率。考虑迭代性，有

$${\mathcal{D}}_t\left(\mathbf{x}\right)={\mathcal{D}}_{t-1}\left(\mathbf{x}\right)\frac{{\sum }_{\mathbf{x}}^{}{e}^{-f\left(\mathbf{x}\right)H_{t-2}\left(\mathbf{x}\right)}}{{\sum }_{\mathbf{x}}^{}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}\frac{e^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}{e^{-f\left(\mathbf{x}\right)H_{t-2}\left(\mathbf{x}\right)}}=\frac{{\mathcal{D}}_{t-1}\left(\mathbf{x}\right)e^{-f\left(\mathbf{x}\right){\alpha }_{t-1}{h}_{t-1}\left(\mathbf{x}\right)}}{{\sum }_{\mathbf{x}}^{}{\mathcal{D}}_{t-1}\left(\mathbf{x}\right)e^{-f\left(\mathbf{x}\right){\alpha }_{t-1}{h}_{t-1}\left(\mathbf{x}\right)}}$$

接下来考虑${\alpha }_t$的计算，同样从优化指数损失出发

$$\begin{array}{rl}{\alpha }_t& =\underset{\alpha }{\mathrm{argmin}}{e}^{-\alpha }\sum _{\mathbf{x}:h_t\left(\mathbf{x}\right)=f\left(\mathbf{x}\right)}\frac{e^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}{{\sum }_{\mathbf{x}}^{}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}+e^{\alpha }\sum _{\mathbf{x}:h_t\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)}\frac{e^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}{{\sum }_{\mathbf{x}}^{}{e}^{-f\left(\mathbf{x}\right)H_{t-1}\left(\mathbf{x}\right)}}\\ & =\underset{\alpha }{\mathrm{argmin}}{e}^{-\alpha }\sum _{\mathbf{x}:h_t\left(\mathbf{x}\right)=f\left(\mathbf{x}\right)}{\mathcal{D}}_t\left(\mathbf{x}\right)+e^{\alpha }\sum _{\mathbf{x}:h_t\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)}{\mathcal{D}}_t\left(\mathbf{x}\right)\\ & =\underset{\alpha }{\mathrm{argmin}}{e}^{-\alpha }{P}_{\mathbf{x}{\mathcal{D}}_t}\left(h_t\left(\mathbf{x}\right)=f\left(\mathbf{x}\right)\right)+e^{\alpha }{P}_{\mathbf{x}{\mathcal{D}}_t}\left(h_t\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)\right)\\ & \stackrel{\eta =P_{\mathbf{x}{\mathcal{D}}_t}\left(h_t\left(\mathbf{x}\right)\ne f\left(\mathbf{x}\right)\right)}{=}\underset{\alpha }{\mathrm{argmin}}{e}^{-\alpha }\left(1-\eta \right)+e^{\alpha }\eta \end{array}$$

从而

$${\alpha }_t=\frac{1}{2}\ln \frac{1-\eta }{\eta }$$

最终结果采用加权平均法集成输出

Boosting算法要求基学习器能对特定数据分布进行学习，有两种实现方式：

• 带权学习算法：重赋权(re-weighting)——在每次迭代时根据样本分布为每个训练样本重新赋权；
• 无权学习算法：重采样(re-sampling)——在每次迭代时根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。

3 Python实现

3.1 算法流程

基本流程如表所示

3.2 核心代码

核心训练代码如下

def train(self):
    self.base = []
    self.alpha = []
    # 样本权重
    w = np.ones(self.m) / self.m
    data = self.data
    for i in range(self.T):
        # 训练个体学习器
        tree = DT(data)
        tree.generateTree(tree.calGainInfo, layer=1)
        # 计算错误率
        _, res = tree.calPredictAcc(data, tree.tree)
        epi = np.sum(w[np.squeeze(np.argwhere(res==0))])
        if epi > 0.5 or epi == 0:
            break
        # 计算分类器权重
        alpha = 0.5 * np.log((1 - epi) / epi)
        # 更新样本权重
        res[res==0] = -1
        w = w * np.exp(-alpha * res)
        w = w / sum(w)
        # 添加个体学习器
        self.base.append(tree)
        self.alpha.append(alpha)
        # 基于样本权重采样(轮盘赌算法)
        p0 = 0
        cp = []
        for j in range(self.m):
            p0 = p0 + w[j]
            cp.append(p0)
        index = [bisect_left(cp, random.random()) for _ in range(self.m)]
        data = self.data.iloc[index]

3.3 可视化

1个个体学习器的分类情况

3个个体学习器的分类情况

5个个体学习器的分类情况

完整代码通过下方名片联系博主获取

? 更多精彩专栏：

• 《ROS从入门到精通》
• 《Pytorch深度学习实战》
• 《机器学习强基计划》
• 《运动规划实战精讲》
• …