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論文）