大話AdaBoost演算法

06-24

大話AdaBoost演算法

原創聲明：本文為 SIGAI 原創文章，僅供個人學習使用，未經允許，不得轉，不能用於商業目的。

演算法的誕生

AI 39年（公元1995年），扁鵲成立了一家專治某疑難雜症的醫院，經過半年的精心籌備，硬體設施已全部到位，只缺經驗豐富的醫生前來坐診。找幾個獵頭打聽了一下，乖乖，請一個資深專家（總監頭銜的），一年的工資就得250萬。這恐怕還不夠去知名搜索引擎投放廣告！

窮則思變，扁鵲院長想來想去，找到了兩個天才的顧問，名叫Freund和Schapire，想請他們出出主意，怎樣用較低的成本解決醫生的問題。這兩位老兄想到了同一個點子：

三個臭皮匠，賽過諸葛亮

我們玩人海戰術！不如去醫學院招一批應屆生，給他們訓練一段時間然後上崗，組成一個會診小組，一起來給病人看病，集體決策。扁鵲很快招來了8個年輕的新手：

趙大夫，錢大夫，孫大夫，李大夫，周大夫，吳大夫，鄭大夫，王大夫

怎麼訓練這些新人呢？兩個顧問設計出了一套培訓方案：

1.用大量的病例讓這些新手依次學習，每個大夫自己琢磨怎樣診斷，學習結束後統計一下每個人在這些病例上的診斷準確率

2.訓練時，前面的大夫誤診的病例，後面的大夫要重點學習研究，所謂查缺補漏

3.訓練結束之後，給每個大夫打分，如果一個大夫對病例學習的越好，也就是說在這些學習的病例集上診斷的準確率越高，他在後面診斷病人時的話語權就越大

扁鵲院長跑到其他醫院買回了1萬個病例，這些病例是這樣的：

接下來培訓過程開始了。首先接受培訓的是趙大夫，經過學習總結，他摸索出了一套診斷規則，這套規則表現很不錯，至少在學慣用的病例集上，達到了70%的診斷準確率。學習完成之後，他給每一條病例調整了權重，被他誤診的病例，權重增大，診斷正確的病例，權重調小，以便於後面的醫生有重點的學習。

接下來讓錢大夫學習，他同樣學習這些病例，但重點要關注被趙大夫誤診的那些病例，經過一番訓練，錢大夫達到了75%的準確率。學習完之後，他也調整了這些病例的權重，被他誤診的病例，加大權重，否則減小權重。

後面的過程和前面類似，依次訓練孫大夫，李大夫，周大夫，吳大夫，鄭大夫，王大夫，每個大夫在學習的時候重點關注被前面的大夫誤診的病例，學習完之後調整每條病例的權重。這樣到最後，王大夫對前面這些大夫都誤診的病例特別擅長，專攻這些情況的疑難雜症！

學習期結束之後，扁鵲院長匯總出了這8個大夫的診斷準確率：

當所有大夫都培訓完成之後，就可以讓他們一起坐堂問診了。Freund和Schapire設計出了這樣一套診斷規則：來一個病人之後，8個大夫一起診斷，然後投票。如果一個大夫之前在學習時的診斷準確率為p，他在投票時的話語權是：

後面Freund和Schapire會解釋這個規則的來由。按照這個計算規則，8個大夫的話語權為：

這樣診斷結果的計算方法為，先匯總整合8個大夫的診斷結果：

在這裡對病人的診斷結果有兩種可能，陽性和陰性，我們量化表示，+1表示陽性，-1表示陰性。

最後的診斷結果是：如果上面計算出來的s值大於0，則認為是陽性，否則為陰性。

第一個病人來了，8個大夫一番診斷之後，各自給出了結果：

現在是投票集體決策的時候了。投票值為：

按照規則，這個病人被判定為陽性。醫院運營了3個月，效果出奇的好，扁鵲院長統計了一下，診斷準確率居然高達95%，不比一個資深老專家差！每個醫生一年的工資10萬，8個醫生總共才80萬，這比請一個資深專家要便宜170萬，太划算了！

這次成功之後，Freund和Schapire決定把這種方法推廣到其他行業，用於解決一些實際問題。這些行業要解決的問題都有一個特點：要做出一個決策，這個決策有兩種可能，例如銀行要根據客戶的收入、負債情況、信用記錄等信息決定給客戶貸款還是不貸款；人臉識別公司要判斷一張圖像是人臉還是不是人臉。這就是機器學習中的二分類問題，給定一個樣本數據，判斷這個樣本的類別。對於上面的疾病診斷來說，樣本數據就是病人的各項檢查數據，類別是陰性和陽性。兩位天才給這種方法取了一個名字：

AdaBoost演算法

就這樣，機器學習演算法家族中的一個年輕小夥伴誕生了，沒有想到，他後來在很多應用中都大顯身手而被載入史冊。

集成學習

AdaBoost演算法是一種集成學習（ensemble learning）方法。集成學習是機器學習中的一類方法，它對多個機器學習模型進行組合形成一個精度更高的模型，參與組合的模型稱為弱學習器（weak learner）。在預測時使用這些弱學習器模型聯合起來進行預測；訓練時需要用訓練樣本集依次訓練出這些弱學習器。典型的集成學習演算法是隨機森林和boosting演算法，而AdaBoost演算法是boosting演算法的一種實現版本。

