adaboost----从基于加法模型的前向分步算法推导出adaboost

目录

一 加法模型

1 什么是加法模型

2 存在弊端

二 前向分步算法

1 什么前向分步算法

2 学习加法模型的前向分步算法步骤如下：

三 adaboost

1 定理：

2 解析：

3 证明：

   (1)基函数

   (2)损失函数

四 代码实现

五 总结

一 加法模型

1 什么是加法模型

加法模型(additive model)又叫可加模型,

具体细化到生活中的实例，就比方说你在建一座跨海大桥，需要设计方案，不同的人对此有不同的思路，桥梁专家对于桥梁建设有方案，材料专家对于建桥的材料有思路，海洋专家对于大桥下面的海洋水流有建议，综合不同人的思路及建议，完整的整理相加出一套解决方案。

加法模型的数学抽象（公式）：

其中各个参数的含义：

指的是基函数（可以理解为此人对于建桥的意见，例如材料专家给出要使用钢筋混凝土浇筑）

基函数参数（可以理解为此人的特点，例如是桥梁专家，或者是水利专家）

基函数系数（此人的重要性，例如在建桥中，首先要服从桥梁专家，气候专家的意见权重就要小一些）

x指的就是这个问题（建桥问题）

在给定训练数据和损失函数的L(y,f(x))的条件下，学习加法模型f(x)损失函数最小化

这是一个复杂的优化问题。

2 存在弊端

   计算困难，所以采用前向分布算法来逐步计算参数，每一步只学习一个基函数及其系数，逐步逼近优化目标函数。简化优化的复杂度。

二 前向分步算法

1 什么前向分步算法

前向分步算法是简化复杂优化问题的一种方法。因为学习的是加法模型，所以能够从前向后，一步一步学习，每一步只学习一个基函数和它的系数，逐步逼近复杂的优化问题的目标函数。每步只需要优化所有样本的损失函数就可以了：

2 学习加法模型的前向分步算法步骤如下：

输入：

基函数集{b(x;γ)}

输出：加法模型f(x)

(1)初始化f0(x)=0

(2)对m=1，2，3，4……M

          a 极小化损失函数

得到参数

           b 更新 

 (3)得到加法模型

这样，前向分步算法将同时求解从m=1到M的所有βm与γm的优化问题简化为逐个求解各个βm与γm的优化问题了。

三 adaboost

由前向分步算法可以推导出adaboost。

1 定理：

       adaboost算法是前向分步加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。

2 解析：

adaboost与前向分步算法的关系就像java中对象与类的关系一样。类是对象的抽象，而对象是类的具体实例。说adaboost是特例是因为它明确了加法模型的组成是基本分类器，明确了损失函数为指数函数。

3 证明：

   (1)基函数

 前向分步算法学习的是加法模型，当基函数为基本分类器是，加法模型等价于adaboost的最终分类器

。

它是由基本分类器Gm(x)及其系数αm组成的(m = 1,2,……M)。前向分步算法逐一学习基函数，这一过程与adaboost算法逐一学习基本分类器的过程一致。

   (2)损失函数

下面证明：当前向分步算法的损失函数是指数函数(

)时，它学习的具体操作等价于adaboost算法学习的具体操作:

 假设经过m-1轮迭代前向分步算法已经得到fm-1(x)：

在m轮迭代得到αm，Gm(x)和fm(x)。

。目标是使前向分步算法得到的αm和Gm(x)使fm(x)在训练数据集T上的指数损失最小。用公式表示为：把

带入指数损失函数

得到

--------------------（公式一）

假设

上面的式子可以表示为

---------------（公式二）

因为

既不依赖α也不依赖于G，所以与最小化无关，但是依赖于fm-1(x)，随着每一轮迭代而发生变化。

现在证明使得上面的公式一达到最小

就是adaboost算法所得的am与Gm(x)。

1)求

对任意的α>0,使得公式公式二最小的G(x)有下面得到

2)求

-------------（公式三）

对于迭代的第m步，假设β为常数，那么公式的右边以及

都可以看成常数，则要让损失函数取得最小值，只需要让

取最小值。因此有

那么βm怎么求得呢？现在假设Gm已知的情况下，回到公式(3)。此时的变量为β，要让损失函数取得最小值，先对β求偏导

这与adaboost算法的样本权重更新只差规范化因子，因而等价。到这里也就推导出了当前向分步算法的损失函数选为指数损失的时候，前向分步算法也就是AdaBoost。

四 代码实现

# -*- coding: utf-8 -*-
# @File  : 
# @Author: zhangyingjie
# @Date  : 
# @Desc  :
from numpy import *

