一種基于Boosting的目標識別方法

肖秦琨，錢春虎，高嵩

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

0 引言

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

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

1 算法描述

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

圖1 Boosting算法示意圖

算法步驟如下:

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

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

（3）圖像預處理:對訓練/測試圖像和目標進行歸一化處理，訓練圖像大小為［128 200］，測試圖像大小為［256 256］;

（4）創(chuàng)建特征庫:選擇8幅圖像建立特征庫，提取20個目標掩膜邊緣取樣點和目標中心的位置，每幅圖像經過4種用于圖像邊緣增強的濾波器，得到640個圖像片段gf，將得到的特征塊（Patches）存儲到特征庫中;

（5）計算特征:利用創(chuàng)建的特征庫片段gf、片段gf的位置wf來計算訓練樣本的特征值，

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

（6）采用Gentle Adaboost算法來訓練檢測器，流程圖如圖2所示:

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

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

② 設置弱分類器:

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

采用公式（4）對每個樣本更新權值:

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

采用公式（5）對每個樣本更新分類器:

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

圖2 Boosting算法訓練檢測器

（7）測試檢測器:

① 采用步驟（5）計算測試樣本的特征值;

② 將特征值代入（6）中進行迭代得到強分類器;

③ 輸出包含目標的邊界盒;

（8）評估檢測器性能:

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

算法流程圖如圖3所示。

圖3 算法流程圖

2 實驗結果與分析

實驗結果如圖4所示。

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

圖4 實驗結果

圖5 查準率－查全率曲線

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

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

3 結束語

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

［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.