1 Motivation of Boosting
我們先來看一個簡單的識别蘋果的例子，老師展示20張圖檔，讓6歲孩子們通過觀察，判斷其中哪些圖檔的内容是蘋果。從判斷的過程中推導如何解決二進制分類問題的方法。
顯然這是一個監督式學習，20張圖檔包括它的标簽都是已知的。首先，學生Michael回答說：所有的蘋果應該是圓形的。根據Michael的判斷，對應到20張圖檔中去，大部分蘋果能被識别出來，但也有錯誤。其中錯誤包括有的蘋果不是圓形，而且圓形的水果也不一定是蘋果。如下圖所示：
上圖中藍色區域的圖檔代表分類錯誤。顯然，隻用“蘋果是圓形的”這一個條件不能保證分類效果很好。我們把藍色區域（分類錯誤的圖檔）放大，分類正确的圖檔縮小，這樣在接下來的分類中就會更加注重這些錯誤樣本。
然後，學生Tina觀察被放大的錯誤樣本和上一輪被縮小的正确樣本，回答說：蘋果應該是紅色的。根據Tina的判斷，得到的結果如下圖所示：
上圖中藍色區域的圖檔一樣代表分類錯誤，即根據這個蘋果是紅色的條件，使得青蘋果和草莓、蕃茄都出現了判斷錯誤。那麼結果就是把這些分類錯誤的樣本放大化，其它正确的樣本縮小化。同樣，這樣在接下來的分類中就會更加注重這些錯誤樣本。
接着，學生Joey經過觀察又說：蘋果也可能是綠色的。根據Joey的判斷，得到的結果如下圖所示：
上圖中藍色區域的圖檔一樣代表分類錯誤，根據蘋果是綠色的條件，使得圖中藍色區域都出現了判斷錯誤。同樣把這些分類錯誤的樣本放大化，其它正确的樣本縮小化，在下一輪判斷繼續對其修正。
後來，學生Jessica又發現：上面有梗的才是蘋果。得到如下結果：
經過這幾個同學的推論，蘋果被定義為：圓的，紅色的，也可能是綠色的，上面有梗。從一個一個的推導過程中，我們似乎得到一個較為準确的蘋果的定義。雖然可能不是非常準确，但是要比單一的條件要好得多。也就是說把所有學生對蘋果的定義融合起來，最終得到一個比較好的對蘋果的總體定義。這種做法就是我們本節課将要讨論的演算法。這些學生代表的就是簡單的hypotheses gtgt，将所有gtgt融合，得到很好的預測模型G。例如，二維平面上簡單的hypotheses（水準線和垂直線），這些簡單gtgt最終組成的較複雜的分類線能夠較好地将正負樣本完全分開，即得到了好的預測模型。
是以，上個蘋果的例子中，不同的學生代表不同的hypotheses gt；最終得到的蘋果總體定義就代表hypothesis G；而老師就代表演算法A，指導學生的注意力集中到關鍵的例子中（錯誤樣本），進而得到更好的蘋果定義。其中的數學原理，我們下一部分詳細介紹。
2 Diversity by Re-weighting
這種算法叫做Weightd Base Algorithm，目的就是最小化bootstrap-weighted error。
其實，這種weightd base algorithm我們之前就介紹過類似的算法形式。例如在soft-margin SVM中，我們引入允許犯錯的項，同樣可以将每個點的error乘以權重因子un。加上該項前的參數C，經過QP，最終得到0≤αn≤Cun，有别于之前介紹的0≤αn≤C。這裡的un相當于每個犯錯的樣本的懲罰因子，并會反映到αn的範圍限定上。
同樣在logistic regression中，同樣可以對每個犯錯誤的樣本乘以相應的un，作為懲罰因子。un表示該錯誤點出現的次數，un越大，則對應的懲罰因子越大，則在最小化error時就應該更加重視這些點。
其實這種example-weighted learning，我們在機器學習基石課程第8次筆記中就介紹過class-weighted的思想。二者道理是相通的。
知道了u的概念後，我們知道不同的u組合經過base algorithm得到不同的gt。那麼如何選取u，使得到的gt之間有很大的不同呢？之是以要讓所有的gt差别很大，是因為上節課aggregation中，我們介紹過gt越不一樣，其aggregation的效果越好，即每個人的意見越不相同，越能運用集體的智慧，得到好的預測模型。
為了得到不同的gt，我們先來看看gt和g(t+1)是怎麼得到的：
乍看上面這個式子，似乎不好求解。但是，我們對它做一些等價處理，其中分式中分子可以看成gt作用下犯錯誤的點，而分母可以看成犯錯的點和沒有犯錯誤的點的集合，即所有樣本點。其中犯錯誤的點和沒有犯錯誤的點分别用橘色方塊和綠色圓圈表示：
3 Adaptive Boosting Algorithm
但是，上述步驟還有兩個問題沒有解決，第一個問題是初始的u應為多少呢？一般來說，為了保證第一次Ein最小的話，設u=1/N即可。這樣最開始的g就能由此推導。第二個問題，最終的G(x)應該怎麼求？是将所有的g(t)合并uniform在一起嗎？一般來說并不是這樣直接uniform求解，因為g(t+1)是通過gt得來的，二者在Ein上的表現差别比較大。是以，一般是對所有的g(t)進行linear或者non-linear組合來得到G(t)。
接下來的内容，我們将對上面的第二個問題進行探讨，研究一種算法，将所有的gt進行linear組合。方法是計算gt的同時，就能計算得到其線性組合系數αt，即aggregate linearly on the fly。這種算法使最終求得g(t+1)的時候，所有gt的線性組合系數α也求得了，不用再重新計算α了。這種Linear Aggregation on the Fly算法流程為：
如何在每次疊代的時候計算αt呢？我們知道αt與ϵt是相關的：ϵt越小，對應的αt應該越大，ϵt越大，對應的αt應該越小。又因為⋄t與ϵt是正相關的，是以，αt應該是⋄t的單調函數。我們構造αt為：
αt這樣取值是有實體意義的，例如當ϵt=1/2時，error很大，跟擲骰子這樣的随機過程沒什麼兩樣，此時對應的⋄t=1，αt=0，即此gt對G沒有什麼貢獻，權重應該設為零。而當ϵt=0時，沒有error，表示該gt預測非常準，此時對應的⋄t=∞，αt=∞，即此gt對G貢獻非常大，權重應該設為無窮大。
這種算法被稱為Adaptive Boosting。它由三部分構成：base learning algorithm A，re-weighting factor ⋄t和linear aggregation αt。這三部分分别對應于我們在本節課開始介紹的例子中的Student，Teacher和Class。
對這個VC bound中的第一項Ein(G)來說，有一個很好的性質：如果滿足ϵt≤ϵ<1/2，則經過T=O(log N)次疊代之後，Ein(G)能減小到等于零的程度。而當N很大的時候，其中第二項也能變得很小。因為這兩項都能變得很小，那麼整個Eout(G)就能被限定在一個有限的上界中。
其實，這種性質也正是AdaBoost算法的精髓所在。隻要每次的ϵt≤ϵ<1/2，即所選擇的矩g比亂猜的表現好一點點，那麼經過每次疊代之後，矩g的表現都會比原來更好一些，逐漸變強，最終得到Ein=0且Eout很小。
4 Adaptive Boosting in Action
上一小節我們已經介紹了選擇一個“弱弱”的算法A（ϵt≤ϵ<1/2，比亂猜好就行），就能經過多次疊代得到Ein=0。我們稱這種形式為decision stump模型。下面介紹一個例子，來看看AdaBoost是如何使用decision stump解決實際問題的。
如下圖所示，二維平面上分布一些正負樣本點，利用decision stump來做切割。
另外一個例子，對于一個相對比較複雜的資料集，如下圖所示。它的分界線從視覺上看應該是一個sin波的形式。如果我們再使用AdaBoost算法，通過decision stump來做切割。在疊代切割100次後，得到的分界線如下所示。
可以看出，AdaBoost-Stump這種非線性模型得到的分界線對正負樣本有較好的分離效果。
課程中還介紹了一個AdaBoost-Stump在人臉識别方面的應用：
5 Summary
本節課主要介紹了Adaptive Boosting。首先通過講一個老師教國小生識别蘋果的例子，來引入Boosting的思想，即把許多“弱弱”的hypotheses合并起來，變成很強的預測模型。然後重點介紹這種算法如何實作，關鍵在于每次疊代時，給予樣本不同的系數u，宗旨是放大錯誤樣本，縮小正确樣本，得到不同的小矩g。并且在每次疊代時根據錯誤ϵ值的大小，給予不同gt不同的權重。最終由不同的gt進行組合得到整體的預測模型G。實際證明，Adaptive Boosting能夠得到有效的預測模型。