肖秦琨，錢春虎，高嵩

（1.西安工業(yè)大學(xué) 電子信息工程學(xué)院，陜西 西安 710032）

0 引言

在機(jī)器學(xué)習(xí)領(lǐng)域中，如何通過(guò)觀測(cè)數(shù)據(jù)的學(xué)習(xí)得到精確估計(jì)是一個(gè)關(guān)鍵問(wèn)題。而在實(shí)際應(yīng)用領(lǐng)域中，構(gòu)造一個(gè)高精度的估計(jì)是很困難的。Boosting是一種試圖提高任意給定學(xué)習(xí)算法精度的方法。它的思想起源 Valiant［1］提出的 PAC（Probably Approximately Correct）學(xué)習(xí)模型。PAC（概率近似正確）是統(tǒng)計(jì)機(jī)器學(xué)習(xí)、集成機(jī)器學(xué)習(xí)等方法的理論基礎(chǔ)。此后很多學(xué)者開(kāi)始了PAC學(xué)習(xí)模型的研究。Kearns和Valiant首次提出了PAC學(xué)習(xí)模型中弱學(xué)習(xí)算法和強(qiáng)學(xué)習(xí)算法的等價(jià)性問(wèn)題［2］，即是否可以將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法?如果兩者等價(jià)，那么只需找到一個(gè)比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法，就可以將其提升為強(qiáng)學(xué)習(xí)算法，而不必尋找通常條件下很難獲得的強(qiáng)學(xué)習(xí)算法。1990年Schapire［3］最先提出了一種可證明的多項(xiàng)式時(shí)間Boosting算法，對(duì)上述問(wèn)題做出了肯定的回答。一年后，F(xiàn)reund［4］設(shè)計(jì)了一種通過(guò)重取樣或過(guò)濾運(yùn)作的高效的BBM（Boost－by－majority）算法。但這兩種算法在實(shí)踐上存在著缺陷，那就是都必須事先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限。1995年Freund與Schapire［5］對(duì)Boosting算法進(jìn)行了改進(jìn)，提出了 AdaBoost（Adaptive Boosting）算法。這個(gè)算法和BBM算法的效率幾乎一樣，但不需要任何關(guān)于弱學(xué)習(xí)器的先驗(yàn)知識(shí)，所以容易應(yīng)用到實(shí)際問(wèn)題中去。然后，Boosting算法經(jīng)過(guò)進(jìn)一步改進(jìn)又有了新的突破，如通過(guò)調(diào)整權(quán)重而運(yùn)作的Ada-Boost.M1、AdaBoost.M2、AdaBoost.R 算法等，解決了早期的 Boosting算法很多實(shí)踐上的問(wèn)題［6］。

和其他算法相比較，Boosting算法有很多優(yōu)點(diǎn):（1）在分類的同時(shí)能夠進(jìn)行特征選取，編程容易，速度快、簡(jiǎn)單;（2）只要給定足夠多的數(shù)據(jù)，Boosting不需要弱分類器的先驗(yàn)知識(shí)，只需要通過(guò)尋找比隨機(jī)稍好的弱分類器，就能最終得到一個(gè)比較好的強(qiáng)分類器;（3）在弱分類器確定后，除了迭代次數(shù)T之外，其他參數(shù)都不需要調(diào)節(jié);（4）能夠得到算法的誤差上界。

1 算法描述

算法示意圖如圖1所示。算法的基本思想如下:（1）采用Gentle Adaboost算法進(jìn)行目標(biāo)識(shí)別，Gentle Adaboost算法是Friedman［7］等在1998年提出的，它是對(duì)Boosting算法的改進(jìn)。首先任意給一個(gè)弱學(xué)習(xí)算法和訓(xùn)練集（x1，y1）…，（xn，yn），此處，xi∈X表示某個(gè)域或?qū)嵗臻g，yi是xi的類別標(biāo)識(shí)，且滿足yi=f（xi），且yi∈Y={+1，－1}。設(shè)迭代次數(shù)為 t，t=1，2…T，設(shè)第 t輪迭代時(shí)第i個(gè)訓(xùn)練樣本（xi，yi）分布的權(quán)重記為wt（i），Gentle Adaboost算法在每輪迭代時(shí)反復(fù)調(diào)用給定的弱學(xué)習(xí)算法。初始化時(shí)，每個(gè)訓(xùn)練樣本的權(quán)重均為w1（i）=1。接著，調(diào)用弱學(xué)習(xí)算法進(jìn)行T次迭代，每次迭代后按訓(xùn)練結(jié)果來(lái)更新訓(xùn)練集上的分布，對(duì)訓(xùn)練失敗的訓(xùn)練樣本賦予較大的權(quán)重，使得下一次對(duì)這些訓(xùn)練樣本更加關(guān)注，從而也得到一個(gè)預(yù)測(cè)序列h1，h2…，hT。T次迭代后，在分類問(wèn)題中最終的預(yù)測(cè)函數(shù)H（x）采用有權(quán)重的投票方式產(chǎn)生，其中H（x）可以這樣表示:

