【文章內(nèi)容簡介】 問題的應(yīng)用中得到了驗證，但是該算法在計算上存在著一些問題，包括訓練算法速度慢、算法復雜而難以實現(xiàn)以及檢測階段運算量大等等。Osuna等人介紹了一種具體的算法并對人臉識別問題進行了實驗。他將樣本集分為兩個集合B 和N，集合B 作為子問題工作樣本集進行SVM 訓練，并給出了兩階多項式分類器在人臉識別問題中的應(yīng)用結(jié)果。試驗結(jié)果表明該方法比Sung 等提出的基于分布特征的學習方法的檢測率有所提高，同時計算復雜度下降，提高了檢測速度。第4章 Adaboost算法 概述 Adaboost算法簡介Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強的最終分類器(強分類器)。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進行訓練，最后將每次訓練得到的分類器最后融合起來，作為最后的決策分類器。使用Adaboost分類器可以排除一些不必要的訓練數(shù)據(jù)特徵，并將關(guān)鍵放在關(guān)鍵的訓練數(shù)據(jù)上面。Adaboost 算法是1995 年提出的一種快速人臉檢測算法，是人臉檢測領(lǐng)域里程碑式的進步，這種算法根據(jù)弱學習的反饋，適應(yīng)性地調(diào)整假設(shè)的錯誤率，使在效率不降低的情況下，檢測正確率得到了很大的提高。Adaboost算法是目前在人臉檢測方面檢測速度較快、檢測效果較好的一種檢測方法，它是一種把弱分類器采用級聯(lián)的方式訓練成為強分類器的方法。這些弱分類器只需要滿足比隨機猜測好一點，就能通過不斷的修正每個弱分類器的權(quán)值，即挑選那些比較好的分類器，拋棄不好的分類器，從而最終形成由這些弱分類器組成的強分類器，相比較其他的方法而言，Adaboost方法對每個弱分類器的權(quán)值的形成都是無人值守的，完全自動化的，因而Adaboost算法有著比較好的易用性。大量的實驗證明，Adaboost算法是有效的將多弱分類器強化成為強分類器的一種方法，經(jīng)過訓練的分類器具有比較好的分類效果，而且速度較快。圖4．1給出了Adaboost人臉檢測算法進行訓練和檢測的流程圖，本文也將分訓練和檢測兩個方面介紹Adaboost算法。檢測過程人臉非人臉Adaboost訓練分類器檢測結(jié)果Adaboost檢測輸入圖像訓練過程 Adaboost人臉檢測算法人體檢測屬模式識別范疇。模式識別方法多種多樣，模式識別系統(tǒng)的最終目標是要在表示空間和解釋空間之間找到一種映射關(guān)系。這種映射可以是一個分類，也可以是回歸或者描述方案。在這里，我們用分類來敘述。分類方法總得來說可以分為兩種：監(jiān)督學習和非監(jiān)督學習。后來又在前兩者的基礎(chǔ)上 發(fā)展出了半監(jiān)督學習方法，這種方法的本質(zhì)仍屬于監(jiān)督學習。統(tǒng)計分類是模式識別發(fā)展過程中建立起來的比較經(jīng)典的方法，其表達方式有著堅實的理論基礎(chǔ)。它主要基于用概率統(tǒng)計模型得到各類別的特征向量分布，以取得分類的功能。特征向量的取得是基于一個類別已知的訓練樣本集合。因此，這是一種監(jiān)督學習的模式識別方法。在這個意義上，分類器是概念驅(qū)動的，用已知類別標簽的樣本訓練分類器從而得知如何分類。繼而對新的樣本集達到分類的效果，統(tǒng)計分類方法有很多具體的方法，它們?nèi)Q于是否采用一個已知的、參數(shù)型的分布模型。Adaboost算法是統(tǒng)計分類方法中一個經(jīng)典算法，它由Boosting算法發(fā)展而來，是由Freund和Schapire在1995年提出的，該算法解決了以前Boosting算法在實踐中存在的各種問題。實驗表明，Adaboost算法能夠顯著提高學習精度。利用Adaboost算法與haar特征（本文將會在第五章詳細介紹haar特征）相結(jié)合的方法進行人臉檢測。Haar特征是一種基于積分圖像的特征，主要在灰度圖像中使用，該特征計算簡單，提取速度較快。Adaboost算法首先提取圖像中的haar特征，再將訓練得到的haar特征轉(zhuǎn)換成弱分類器，最后將得到的弱分類器進行優(yōu)化組合用于人臉檢測。Viola等人在2001年提出使用AdaBoost學習算法的快速人臉檢測方法，實現(xiàn)了實時的正面人臉檢測系統(tǒng)。Viola的系統(tǒng)中主要有三個核心思想：首先，提出了一種稱為“積分圖像”的圖像表示方法，這種表示法能夠快速計算出檢測器用到的特征；其次，利用基于AdaBoost的學習算法，從一個較大的特征集中選擇少量的關(guān)鍵視覺特征，產(chǎn)生一個高效的分類器；最后，再用級聯(lián)的方式將單個的分類器合成為一個更加復雜的分類器，使圖像的背景區(qū)域可以被快速地丟棄，而在有可能存在目標(人臉)的區(qū)域花費更多的計算。該人臉檢測系統(tǒng)在實時正面人臉檢測中能夠達到15幀／秒的速率。由于該方法能夠達到較高的檢測率并且具有目前最好的實時性，因此激發(fā)了更多研究人員在基于類Haar特征和Boost學習算法的實時人臉檢測算法方面的研究。Intel實驗室的Rainer Lienhart擴展了類Haar特征，在Viola提出的類Haar特征的基礎(chǔ)上添加了旋轉(zhuǎn)45度的類Haar特征，在與Viola系統(tǒng)相同檢測率的情況下，降低了10％的誤檢率。微軟研究院Stan ，并設(shè)計了一個金字塔式的檢測器結(jié)構(gòu)用于多視角的人臉檢測。 弱學習與強學習弱分類器的設(shè)計是集成機器學習的重要內(nèi)容之一，與一般機器學習算法區(qū)別在于弱分類器設(shè)計無需考慮線性不可分問題，這是集成機器學習吸引大量應(yīng)用研究者關(guān)注的主要原因。弱分類器的概念來源于Valiant在1984年提出的PAC學習理論，之后Kearns和Valiantl又提出了強PAC學習和弱PAC學習的概念。在PAC學習模型中，若存在一個多項式級學習算法來識別一組概念，并且識別正確率很高，那么這組概念是強可學習的；而如果學習算法識別一組概念的正確率僅比隨機猜測略好，那么這組概念是弱可學習的。隨機猜測一個是或否的問題，將會有50%的正確率。如果一個假設(shè)能夠稍微地提高猜測正確的概率，那么這個假設(shè)就是弱學習算法，得到這個算法的過程稱為弱學習?？梢允褂冒胱詣踊姆椒楹脦讉€任務(wù)構(gòu)造弱學習算法，構(gòu)造過程需要數(shù)量巨大的假設(shè)集合，這個假設(shè)集合是基于某些簡單規(guī)則的組合和對樣本集的性能評估而生成的。如果一個假設(shè)能夠顯著地提高猜測正確的概率，那么這個假設(shè)就稱為強學習。弱分類器就是根據(jù)某些單一依據(jù)來就行粗略分類的分類器，其分來的準確度要求很低，只要達到50%以上即可。雖然弱分類器的分類效果很差，但是試想如果將很多個這樣的弱分類器按照一定的規(guī)則組合起來便可以形成一個高度準確的強分類器，這也就是級聯(lián)分類器。實際上每一個haar特征都可以對應(yīng)一個弱分類器，每一個弱分類器都是根據(jù)它所對應(yīng)的haar特征的參數(shù)來定義的。如果將所有的haar特征都用來對應(yīng)一個弱分類器，那么其總個數(shù)將超過數(shù)十萬個。要想從這樣龐大數(shù)目的弱分類器中訓練出最優(yōu)弱分類器將是一個非常巨大的工程，其訓練時間也將達到數(shù)天之長。因此，這是該進Adaboost性能的一個關(guān)鍵點所在。通常情況下，弱學習算法比強學習算法更容易獲得。Keams和vallant提出了弱學習算法與強學習算法間的等價問題，即能否把弱學習算法轉(zhuǎn)化為強學習算法。如果兩者等價，那么在學習概念時，只需要找到一個比隨機猜測略好的弱學習算法，就可以直接將其提升為強學習算法。Keams和vallant證明：只要有足夠的數(shù)據(jù)，弱學習算法就通過集成的方式生成任意高精度的假設(shè)(強學習方法)。 PAC 基本模型 概述PAC（Probably Approximately Correct）模型是計算學習理論中常用的模型，是由Valiant于1984年首先提出來的，由統(tǒng)計模式識別、決策理淪提出了一些簡單的概念并結(jié)合了計算復雜理論的方法而提出的學習模型。它是研究學習及泛化問題的一個概率框架，不僅可用于神經(jīng)網(wǎng)絡(luò)分類問題，而且可廣泛用于人工智能中的學習問題。PAC學習的實質(zhì)就是在樣本訓練的基礎(chǔ)上，使算法的輸出以概率接近未知的目標概念。PAC學習模型是考慮樣本復雜度及計算復雜度的一個基本框架，成功的學習被定義為形式化的概率理論。 基本概念實例空間指學習器能見到的所有實例，用xn指示每個大小為n的學習問題的實例集，每個為一個實例，為實例空間。概念空間指目標慨念可以從中選取的所有概念的集合，學習器的目標就是要產(chǎn)生目標概念的一個假設(shè)，使其能準確地分類每個實例，對每個n≥1，定義每個為上的一系列概念，為X上的概念空間，也稱為概念類。似設(shè)空間指算法所能輸出的聽有假設(shè)的集合，用表示。對每個目標概念和實例，為實例上的分類值，即當且僅當?shù)娜我凰圃O(shè)h指的是規(guī)則，即對給出的，算法在多項式時間內(nèi)為輸出一預測值。樣本復雜度(sample plexity)指學習器收斂到成功假設(shè)時至少所需的訓練樣本數(shù)。計算復雜度(putational plexity)指學習器收斂到成功假設(shè)時所需的計算量。出錯界限指在成功收斂到一個假設(shè)前，學習器對訓練樣本的錯誤分類的次數(shù)。在某一特定的假設(shè)空間中，對于給定的樣本，若能找到一似設(shè)h，使得對該概念類的任何概念都一致，且該算法的樣本復雜度仍為多項式，則該算法為一致算法。對手學習器樣本產(chǎn)生器EX分布概念類準確度置信度樣本請求帶標記隨機實例實例空間為，概念空間和假設(shè)空間均為的子集，對任意給定的準確度及任意給定的置信度，實例空間上的所有分布及目標空間中的所有目標函數(shù)，若學習器只需多項式個樣本及在多項式時間內(nèi)，最終將以至少的概率輸出一假設(shè)，使得隨機樣本被錯分類的概率，則稱學習器L足PAC學習的。它是考慮樣本復雜度及計算復雜度的一個基本框架，成功的學習被定義為形式化的概率理淪，其模型如圖所示。圖41 PAC學習模型從圖中知PAC模型是與分布無關(guān)的，因?qū)W習器來說，實例上的分布是未知的。該定義不要求學習器輸出零錯誤率的假設(shè)，而只要求其錯誤率被限定在某常數(shù)ε的范圍內(nèi)(ε可以任意小)；同時也不要求學習器對所有的隨機抽取樣本序列都能成功，只要其失敗的概率被限定在某個常數(shù)δ的范圍內(nèi)(δ也可取任意小)即可。這樣將學習到一個可能近似正確的假設(shè)。 PAC模型的不足在實際的機器學習中，PAC模型的不足有：模型中強調(diào)最壞情況，它用最壞情況模型來測量學習算法的計算復雜度及對概念空間中的每個目標概念和實例空間上的每個分布，用最壞情況下所需要的隨機樣本數(shù)作為其樣本復雜度的定義，使得它在實際中不可用；定義中的目標概念和無噪聲的訓練數(shù)據(jù)在實際中是不現(xiàn)實的。樣本復雜度的最壞情況定義意味著即使能準確地計算出某一算法的樣本復雜度，仍然得過高估計假設(shè)的出錯率，這是因為它不是計算某一算法的樣本復雜度(即使存在一個簡單的一致算法)，而是對任意一致算法都成立的一個樣本復雜度的上界。這就使得基本的PAC模型不能預測學習曲線(1earning curve)。 Boosting 方法Boosting 原意為提升、加強?，F(xiàn)在一般指的是將弱學習算法提升為強學習算法的一類算法。Boosting 算法是在Kearns 和Valiant 證明后才真正成熟起來的。1990 年，Schapire 最先構(gòu)造出一種多項式級的算法，即最初的Boosting算法。這種算法可以將弱分類規(guī)則轉(zhuǎn)化成強分類規(guī)則。一年后，F(xiàn)reund 提出了一種效率更高的Boosting 算法。1993 年，Drucker 和Schapire 第一次以神經(jīng)網(wǎng)絡(luò)作為弱學習器，應(yīng)用Boosting 算法來解決實際的OCR 問題。Boosting 算法在分類、建模、圖像分割、數(shù)據(jù)挖掘等領(lǐng)域均已得到簡單而有效的應(yīng)用。1995 年，F(xiàn)reund 和Schapire 提出的Adaboost，是對Boosting 算法的一大提高。 Adaboost算法性能分析強分類器H(x)對訓練樣本集的誤判率稱為訓練誤判率，記為，則有：其中，對于AdaBoost算法，F(xiàn)reund和Schapire 給出了關(guān)于訓練誤判率的重要理論結(jié)果。定理：假設(shè)運行Adaboost算法經(jīng)過T輪訓練后生成的弱分類器分別，……，其對樣本集誤判率分別，則訓練誤判率有上界：。詳細的證明過程可參見文獻。在定理中，如果每個，令則最終強分類器的訓練誤判率上界可改寫為：由此可見，訓練誤判率：隨訓練輪數(shù)T的增大呈指數(shù)級的減小。特別的，如果所有的弱分類器誤判率都相等，即，上式可簡化為：可見，強分類器誤判率隨著弱分類器數(shù)量增多和弱分類器誤判率的降低而迅速下降。只要有足夠多的弱分類器，就可以使強分類器達到任意低的誤判率。對于兩分類問題，只需要弱學習算法的準確性略好于隨機猜測，便可以保證Adaboost算法收斂。第5章 矩形特征與積分圖 引言本章節(jié)將描述對AdaBoost 人臉檢測訓練算法速度很重要的兩方面，特征的選取和特征值的計算。把矩形作為人臉檢測的特征向量，稱為矩形特征。本算法選取了最簡單的5個矩形特征模板進行訓練，以得到一套用于人臉檢測的最適合的矩形特征，事實證明，這種特征選取方法的訓練速度雖然不快，但是檢測效率很高。Viola 提出將積分圖(integral image)應(yīng)用到特征值的計算之中。積分圖的引用，可以只對圖像進行一次遍歷計算，就能夠在用常量時間完成每個特征值的計算，這使得訓練和檢測的速度大大提升。 矩形特征 概述將矩形特征作為對輸入圖像的人臉檢測的特征向量，稱為矩形特征。在給定有限的數(shù)據(jù)情況下，基于特征的檢測能夠編碼特定區(qū)域的狀態(tài)，而且基于特征的系統(tǒng)比基于象素的系統(tǒng)要快得多。矩形特征對一些簡單的圖形結(jié)構(gòu)，比如邊緣、線段，比較敏感，但是其只能描述特定走向（水平、垂直、對角）的結(jié)構(gòu)，因此比較粗略。如下圖51，臉部一些特征能夠由矩形特征簡單地描繪，例如，通常，眼睛要比臉頰顏色更深；鼻梁兩側(cè)要比鼻梁顏色要深；嘴巴要比周圍顏色更深。對于一個2424 檢測器，其內(nèi)的矩形特征數(shù)量超過160,000 個，必須通過特定算法甄選合適的矩形特征，并將其組合成強分類器才能檢測人臉。圖51 矩形特征在人臉上的特征匹配(上行是2424 子窗口內(nèi)選出的