強分類器與弱分類器

AdaBoost演算法的全稱是自適應boosting（Adaptive Boosting），是一種用於二分類問題的演算法，它用弱分類器的線性組合來構造強分類器，可以看成是前面介紹的新手大夫會診例子的抽象。

弱分類器的性能不用太好，僅比隨機猜測強，依靠它們可以構造出一個非常準確的強分類器。強分類器的計算公式為：

其中x是輸入向量，F (x)是強分類器， $f_{t}(X)$ 是弱分類器， $alpha_{t}$ 是弱分類器的權重，T為弱分類器的數量，弱分類器的輸出值為+1或-1，分別對應正樣本和負樣本。這裡的弱分類器就是上面的8位醫生，強分類器代表他們的集體決策。弱分類器的結果就是前面例子中每個醫生的診斷結果，如果一個醫生的判定結果為+1，表示病人為陽性，-1則為陰性。

分類時的判定規則為：

其中sgn是符號函數，是機器學習中經常會使用的一個函數，定義為：

強分類器的輸出值也為+1或-1，同樣對應於正樣本和負樣本，也就是醫生集體會診的結果。這裡的強分類器模型就是這就是上面的診斷規則的抽象化。弱分類器和它們的權重通過訓練演算法得到，後面我們會介紹。之所以叫弱分類器，是因為它們的精度不用太高，對於二分類問題，只要保證準確率大於0.5即可，即比隨機猜測強，隨機猜測也有50%的準確率。在上面的例子中，即使每個醫生的準確率只有60%-75%，集體決策的準確率仍然能夠達到95%以上。這種看似簡單的組合，能夠帶來演算法精度上的大幅度提升。

訓練演算法

下面來看AdaBoost演算法的模型是怎麼訓練出來的，這是訓練8位醫生過程的抽象。演算法依次訓練每一個弱分類器，並確定它們的權重值。

在這裡，訓練樣本帶有權重值，初始時所有樣本的權重相等，在訓練過程中，被前面的弱分類器錯分的樣本會加大權重，反之會減小權重，這樣接下來的弱分類器會更加關注這些難分的樣本。弱分類器的權重值根據它的準確率構造，精度越高的弱分類器權重越大。

給定 $l$ 個訓練樣本 $(x_{i},y_{i})$ ，其中 $x_{i}$ 是特徵向量， $y_{i}$ 為類別標籤，其值為+1或-1。訓練演算法的流程為：

初始化樣本權重值，所有樣本的初始權重相等：

循環，對t = 1,..., T依次訓練每個弱分類器：

訓練一個弱分類器 $f_{t}(X)$ ，並計算它對訓練樣本集的錯誤率 $e_{t}$

計算弱分類器的權重：

更新所有樣本的權重：

其中 $Z_{t}$ 為歸一化因子，它是所有樣本的權重之和：

結束循環

最後得到強分類器：

根據計算公式，錯誤率低的弱分類器權重大，它是準確率的增函數。沿用醫生集體會診的例子，如果在之前的診斷中醫生的技術更好，對病人情況的判斷更準確，那麼可以加大他在此次會診時說話的分量即權重。弱分類器在訓練樣本集上的錯誤率計算公式為：

在這裡考慮了樣本權重值。因為可以保證在訓練集上弱分類器的正確率大於0.5，所以有：

因此弱分類器的權重大於0。弱分類器的錯誤率小於0.5是能保證的，如果準確率小於0.5，只需要將弱分類器的輸出反號

即可。對於被弱分類器正確分類的樣本，有：

對於被弱分類器錯誤分類的樣本，有：

因此樣本權重更新公式可以簡化為：

由於：

它可以進一步可以簡化成：

被上一個弱分類器錯誤分類的樣本權重會增大，正確分類的樣本權重減小，訓練下一個弱分類器時演算法會關注在上一輪中被錯分的樣本。這對應於每個醫生在學習之後對病例權重的調整。給樣本加權重是有必要的，如果樣本沒有權重，每個弱分類器的訓練樣本是相同的，訓練出來的弱分類器也是一樣的，這樣訓練多個弱分類器沒有意義。AdaBoost演算法的原則是：

關注之前被錯分的樣本，準確率高的弱分類器有更大的權重。

上面的演算法中並沒有說明弱分類器是什麼樣的，具體實現時應該選擇什麼樣的分類器作為弱分類器？在實際應用時一般用深度很小的決策樹，在後面將會詳細介紹。強分類器是弱分類器的線性組合，如果弱分類器是線性函數，無論怎樣組合，強分類器都是線性的，因此應該選擇非線性的分類器做弱分類器。至此，我們介紹了AdaBoost演算法的基本原理與訓練過程，在後面的文章中，我們會介紹這種演算法的理論依據，以及其他版本的實現，在現實問題中的應用。

原創聲明：本文為 SIGAI 原創文章，僅供個人學習使用，未經允許，不能用於商業目的。