本系列文章總共有7篇，目錄索引以下：
　　AdaBoost 人臉檢測介紹(1) : AdaBoost身世之謎
　　AdaBoost 人臉檢測介紹(2) : 矩形特點(diǎn)和積分圖
　　AdaBoost 人臉檢測介紹(3) : AdaBoost算法流程

0. 引言

　　學(xué)習(xí)和使用AdaBoost算法來研究人臉檢測有好幾個(gè)月了，1直以來想對AdaBoost的算法和原理做1個(gè)總結(jié)，在網(wǎng)上也參考了很多牛人的博客和看了1些專業(yè)論文，總是覺得總結(jié)的不夠全面和詳細(xì)，因此想對AdaBoost的來龍去脈做1個(gè)詳細(xì)的總結(jié)，對算法里觸及到的原理，自己經(jīng)過細(xì)致考證和推理，給出了詳細(xì)的理論證明和代碼驗(yàn)證，而不單單是停留在只知結(jié)果而不知推理的層面上。因此需要花很多時(shí)間來總結(jié)和寫下自己在AdaBoost道路上學(xué)習(xí)和研究的心路歷程！在后面會給出所有的參考文獻(xiàn)，對網(wǎng)上眾多的未曾謀面的牛人表示感謝！

1. AdaBoost身世之謎

　　Boost 算法系列的起源來自于PAC學(xué)習(xí)模型。這套理論主要研究的是甚么時(shí)候1個(gè)問題是可被學(xué)習(xí)的，固然也會探討針對可學(xué)習(xí)問題的具體的學(xué)習(xí)算法。這套理論是由Valiant提出來的，也因此（還有其他貢獻(xiàn)哈）他取得了2010年的圖靈獎(jiǎng)。這里也貼出Valiant的頭像，表示下俺等菜鳥的膜拜之情。

1.1 PAC學(xué)習(xí)模型

1.1.1 概述

　　可學(xué)習(xí)理論可以分為統(tǒng)計(jì)學(xué)習(xí)理論和計(jì)算學(xué)習(xí)理論兩大部份[1]。統(tǒng)計(jì)學(xué)習(xí)理論與經(jīng)驗(yàn)進(jìn)程有著密切的聯(lián)系，而計(jì)算學(xué)習(xí)理論是幾率理論中發(fā)展比較成熟的1個(gè)重要分支，它主要用于處理在實(shí)驗(yàn)的基礎(chǔ)上進(jìn)行的各種量的估計(jì)，研究當(dāng)采樣愈來愈多的時(shí)候，這些估計(jì)值是不是收斂到未知的真值的問題，它的理論基礎(chǔ)主要是幾率理論；計(jì)算學(xué)習(xí)理論主要研究如何構(gòu)造有效的學(xué)習(xí)算法和討論學(xué)習(xí)算法的計(jì)算復(fù)雜性問題。

　　PAC（Probably Approximately Correct）模型是計(jì)算學(xué)習(xí)理論中經(jīng)常使用的模型，它是由Valiant于1984年首先提出來的[2]。這篇論文認(rèn)為“學(xué)習(xí)”是模式明顯清晰或模式不存在時(shí)仍能獲得知識的1種“進(jìn)程”，并給出了1個(gè)從計(jì)算角度來取得這類“進(jìn)程”的方法，這類方法包括：（1）適當(dāng)信息搜集機(jī)制的選擇；（2）學(xué)習(xí)的協(xié)議；（3）對能在公道步驟內(nèi)完成學(xué)習(xí)的概念的分類。雖然內(nèi)在的算法復(fù)雜性限制了能夠?qū)W習(xí)的概念的范圍，論文依然給出了1些有現(xiàn)實(shí)意義的，重要的，能夠?qū)W習(xí)的概念例子。

　　PAC學(xué)習(xí)的實(shí)質(zhì)就是在樣本訓(xùn)練的基礎(chǔ)上，使算法的輸出以幾率接近未知的目標(biāo)概念。PAC學(xué)習(xí)模型是斟酌樣本復(fù)雜度（指學(xué)習(xí)器收斂到成功假定時(shí)最少所需的訓(xùn)練樣本數(shù)）及計(jì)算復(fù)雜度（指學(xué)習(xí)器收斂到成功假定時(shí)所需的計(jì)算量）的1個(gè)基本框架，成功的學(xué)習(xí)被定義為情勢化的幾率理論。

　　簡單說來，PAC學(xué)習(xí)模型不要求你每次都正確，只要能在多項(xiàng)式個(gè)樣本和多項(xiàng)式時(shí)間內(nèi)得到滿足需求的正確率，就算是1個(gè)成功的學(xué)習(xí)。

1.1.2 PAC數(shù)學(xué)描寫

　　下面扼要描寫PAC學(xué)習(xí)模型：
　　① Х為樣本空間，包括所有可以用于學(xué)習(xí)的樣本集合;
　　② Ｃ為概念空間，包括所有可以選取的目標(biāo)概念T；
　　③ Ｖ為分類集合，其值為目標(biāo)概念的所有分類 {v1,...,vk}。最簡單的情況為2值，V={0,1};
　　④ Ｈ為假定空間，包括算法所輸出的所有假定Hm(T,x).

　　學(xué)習(xí)器L的目的是找到目標(biāo)概念的1個(gè)假定，使其能對每一個(gè)樣本進(jìn)行分類。我們依照某種固定的（可能未知的）散布 P(x) 獨(dú)立抽取樣本x1,…,xm，L 返回 hT(xt)的值：hT(xt)∈V 為 T 的唆使函數(shù)，表示 L 對 xt 的分類。
　　因而可以取得1組數(shù)據(jù)：

構(gòu)造適當(dāng)?shù)乃惴?{Am}，Am為到概念空間的映照 Am:[X×V]m→C ，并定義：

則 Hm(T,x) 就是目標(biāo)概念T 對樣本 x1,…,xm 的1個(gè)假定。

　　我們希望能夠找到1個(gè)對所有樣本都正確的假定，在實(shí)際學(xué)習(xí)中，這是不可能的。如果學(xué)習(xí)器 L 終究將以 (1?d) 的幾率（d 稱為假定的置信度）輸出1個(gè)假定 h∈H，而且隨機(jī)樣本被毛病分類的幾率小于假定毛病率 e，我們就認(rèn)為這個(gè)假定為成功假定。

　　如果學(xué)習(xí)器 L 只需要多項(xiàng)式 p(m,1/e,1/d) 個(gè)樣本和在多項(xiàng)式 p(

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