接上一篇文章

AdaBoost-SAMME 算法推导

同算法步骤中的前提条件一样，假设训练集 T = { X_i, y_i }，i = 1，…，N，y 的取值有 M 种可能，h(x) 为估计器，估计器的数量为 K。

为了适应多分类问题，AdaBoost-SAMME 算法将原本为数值的标签 y 转化成一个向量的形式，如式 4-9 所示：

下面用一个例子来说明式 4-9 的含义，假设标签 y 可取 1，2，3，标签集 y = { 2，1，2，3 }，这时根据式 4-9 可以得到对应的转换后的标签集如式 4-10 所示：

同样将算法解释为加法模型，通过多个估计器 h(x) 加权以后得到最后的强估计器 H(x)，代价函数使用指数函数

（1）代价函数，这里比原始算法多了一个 1 / M，是为了后面计算方便，同时 H(X_i) 也是一个向量

（2）带入式 4-1 中的（3）式

（3）同样定义一个 ω，包含前一轮的强估计器等与 α 无关的值

（4）带入 ω 得到代价函数的表达式

（5）目标为找到最优的估计器权重 α 使得代价函数的取值最小

我们先来看代价函数的指数部分，即预测值与标签值的点积。讨论以下两种情况：

当预测值与标签值相同的时候，向量中 1 的位置一致，-1 / (M – 1) 一共有 M – 1 个，得到如下的点积结果：

当预测值与标签值不相同的时候，向量中 1 的位置不一致，-1 / (M – 1) 一共有 M – 2 个，得到如下的点积结果：

结合以上两种情况，得到如下结果：

（1）代价函数 Cost(α)

（2）分两种情况带入式 4-14

（3）增加第二、三两项，不影响最后的结果

（4）将（3）式中前两项和后两项分别合并得到

（1）对代价函数求导数并令其为零

（2）定义错误率 e_k 的表达式

（3）将错误率 e_k 带入（2）式

（4）两边同时乘以 exp(α / (M – 1))

（5）移项后整理得

（6）求得最后的估计器权重 α 的表达式

式 4-16 中估计器权重 α 的表达式前面的常数在进过归一化后对结果没有影响，后面的样本权重更新的公式一样也是简化后的结果。更多详细的算法说明请参考原始论文——Multi-class AdaBoost7

AdaBoost-SAMME.R 算法推导

AdaBoost-SAMME.R 算法是 AdaBoost-SAMME 算法的变体，该算法是使用加权概率估计来更新加法模型，如式 4-17 所示：

代价函数使用的依然是指数函数，不同的是已经没有了估计器权重或者说每一个估计器的权重都为 1，且改成了期望的形式，其中 h(x) 返回的是 M 维的向量，同时为保证求出的 h(x) 唯一，加上了向量的各个元素之和为 0 的限制条件。

成本函数可以拆分为每个类的单独期望，然后相加：

先来看看当 y = 1 时，y * h(x) 的结果：

（1）当 y = 1 时，转换后 y 的向量形式

（2）计算点积的结果

（3）合并最后的项

（4）根据限制条件替换

（5）得到化简后的结果

（1）带入式 4-20

（2）提出与期望无关的项

（3）另后面的期望为 P(y = 1 | x)

（4）同理可以得每一类的期望结果

将上述结果代入代价函数得到：

这时可以使用拉格朗日乘数法来求解上述问题，其拉格朗日函数 L 如下：

拉格朗日函数分别对 h(x) 的各个分量求导数：

两两联立式 4-24 ，分别求出各个分量的结果，下面以第一个为例：

（1）联立导数中的第 1，2 式子

（2）消掉相同的常数项再两边同时取对数

（3）移项化简后得

（1）～（3）同理可得

（4）将（1）～（3）式累加起来根据限制条件化简

（5）将最后一项补充完整

（6）得到第一个分量的结果

同理可得 h(x) 各个分量的结果

样本权重的更新如下，将 h(x) 带入更新方法中，可以看到更新方法只保留了前面一项，因为后面一项为每一类的 p(x) 求和，可以认为是一个常数，归一化以后不影响最后的结果。

这样就得到了算法步骤中的样本权重的更新公式，更多详细的算法说明也请参考原始论文——Multi-class AdaBoost7

五、代码实现

