《機器學習實戰》學習總結（八）——Adaboost演算法

04-27

摘要

1. AdaBoost元演算法

2. AdaBoost元演算法誤差分析

3. 代碼實現與解釋

AdaBoost演算法

AdaBoost演算法是集成學習的一種。

集成學習就是構建多個「基學習器」，之後再將它們結合來完成學習任務的方法。集成學習通過將多個學習器進行綜合，其性能通常比單個學習器要好。我們之前提過的隨機森林就是集成學習的一種。

Adaboost演算法：先從初始訓練集合中訓練出一個基學習器，再根據基學習器的表現對訓練樣本的權重進行調整，使得先前基學習器做錯的樣本在後續得到更多的關注，然後基於調整後的樣本權重來訓練下一個基學習器，直到基學習器的數目達到事先指定的數目M，最終將這M個學習器進行加權組合。

首先我們假設給定一個二分類的訓練數據集：

$T=left{ (x_{1},y_{1}), (x_{2},y_{2}),... (x_{N},y_{N}) ight}$

其中 $xin R^{n}$ , $yin left{ -1,+1 ight}$ 。

初始化樣本的權重為：

$D_{1}=left{ w_{11},w_{12},...w_{1N} ight},w_{1i}=frac{1}{N}$

第m個基分類器的樣本權重為：

$D_{m}=left{ w_{m1},w_{m2},...w_{mN} ight}，sum_{i=1}^{N}{w_{mi}=1}$

我們構建M個基學習器，最終的學習器即為基學習器的線性組合：

$f(x)=sum_{i=1}^{M}{alpha_{i}G_{i}(x)}$

其中 $alpha_{i}$ 為第i個基學習器的係數， $G_{i}(x)$ 為第i個基學習器。

接下來我們定義 $G_m(x)$ 在訓練集合中的分類誤差率為：

$e_m=sum_{i=1}^{N}{P(G_m(x_i) e y_i)}=sum_{i=1}^{N}{w_{mi}I(G_m(x_i) e y_i)}$

也就是說 $G_m(x)$ 在加權訓練數據集中的分類誤差率為被誤分類的樣本權值之和。注意一下，我們定義的基學習器，其 $e_m<0.5$ 。.

接著我們定義損失函數為指數損失函數：

$L(y,f(x))=E_{xsim D}left[ exp(-yf(x)) ight]$

其中y是樣本的實際類別，f(x)是預測的類別，樣本x的權重服從D分布。E代表求期望。

損失函數為什麼這樣定義？下面一起證明一下：

若f(x)能使損失函數最小化，那我們考慮上式對f(x)的偏導為零：

$frac{alpha L(y,f(x))}{alpha f(x)}=-e^{-f(x)}P(y=1|x)+e^{f(x)}P(y=-1|x)$

令上式為零，得：

$f(x)=frac{1}{2}lnfrac{P(y=1|x)}{P(y=-1|x)}$

因此，有

$sign(f(x))=sign(frac{1}{2}lnfrac{P(y=1|x)}{P(y=-1|x)})$

當P(y=1|x)>P(y=-1|x)時，sign(f(x))=1

當P(y=1|x)>P(y=-1|x)時，sign(f(x))=-1

這樣的分類規則正是我們所需要的，若指數函數最小化，則分類錯誤率也最小，它們倆是一致的。所以我們的損失函數可以這樣定義。

定義完了損失函數，我們看怎麼來進行基分類器 $G_m(x)$ 和係數 $alpha_{i}$ 的求取。

第一個分類器G1(x)是直接將基學習演算法用於初始數據分布求得，之後不斷迭代，生成 $alpha_m$ 和 $G_m$ 。當第m個基分類器產生後,我們應該使得其在數據集第m輪樣本權重基礎上的指數損失最小，即

$L(alpha_m,G_m(x))=argmin$ $E_{xsim D_m}left[ {exp(-yalpha_mG_m(x))} ight]$

$=E_{xsim D_m}left[ sum_{y_i=G_m(x_i)}{e^{-alpha_m}}+sum_{y_i e G_m(x_i)}{e^{alpha_m}} ight]$

$=e^{-alpha_m}P(y_i=G_m(x_i))+e^{alpha_m}P(y_i e G_m(x_i))$

$=e^{-alpha_m}(1-e_m)+e^{alpha_m}e_m$

首先，我們求解 $G_m(x)$ ,對任意的 $alpha>0$ ,最優的 $G_m(x)$ 應為：

$G_{m}(x)=argminsum_{i=1}^{N}{{w}_{mi}I(y_i e G_m(x_i))}$

其中 $w_{mi}$ 是第m輪訓練樣本的權重。 $G_m(x)$ 就是在第m輪中使得加權訓練樣本誤差率最小的分類器。