圖1 Boosting算法示意圖

算法步驟如下:

（1）給定樣本（x1，y1），…，（xn，yn），背景樣本 yi= －1，目標(biāo)樣本yi=1;

（2）創(chuàng)建圖像集:從LabelMe中選擇含有car類目標(biāo)的圖像200幅作為訓(xùn)練集，若干幅圖像作為測(cè)試集;

（3）圖像預(yù)處理:對(duì)訓(xùn)練/測(cè)試圖像和目標(biāo)進(jìn)行歸一化處理，訓(xùn)練圖像大小為［128 200］，測(cè)試圖像大小為［256 256］;

（4）創(chuàng)建特征庫(kù):選擇8幅圖像建立特征庫(kù)，提取20個(gè)目標(biāo)掩膜邊緣取樣點(diǎn)和目標(biāo)中心的位置，每幅圖像經(jīng)過(guò)4種用于圖像邊緣增強(qiáng)的濾波器，得到640個(gè)圖像片段gf，將得到的特征塊（Patches）存儲(chǔ)到特征庫(kù)中;

（5）計(jì)算特征:利用創(chuàng)建的特征庫(kù)片段gf、片段gf的位置wf來(lái)計(jì)算訓(xùn)練樣本的特征值，

其中*表示卷積算子，?表示歸一化互相關(guān)，對(duì)wf的卷積用來(lái)確定圖像片段是否出現(xiàn)在期望位置上，從中找出背景樣本和目標(biāo)樣本的位置;

（6）采用Gentle Adaboost算法來(lái)訓(xùn)練檢測(cè)器，流程圖如圖2所示:

① 設(shè)迭代次數(shù)為 t，t=1，2…T，第 i個(gè)訓(xùn)練樣本（xi，yi）分布的權(quán)重記為wi，初始化權(quán)值為wi=1，

其中 i=1，2…n，H（x）=0;

② 設(shè)置弱分類器:

ht（x）由四個(gè)參數(shù)［a，b，θ，k］來(lái)決定，對(duì)正確分類（xk≥θ）賦予權(quán)值 a，其中 t=1，2…T;

采用公式（4）對(duì)每個(gè)樣本更新權(quán)值:

其中，yi為輸出期望，i=1，2…n;

采用公式（5）對(duì)每個(gè)樣本更新分類器:

③輸出強(qiáng)分類器:H（x）由公式（1）得出。當(dāng)x≥0，sign（x）為1，否則為－1;

圖2 Boosting算法訓(xùn)練檢測(cè)器

（7）測(cè)試檢測(cè)器:

① 采用步驟（5）計(jì)算測(cè)試樣本的特征值;

② 將特征值代入（6）中進(jìn)行迭代得到強(qiáng)分類器;

③ 輸出包含目標(biāo)的邊界盒;

（8）評(píng)估檢測(cè)器性能:

采用正確率－召回率（Precision-Recall）曲線對(duì)檢測(cè)精度進(jìn)行全面評(píng)估。查全率（recall）用橫坐標(biāo)表示，即檢測(cè)正確的目標(biāo)數(shù)量與特定類型的所有目標(biāo)數(shù)量的比值;查準(zhǔn)率（precision）用縱坐標(biāo)表示，即檢測(cè)正確的目標(biāo)數(shù)量與檢測(cè)目標(biāo)總數(shù)的比值。檢測(cè)的結(jié)果用包含目標(biāo)的邊界盒表示。

算法流程圖如圖3所示。