使用 Python 实现 AdaBoost 算法

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class adaboostc():
    """
    AdaBoost 分类算法
    """

    def __init__(self, n_estimators = 100):
        # AdaBoost弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """
        AdaBoost 分类算法拟合
        """
        # 初始化样本权重向量
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 估计器数组
        estimators = []
        # 估计器权重数组
        weights = []
        # 遍历估计器
        for i in range(self.n_estimators):
            # 初始化最大深度为1的决策树估计器
            estimator = DecisionTreeClassifier(max_depth = 1)
            # 按照样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 预测训练集
            y_predict = estimator.predict(X)
            # 计算误差率
            e = np.sum(sample_weights[y_predict != y])
            # 当误差率大于等于0.5时跳出循环
            if e >= 0.5:
                self.n_estimators = i
                break
            # 计算估计器权重
            weight = 0.5 * np.log((1 - e) / e)
            # 计算样本权重
            temp_weights = np.multiply(sample_weights, np.exp(- weight * np.multiply(y, y_predict)))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            weights.append(weight)
            estimators.append(estimator)
        self.weights = weights
        self.estimators = estimators

    def predict(self, X):
        """
        AdaBoost 分类算法预测
        """
        y = np.zeros(X.shape[0])
        # 遍历估计器
        for i in range(self.n_estimators):
            estimator = self.estimators[i]
            weight = self.weights[i]
            # 预测结果
            predicts = estimator.predict(X)
            # 按照估计器的权重累加
            y += weight * predicts
        # 根据权重的正负号返回结果
        return np.sign(y)

使用 Python 实现 AdaBoost-SAMME 算法

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class adaboostmc():
    """
    AdaBoost 多分类SAMME算法
    """

    def __init__(self, n_estimators = 100):
        # AdaBoost弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """
        AdaBoost 多分类SAMME算法拟合
        """
        # 标签分类
        self.classes = np.unique(y)
        # 标签分类数
        self.n_classes = len(self.classes)
        # 初始化样本权重向量
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 估计器数组
        estimators = []
        # 估计器权重数组
        weights = []
        # 遍历估计器
        for i in range(self.n_estimators):
            # 初始化最大深度为1的决策树估计器
            estimator = DecisionTreeClassifier(max_depth = 1)
            # 按照样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 训练集预测结果
            y_predict = estimator.predict(X)
            incorrect = y_predict != y
            # 计算误差率
            e = np.sum(sample_weights[incorrect])
            # 计算估计器权重
            weight = np.log((1 - e) / e) + np.log(self.n_classes - 1)
            # 计算样本权重
            temp_weights = np.multiply(sample_weights, np.exp(weight * incorrect))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            weights.append(weight)
            estimators.append(estimator)
        self.weights = weights
        self.estimators = estimators

    def predict(self, X):
        """
        AdaBoost 多分类SAMME算法预测
        """
        # 加权结果集合
        results = np.zeros((X.shape[0], self.n_classes))
        # 遍历估计器
        for i in range(self.n_estimators):
            estimator = self.estimators[i]
            weight = self.weights[i]
            # 预测结果
            predicts = estimator.predict(X)
            # 遍历标签分类
            for j in range(self.n_classes):
                # 对应标签分类的权重累加
                results[predicts == self.classes[j], j] += weight
        # 取加权最大对应的分类作为最后的结果
        return self.classes.take(np.argmax(results, axis=1), axis=0)

使用 Python 实现 AdaBoost-SAMME.R 算法

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class adaboostmcr():
    """
    AdaBoost 多分类SAMME.R算法
    """

    def __init__(self, n_estimators = 100):
        # AdaBoost弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """
        AdaBoost 多分类SAMME.R算法拟合
        """
        # 标签分类
        self.classes = np.unique(y)
        # 标签分类数
        self.n_classes = len(self.classes)
        # 初始化样本权重
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 估计器数组
        estimators = []
        # 论文中对 y 的定义
        y_codes = np.array([-1. / (self.n_classes - 1), 1.])
        # 将训练集中的标签值转换成论文中的矩阵形式
        y_coding = y_codes.take(self.classes == y[:, np.newaxis])
        # 遍历估计器
        for i in range(self.n_estimators):
            # 初始化最大深度为1的决策树估计器
            estimator = DecisionTreeClassifier(max_depth = 1)
            # 根据样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 预测训练集标签值的概率
            y_predict_proba = estimator.predict_proba(X)
            # 处理概率为0的结果，避免取对数是结果为负无穷大的问题
            np.clip(y_predict_proba, np.finfo(y_predict_proba.dtype).eps, None, out=y_predict_proba)
            # 计算样本权重
            temp_weights = sample_weights * np.exp(- ((self.n_classes - 1) / self.n_classes) * np.sum(np.multiply(y_coding, np.log(y_predict_proba)), axis=1))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            estimators.append(estimator)
        self.estimators = estimators

    def predict(self, X):
        """
        AdaBoost 多分类SAMME.R算法预测
        """
        # 结果集合
        results = np.zeros((X.shape[0], self.n_classes))
        # 遍历估计器
        for i in range(self.n_estimators):
            estimator = self.estimators[i]
            # 预测标签值的概率
            y_predict_proba = estimator.predict_proba(X)
            # 同样需要处理零概率的问题
            np.clip(y_predict_proba, np.finfo(y_predict_proba.dtype).eps, None, out=y_predict_proba)
            # 对概率取对数
            y_predict_proba_log = np.log(y_predict_proba)
            # 计算 h(x)
            h = (self.n_classes - 1) * (y_predict_proba_log - (1 / self.n_classes) * np.sum(y_predict_proba_log, axis=1)[:, np.newaxis])
            # 累加
            results += h
        # 取累加最大对应的分类作为最后的结果
        return self.classes.take(np.argmax(results, axis=1), axis=0)

使用 Python 实现 AdaBoost.R2 算法

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class adaboostr():
    """
    AdaBoost 回归算法
    """

    def __init__(self, n_estimators = 100):
        # AdaBoost弱学习器数量
        self.n_estimators = n_estimators

    def fit(self, X, y):
        """
        AdaBoost 回归算法拟合
        """
        # 初始化样本权重向量
        sample_weights = np.ones(X.shape[0]) / X.shape[0]
        # 估计器数组
        estimators = []
        # 估计器权重数组
        weights = []
        # 遍历估计器
        for i in range(self.n_estimators):
            # 初始化最大深度为3的决策树估计器
            estimator = DecisionTreeRegressor(max_depth = 3)
            # 根据样本权重拟合训练集
            estimator.fit(X, y, sample_weight=sample_weights)
            # 预测结果
            y_predict = estimator.predict(X)
            # 计算误差向量（线性误差）
            errors = np.abs(y_predict - y)
            errors = errors / np.max(errors)
            # 计算误差率
            e = np.sum(np.multiply(errors, sample_weights))
            # 当误差率大于等于0.5时跳出循环
            if e >= 0.5:
                self.n_estimators = i
                break
            # 计算估计器权重
            weight = e / (1 - e)
            # 计算样本权重
            temp_weights = np.multiply(sample_weights, np.power(weight, 1 - errors))
            # 归一化样本权重
            sample_weights = temp_weights / np.sum(temp_weights)
            weights.append(weight)
            estimators.append(estimator)
        self.weights = np.array(weights)
        self.estimators = np.array(estimators)

    def predict(self, X):
        """
        AdaBoost 回归算法预测
        """
        # 论文中权重的定义
        weights = np.log(1 / self.weights)
        # 预测结果矩阵
        predictions = np.array([self.estimators[i].predict(X) for i in range(self.n_estimators)]).T
        # 根据预测结果排序后的下标
        sorted_idx = np.argsort(predictions, axis=1)
        # 根据排序结果依次累加估计器权重，得到新的累积权重矩阵，类似累积分布函数的定义
        weight_cdf = np.cumsum(weights[sorted_idx], axis=1, dtype=np.float64)
        # 累积权重矩阵中大于其中中位数的结果
        median_or_above = weight_cdf >= 0.5 * weight_cdf[:, -1][:, np.newaxis]
        # 中位数结果对应的下标
        median_idx = median_or_above.argmax(axis=1)
        # 对应的估计器
        median_estimators = sorted_idx[np.arange(X.shape[0]), median_idx]
        # 取对应的估计器的预测结果作为最后的结果
        return predictions[np.arange(X.shape[0]), median_estimators]

6.第三方库实现

scikit-learn3实现自适应增强分类

from sklearn.ensemble import AdaBoostClassifier

# 自适应增强分类器 SAMME 算法
clf = AdaBoostClassifier(n_estimators = 50, random_state = 0, algorithm = "SAMME")
# 自适应增强分类器 SAMME.R 算法
clf = AdaBoostClassifier(n_estimators = 50, random_state = 0, algorithm = "SAMME.R")
# 拟合数据集
clf = clf.fit(X, y)

scikit-learn4实现自适应增强回归

from sklearn.ensemble import AdaBoostRegressor

# 自适应增强回归器
clf = AdaBoostRegressor(n_estimators = 50, random_state = 0)
# 拟合数据集
clf = clf.fit(X, y)

七、实例演示

图 7-1 展示了使用自适应增强算法进行二分类的结果，红色表示标签值为 -1 的样本点，蓝色代表标签值为 1 的样本点。浅红色的区域为预测值为 -1 的部分，浅蓝色的区域则为预测值为 1 的部分

图 7-2 、图 7-3 分别展示了使用 SAMME 和 SAMME.R 算法进行多分类的结果，红色表示标签值为 0 的样本点，蓝色代表标签值为 1 的样本点，绿色代表标签值为 2 的样本点。浅红色的区域为预测值为 0 的部分，浅蓝色的区域则为预测值为 1 的部分，浅绿色的区域则为预测值为 1 的部分

图 7-4 展示了使用自适应增强算法进行回归的结果

八、思维导图

9. 参考文献

1. https://en.wikipedia.org/wiki/Boosting_(machine_learning)
   
2. https://en.wikipedia.org/wiki/AdaBoost
   
3. https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html
   
4. https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostRegressor.html
   
5. https://www.face-rec.org/algorithms/Boosting-Ensemble/decision-theoretic_generalization.pdf
   
6. https://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.21.5683&rep=rep1&type=pdf
   
7. https://hastie.su.domains/Papers/samme.pdf
   

如需完整演示，请单击此处

注：本文力求准确、通俗易懂，但由于作者也是初学者，水平有限，文中如有错误或遗漏，恳请读者批评指正，留言指正

本文首发于——AI导图，欢迎关注