在得到 $G_m(x)$ 後，我們來求 $alpha_m$ 。 $alpha_m$ 應該使得損失函數最小，所以令下式對 $alpha_m$ 求導等於零：

$frac{alpha L(alpha_m,G_m(x))}{alphaalpha_m}=-e^{-alpha_{m}}(1-e_m)+e^{alpha_{m}}e_m=0$

得到 $alpha_m$ 的表達式：

$alpha_m=frac{1}{2}ln(frac{1-e_m}{e_m})$

由於 $e_m<0.5$ ，所以 $alpha_m>0$ ,且 $alpha_m$ 隨著 $e_m$ 的減小而增大。

這時候我們就可以得到Adaboost的迭代公式：

$f_{m}(x)=f_{m-1}(x)+alpha_{m}G_{m}(x)$

這時候就只剩下最後一個問題，之前說，我們會根據基學習器的表現對訓練樣本的權重進行調整，使得先前基學習器做錯的樣本在後續得到更多的關注。那訓練樣本的權重分布 $D_m$ 應該怎麼變化呢?

這一部分在周志華老師《機器學習》P175有詳細的推導，感興趣的讀者可以自行查閱。我這裡直接給出 $D_m$ 的迭代公式，並證明其可行性。

$D_{m}=(w_{m,1},w_{m,2},...w_{m,N})$

$D_{m+1}=(w_{m+1,1},w_{m+1,2},...w_{m+1,N})$

$w_{m+1,i}=frac{w_{mi}exp(-alpha_my_iG_m(x_i))}{Z_m}$

其中 $Z_m=sum_{i=1}^{N}{w_{mi}exp(-alpha_my_iG_m(x_i))}$ ，是一個常數。

上面就是樣本權重 $D_m$ 的迭代公式。我們發現：

當 $G_m(x_i)= y_i$ 時：

$w_{m+1,i}=frac{w_{mi}}{Z_m}e^{-alpha_m}$

當 $G_m(x_i) e y_i$ 時：

$w_{m+1,i}=frac{w_{mi}}{Z_m}e^{alpha_m}$

由於 $alpha_m>0$ ，從上面的式子可以看到，當樣本i上一次被誤分類時，其下一次的權重 $w_{m+1,i}$ 會變大；而當樣本i上一次被分類正確時，其下一次的權重 $w_{m+1,i}$ 會變小。因此，誤分類樣本在下一輪學習中起到的作用更大，這也是Adaboost的一個特點。

以上就是Adaboost演算法原理部分的全部內容，從基學習器到其係數，再到數據集合的權重迭代，我們都給出了較為詳細的公式推導。希望給大家一些幫助。

Adaboost演算法的誤差

先給大家結論：隨著集成學習中個體分類器數目的增加，其集成的錯誤率將成指數級下降，最終趨向於零。

當然，如果分類器數目過多也會發生過擬合現象，導致分類器的泛化能力不強，所以我們應該在其中尋求一種平衡。

關於演算法誤差這個點，李航老師《統計學習方法》P142和周志華老師《機器學習》P172頁都有解釋。李航老師的證明更為詳細。周志華老師的證明用到了Hoeffding不等式。

最終得到的不等式：

$P(f(x) e y)=sum_{k=0}^{N/2向下取整}{C_N^{k}(1-e)^k(e)^{N-k}}leq exp(-frac{1}{2}N(1-2e)^2)$

我們發現，隨著個體分類器數目的增加，其集成的錯誤率將成指數級下降。當然前提條件是每個基分類器的分類正確率要高於50%，即 $e_i<0.5$ .

代碼實現與注釋

在下面的程序中，基分類器選用的是決策樹，但是基分類器可以選取我們所知道的任意一個分類器都可以，比如神經網路等。

1.單層決策樹生成函數

程序清單：

