AdaBoost 人臉檢測介紹(5) : AdaBoost算法的誤差界限

　　本系列文章總共有七篇，目錄索引如下：

　　AdaBoost 人臉檢測介紹(1) : AdaBoost身世之謎

　　AdaBoost 人臉檢測介紹(2) : 矩形特征和積分圖

　　AdaBoost 人臉檢測介紹(3) : AdaBoost算法流程

　　AdaBoost 人臉檢測介紹(4) : AdaBoost算法舉例

　　AdaBoost 人臉檢測介紹(5) : AdaBoost算法的誤差界限

　　AdaBoost 人臉檢測介紹(6) : 使用OpenCV自帶的 AdaBoost程式訓練并檢測目标

　　AdaBoost 人臉檢測介紹(7) : Haar特征CvHaarClassifierCascade等結構分析

5. AdaBoost算法的誤差界限

　　通過上面的例子可知，AdaBoost在學習的過程中不斷減少訓練誤差 e，直到各個弱分類器組合成最終分類器。那這個最終分類器的誤差界限到底是多少呢？事實上，AdaBoost最終分類器的訓練誤差的上界是：

Error=1N∑i=1NI(G(xi)≠yi)≤1N∑iexp(−yif(xi))=∏mZm

Remark: 參考了一些資料包括論文和部落格，論文中很少有直接給出證明的，而部落格中幾乎沒有一個證明從數學上來說是嚴謹的！此處本人将嚴格嚴謹的數學證明給出來，其實對于做純工程的IT人士來說，不需要知道數學證明也無需知道該結論，隻需要知道怎麼使用該算法即可！

證明： 1）我們首先證明左邊的不等式：

　　● 當 G(xi)=yi 時，示性函數 I(G(xi)≠yi) 取值為0，而 exp(−yif(xi))>0 .

　　● 當 G(xi)≠yi 時，示性函數 I(G(xi)≠yi) 取值為1，而此時 yi 和 f(xi) 符号相反，是以 −yif(xi) 的值就為正，故 exp(−yif(xi))>1 .

是以我們就證明了左邊的不等式！

　　2）接下來我們要證明右邊的等式：

　　　由分類器權值疊代公式 wm+1,i=wmiZmexp(−αmyiGm(xi)) 出發來證明：

在上式中令 m=M ，并記住 w1,i=1N, f(x)=∑Mj=1αjGj(x) ，是以有：

wM+1,i=w1,i∏Mj=1Zjexp(−yif(xi))=1Nexp(−yif(xi))/∏j=1MZj

因為對任何 m ，wmi皆為一個分布，即 ∑Ni=1wmi=1 ，是以有： 1=∑i=1NwM+1,i=1N∑i=1N⎛⎝exp(−yif(xi))∏Mj=1Zj⎞⎠

而 ∏Mj=1Zj 是一個與 i 無關的常量，可以提取出來，是以就得到：1N∑i=1Nexp(−yif(xi))=∏j=1MZj

是以我們就證明了右邊的等式■ <script type="math/tex; mode=display" id="MathJax-Element-455"></script>

　　這個結果說明，可以在每一輪選取适當的 Gm 使得 Zm 最小，進而使得訓練誤差下降最快。接着，我們來繼續求上述結果的上界。首先對 Zm 進行适當的變形：

Zm=∑i=1Nwmiexp(−αmyiGm(xi))=∑yi=Gm(xi)∑yi=Gm(xi)wmie−αm+∑yi≠Gm(xi)∑yi=Gm(xi)wmieαm

由 em 的定義可知： Zm=∑yi=Gm(xi)wmie−αm+∑yi≠Gm(xi)wmieαm=(1−em)e−αm+emeαm

由 αm 的定義可知 eαm=1−emem−−−−√ ，再令 γm=12−em ，是以有： Zm=(1−em)e−αm+emeαm=2em(1−em)−−−−−−−−−√=1−4γ2m−−−−−−−√

由泰勒展開式很容易證明不等式： 1−x≤e−x . 将此不等式應用到上式中得到： Zm=1−4γ2m−−−−−−−√≤e−2γ2m

将此結果應用到前面的誤差界限不等式中得到： Error=1N∑i=1NI(G(xi)≠yi)≤∏m=1MZm≤exp(−2∑m=1Mγ2m)≤exp(−2Mγ2)

其中 γm=12−em,  γ=min{γ1,γ2,...,γM}>0 。

　　這個結論表明，AdaBoost的訓練誤差是以指數速率下降的。另外，AdaBoost算法不需要事先知道下界 γ ，AdaBoost具有自适應性，它能适應弱分類器各自的訓練誤差率。

[同步本人網易部落格文章] AdaBoost 人臉檢測介紹(5) : AdaBoost算法的誤差界限