圖3 算法流程圖

2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)結(jié)果如圖4所示。

在圖4中第一列表示輸入真實(shí)圖像;第二列表示Boosting邊界，代表輸出分類結(jié)果的置信度。y H（x）是Boosting邊界［8］，y是樣本標(biāo)簽，y= +1表示目標(biāo)，y=－1表示背景。邊界越大，出現(xiàn)目標(biāo)的可能性也越大;第三列表示閾值處理結(jié)果;第四列表示輸出包含目標(biāo)的邊界盒。圖4（a）（b）表示Boosting對(duì)多目

圖4 實(shí)驗(yàn)結(jié)果

圖5 查準(zhǔn)率－查全率曲線

標(biāo)檢測(cè)的結(jié)果，圖4（c）（d）（e）表示對(duì)單目標(biāo)的檢測(cè)結(jié)果。從檢測(cè)結(jié)果看:圖4（a）（e）的目標(biāo)被完全正確的檢測(cè)出來(lái);圖4（b）除了car被檢測(cè)出來(lái)，由于建筑物下方邊界值太大，被錯(cuò)誤檢測(cè)出來(lái);圖4（c）（d）也把car檢測(cè)出來(lái)，由于斑馬線的邊界值太大，被錯(cuò)誤檢測(cè)出來(lái)。Precision-Recall曲線如圖5所示。

從圖5的查準(zhǔn)率－查全率（Precision-Recall）曲線可以看出:開(kāi)始檢測(cè)時(shí)precision最高，即正確檢測(cè)到的目標(biāo)占所有檢測(cè)到目標(biāo)的比例最大，recall較低;隨著測(cè)試圖像的增多，檢測(cè)正確的目標(biāo)也逐漸增加，因此recall升高，但是錯(cuò)誤檢測(cè)的目標(biāo)也增多了，所以precision總體呈現(xiàn)下降趨勢(shì)。最終檢測(cè)的查全率和查準(zhǔn)率分別為83.72%和33.96%。由于car本身的特征很多、噪聲的干擾，對(duì)實(shí)驗(yàn)的結(jié)果造成了影響。

3 結(jié)束語(yǔ)

Boosting算法收到關(guān)注的原因在于它的簡(jiǎn)單、高效。在實(shí)際應(yīng)用中，我們可以將一個(gè)弱學(xué)習(xí)算法通過(guò)Boosting將其提升為強(qiáng)學(xué)習(xí)算法，使算法精度達(dá)到提高。但Boosting也容易受到一些因素干擾如若學(xué)習(xí)器太弱、訓(xùn)練數(shù)據(jù)不足、迭代次數(shù)不合理、存在噪聲等。如何解決這些問(wèn)題，將是Boosting值得研究的方向。另外，Boosting在語(yǔ)音識(shí)別、文本分類、書(shū)寫(xiě)體字符識(shí)別等實(shí)際應(yīng)用領(lǐng)域也有廣泛的前景。

［1］ Valiant L G.A Theory of the Learnable［J］.Communicationsofthe ACM，1984，27（22）:1134－1142.

［2］ Michael Kearns and Leslie G Valiant.Learning Boolean Formulate or Finite Automata is as Hard as Factoring［R］.Technical Report TR －14－ 88 Harvard University Aiken Computation Laboratory，August，1988，28（1）:330－400.

［3］ Schapire R E.The Strength of Weak Learn-ability［J］.Machine Learning，1990，5（2）:197－227.

［4］ Freund Y.Boosting a Weak Learning Algorithm by Majority［J］.Information and Computation，1995，121（2）:256－285.

［5］ Freund Y，Schapire R E .A Decision-Theoretic Generalization of Online Learning and an Application to Boosting［J］.Journal of Computer and System Sciences，1997，55（1）:119 －139.

［6］Friedman J，Hastie T，Tibshirani R.Additive Logistic Regression［R］.A Statistical View of Boosting，1998，28（2）:330－400.

［7］ Friedman J，Hastie T，Tibshirani R.Additive Logistic Regression［R］.A Statistical View of Boosting，2000，28（2）:337－407.

［8］ SCHAPIRE R E.The Boosting Approach to Machine Learning［C］.Proceedings of MSRI Workshop on Non linear Estimation and Classification，New York，2002.