AdaBoost算法相關(guān)理論和算法介紹

作者簡(jiǎn)介

張磊：從事AI醫(yī)療算法相關(guān)工作個(gè)人微信公眾號(hào)：機(jī)器學(xué)習(xí)算法那些事（微信ID：zl13751026985）

目錄

1. Boosting算法基本原理

2. Boosting算法的權(quán)重理解

3. AdaBoost的算法流程

4. AdaBoost算法的訓(xùn)練誤差分析

5. AdaBoost算法的解釋

6. AdaBoost算法的過(guò)擬合問(wèn)題討論

7. AdaBoost算法的正則化

8. 總結(jié)

本文詳細(xì)總結(jié)了AdaBoost算法的相關(guān)理論，相當(dāng)于深入理解AdaBoost算法，該文詳細(xì)推導(dǎo)了AdaBoost算法的參數(shù)求解過(guò)程以及討論了模型的過(guò)擬合問(wèn)題。

AdaBoost算法的解釋

AdaBoost算法是一種迭代算法，樣本權(quán)重和學(xué)習(xí)器權(quán)重根據(jù)一定的公式進(jìn)行更新，第一篇文章給出了更新公式，但是并沒(méi)有解釋原因，本節(jié)用前向分布算法去推導(dǎo)樣本權(quán)重和學(xué)習(xí)器權(quán)重的更新公式。

1. 前向分布算法

考慮加法模型：

給定訓(xùn)練數(shù)據(jù)和損失函數(shù)L(y,f(x))的條件下，構(gòu)建最優(yōu)加法模型f(x)的問(wèn)題等價(jià)于損失函數(shù)最小化：

我們利用前向分布算法來(lái)求解（2）式的最優(yōu)參數(shù)，前向分布算法的核心是從前向后，每一步計(jì)算一個(gè)基函數(shù)及其系數(shù)，逐步逼近優(yōu)化目標(biāo)函數(shù)式（2），那么就可以簡(jiǎn)化優(yōu)化的復(fù)雜度。

算法思路如下：

M-1個(gè)基函數(shù)的加法模型：

M個(gè)基函數(shù)的加法模型：

由（3）（4）得：

因此，極小化M個(gè)基函數(shù)的損失函數(shù)等價(jià)于：

前向分布算法的思想是從前向后計(jì)算，當(dāng)我們已知的值時(shí)，可通過(guò)（6）式遞歸來(lái)計(jì)算第 i 個(gè)基函數(shù)及其系數(shù)，i = 1,2,...M。

結(jié)論：通過(guò)前向分布算法來(lái)求解加法模型的參數(shù)。

2. AdaBoost損失函數(shù)最小化

AdaBoost算法的強(qiáng)分類器是一系列弱分類器的線性組合：

其中f(x)為強(qiáng)分類器，共M個(gè)弱分類器，是對(duì)應(yīng)的弱分類器權(quán)重。

由（7）式易知，f(x)是一個(gè)加法模型。

AdaBoost的損失函數(shù)L(y,f(x))為指數(shù)函數(shù)：

利用前向分布算法最小化（8）式，可得到每一輪的弱學(xué)習(xí)器和弱學(xué)習(xí)器權(quán)值。第m輪的弱學(xué)習(xí)器和權(quán)值求解過(guò)程：

首先根據(jù)（9）式來(lái)求解弱學(xué)習(xí)器，權(quán)值α看作常數(shù)：

求解弱學(xué)習(xí)器后，（9）式對(duì)α求導(dǎo)并使導(dǎo)數(shù)為0，得：

其中，α是弱學(xué)習(xí)器權(quán)值，e為分類誤差率：

因?yàn)锳daBoost是加法迭代模型：

以及，得：

結(jié)論：式(14)(15)(16)與第一篇文章介紹AdaBoost算法的權(quán)重更新完全一致，即AdaBoost算法的權(quán)重更新與AdaBoost損失函數(shù)最優(yōu)化是等價(jià)的，每次更新都是模型最優(yōu)化的結(jié)果，（13）式的含義是每一輪弱學(xué)習(xí)器是最小化訓(xùn)練集權(quán)值誤差率的結(jié)果。一句話，AdaBoost的參數(shù)更新和弱學(xué)習(xí)器模型構(gòu)建都是模型最優(yōu)化的結(jié)果。

AdaBoost算法的過(guò)擬合問(wèn)題討論

1. 何時(shí)該討論過(guò)擬合問(wèn)題

