作者簡介

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

目錄

1. Boosting算法基本原理

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

3. AdaBoost的算法流程

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

5. AdaBoost算法的解釋

6. AdaBoost算法的過擬合問題討論

7. AdaBoost算法的正則化

8. 總結(jié)

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

AdaBoost算法的解釋

AdaBoost算法是一種迭代算法，樣本權(quán)重和學(xué)習(xí)器權(quán)重根據(jù)一定的公式進行更新，第一篇文章給出了更新公式，但是并沒有解釋原因，本節(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)的問題等價于損失函數(shù)最小化：

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

算法思路如下：

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

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

由（3）（4）得：

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

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

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

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

AdaBoost算法的強分類器是一系列弱分類器的線性組合：

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

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

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

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

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

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

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

因為AdaBoost是加法迭代模型：

以及，得：

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

AdaBoost算法的過擬合問題討論

1. 何時該討論過擬合問題

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

2. 問題的提出

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

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

3. 邊界理論

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

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

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

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

4. 不同模型的邊界評估

1） 線性分類模型的邊界評估

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

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

2） logistic分類模型的邊界評估

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

3）AdaBoost分類模型邊界評估

AdaBoost的強分類器：

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

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

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

AdaBoost算法的正則化

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

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

加入正則化項：

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

總結(jié)

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

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

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

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