摘要

1。 AdaBoost元演算法

2。 AdaBoost元演算法誤差分析

3。 程式碼實現與解釋

AdaBoost演算法

AdaBoost演算法是整合學習的一種。

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

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

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

T=\left\{ (x_{1},y_{1}), (x_{2},y_{2}),... (x_{N},y_{N})\right\}

其中

x\in R^{n}

，

y\in \left\{ -1,+1 \right\}

。

初始化樣本的權重為：

D_{1}=\left\{ w_{11},w_{12},...w_{1N} \right\},w_{1i}=\frac{1}{N}

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

D_{m}=\left\{ w_{m1},w_{m2},...w_{mN} \right\}，\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)\ne y_i)}=\sum_{i=1}^{N}{w_{mi}I(G_m(x_i) \ne y_i)}

也就是說

G_m(x)

在加權訓練資料集中的分類誤差率為被誤分類的樣本權值之和。注意一下，我們定義的基學習器，其

e_m<0.5

。。

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

L(y,f(x))=E_{x\sim D}\left[ exp(-yf(x)) \right]

其中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}ln\frac{P(y=1|x)}{P(y=-1|x)}

因此，有

sign(f(x))=sign(\frac{1}{2}ln\frac{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_{x\sim D_m}\left[ {exp(-y\alpha_mG_m(x))} \right]

=E_{x\sim D_m}\left[ \sum_{y_i=G_m(x_i)}{e^{-\alpha_m}}+\sum_{y_i\ne G_m(x_i)}{e^{\alpha_m}} \right]

=e^{-\alpha_m}P(y_i=G_m(x_i))+e^{\alpha_m}P(y_i\ne 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)=argmin\sum_{i=1}^{N}{{w}_{mi}I(y_i\ne 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))}{\alpha\alpha_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)\ne 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)\ne 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

，

“

\n

”

）

# 如果分類錯誤率為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

（

‘

\t

’

））

dataMat

=

［］；

labelMat

=

［］

fr

=

open

（

fileName

）

for

line

in

fr

。

readlines

（）：

lineArr

=

［］

curLine

=

line

。

strip

（）

。

split

（

‘

\t

’

）

# 對每一個特徵

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實現，這是機器學習主流語言，本人也會盡力對程式碼做出較為詳盡的註釋。