第8.13节 MultiAdaBoost原理与实现
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
8.13 MultiAdaBoost原理与实现 8.13.1 算法思想 8.13.2 算法原理 8.13.3 从零实现SAMME算法 8.13.4 SAMME损失函数 8.13.5 SAMME求解 8.13.6 小结 引用
8.13 MultiAdaBoost原理与实现
在第8.12节内容中，笔者详细介绍了AdaBoost算法的思想原理和实现过程，算是对于AdaBoost算法框架有了一个基本的认识。根据AdaBoost算法的原理可知，其最初主要是被用于二分类任务中[1]，因此它并不能很好地处理多分类问题。
8.13.1 算法思想
根据AdaBoost算法中分类器权重的计算公式(8.87)可以得到模型误差与模型权重之间的函数关系，如图8-52所示。
从图8-52可以看出，当模型误差大于0.5时，模型权重将会小于0，而根据式(8.88)可知此时将会乘以一个小于1的数，从而使得朝着错误的方向（变小）进行更新，这显然与Adaboost的思想相违背（越容易分错的样本点对应的样本权重越大）。
由于在二分类场景下，我们总能相对容易地找到误差小于0.5（可以近似的看成准确率）的模型，但是随着分类数量的增加初始时模型的误差很难再小于0.5，而这将导致被上一个模型分类错误的样本在下一个模型中同样得不到修正。
如图8-53所示为AdaBoost模型在某个三分类数据集上（训练集和测试集随机划分10次）训练后在测试集上的平均结果。从图2左侧的结果可知，AdaBoost在迭代伊始测试误差便大于0.5，且随着迭代次数的增加最终稳定在0.53左右，也就是说随着迭代过程的增加模型的拟合能力并没有提升。根据图2中间的结果可知，模型误差先是小于0.5，然后在若干次迭代之后便稳定在了0.5附近，而这也导致模型权重从一开始的大于0到在若干次迭代后便一直处于0附近，如图8-53右所示。根据式(8.88)可知，当时，将会保持不变，进而使得被错分类的样本点得不到修正。
基于原始AdaBoost算法所存在的问题，Hastie等人[1]在2009年提出了一种基于AdaBoost改进的多分类AdaBoost算法——基于指数损失函数的多分类分步加法模型（ Stagewise Additive Modeling using a Multi-class Exponential loss function, SAMME）。
8.13.2 算法原理
SAMME算法的思想和整体框架同AdaBoost一样，仅仅只是用了一种特殊的形式来表示每个模型的预测输出，并最终得到了在多分类场景下AdaBoost的更新迭代公式，具体的详细求解过程将在后续进行介绍。
假设为个弱分类器，数据集一共有个样本，则SAMME算法可以通过如下过程来进行表示：
(1) 初始化每个样本的权重为；
(2) 根据式(8.108)~式(8.110)分别计算每个分类器对应下的分类器误差，分类器权重和样本权重及标准化
其中表示标签对应的类别编号；表示分类的类别数。
(3) 将训练得到的个弱分类器根据式(8.111)中的方式进行集成，然后输出得到样本的预测结果：
其中为指示函数，条件成立是取1，不成立时取0。
从上述过程可以看出，SAMME算法与之前的二分类AdaBoost算法的唯一差别就是体现在公式(8.109)上，前者多了这一项。进一步，根据式(8.109)可知，为了使得，则必须有
同时，可以发现当时，上述求解过程便完全等价于AdaBoost算法了。
8.13.3 从零实现SAMME算法
由于SAMME算法的求解推导过程稍显复杂，且目前已经知道了整个算法的求解过程，所以下面笔者先来介绍如何从零实现SAMME算法，然后再介绍整个求解推导过程。同时，在sklearn中只需要在实例化AdaBoostClassifier类时将 algorithm参数指定为'SAMME'即可使用SAMME算法，这里就不再重复进行示例，参考第8.12.3节内容即可。
根据第8.13.2节内容中的求解过程可知，SAMME算法同样并不是某种特定算法的称谓，而是一种模型训练和预测的策略。因此下面将以前面介绍的多项式朴素贝叶斯（MultinomialBN）算法作为弱分类器进行实现。
1. 带权重的朴素贝叶斯
根据第8.12节介绍的内容可知，AdaBoost算法会为每个样本赋予一个权重值，在上一个模型中被错分的样本在下一个模型中将具有更高的权重，以此来尽可能保证每个样本都能够被划分正确。因此，对于每个弱分类器来说还需要在原有算法基础之上实现样本权重对分类结果的影响，而这也是为什么sklear框架中基本上每个算法都有sample_weight这个参数的缘故（默认情况下其取值为None，即不考虑样本权重，也可以理解为等权重）。
同时，对于每个算法模型来说都有不同的策略来考虑如何将样本权重融入到模型中，即每个算法在加入样本权重后的实现方式不同。下面，以最简单的多项式朴素贝叶斯算法为例来进行介绍整体的思想原理。
根据第7章对朴素贝叶斯算法原理的介绍可知，贝叶斯算法在求解过程中的一个关键因素就是计算得到每个样本可能属于某个类别的先验概率，即。在贝叶斯算法中，可以通过最大似然估计，即训练集中每个类别下对应样本的数量在总样本数中的占比来求得相应的先验概率。因此，基于类似的想法我们还可以人工经验来调整相应的先验概率，即根据重要性人为地赋予每个样本一个权重值，并最终作用于先验概率。
例如现有某三分类数据集的标签为y=[0,1,1,2,2]，其对应每个样本的权重为sample_weight=[0.1,0.1,0.3,0.4,0.1]，则此时有：
不考虑样本权重时每个类别的先验概率为：
考虑样本权重时每个类别的先验概率为：
首先需要将原始标签转换为One-hot编码形式，即Y=[[1,0,0],[0,1,0],[0,1,0],[0,0,1],[0,0,1]]，然后再以按位乘的方式计算其与sample_weight的乘积，结果为[[0.1,0,0],[0,0.1,0],[0,0.3,0],[0,0,0.4],[0,0,0.1]]，进一步对该结果在列上进行求和可得[0.1,0.4,0.5]，最后每个类别的先验概率为
最后，上述过程可以通过如下代码来进行实现
1 def compute_class_prior(y, sample_weight=None):
2 labelbin = LabelBinarizer()
3 Y = labelbin.fit_transform(y)
4 if sample_weight is not None:
5 Y = Y.astype(np.float64, copy=False)
6 sample_weight = np.reshape(sample_weight, [1, -1]) # [1,n_samples]
7 Y *= sample_weight.T # [n_samples,n_classes_] * [n_samples,1] 按位乘
8 class_count = Y.sum(axis=0) # Y: shape(n,n_classes) Y.sum(): shape(n_classes,)
9 class_prior = class_count / class_count.sum()
10 return class_prior
在上述代码中，第2-3行将标签转化为one-hot形式；第4-7行则是根据sample_weight重新调整标签矩阵Y；第8-9行则是计算每个类别的先验概率。完整代码可参见Book/Chapter08/C19_bayes_class_prior.py文件。
2. 定义初始化方法
在完成考虑样本权重的多项式朴素贝叶斯后，接下来便可以一步一步实现整个SAMME算法。首先，根据需要定义一个名为MyAdaBoostClassifier的类，并定义其对应的初始化方法，代码如下：
1 class MyAdaBoostClassifier():
2 def __init__(self,base_estimator=None,
3 n_estimators=50,
4 algorithm='SAMME'):
5 self.algorithm = algorithm
6 self.n_estimators = n_estimators
7 self.base_estimator = base_estimator
8 self.estimators_ = []
9 self.estimator_weights_ = np.zeros(self.n_estimators, dtype=np.float64)
10 self.estimator_errors_ = np.zeros(self.n_estimators, dtype=np.float64)
在上述代码中，第5-7行中base_estimator表示指定相应的弱分类器，n_estimators表示弱分类器的数量；algorithm表示指定相应的Boost算法；第8行定义一个列表用于后续保存所有的弱分类器；第9行定义一个向量用于后续保存每个模型对应的权重；第10行用于后续保存每个模型拟合后对应的误差。
3. SAMME计算过程实现
接着，根据式(8.108)~式(8.110)来实现SAMME算法的整体计算过程，实现代码如下所示：
1 def _single_boost_samme(self, iboost, X, y, sample_weight):
2 estimator = deepcopy(self.base_estimator) # 克隆一个分类器
3 self.estimators_.append(estimator) # 保存每个分类器
4 estimator.fit(X, y, sample_weight=sample_weight)
5 y_predict = estimator.predict(X)
6 if iboost == 0:
7 self.classes_ = getattr(estimator, 'classes_', None)
8 self.n_classes_ = len(self.classes_)
9 incorrect = y_predict != y
10 estimator_error = np.average(incorrect, weights=sample_weight, axis=0)
11 if estimator_error >= 1. - (1. / self.n_classes_):
12 self.estimators_.pop(-1)
13 if len(self.estimators_) == 0:
14 raise ValueError('BaseClassifier in AdaBoostClassifier '
15 'ensemble is worse than random, ensemble '
16 'can not be fit.')
17 return None, None, None
18 estimator_weight = np.log((1. - estimator_error) /
19 estimator_error) + np.log(self.n_classes_ - 1.)
20 sample_weight *= np.exp(estimator_weight * incorrect)
21 return sample_weight, estimator_weight, estimator_error
22
23 def _boost(self, iboost, X, y, sample_weight):
24 if self.algorithm == 'SAMME':
25 return self._single_boost_samme(iboost, X, y, sample_weight)
在上述代码中，第1行里iboost表示对第iboost个弱分类器进行拟合，X,y表示训练集，sample_weight表示当前状态下的样本权重；第2~5行分别是先克隆一个新的弱分类器，然后进行保存，进一步根据训练集对其进行拟合，最后让该弱分类器对训练集中的样本进行预测；第6~8行是用来获取训练集中样本的类别和类别数；第9~10行则是实现式(8.108)对应的计算过程；第11~17行则是判断当前分类器的误差不满足式(8.112)中的条件时的处理流程；第18-20行则是分别实现式(8.109)和式(8.110)中样本权重的计算过程；第23~25行则是对不同的Boost算法进行整合，例如还SAMME.R等算法。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！
4. SAMME算法拟合过程实现
在完成SAMME算法的单步拟合过程后便可以进一步完成整个模型的训练过程，实现代码如下所示：