模型的泛化誤差可分解為偏差、方差與噪聲之和。當(dāng)模型的擬合能力不夠強(qiáng)時(shí)，泛化誤差由偏差主導(dǎo)；當(dāng)模型的擬合能力足夠強(qiáng)時(shí)，泛化誤差由方差主導(dǎo)。因此，當(dāng)模型的訓(xùn)練程度足夠深時(shí)，我們才考慮模型的過(guò)擬合問(wèn)題。

2. 問(wèn)題的提出

如下圖為同一份訓(xùn)練數(shù)據(jù)的不同模型分類情況：

圖（1）（2）的訓(xùn)練誤差都為0，那么這兩種分類模型的泛化能力孰優(yōu)孰劣？在回答這個(gè)問(wèn)題，我想首先介紹下邊界理論（Margin Theory）。

3. 邊界理論

周志華教授在《集成學(xué)習(xí)方法基礎(chǔ)與算法》證明了：

其中，為泛化誤差率，為邊界閾值。

由上式可知，泛化誤差收斂于某個(gè)上界，訓(xùn)練集的邊界（Margin）越大，泛化誤差越小，防止模型處于過(guò)擬合情況。如下圖：

結(jié)論：增加集成學(xué)習(xí)的弱學(xué)習(xí)器數(shù)目，邊界變大，泛化誤差減小。

4. 不同模型的邊界評(píng)估

1） 線性分類模型的邊界評(píng)估

用邊界理論回答第一小節(jié)的問(wèn)題

線性分類模型的邊界定義為所有樣本點(diǎn)到分類邊界距離的最小值，第一小節(jié)的圖（b）的邊界值較大，因此圖（b）的泛化能力較好。

2） logistic分類模型的邊界評(píng)估

logistic分類模型的邊界定義為所有輸入樣本特征絕對(duì)值的最小值，由下圖可知，模型b邊界大于模型a邊界，因此，模型b的泛化能力強(qiáng)于模型a 。

3）AdaBoost分類模型邊界評(píng)估

AdaBoost的強(qiáng)分類器：

AdaBoost的邊界定義為f(x)的絕對(duì)值，邊界越大，泛化誤差越好。

當(dāng)訓(xùn)練程度足夠深時(shí)，弱學(xué)習(xí)器數(shù)目增加，f(x)絕對(duì)值增加，則泛化能力增強(qiáng)。

結(jié)論：AdaBoost算法隨著弱學(xué)習(xí)器數(shù)目的增加，邊界變大，泛化能力增強(qiáng)。

AdaBoost算法的正則化

為了防止AdaBoost過(guò)擬合，我們通常也會(huì)加入正則化項(xiàng)。AdaBoost的正則化項(xiàng)可以理解為學(xué)習(xí)率（learning rate）。

AdaBoost的弱學(xué)習(xí)器迭代：

加入正則化項(xiàng)：

v的取值范圍為：0 < v < 1。因此，要達(dá)到同樣的訓(xùn)練集效果，加入正則化項(xiàng)的弱學(xué)習(xí)器迭代次數(shù)增加，由上節(jié)可知，迭代次數(shù)增加可以提高模型的泛化能力。

總結(jié)

AdaBoost的核心思想在于樣本權(quán)重的更新和弱分類器權(quán)值的生成，樣本權(quán)重的更新保證了前面的弱分類器重點(diǎn)處理普遍情況，后續(xù)的分類器重點(diǎn)處理疑難雜癥。最終，弱分類器加權(quán)組合保證了前面的弱分類器會(huì)有更大的權(quán)重，這其實(shí)有先抓總體，再抓特例的分而治之思想。

關(guān)于AdaBoost算法的過(guò)擬合問(wèn)題，上兩節(jié)描述當(dāng)弱學(xué)習(xí)器迭代數(shù)增加時(shí)，泛化能力增強(qiáng)。AdaBoost算法不容易出現(xiàn)過(guò)擬合問(wèn)題，但不是絕對(duì)的，模型可能會(huì)處于過(guò)擬合的情況：

（1）弱學(xué)習(xí)器的復(fù)雜度很大，因此選擇較小復(fù)雜度模型可以避免過(guò)擬合問(wèn)題，如選擇決策樹(shù)樁。adaboost + 決策樹(shù) = 提升樹(shù)模型。

（2）訓(xùn)練數(shù)據(jù)含有較大的噪聲，隨著迭代次數(shù)的增加，可能出現(xiàn)過(guò)擬合情況。