作者簡介

張磊：從事AI醫療算法相關工作個人微信公眾號：機器學習算法那些事（微信ID：zl13751026985）

目錄

1. Boosting算法基本原理

2. Boosting算法的權重理解

3. AdaBoost的算法流程

4. AdaBoost算法的訓練誤差分析

5. AdaBoost算法的解釋

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

7. AdaBoost算法的正則化

8. 總結

本文詳細總結了AdaBoost算法的相關理論，相當于深入理解AdaBoost算法，該文詳細推導了AdaBoost算法的參數求解過程以及討論了模型的過擬合問題。

AdaBoost算法的解釋

AdaBoost算法是一種迭代算法，樣本權重和學習器權重根據一定的公式進行更新，第一篇文章給出了更新公式，但是并沒有解釋原因，本節用前向分布算法去推導樣本權重和學習器權重的更新公式。

1. 前向分布算法

考慮加法模型：

給定訓練數據和損失函數L(y,f(x))的條件下，構建最優加法模型f(x)的問題等價于損失函數最小化：

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

算法思路如下：

M-1個基函數的加法模型：

M個基函數的加法模型：

由（3）（4）得：

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

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

結論：通過前向分布算法來求解加法模型的參數。

2. AdaBoost損失函數最小化

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

其中f(x)為強分類器，共M個弱分類器，是對應的弱分類器權重。

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

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

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

首先根據（9）式來求解弱學習器，權值α看作常數：

求解弱學習器后，（9）式對α求導并使導數為0，得：

其中，α是弱學習器權值，e為分類誤差率：

因為AdaBoost是加法迭代模型：

以及，得：

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

AdaBoost算法的過擬合問題討論

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

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

2. 問題的提出

如下圖為同一份訓練數據的不同模型分類情況：

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

3. 邊界理論

周志華教授在《集成學習方法基礎與算法》證明了：

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

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

結論：增加集成學習的弱學習器數目，邊界變大，泛化誤差減小。

4. 不同模型的邊界評估

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

用邊界理論回答第一小節的問題

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

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

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

3）AdaBoost分類模型邊界評估

AdaBoost的強分類器：

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

當訓練程度足夠深時，弱學習器數目增加，f(x)絕對值增加，則泛化能力增強。

結論：AdaBoost算法隨著弱學習器數目的增加，邊界變大，泛化能力增強。

AdaBoost算法的正則化

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

AdaBoost的弱學習器迭代：

加入正則化項：

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

總結

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

關于AdaBoost算法的過擬合問題，上兩節描述當弱學習器迭代數增加時，泛化能力增強。AdaBoost算法不容易出現過擬合問題，但不是絕對的，模型可能會處于過擬合的情況：

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

（2）訓練數據含有較大的噪聲，隨著迭代次數的增加，可能出現過擬合情況。