def stumpClassify(dataMat, dimen, threshVal, threshIneq):  # 数据集，第几个特征，分割值，lt/gt
    " 分割值左侧为负类或者右侧为负类 "
    retArray = ones([shape(dataMat)[0], 1])  # 定义一个都为1的数组，根据条件更新满足条件的值为-1
    if threshIneq == 'lt':
        retArray[dataMat[:, dimen] <= threshVal] = -1.0  # 将数据集中小于等于分割值的划分为-1
    else:
        retArray[dataMat[:, dimen] > threshVal] = -1.0  # 将数据集中大于分割值的划分为-1
    return retArray


def buildStump(dataSet, labels, D):
    "构建决策树桩"
    dataMat = mat(dataSet)
    classLabels = mat(labels).T
    m, n = shape(dataMat)
    numStep = 10.0
    bestStump = {}
    bestClassEst = mat(zeros([m, 1]))
    minErr = inf

    for i in range(n):  # 循环特征
        rangeMin = dataMat[:, i].min()  # 当前特征值中最小的值
        rangeMax = dataMat[:, i].max()  # 当前特征值中最大的值
        threshStep = (rangeMax - rangeMin) / float(numStep)  # 步伐=（最大值-最小值)/比较次数
        # minErr=inf 之前放在此处造成了错误
        weightedErr = 0.0
        for j in range(-1, int(numStep) + 1):  # 循环当前特征的分割值
            threshVal = rangeMin + j * threshStep   # 计算分割值=最小值 + 第几次比较 * 步伐
            for ineq in ['lt', 'gt']:  # 分别处理小于等于分割值和大于分割值的情况
                errArr = mat(ones([m, 1]))
                predictVal = stumpClassify(dataMat, i, threshVal, ineq)
                errArr[predictVal == classLabels] = 0  # 被正确分类的值为0，被错误分类的值不变(1)，
                weightedErr = float((mat(D).T * mat(errArr)))  # 分类误差率=权重*被错误分类个数

                print("第(%d)个特征，当前特征第(%d)次分割，分割值为(%f)，(%s)分类误差率 =(%f)" % (i, j, threshVal, ineq, weightedErr))
                
                if (weightedErr < minErr):
                    print("错误分割率为(%2f)" % (weightedErr))
                    minErr = weightedErr
                    bestStump['thresh'] = threshVal  # 分割值
                    bestStump['dim'] = i   # 第几个特征
                    bestStump['ineq'] = ineq  # 左侧为负类还是右侧为负类
                    bestClasEst = predictVal.copy()  # 最好的分割结果
                else: pass
    return bestStump, minErr, bestClasEst


def loadSimpData():
    # ' 加载数据 '
    datMat = matrix([[1., 2.1], [2., 1.1], [1.3, 1.], [1., 1.], [2., 1.]])
    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat, classLabels


def adaBoostTrainDS(dataArr, classLabels, numIter=40):
    m, n = shape(dataArr)
    D = mat(ones([m, 1])/m)
    print(D)
    weakClassEst = []
    aggErrRate = 0.0
    aggClassEst = mat(zeros([m, 1]))
    for i in range(numIter):
        aggErr = zeros([m, 1])
        bestStump, err, bestClassEst = buildStump(dataArr, classLabels, D)
        alpha = float(log((1.0-err)/max(float(err), 1e-16))/2.0)  # 基本分类器系数
        bestStump['alpha'] = alpha
        weakClassEst.append(bestStump)
        expon = multiply(-1.0 * alpha * mat(classLabels).T, bestClassEst)   # 计算公式中-αm*yi*Gm(xi) 即e的指数exponential

        D = multiply(D, exp(expon))  # 计算权值分布公式中的分子
        D = D/D.sum()                # 除以权值分布公式中的分母，归一化处理

        aggClassEst += alpha * bestClassEst   # 累加基本分类器

        aggErr = multiply(sign(aggClassEst) != mat(classLabels).T, ones([m, 1]))  # 预测值与真实值不相等为1，相等为0
        aggErrRate = aggErr.sum()/m  # 误差率

        if aggErrRate == 0: break

    print('total Error:', aggErrRate)
    return weakClassEst

if __name__ == '__main__':

    dataArr, classLabels = loadSimpData()
    classifierArray = adaBoostTrainDS(dataArr, classLabels, 9)
    print(classifierArray)
           

输出结果：

[{'thresh': 1.3, 'dim': 0, 'ineq': 'lt', 'alpha': 0.6931471805599453}, {'thresh': 1.0, 'dim': 1, 'ineq': 'lt', 'alpha': 0.9729550745276565}, {'thresh': 0.9, 'dim': 0, 'ineq': 'lt', 'alpha': 0.8958797346140273}]

五 总结

由前向分布算法可以推导出adaboost，adaboost算法是前向分步加法算法的特例。

参考资料：

         集成学习系列(三)-AdaBoost训练误差分析（把推导过程写的很明白，特别好）

         从前向分步算法推导出AdaBoost（太棒了，特别详细）  

         第三篇--加法模型与提升方法boost

         adaboost算法

         广义可加模型与经典线性回归模型的比较研究（百度网盘存储pdf论文）