from numpy import *# 載入數據def loadsimpData(): dataMat=matrix([[1,2.1], [2,1.1], [1.3,1], [1,1], [2,1]]) classLabels=[1,1,-1,-1,1] return dataMat,classLabels# 單層決策樹生成函數# dimen是哪一個特徵；threshVal是特徵閾值；threshIneq是大於還是小於def stumpClassify(dataMatrix,dimen,threshVal,threshIneq): # 初始化一個全1列表 retArray=ones((shape(dataMatrix)[0],1)) if(threshIneq==lt): # 以閾值劃分後，小於等於閾值的，類別定為-1 retArray[dataMatrix[:,dimen]<=threshVal]=-1.0 else: retArray[dataMatrix[:,dimen]>threshVal]=-1.0 return retArray# D是權重向量def buildStump(dataArr,classLabels,D): dataMatrix=mat(dataArr);labelMat=mat(classLabels).T m,n=shape(dataMatrix) numSteps=10.0;bestStump={};bestClassEst=mat(zeros((m,1))) # 最小值初始化為無窮大 minError=inf # 對每一個特徵 for i in range(n): # 找到最大值和最小值 rangeMin=dataMatrix[:,i].min() rangeMax=dataMatrix[:,i].max() # 確定步長 stepSize=(rangeMax-rangeMin)/numSteps for j in range(-1,int(numSteps)+1): for inequal in [lt,gt]: # 得到閾值 threshVal=(rangeMin+float(j)*stepSize) # 調用函數，並得到分類列表 predictedVals=stumpClassify(dataMatrix,i,threshVal,inequal) # 初始化errArr errArr=mat(ones((m,1))) # 將errArr中分類正確的置為0 errArr[predictedVals==labelMat]=0 # 計算加權錯誤率 weightedError=D.T*errArr # print("split:dim %d,thresh %.2f,thresh inequal:" # "%s,the weighted error is %.3f"%(i,threshVal, inequal,weightedError)) # 如果錯誤率比之前的小 if(weightedError<minError): minError=weightedError # bestClassEst中是錯誤最小的分類類別 bestClassEst=predictedVals.copy() bestStump[dim]=i bestStump[thresh]=threshVal bestStump[ineq]=inequal return bestStump,minError,bestClassEst

2.基於單層決策樹的Adaboost訓練過程

程序清單：

# 基於單層決策樹的Adaboost訓練過程# numIt表示最多迭代的次數def adaBoostTrainDS(dataArr,classLabels,numIt=40): weakClassArr=[] m=shape(dataArr)[0] # 初始化權重矩陣D,1/m D=mat(ones((m,1))/m) # 初始化，aggClassEst裡面存放的是類別估計的累計值 aggClassEst=mat(zeros((m,1))) for i in range(numIt): bestStump,error,classEst=buildStump(dataArr,classLabels,D) print("D:",D.T) # 計算分類器的係數；max（）的作用是防止error=0 alpha=float(0.5*log((1.0-error)/max(error,1e-16))) bestStump[alpha]=alpha weakClassArr.append(bestStump) print("classEst:",classEst.T) # 下面三行是對權重向量進行更新，具體公式推導見正文 expon=multiply(-1*alpha*mat(classLabels).T,classEst) D=multiply(D,exp(expon)) D=D/D.sum() # 計算類別估計的累加值 aggClassEst+=alpha*classEst print(aggClassEst:,aggClassEst.T) # 計算分類錯誤的個數 aggErrors=multiply(sign(aggClassEst)!=mat(classLabels).T, ones((m,1))) # 計算分類錯誤率 errorRate=aggErrors.sum()/m print("total error:",errorRate," ") # 如果分類錯誤率為0，則結束 if(errorRate==0):break # 返回建立的分類器列表 return weakClassArr

3.Adaboost分類函數

程序清單：

# adaBoost分類函數# datToClass是待分類數據；classifierArr是建立好的分類器列表def adaClassify(datToClass,classifierArr): dataMatrix=mat(datToClass) m=shape(dataMatrix)[0] aggClassEst=mat(zeros((m,1))) # 對每一個弱分類器 for i in range(len(classifierArr)): # 得到分類類別 classEst=stumpClassify(dataMatrix,classifierArr[i][dim], classifierArr[i][thresh], classifierArr[i][ineq]) # 計算類別估計累加值 aggClassEst+=classifierArr[i][alpha]*classEst print(aggClassEst) # 返回類別；sign(x)函數：x>0返回1；x<0返回-1；x=0返回0 return sign(aggClassEst)# 自適應數據載入函數def loadDataSet(fileName): # 得到特徵數目 numFeat=len(open(fileName).readline().split( )) dataMat=[];labelMat=[] fr=open(fileName) for line in fr.readlines(): lineArr=[] curLine=line.strip().split( ) # 對每一個特徵 for i in range(numFeat-1): lineArr.append(float(curLine[i])) dataMat.append(lineArr) labelMat.append(float(curLine[-1])) # 返回特徵矩陣和類別矩陣 return dataMat,labelMat

以上就是Adaboost演算法的全部內容，下一節我們一起學習線性回歸、局部加權線性回歸和收縮方法。

聲明

最後，所有資料均本人自學整理所得，如有錯誤，歡迎指正，有什麼建議也歡迎交流，讓我們共同進步！轉載請註明作者與出處。

以上原理部分主要來自於《機器學習》—周志華，《統計學習方法》—李航，《機器學習實戰》—Peter Harrington。代碼部分主要來自於《機器學習實戰》，代碼用Python3實現，這是機器學習主流語言，本人也會儘力對代碼做出較為詳盡的注釋。