<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 8 -- Adaptive Boosting 上節課我們主要開始介紹Aggregation Models,目的是將不同的hypothesis得到的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)集合起來,利用集體智慧得到更好的預測模型G。首先我們介紹了Blending,blending是將已存在的所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)結合起來,可以是uniformly,linearly,或者non-linearly組合形式。然后,我們討論了在沒有那么多![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的情況下,使用bootstrap方式,從已有數據集中得到新的類似的數據集,從而得到不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)。這種做法稱為bagging。本節課將繼續從這些概念出發,介紹一種新的演算法。 ### **Motivation of Boosting** 我們先來看一個簡單的識別蘋果的例子,老師展示20張圖片,讓6歲孩子們通過觀察,判斷其中哪些圖片的內容是蘋果。從判斷的過程中推導如何解決二元分類問題的方法。 顯然這是一個監督式學習,20張圖片包括它的標簽都是已知的。首先,學生Michael回答說:所有的蘋果應該是圓形的。根據Michael的判斷,對應到20張圖片中去,大部分蘋果能被識別出來,但也有錯誤。其中錯誤包括有的蘋果不是圓形,而且圓形的水果也不一定是蘋果。如下圖所示: ![這里寫圖片描述](https://img.kancloud.cn/89/93/8993062f67165b55ad4ff5ab70376a7b_426x244.jpg) 上圖中藍色區域的圖片代表分類錯誤。顯然,只用“蘋果是圓形的”這一個條件不能保證分類效果很好。我們把藍色區域(分類錯誤的圖片)放大,分類正確的圖片縮小,這樣在接下來的分類中就會更加注重這些錯誤樣本。 然后,學生Tina觀察被放大的錯誤樣本和上一輪被縮小的正確樣本,回答說:蘋果應該是紅色的。根據Tina的判斷,得到的結果如下圖所示: ![這里寫圖片描述](https://img.kancloud.cn/21/08/21081be5607aa20a363036f71b304306_424x266.jpg) 上圖中藍色區域的圖片一樣代表分類錯誤,即根據這個蘋果是紅色的條件,使得青蘋果和草莓、西紅柿都出現了判斷錯誤。那么結果就是把這些分類錯誤的樣本放大化,其它正確的樣本縮小化。同樣,這樣在接下來的分類中就會更加注重這些錯誤樣本。 接著,學生Joey經過觀察又說:蘋果也可能是綠色的。根據Joey的判斷,得到的結果如下圖所示: ![這里寫圖片描述](https://img.kancloud.cn/ea/2a/ea2ada369b59f2970137e0d7c569e55d_421x268.jpg) 上圖中藍色區域的圖片一樣代表分類錯誤,根據蘋果是綠色的條件,使得圖中藍色區域都出現了判斷錯誤。同樣把這些分類錯誤的樣本放大化,其它正確的樣本縮小化,在下一輪判斷繼續對其修正。 后來,學生Jessica又發現:上面有梗的才是蘋果。得到如下結果: ![這里寫圖片描述](https://img.kancloud.cn/e6/c1/e6c120aa4c724d9b1d841d4c375503d7_403x206.jpg) 經過這幾個同學的推論,蘋果被定義為:圓的,紅色的,也可能是綠色的,上面有梗。從一個一個的推導過程中,我們似乎得到一個較為準確的蘋果的定義。雖然可能不是非常準確,但是要比單一的條件要好得多。也就是說把所有學生對蘋果的定義融合起來,最終得到一個比較好的對蘋果的總體定義。這種做法就是我們本節課將要討論的演算法。這些學生代表的就是簡單的hypotheses ![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),將所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)融合,得到很好的預測模型G。例如,二維平面上簡單的hypotheses(水平線和垂直線),這些簡單![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)最終組成的較復雜的分類線能夠較好地將正負樣本完全分開,即得到了好的預測模型。 ![這里寫圖片描述](https://img.kancloud.cn/7e/0e/7e0e2ebc3f697d21bd5edf3b92a22baf_248x245.jpg) 所以,上個蘋果的例子中,不同的學生代表不同的hypotheses ![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg);最終得到的蘋果總體定義就代表hypothesis G;而老師就代表演算法A,指導學生的注意力集中到關鍵的例子中(錯誤樣本),從而得到更好的蘋果定義。其中的數學原理,我們下一部分詳細介紹。 ![這里寫圖片描述](https://img.kancloud.cn/cb/fc/cbfcf794374b50c00c6f697f1bd9ed8d_580x110.jpg) ### **Diversity by Re-weighting** 在介紹這個演算法之前,我們先來講一下上節課就介紹過的bagging。Bagging的核心是bootstrapping,通過對原始數據集D不斷進行bootstrap的抽樣動作,得到與D類似的數據集![](https://img.kancloud.cn/1d/17/1d17d480b05935698667ef7f95e46346_20x20.jpg),每組![](https://img.kancloud.cn/1d/17/1d17d480b05935698667ef7f95e46346_20x20.jpg)都能得到相應的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),從而進行aggregation的操作。現在,假如包含四個樣本的D經過bootstrap,得到新的![](https://img.kancloud.cn/1d/17/1d17d480b05935698667ef7f95e46346_20x20.jpg)如下: ![這里寫圖片描述](https://img.kancloud.cn/aa/dd/aadd52ff179f4e9cc7fc6afa3d201e70_579x77.jpg) 那么,對于新的![](https://img.kancloud.cn/1d/17/1d17d480b05935698667ef7f95e46346_20x20.jpg),把它交給base algorithm,找出![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)最小時對應的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),如下圖右邊所示。 ![](https://img.kancloud.cn/75/2a/752ae7a2adef59ebdb82f8c802701842_200x54.jpg) 由于![](https://img.kancloud.cn/1d/17/1d17d480b05935698667ef7f95e46346_20x20.jpg)完全是D經過bootstrap得到的,其中樣本![](https://img.kancloud.cn/71/4e/714eb20038a6837666bd66a8f1cc1923_54x18.jpg)出現2次,![](https://img.kancloud.cn/9c/10/9c10a8e49ab6de105ef28ce034b6edac_54x18.jpg)出現1次,![](https://img.kancloud.cn/73/e9/73e92367fcd971b1c1c7f72e5ac24fd8_54x18.jpg)出現0次,![](https://img.kancloud.cn/3d/00/3d009501d1e734ad358451e742e364b6_54x18.jpg)出現1次。引入一個參數![](https://img.kancloud.cn/7d/26/7d2635eef468491bbf4e560245f7806d_14x11.jpg)來表示原D中第i個樣本在![](https://img.kancloud.cn/1d/17/1d17d480b05935698667ef7f95e46346_20x20.jpg)中出現的次數,如下圖左邊所示。 ![](https://img.kancloud.cn/4f/fe/4ffe18b72a2aa01a522ec17729f35a22_242x54.jpg) ![這里寫圖片描述](https://img.kancloud.cn/0b/a8/0ba82d217e961e4d8a7e68affd7df0c8_561x211.jpg) 參數u相當于是權重因子,當![](https://img.kancloud.cn/1d/17/1d17d480b05935698667ef7f95e46346_20x20.jpg)中第i個樣本出現的次數越多的時候,那么對應的![](https://img.kancloud.cn/7d/26/7d2635eef468491bbf4e560245f7806d_14x11.jpg)越大,表示在error function中對該樣本的懲罰越多。所以,從另外一個角度來看bagging,它其實就是通過bootstrap的方式,來得到這些![](https://img.kancloud.cn/7d/26/7d2635eef468491bbf4e560245f7806d_14x11.jpg)值,作為犯錯樣本的權重因子,再用base algorithn最小化包含![](https://img.kancloud.cn/7d/26/7d2635eef468491bbf4e560245f7806d_14x11.jpg)的error function,得到不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)。這個error function被稱為bootstrap-weighted error。 這種算法叫做Weightd Base Algorithm,目的就是最小化bootstrap-weighted error。 ![這里寫圖片描述](https://img.kancloud.cn/82/d7/82d7084a9382e6041c5bb7d5eba51778_580x111.jpg) 其實,這種weightd base algorithm我們之前就介紹過類似的算法形式。例如在soft-margin SVM中,我們引入允許犯錯的項,同樣可以將每個點的error乘以權重因子![](https://img.kancloud.cn/9d/fb/9dfb1eacfb8c296f4a91d2ae47171d9e_18x11.jpg)。加上該項前的參數C,經過QP,最終得到![](https://img.kancloud.cn/74/9b/749b2c15fdc82be016843fde89d112dd_110x15.jpg),有別于之前介紹的![](https://img.kancloud.cn/f4/15/f415ef1ff3d458fabf370faac6c4e59a_92x15.jpg)。這里的![](https://img.kancloud.cn/9d/fb/9dfb1eacfb8c296f4a91d2ae47171d9e_18x11.jpg)相當于每個犯錯的樣本的懲罰因子,并會反映到![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)的范圍限定上。 同樣在logistic regression中,同樣可以對每個犯錯誤的樣本乘以相應的![](https://img.kancloud.cn/9d/fb/9dfb1eacfb8c296f4a91d2ae47171d9e_18x11.jpg),作為懲罰因子。![](https://img.kancloud.cn/9d/fb/9dfb1eacfb8c296f4a91d2ae47171d9e_18x11.jpg)表示該錯誤點出現的次數,![](https://img.kancloud.cn/9d/fb/9dfb1eacfb8c296f4a91d2ae47171d9e_18x11.jpg)越大,則對應的懲罰因子越大,則在最小化error時就應該更加重視這些點。 ![這里寫圖片描述](https://img.kancloud.cn/b5/df/b5dfb857e879e91e1040aff2465e9333_560x129.jpg) 其實這種example-weighted learning,我們在機器學習基石課程第8次筆記中就介紹過class-weighted的思想。二者道理是相通的。 知道了u的概念后,我們知道不同的u組合經過base algorithm得到不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)。那么如何選取u,使得到的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)之間有很大的不同呢?之所以要讓所有的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)差別很大,是因為上節課aggregation中,我們介紹過![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)越不一樣,其aggregation的效果越好,即每個人的意見越不相同,越能運用集體的智慧,得到好的預測模型。 為了得到不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),我們先來看看![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)和![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)是怎么得到的: ![這里寫圖片描述](https://img.kancloud.cn/ce/69/ce699944f8cc1f0acffdc6a2d9e1273f_580x203.jpg) 如上所示,![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)是由![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg)得到的,![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)是由![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)得到的。如果![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)這個模型在使用![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)的時候得到的error很大,即預測效果非常不好,那就表示由![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)計算的![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)會與![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)有很大不同。而![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)與![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)差異性大正是我們希望看到的。 怎么做呢?方法是利用![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)在使用![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)的時候表現很差的條件,越差越好。如果在![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)作用下,![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)中的表現(即error)近似為0.5的時候,表明![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)對![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)的預測分類沒有什么作用,就像拋硬幣一樣,是隨機選擇的。這樣的做法就能最大限度地保證![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)會與![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)有較大的差異性。其數學表達式如下所示: ![這里寫圖片描述](https://img.kancloud.cn/48/6b/486bf0ee55fc98907eaf92fb735f1c7b_391x104.jpg) 乍看上面這個式子,似乎不好求解。但是,我們對它做一些等價處理,其中分式中分子可以看成![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)作用下犯錯誤的點,而分母可以看成犯錯的點和沒有犯錯誤的點的集合,即所有樣本點。其中犯錯誤的點和沒有犯錯誤的點分別用橘色方塊和綠色圓圈表示: ![這里寫圖片描述](https://img.kancloud.cn/dc/04/dc04eff0235b7e4bb043d38deca21317_580x109.jpg) 要讓分式等于0.5,顯然只要將犯錯誤的點和沒有犯錯誤的點的數量調成一樣就可以了。也就是說,在![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)作用下,讓犯錯的![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)數量和沒有犯錯的![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)數量一致就行(包含權重![](https://img.kancloud.cn/98/ca/98cacb74c4be64024bfabdcbd7945555_31x21.jpg))。一種簡單的方法就是利用放大和縮小的思想(本節課開始引入識別蘋果的例子中提到的放大圖片和縮小圖片就是這個目的),將犯錯誤的![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg)和沒有犯錯誤的![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg)做相應的乘積操作,使得二者值變成相等。例如![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg) of incorrect為1126,![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg) of correct為6211,要讓![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)中錯誤比例正好是0.5,可以這樣做,對于incorrect ![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg): ![](https://img.kancloud.cn/50/37/5037dcf72cf58a830dba810dd5ac629b_145x23.jpg) 對于correct ![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg): ![](https://img.kancloud.cn/d6/a8/d6a827b68bd416d235b4267dd397354e_146x23.jpg) 或者利用犯錯的比例來做,令weighted incorrect rate和weighted correct rate分別設為![](https://img.kancloud.cn/3f/4a/3f4a79a627da9dd4765ef79f22523ef4_36x37.jpg)和![](https://img.kancloud.cn/04/14/041414efc793fa81998e40c40712d763_36x37.jpg)。一般求解方式是令犯錯率為![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg),在計算![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)的時候,![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg)分別乘以![](https://img.kancloud.cn/de/1e/de1e9aaa650c3f7b1958fe593e631140_56x18.jpg)和![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/9b/70/9b70052aa33305e6bea47ae18b2cb972_580x238.jpg) ### **Adaptive Boosting Algorithm** 上一部分,我們介紹了在計算![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)的時候,![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg)分別乘以![](https://img.kancloud.cn/de/1e/de1e9aaa650c3f7b1958fe593e631140_56x18.jpg)和![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)。下面將構造一個新的尺度因子: ![](https://img.kancloud.cn/22/76/2276333cb4ec9ea6411f5ab1a5b39934_106x45.jpg) 那么引入這個新的尺度因子之后,對于錯誤的![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg),將它乘以![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg);對于正確的![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg),將它除以![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg)。這種操作跟之前介紹的分別乘以![](https://img.kancloud.cn/de/1e/de1e9aaa650c3f7b1958fe593e631140_56x18.jpg)和![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)的效果是一樣的。之所以引入![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg)是因為它告訴我們更多的物理意義。因為如果![](https://img.kancloud.cn/5d/58/5d58566443bdba637e8aca51c9b1b8de_48x37.jpg),得到![](https://img.kancloud.cn/8a/07/8a07508707c27001ecd4812a21a6e93b_48x15.jpg),那么接下來錯誤的![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg)與![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg)的乘積就相當于把錯誤點放大了,而正確的![](https://img.kancloud.cn/fc/68/fc6809bfd75d2e2b54ed2e3bb05438d6_18x21.jpg)與![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg)的相除就相當于把正確點縮小了。這種scale up incorrect和scale down correct的做法與本節課開始介紹的學生識別蘋果的例子中放大錯誤的圖片和縮小正確的圖片是一個原理,讓學生能夠將注意力更多地放在犯錯誤的點上。通過這種scaling-up incorrect的操作,能夠保證得到不同于![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/e6/65/e6659ea8582bcc6382ebd4f8cf30517a_580x223.jpg) 值得注意的是上述的結論是建立在![](https://img.kancloud.cn/5d/58/5d58566443bdba637e8aca51c9b1b8de_48x37.jpg)的基礎上,如果![](https://img.kancloud.cn/c0/03/c003d6d9f1efb5ecab26fde24ebd22ed_48x37.jpg),那么就做相反的推論即可。關于![](https://img.kancloud.cn/c0/03/c003d6d9f1efb5ecab26fde24ebd22ed_48x37.jpg)的情況,我們稍后會進行說明。 從這個概念出發,我們可以得到一個初步的演算法。其核心步驟是每次迭代時,利用![](https://img.kancloud.cn/22/76/2276333cb4ec9ea6411f5ab1a5b39934_106x45.jpg)把![](https://img.kancloud.cn/91/94/919416aaa4fa7fcfa65746f22751d19f_15x11.jpg)更新為![](https://img.kancloud.cn/71/6e/716e71a764124dcf1f22cc1679c41407_31x13.jpg)。具體迭代步驟如下: ![這里寫圖片描述](https://img.kancloud.cn/cf/69/cf69b718deff24adbd5b6f6ea2d7ad3d_580x195.jpg) 但是,上述步驟還有兩個問題沒有解決,第一個問題是初始的![](https://img.kancloud.cn/46/20/462048c0db928d4fce913ca774d0a62e_25x18.jpg)應為多少呢?一般來說,為了保證第一次![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)最小的話,設![](https://img.kancloud.cn/8c/d2/8cd2d9e50cd3d9f5688f37239e56258e_71x37.jpg)即可。這樣最開始的![](https://img.kancloud.cn/03/45/034516beaf2a48cbc168d2b4c87b89e2_15x12.jpg)就能由此推導。第二個問題,最終的G(x)應該怎么求?是將所有的g(t)合并uniform在一起嗎?一般來說并不是這樣直接uniform求解,因為![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)是通過![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)得來的,二者在![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)上的表現差別比較大。所以,一般是對所有的g(t)進行linear或者non-linear組合來得到G(t)。 ![這里寫圖片描述](https://img.kancloud.cn/aa/b1/aab148c88f785d44d7dc63978a651e85_580x106.jpg) 接下來的內容,我們將對上面的第二個問題進行探討,研究一種算法,將所有的g(t)進行linear組合。方法是計算![](https://img.kancloud.cn/e4/40/e440a560426f65dffb3508ae270ca7ff_28x18.gif)的同時,就能計算得到其線性組合系數![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg),即aggregate linearly on the fly。這種算法使最終求得![](https://img.kancloud.cn/06/8d/068d9116e004e7c136e216eb2be5b1fd_30x13.jpg)的時候,所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的線性組合系數![](https://img.kancloud.cn/38/9a/389a9983ea24ad0b3af0559c2aca381b_11x8.gif)也求得了,不用再重新計算![](https://img.kancloud.cn/38/9a/389a9983ea24ad0b3af0559c2aca381b_11x8.gif)了。這種Linear Aggregation on the Fly算法流程為: ![這里寫圖片描述](https://img.kancloud.cn/2b/12/2b12ef5ffa94407c87eaf2246776890c_579x191.jpg) 如何在每次迭代的時候計算![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)呢?我們知道![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)與![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)是相關的:![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)越小,對應的![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)應該越大,![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)越大,對應的![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)應該越小。又因為![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg)與![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)是正相關的,所以,![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)應該是![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg)的單調函數。我們構造![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)為: ![](https://img.kancloud.cn/ea/b9/eab95d02dbe9cb6140df85ed268453af_86x18.jpg) ![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)這樣取值是有物理意義的,例如當![](https://img.kancloud.cn/54/fb/54fbdc768e47362b13a62286083a2e02_48x37.jpg)時,error很大,跟擲骰子這樣的隨機過程沒什么兩樣,此時對應的![](https://img.kancloud.cn/94/1c/941cc9bf354dede942c94dcc86b0ecf2_48x13.jpg),![](https://img.kancloud.cn/ed/73/ed73b2b59c0c847094db87683a441bc5_50x15.jpg),即此![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)對G沒有什么貢獻,權重應該設為零。而當![](https://img.kancloud.cn/e3/5a/e35ae6553ddaeb0b2919d82e1dba19e0_46x15.jpg)時,沒有error,表示該![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)預測非常準,此時對應的![](https://img.kancloud.cn/77/36/7736d6d1fe8254b1f129b4710997a0cf_58x13.jpg),![](https://img.kancloud.cn/6c/1b/6c1b9454de1850aaccbac131608feb80_59x12.jpg),即此![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)對G貢獻非常大,權重應該設為無窮大。 ![這里寫圖片描述](https://img.kancloud.cn/f1/4e/f14eebf72d1ac9df5ffcac0701ba33af_580x101.jpg) 這種算法被稱為Adaptive Boosting。它由三部分構成:base learning algorithm A,re-weighting factor ![](https://img.kancloud.cn/16/ca/16caf5e492e3b97c638eda337150ecf6_15x12.jpg)和linear aggregation ![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)。這三部分分別對應于我們在本節課開始介紹的例子中的Student,Teacher和Class。 ![這里寫圖片描述](https://img.kancloud.cn/18/3f/183f794f909cc3193aa69490e3fed0df_580x77.jpg) 綜上所述,完整的adaptive boosting(AdaBoost)Algorithm流程如下: ![這里寫圖片描述](https://img.kancloud.cn/10/4f/104facb90fbc2312d74eaa22a87c5e67_580x305.jpg) 從我們之前介紹過的VC bound角度來看,AdaBoost算法理論上滿足: ![這里寫圖片描述](https://img.kancloud.cn/35/d1/35d1933f599411c86ad8d35374d5acf1_580x237.jpg) 上式中,![](https://img.kancloud.cn/da/1b/da1b53fcdf902dd29b665c1494f87625_60x18.jpg)的上界由兩部分組成,一項是![](https://img.kancloud.cn/1b/4a/1b4a817b0f973cbbe4f99c0c1701552b_53x18.jpg),另一項是模型復雜度O(*)。模型復雜度中![](https://img.kancloud.cn/4a/f3/4af352c1849155c1c6016277323ec54b_52x18.jpg)是![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的VC Dimension,T是迭代次數,可以證明G的![](https://img.kancloud.cn/bb/8e/bb8ebbb8d58c4c5eb5c1245defc47a71_22x16.jpg)服從![](https://img.kancloud.cn/0f/3d/0f3dfd1187885afe9f14386964a6b453_148x18.jpg)。 對這個VC bound中的第一項![](https://img.kancloud.cn/1b/4a/1b4a817b0f973cbbe4f99c0c1701552b_53x18.jpg)來說,有一個很好的性質:如果滿足![](https://img.kancloud.cn/f2/63/f2639afeb80b7843ea7007077045b8bd_79x37.jpg),則經過![](https://img.kancloud.cn/0a/6f/0a6f3fc34aa1491153b33a6a6028c315_110x18.jpg)次迭代之后,![](https://img.kancloud.cn/1b/4a/1b4a817b0f973cbbe4f99c0c1701552b_53x18.jpg)能減小到等于零的程度。而當N很大的時候,其中第二項也能變得很小。因為這兩項都能變得很小,那么整個![](https://img.kancloud.cn/da/1b/da1b53fcdf902dd29b665c1494f87625_60x18.jpg)就能被限定在一個有限的上界中。 其實,這種性質也正是AdaBoost算法的精髓所在。只要每次的![](https://img.kancloud.cn/f2/63/f2639afeb80b7843ea7007077045b8bd_79x37.jpg),即所選擇的矩g比亂猜的表現好一點點,那么經過每次迭代之后,矩g的表現都會比原來更好一些,逐漸變強,最終得到![](https://img.kancloud.cn/ee/11/ee1179c7ba76c387ed2d14d1f656f2c9_60x15.jpg)且![](https://img.kancloud.cn/87/b8/87b80d62d6a06ab606269c8e5d6405c2_31x15.jpg)很小。 ![這里寫圖片描述](https://img.kancloud.cn/c3/f9/c3f91d9ffc5a0287a1a7b022c79cb03c_580x77.jpg) ### **Adaptive Boosting in Action** 上一小節我們已經介紹了選擇一個“弱弱”的算法A(![](https://img.kancloud.cn/f2/63/f2639afeb80b7843ea7007077045b8bd_79x37.jpg),比亂猜好就行),就能經過多次迭代得到![](https://img.kancloud.cn/ee/11/ee1179c7ba76c387ed2d14d1f656f2c9_60x15.jpg)。我們稱這種形式為decision stump模型。下面介紹一個例子,來看看AdaBoost是如何使用decision stump解決實際問題的。 如下圖所示,二維平面上分布一些正負樣本點,利用decision stump來做切割。 ![這里寫圖片描述](https://img.kancloud.cn/7e/e3/7ee3a87e2bcd4cae233dbf3a9c4a274d_281x279.jpg) 第一步: ![這里寫圖片描述](https://img.kancloud.cn/a9/53/a953fe6af3d7aab4e82de01862dd6be3_282x278.jpg) 第二步: ![這里寫圖片描述](https://img.kancloud.cn/12/b7/12b7c3c0f69b3ec40372c74994f59bbc_283x279.jpg) 第三步: ![這里寫圖片描述](https://img.kancloud.cn/e7/60/e7607a1a5066abf6a9c6c4d10673206b_283x279.jpg) 第四步: ![這里寫圖片描述](https://img.kancloud.cn/0a/1d/0a1df9361b85ba9d4ab694caf95874f2_280x279.jpg) 第五步: ![這里寫圖片描述](https://img.kancloud.cn/b2/b5/b2b5569f2f547fe38ea5b3e26237d189_279x279.jpg) 可以看到,經過5次迭代之后,所有的正負點已經被完全分開了,則最終得到的分類線為: ![這里寫圖片描述](https://img.kancloud.cn/ff/6a/ff6aa69bea013b48f2be62ef1e18ea2b_280x278.jpg) 另外一個例子,對于一個相對比較復雜的數據集,如下圖所示。它的分界線從視覺上看應該是一個sin波的形式。如果我們再使用AdaBoost算法,通過decision stump來做切割。在迭代切割100次后,得到的分界線如下所示。 ![這里寫圖片描述](https://img.kancloud.cn/32/47/3247e34b6c2d269b75efb6c4c0f76d85_280x282.jpg) 可以看出,AdaBoost-Stump這種非線性模型得到的分界線對正負樣本有較好的分離效果。 課程中還介紹了一個AdaBoost-Stump在人臉識別方面的應用: ![這里寫圖片描述](https://img.kancloud.cn/26/87/26878d54bc0689454e3ac65b328d75aa_577x335.jpg) ### **總結** 本節課主要介紹了Adaptive Boosting。首先通過講一個老師教小學生識別蘋果的例子,來引入Boosting的思想,即把許多“弱弱”的hypotheses合并起來,變成很強的預測模型。然后重點介紹這種算法如何實現,關鍵在于每次迭代時,給予樣本不同的系數u,宗旨是放大錯誤樣本,縮小正確樣本,得到不同的小矩g。并且在每次迭代時根據錯誤![](https://img.kancloud.cn/f1/f4/f1f442a329c8d3df85dce68831d660fe_7x8.jpg)值的大小,給予不同![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)不同的權重。最終由不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)進行組合得到整體的預測模型G。實際證明,Adaptive Boosting能夠得到有效的預測模型。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看