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

0. 引言

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

1. AdaBoost身世之謎

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

1.1 PAC學習模型

1.1.1 概述

　　可學習理論可以分為統計學習理論和計算學習理論兩大部份[1]。統計學習理論與經驗進程有著密切的聯系，而計算學習理論是幾率理論中發展比較成熟的1個重要分支，它主要用于處理在實驗的基礎上進行的各種量的估計，研究當采樣愈來愈多的時候，這些估計值是不是收斂到未知的真值的問題，它的理論基礎主要是幾率理論；計算學習理論主要研究如何構造有效的學習算法和討論學習算法的計算復雜性問題。

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

　　PAC學習的實質就是在樣本訓練的基礎上，使算法的輸出以幾率接近未知的目標概念。PAC學習模型是斟酌樣本復雜度（指學習器收斂到成功假定時最少所需的訓練樣本數）及計算復雜度（指學習器收斂到成功假定時所需的計算量）的1個基本框架，成功的學習被定義為情勢化的幾率理論。

　　簡單說來，PAC學習模型不要求你每次都正確，只要能在多項式個樣本和多項式時間內得到滿足需求的正確率，就算是1個成功的學習。

1.1.2 PAC數學描寫

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

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

構造適當的算法 {Am}，Am為到概念空間的映照 Am:[X×V]m→C ，并定義：

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

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

　　如果學習器 L 只需要多項式 p(m,1/e,1/d) 個樣本和在多項式 p(

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