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

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 11 -- Gradient Boosted Decision Tree 上節課我們主要介紹了Random Forest算法模型。Random Forest就是通過bagging的方式將許多不同的decision tree組合起來。除此之外,在decision tree中加入了各種隨機性和多樣性,比如不同特征的線性組合等。RF還可以使用OOB樣本進行self-validation,而且可以通過permutation test進行feature selection。本節課將使用Adaptive Boosting的方法來研究decision tree的一些算法和模型。 ### **Adaptive Boosted Decision Tree** Random Forest的算法流程我們上節課也詳細介紹過,就是先通過bootstrapping“復制”原樣本集D,得到新的樣本集D’;然后對每個D’進行訓練得到不同的decision tree和對應的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg);最后再將所有的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)通過uniform的形式組合起來,即以投票的方式得到G。這里采用的Bagging的方式,也就是把每個![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的預測值直接相加。現在,如果將Bagging替換成AdaBoost,處理方式有些不同。首先每輪bootstrap得到的D’中每個樣本會賦予不同的權重![](https://img.kancloud.cn/96/b1/96b1486081363aa9f8d6be8601bc1f04_24x18.jpg);然后在每個decision tree中,利用這些權重訓練得到最好的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg);最后得出每個![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)所占的權重,線性組合得到G。這種模型稱為AdaBoost-D Tree。 ![這里寫圖片描述](https://img.kancloud.cn/dd/fa/ddfadfe881dfcaed819eaea8c7cbe829_560x206.jpg) 但是在AdaBoost-DTree中需要注意的一點是每個樣本的權重![](https://img.kancloud.cn/96/b1/96b1486081363aa9f8d6be8601bc1f04_24x18.jpg)。我們知道,在Adaptive Boosting中進行了bootstrap操作,![](https://img.kancloud.cn/96/b1/96b1486081363aa9f8d6be8601bc1f04_24x18.jpg)表示D中每個樣本在D’中出現的次數。但是在決策樹模型中,例如C&RT算法中并沒有引入![](https://img.kancloud.cn/96/b1/96b1486081363aa9f8d6be8601bc1f04_24x18.jpg)。那么,如何在決策樹中引入這些權重![](https://img.kancloud.cn/96/b1/96b1486081363aa9f8d6be8601bc1f04_24x18.jpg)來得到不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)而又不改變原來的決策樹算法呢? 在Adaptive Boosting中,我們使用了weighted algorithm,形如: ![](https://img.kancloud.cn/89/f2/89f214a480805c9fb3a0fceb4abbbf2f_266x54.jpg) 每個犯錯誤的樣本點乘以相應的權重,求和再平均,最終得到了![](https://img.kancloud.cn/04/73/04735e728c53df57f112d62bf2fd02b9_49x19.jpg)。如果在決策樹中使用這種方法,將當前分支下犯錯誤的點賦予權重,每層分支都這樣做,會比較復雜,不易求解。為了簡化運算,保持決策樹算法本身的穩定性和封閉性,我們可以把決策樹算法當成一個黑盒子,即不改變其結構,不對算法本身進行修改,而從數據來源D’上做一些處理。按照這種思想,我們來看權重u實際上表示該樣本在bootstrap中出現的次數,反映了它出現的概率。那么可以根據u值,對原樣本集D進行一次重新的隨機sampling,也就是帶權重的隨機抽樣。sampling之后,會得到一個新的D’,D’中每個樣本出現的幾率與它權重u所占的比例應該是差不多接近的。因此,使用帶權重的sampling操作,得到了新的樣本數據集D’,可以直接代入決策樹進行訓練,從而無需改變決策樹算法結構。sampling可看成是bootstrap的反操作,這種對數據本身進行修改而不更改算法結構的方法非常重要! ![這里寫圖片描述](https://img.kancloud.cn/df/57/df57bbee4d969ffe826cdfd5c2208337_561x149.jpg) 所以,AdaBoost-DTree結合了AdaBoost和DTree,但是做了一點小小的改變,就是使用sampling替代權重![](https://img.kancloud.cn/96/b1/96b1486081363aa9f8d6be8601bc1f04_24x18.jpg),效果是相同的。 ![這里寫圖片描述](https://img.kancloud.cn/be/c9/bec95006c48731d52738c61a2edce9cc_389x77.jpg) 上面我們通過使用sampling,將不同的樣本集代入決策樹中,得到不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)。除此之外,我們還要確定每個![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)所占的權重![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)。之前我們在AdaBoost中已經介紹過,首先算出每個![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的錯誤率![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg),然后計算權重: ![](https://img.kancloud.cn/0e/cc/0ecc8c92250b7c043b1b081f9fabff11_185x45.jpg) 如果現在有一棵完全長成的樹(fully grown tree),由所有的樣本![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)訓練得到。若每個樣本都不相同的話,一刀刀切割分支,直到所有的![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)都被完全分開。這時候,![](https://img.kancloud.cn/e3/f4/e3f4800b6f363dfc7cc30376e111c28e_87x18.jpg),加權的![](https://img.kancloud.cn/87/78/877870c55ccf0905a0a12c35d5f0ffc1_87x19.jpg)而且![](https://img.kancloud.cn/77/39/7739dfd2d81d7bafb881b2b1a88a02de_12x11.jpg)也為0,從而得到權重![](https://img.kancloud.cn/6c/1b/6c1b9454de1850aaccbac131608feb80_59x12.jpg)。![](https://img.kancloud.cn/6c/1b/6c1b9454de1850aaccbac131608feb80_59x12.jpg)表示該![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)所占的權重無限大,相當于它一個就決定了G結構,是一種autocracy,而其它的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)對G沒有影響。 ![這里寫圖片描述](https://img.kancloud.cn/81/41/8141c2d879d3db7e37b3ef10dde1c2ef_581x122.jpg) 顯然![](https://img.kancloud.cn/6c/1b/6c1b9454de1850aaccbac131608feb80_59x12.jpg)不是我們想看到的,因為autocracy總是不好的,我們希望使用aggregation將不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)結合起來,發揮集體智慧來得到最好的模型G。首先,我們來看一下什么原因造成了![](https://img.kancloud.cn/6c/1b/6c1b9454de1850aaccbac131608feb80_59x12.jpg)。有兩個原因:一個是使用了所有的樣本![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)進行訓練;一個是樹的分支過多,fully grown。針對這兩個原因,我們可以對樹做一些修剪(pruned),比如只使用一部分樣本,這在sampling的操作中已經起到這類作用,因為必然有些樣本沒有被采樣到。除此之外,我們還可以限制樹的高度,讓分支不要那么多,從而避免樹fully grown。 ![這里寫圖片描述](https://img.kancloud.cn/fc/14/fc14659379bf7bf58cf48db892f3a799_580x87.jpg) 因此,AdaBoost-DTree使用的是pruned DTree,也就是說將這些預測效果較弱的樹結合起來,得到最好的G,避免出現autocracy。 ![這里寫圖片描述](https://img.kancloud.cn/c0/39/c039eb4b6f3abbaf7efa74174e8fd80d_390x55.jpg) 剛才我們說了可以限制樹的高度,那索性將樹的高度限制到最低,即只有1層高的時候,有什么特性呢?當樹高為1的時候,整棵樹只有兩個分支,切割一次即可。如果impurity是binary classification error的話,那么此時的AdaBoost-DTree就跟AdaBoost-Stump沒什么兩樣。也就是說AdaBoost-Stump是AdaBoost-DTree的一種特殊情況。 ![這里寫圖片描述](https://img.kancloud.cn/29/63/2963fce37b0fa0dfebef08c1e517b0b9_580x196.jpg) 值得一提是,如果樹高為1時,通常較難遇到![](https://img.kancloud.cn/e3/5a/e35ae6553ddaeb0b2919d82e1dba19e0_46x15.jpg)的情況,且一般不采用sampling的操作,而是直接將權重u代入到算法中。這是因為此時的AdaBoost-DTree就相當于是AdaBoost-Stump,而AdaBoost-Stump就是直接使用u來優化模型的。 ### **Optimization View of AdaBoost** 接下來,我們繼續將繼續探討AdaBoost算法的一些奧妙之處。我們知道AdaBoost中的權重的迭代計算如下所示: ![這里寫圖片描述](https://img.kancloud.cn/af/4f/af4f7cff87d9d6ffe34fb1d61c2aa2bd_580x104.jpg) 之前對于incorrect樣本和correct樣本,![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)的表達式不同。現在,把兩種情況結合起來,將![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)寫成一種簡化的形式: ![](https://img.kancloud.cn/6f/a7/6fa7f63b85ce7e752be82722b55cb149_374x25.jpg) 其中,對于incorrect樣本,![](https://img.kancloud.cn/4b/2a/4b2a7545a72b16b2efd0e035393f19e3_97x18.jpg),對于correct樣本,![](https://img.kancloud.cn/a9/47/a9475fd78aabc271791da4b2dce76584_97x18.jpg)。從上式可以看出,![](https://img.kancloud.cn/f2/bc/f2bc989a6a549814ab1c11cb4d2c1ac5_40x23.jpg)由![](https://img.kancloud.cn/ad/bb/adbb864976abca7b7c2007dba232a6c9_24x23.jpg)與某個常數相乘得到。所以,最后一輪更新的![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)可以寫成![](https://img.kancloud.cn/02/0e/020e3eaac7a4bbc14732aab41ade4c8e_25x23.jpg)的級聯形式,我們之前令![](https://img.kancloud.cn/41/f0/41f03381d3f2ecd78684d997995cf160_71x37.jpg),則有如下推導: ![](https://img.kancloud.cn/59/43/5943e908050d6743dbe4fe84757cd090_500x54.jpg) 上式中![](https://img.kancloud.cn/32/ad/32ada55f311f4ef7d5f84799cbcb95d1_91x54.jpg)被稱為voting score,最終的模型![](https://img.kancloud.cn/5d/8f/5d8f73bdb78cd14f074debd4ab60acb6_179x54.jpg)。可以看出,在AdaBoost中,![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)與![](https://img.kancloud.cn/d8/a5/d8a5c10f319d548774877f80227ae6d9_234x18.jpg)成正比。 ![這里寫圖片描述](https://img.kancloud.cn/43/47/4347874c1c52a48b9efe7f8f2a7a140b_580x277.jpg) 接下來我們繼續看一下voting score中蘊含了哪些內容。如下圖所示,voting score由許多![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg)乘以各自的系數![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)線性組合而成。從另外一個角度來看,我們可以把![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg)看成是對![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)的特征轉換![](https://img.kancloud.cn/4a/50/4a5061953958210449e6e589aca1dcfa_48x18.jpg),![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)就是線性模型中的權重![](https://img.kancloud.cn/49/4f/494f262c0ded99d8ddd368cee8ff26d6_17x11.jpg)。看到這里,我們回憶起之前SVM中,w與![](https://img.kancloud.cn/d6/f7/d6f7494c7fac45ea04c2bdbf85ab546d_43x18.jpg)的乘積再除以w的長度就是margin,即點到邊界的距離。另外,乘積項再與![](https://img.kancloud.cn/23/f1/23f1fdeb27de71b5e6113986f1b2bfa6_17x12.jpg)相乘,表示點的位置是在正確的那一側還是錯誤的那一側。所以,回過頭來,這里的voting score實際上可以看成是沒有正規化(沒有除以w的長度)的距離,即可以看成是該點到分類邊界距離的一種衡量。從效果上說,距離越大越好,也就是說voting score要盡可能大一些。 ![這里寫圖片描述](https://img.kancloud.cn/46/06/4606033a6f76a92b2992c52f9272ce22_580x198.jpg) 我們再來看,若voting score與![](https://img.kancloud.cn/23/f1/23f1fdeb27de71b5e6113986f1b2bfa6_17x12.jpg)相乘,則表示一個有對錯之分的距離。也就是說,如果二者相乘是負數,則表示該點在錯誤的一邊,分類錯誤;如果二者相乘是正數,則表示該點在正確的一邊,分類正確。所以,我們算法的目的就是讓![](https://img.kancloud.cn/23/f1/23f1fdeb27de71b5e6113986f1b2bfa6_17x12.jpg)與voting score的乘積是正的,而且越大越好。那么在剛剛推導的![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)中,得到![](https://img.kancloud.cn/2d/de/2ddeca3da9d92a18a782ebec2438313e_184x18.jpg)越小越好,從而得到![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)越小越好。也就是說,如果voting score表現不錯,與![](https://img.kancloud.cn/23/f1/23f1fdeb27de71b5e6113986f1b2bfa6_17x12.jpg)的乘積越大的話,那么相應的![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)應該是最小的。 ![這里寫圖片描述](https://img.kancloud.cn/29/fc/29fcb797bd4de34f2a5f8d94212807ff_579x123.jpg) 那么在AdaBoost中,隨著每輪學習的進行,每個樣本的![](https://img.kancloud.cn/ad/bb/adbb864976abca7b7c2007dba232a6c9_24x23.jpg)是逐漸減小的,直到![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)最小。以上是從單個樣本點來看的。總體來看,所有樣本的![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)之和應該也是最小的。我們的目標就是在最后一輪(T+1)學習后,讓所有樣本的![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)之和盡可能地小。![](https://img.kancloud.cn/1d/75/1d7548066e5a8dfbf0516d289453845a_45x23.jpg)之和表示為如下形式: ![這里寫圖片描述](https://img.kancloud.cn/5d/da/5dda8024f1594ca45f9915e3f63510e2_579x113.jpg) 上式中,![](https://img.kancloud.cn/32/ad/32ada55f311f4ef7d5f84799cbcb95d1_91x54.jpg)被稱為linear score,用s表示。對于0/1 error:若ys&lt;0,則![](https://img.kancloud.cn/e7/02/e702cd1077901c02dc6e66e1bc43c3d5_77x18.jpg);若ys&gt;=0,則![](https://img.kancloud.cn/04/63/04633e410c2cba66b9eeb8491d8b0721_78x18.jpg)。如下圖右邊黑色折線所示。對于上式中提到的指數error,即![](https://img.kancloud.cn/04/31/043161561a94f97651f8ef8192338d47_192x18.jpg),隨著ys的增加,error單調下降,且始終落在0/1 error折線的上面。如下圖右邊藍色曲線所示。很明顯,![](https://img.kancloud.cn/11/44/1144dfd5b347006d7cd4641dadb91ff2_95x18.jpg)可以看成是0/1 error的上界。所以,我們可以使用![](https://img.kancloud.cn/11/44/1144dfd5b347006d7cd4641dadb91ff2_95x18.jpg)來替代0/1 error,能達到同樣的效果。從這點來說,![](https://img.kancloud.cn/a2/fc/a2fc3221e8963ed30ece4be8a33a8f41_73x54.jpg)可以看成是一種error measure,而我們的目標就是讓其最小化,求出最小值時對應的各個![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)和![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/cf/26/cf26aa91471dbe69f19df55ab669896b_584x245.jpg) 下面我們來研究如何讓![](https://img.kancloud.cn/a2/fc/a2fc3221e8963ed30ece4be8a33a8f41_73x54.jpg)取得最小值,思考是否能用梯度下降(gradient descent)的方法來進行求解。我們之前介紹過gradient descent的核心是在某點處做一階泰勒展開: ![這里寫圖片描述](https://img.kancloud.cn/54/ca/54ca233fda7f9611ad49a621b1789505_580x84.jpg) 其中,![](https://img.kancloud.cn/66/37/663765e925c509b920eb6bce47a0fa24_18x11.jpg)是泰勒展開的位置,v是所要求的下降的最好方向,它是梯度![](https://img.kancloud.cn/16/61/16615697e7323ee439d71d6327df1c89_73x18.jpg)的反方向,而![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)是每次前進的步長。則每次沿著當前梯度的反方向走一小步,就會不斷逼近谷底(最小值)。這就是梯度下降算法所做的事情。 現在,我們對![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)做梯度下降算法處理,區別是這里的方向是一個函數![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),而不是一個向量![](https://img.kancloud.cn/66/37/663765e925c509b920eb6bce47a0fa24_18x11.jpg)。其實,函數和向量的唯一區別就是一個下標是連續的,另一個下標是離散的,二者在梯度下降算法應用上并沒有大的區別。因此,按照梯度下降算法的展開式,做出如下推導: ![這里寫圖片描述](https://img.kancloud.cn/38/c3/38c3debbd100a0ec90ed6449c689c9c2_581x222.jpg) 上式中,![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)表示當前的方向,它是一個矩,![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)是沿著當前方向前進的步長。我們要求出這樣的![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)和![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg),使得![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)是在不斷減小的。當![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)取得最小值的時候,那么所有的方向即最佳的![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)和![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)就都解出來了。上述推導使用了在![](https://img.kancloud.cn/e0/31/e0314ba7c7f9a6438652d768620b10c6_116x18.jpg)處的一階泰勒展開近似。這樣經過推導之后,![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)被分解為兩個部分,一個是前N個u之和![](https://img.kancloud.cn/5c/35/5c35c50e3c73d3aafe97ff22ff17ebbe_53x54.jpg),也就是當前所有的![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)之和;另外一個是包含下一步前進的方向![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)和步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)的項![](https://img.kancloud.cn/96/d3/96d3e15af13d3173083fb8765f619546_140x54.jpg)。![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)的這種形式與gradient descent的形式基本是一致的。 那么接下來,如果要最小化![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)的話,就要讓第二項![](https://img.kancloud.cn/96/d3/96d3e15af13d3173083fb8765f619546_140x54.jpg)越小越好。則我們的目標就是找到一個好的![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)(即好的方向)來最小化![](https://img.kancloud.cn/3c/c4/3cc4a60fa154bd94ed988afbfe4501b9_142x54.jpg),此時先忽略步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/39/d0/39d0f3c530689f1e1289f91f0d31a3b9_578x39.jpg) 對于binary classification,![](https://img.kancloud.cn/23/f1/23f1fdeb27de71b5e6113986f1b2bfa6_17x12.jpg)和![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)均限定取值-1或+1兩種。我們對![](https://img.kancloud.cn/3c/c4/3cc4a60fa154bd94ed988afbfe4501b9_142x54.jpg)做一些推導和平移運算: ![這里寫圖片描述](https://img.kancloud.cn/46/36/46368e9a2075d287af2e3ecbd2b39fb1_580x276.jpg) 最終![](https://img.kancloud.cn/3c/c4/3cc4a60fa154bd94ed988afbfe4501b9_142x54.jpg)化簡為兩項組成,一項是![](https://img.kancloud.cn/16/bc/16bc1164d80fb19b45a7b3fc0c081b09_70x54.jpg);另一項是![](https://img.kancloud.cn/fb/20/fb203e05885655252832f3512afa6503_100x25.jpg)。則最小化![](https://img.kancloud.cn/3c/c4/3cc4a60fa154bd94ed988afbfe4501b9_142x54.jpg)就轉化為最小化![](https://img.kancloud.cn/a3/78/a3780c5f74844847a9acf6ed7217e4ab_60x25.jpg)。要讓![](https://img.kancloud.cn/a3/78/a3780c5f74844847a9acf6ed7217e4ab_60x25.jpg)最小化,正是由AdaBoost中的base algorithm所做的事情。所以說,AdaBoost中的base algorithm正好幫我們找到了梯度下降中下一步最好的函數方向。 ![這里寫圖片描述](https://img.kancloud.cn/e4/44/e444a06c77f432b0804715bafc119a2c_387x30.jpg) 以上就是從數學上,從gradient descent角度驗證了AdaBoost中使用base algorithm得到的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)就是讓![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)減小的方向,只不過這個方向是一個函數而不是向量。 在解決了方向問題后,我們需要考慮步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)如何選取。方法是在確定方向![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)后,選取合適的![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg),使![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)取得最小值。也就是說,把![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)看成是步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)的函數,目標是找到![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)最小化時對應的![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)值。 ![這里寫圖片描述](https://img.kancloud.cn/ff/bd/ffbdea3374e5a91d9ca78ed761cd8549_580x112.jpg) 目的是找到在最佳方向上的最大步進長度,也就是steepest decent。我們先把![](https://img.kancloud.cn/c4/ad/c4adf360d3f73f863dadd8b2f7ac8c07_44x19.jpg)表達式寫下來: ![](https://img.kancloud.cn/75/9a/759a8d525a298add8fa03e5b5e67ce6d_252x54.jpg) 上式中,有兩種情況需要考慮: * **![](https://img.kancloud.cn/a1/8e/a18ee9f7e0160b8891627f17b12db95d_87x18.jpg):![](https://img.kancloud.cn/9f/2d/9f2d13f149fb835966b4efd1b13c43e7_90x23.jpg) correct** * **![](https://img.kancloud.cn/0b/4d/0b4da1f185aaf06d7ee806d6594d4541_87x18.jpg):![](https://img.kancloud.cn/bd/a9/bda9fc97de291c24dadf0e09af7d951c_90x23.jpg) incorrect** 經過推導,可得: ![](https://img.kancloud.cn/ad/9e/ad9e263497a5e1bb6d22decda2c2a49b_392x54.jpg) ![這里寫圖片描述](https://img.kancloud.cn/e5/b7/e5b7f280791fb951a927c4ae2364e63d_581x176.jpg) 然后對![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)求導,令![](https://img.kancloud.cn/b7/af/b7afe85300f2d8650d0e5e1019c00064_90x45.jpg),得: ![](https://img.kancloud.cn/ea/8d/ea8d6d301d39f974e14ebc8b9b71dc91_161x45.jpg) 由此看出,最大的步進長度就是![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg),即AdaBoost中計算![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)所占的權重。所以,AdaBoost算法所做的其實是在gradient descent上找到下降最快的方向和最大的步進長度。這里的方向就是![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),它是一個函數,而步進長度就是![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)。也就是說,在AdaBoost中確定![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)和![](https://img.kancloud.cn/61/cd/61cd484a3def0840e0d3a201a1b9ae83_16x11.jpg)的過程就相當于在gradient descent上尋找最快的下降方向和最大的步進長度。 ### **Gradient Boosting** 前面我們從gradient descent的角度來重新介紹了AdaBoost的最優化求解方法。整個過程可以概括為: ![這里寫圖片描述](https://img.kancloud.cn/b9/19/b9192aa1d4e870330e5875458727743b_580x145.jpg) 以上是針對binary classification問題。如果往更一般的情況進行推廣,對于不同的error function,比如logistic error function或者regression中的squared error function,那么這種做法是否仍然有效呢?這種情況下的GradientBoost可以寫成如下形式: ![這里寫圖片描述](https://img.kancloud.cn/53/65/536589dab9492eb64eb0e09f408971cd_580x146.jpg) 仍然按照gradient descent的思想,上式中,![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)是下一步前進的方向,![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)是步進長度。此時的error function不是前面所講的exp了,而是任意的一種error function。因此,對應的hypothesis也不再是binary classification,最常用的是實數輸出的hypothesis,例如regression。最終的目標也是求解最佳的前進方向![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)和最快的步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/8a/14/8a149fcd3f0dcab3ccdb2fd8231e7aa7_390x55.jpg) 接下來,我們就來看看如何求解regression的GradientBoost問題。它的表達式如下所示: ![這里寫圖片描述](https://img.kancloud.cn/61/35/6135280adf7df096651bbb986adc3cc0_580x111.jpg) 利用梯度下降的思想,我們把上式進行一階泰勒展開,寫成梯度的形式: ![這里寫圖片描述](https://img.kancloud.cn/91/5e/915e2c1713c1a6c3437d1ba30196a211_580x152.jpg) 上式中,由于regression的error function是squared的,所以,對s的導數就是![](https://img.kancloud.cn/6c/52/6c522df0f3b2af3f9c59b85bc7d12e6e_79x18.jpg)。其中標注灰色的部分表示常數,對最小化求解并沒有影響,所以可以忽略。很明顯,要使上式最小化,只要令![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)是梯度![](https://img.kancloud.cn/6c/52/6c522df0f3b2af3f9c59b85bc7d12e6e_79x18.jpg)的反方向就行了,即![](https://img.kancloud.cn/4f/03/4f03feaec1f0b036d4fe5fad03a2275e_159x18.jpg)。但是直接這樣賦值,并沒有對![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)的大小進行限制,一般不直接利用這個關系求出![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/ef/8d/ef8dd4745f7dc701ca3951aa9a6c3efe_580x49.jpg) 實際上![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)的大小并不重要,因為有步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)。那么,我們上面的最小化問題中需要對![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)的大小做些限制。限制![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)的一種簡單做法是把![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)的大小當成一個懲罰項(![](https://img.kancloud.cn/06/f6/06f602e24bd11f8d70f9336ba37c338c_48x20.jpg))添加到上面的最小化問題中,這種做法與regularization類似。如下圖所示,經過推導和整理,忽略常數項,我們得到最關心的式子是: ![](https://img.kancloud.cn/66/d3/66d31f2711ea28d69f2c32a3f1325b73_238x54.jpg) 上式是一個完全平方項之和,![](https://img.kancloud.cn/3a/3a/3a3a2ed5b3fc34cb5a363890c0f15085_56x12.jpg)表示當前第n個樣本真實值和預測值的差,稱之為余數。余數表示當前預測能夠做到的效果與真實值的差值是多少。那么,如果我們想要讓上式最小化,求出對應的![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)的話,只要讓![](https://img.kancloud.cn/52/37/5237cc8b14bcc25d13b54be9732c27e2_41x18.jpg)盡可能地接近余數![](https://img.kancloud.cn/3a/3a/3a3a2ed5b3fc34cb5a363890c0f15085_56x12.jpg)即可。在平方誤差上盡可能接近其實很簡單,就是使用regression的方法,對所有N個點![](https://img.kancloud.cn/13/bb/13bb270e90d4438874604745d28cbdd9_96x18.jpg)做squared-error的regression,得到的回歸方程就是我們要求的![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/44/d3/44d3a66207103ff4e66358d0c5b195b1_580x253.jpg) 以上就是使用GradientBoost的思想來解決regression問題的方法,其中應用了一個非常重要的概念,就是余數![](https://img.kancloud.cn/3a/3a/3a3a2ed5b3fc34cb5a363890c0f15085_56x12.jpg)。根據這些余數做regression,得到好的矩![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg),方向函數![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg)也就是由余數決定的。 ![這里寫圖片描述](https://img.kancloud.cn/54/b8/54b8f4d17471a93c620dc5cc2dcef41d_390x55.jpg) 在求出最好的方向函數![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg)之后,就要來求相應的步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)。表達式如下: ![這里寫圖片描述](https://img.kancloud.cn/4e/1d/4e1d8af9c0f0643ee8ddd5d6e927e4eb_580x137.jpg) 同樣,對上式進行推導和化簡,得到如下表達式: ![這里寫圖片描述](https://img.kancloud.cn/bb/5a/bb5aeb91c9b1106f58da9fd7e0a11bcf_580x131.jpg) 上式中也包含了余數![](https://img.kancloud.cn/3a/3a/3a3a2ed5b3fc34cb5a363890c0f15085_56x12.jpg),其中![](https://img.kancloud.cn/fd/dc/fddc1fe62e2f741c1a410522d70f45a9_46x18.jpg)可以看成是![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)的特征轉換,是已知量。那么,如果我們想要讓上式最小化,求出對應的![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)的話,只要讓![](https://img.kancloud.cn/3c/70/3c70b47c1cecbf0d22aca0d9c853360a_55x18.jpg)盡可能地接近余數![](https://img.kancloud.cn/3a/3a/3a3a2ed5b3fc34cb5a363890c0f15085_56x12.jpg)即可。顯然,這也是一個regression問題,而且是一個很簡單的形如y=ax的線性回歸,只有一個未知數![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)。只要對所有N個點![](https://img.kancloud.cn/75/59/755922c6b383f29532deede77721383b_133x18.jpg)做squared-error的linear regression,利用梯度下降算法就能得到最佳的![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)。 將上述這些概念合并到一起,我們就得到了一個最終的演算法Gradient Boosted Decision Tree(GBDT)。可能有人會問,我們剛才一直沒有說到Decison Tree,只是講到了GradientBoost啊?下面我們來看看Decison Tree究竟是在哪出現并使用的。其實剛剛我們在計算方向函數![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的時候,是對所有N個點![](https://img.kancloud.cn/13/bb/13bb270e90d4438874604745d28cbdd9_96x18.jpg)做squared-error的regression。那么這個回歸算法就可以是決策樹C&RT模型(決策樹也可以用來做regression)。這樣,就引入了Decision Tree,并將GradientBoost和Decision Tree結合起來,構成了真正的GBDT算法。GBDT算法的基本流程圖如下所示: ![這里寫圖片描述](https://img.kancloud.cn/2a/f5/2af571bcf0bc306ca2e2b354827f5f0a_580x237.jpg) 值得注意的是,![](https://img.kancloud.cn/dd/b4/ddb420243a0a90f9e1b8110eac2e7b25_16x11.jpg)的初始值一般均設為0,即![](https://img.kancloud.cn/5d/d9/5dd9f3ced8cf16c37b54ddaed8dbd7f2_179x16.jpg)。每輪迭代中,方向函數![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)通過C&RT算法做regression,進行求解;步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)通過簡單的單參數線性回歸進行求解;然后每輪更新![](https://img.kancloud.cn/dd/b4/ddb420243a0a90f9e1b8110eac2e7b25_16x11.jpg)的值,即![](https://img.kancloud.cn/72/6c/726c20cb88edf3c2b9d4b00546f5902a_147x18.jpg)。T輪迭代結束后,最終得到![](https://img.kancloud.cn/06/db/06db451c3cc01494e8887a363fdc97a0_146x54.jpg)。 值得一提的是,本節課第一部分介紹的AdaBoost-DTree是解決binary classification問題,而此處介紹的GBDT是解決regression問題。二者具有一定的相似性,可以說GBDT就是AdaBoost-DTree的regression版本。 ![這里寫圖片描述](https://img.kancloud.cn/3d/d4/3dd421a27bd4821719d013e133009ead_388x53.jpg) ### **Summary of Aggregation Models** 從機器學習技法課程的第7節課筆記到現在的第11節課筆記,我們已經介紹完所有的aggregation模型了。接下來,我們將對這些內容進行一個簡單的總結和概括。 首先,我們介紹了blending。blending就是將所有已知的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg) aggregate結合起來,發揮集體的智慧得到G。值得注意的一點是這里的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)都是已知的。blending通常有三種形式: * **uniform:簡單地計算所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的平均值** * **non-uniform:所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的線性組合** * **conditional:所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的非線性組合** 其中,uniform采用投票、求平均的形式更注重穩定性;而non-uniform和conditional追求的更復雜準確的模型,但存在過擬合的危險。 ![這里寫圖片描述](https://img.kancloud.cn/9a/ce/9ace96b91a7c3d6b174d32656665edc2_584x249.jpg) 剛才講的blending是建立在所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)已知的情況。那如果所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)未知的情況,對應的就是learning模型,做法就是一邊學![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),一邊將它們結合起來。learning通常也有三種形式(與blending的三種形式一一對應): * **Bagging:通過bootstrap方法,得到不同![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),計算所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的平均值** * **AdaBoost:通過bootstrap方法,得到不同![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的線性組合** * **Decision Tree:通過數據分割的形式得到不同的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg),所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)的非線性組合** 然后,本節課我們將AdaBoost延伸到另一個模型GradientBoost。對于regression問題,GradientBoost通過residual fitting的方式得到最佳的方向函數![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)和步進長度![](https://img.kancloud.cn/ea/7b/ea7be4a5cce8f4286fbf9fa894a62760_9x12.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/dd/24/dd243e50c3fb000204fdb48e556ce388_584x373.jpg) 除了這些基本的aggregation模型之外,我們還可以把某些模型結合起來得到新的aggregation模型。例如,Bagging與Decision Tree結合起來組成了Random Forest。Random Forest中的Decision Tree是比較“茂盛”的樹,即每個樹的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)都比較強一些。AdaBoost與Decision Tree結合組成了AdaBoost-DTree。AdaBoost-DTree的Decision Tree是比較“矮弱”的樹,即每個樹的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)都比較弱一些,由AdaBoost將所有弱弱的樹結合起來,讓綜合能力更強。同樣,GradientBoost與Decision Tree結合就構成了經典的算法GBDT。 ![這里寫圖片描述](https://img.kancloud.cn/c0/3c/c03c4348512ceda6ad30c9f447a35102_585x338.jpg) Aggregation的核心是將所有的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)結合起來,融合到一起,即集體智慧的思想。這種做法之所以能得到很好的模型G,是因為aggregation具有兩個方面的優點:cure underfitting和cure overfitting。 第一,aggregation models有助于防止欠擬合(underfitting)。它把所有比較弱的![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)結合起來,利用集體智慧來獲得比較好的模型G。aggregation就相當于是feature transform,來獲得復雜的學習模型。 第二,aggregation models有助于防止過擬合(overfitting)。它把所有![](https://img.kancloud.cn/7f/6b/7f6b19f632c7de7dc0365d013fa05113_14x12.jpg)進行組合,容易得到一個比較中庸的模型,類似于SVM的large margin一樣的效果,從而避免一些極端情況包括過擬合的發生。從這個角度來說,aggregation起到了regularization的效果。 由于aggregation具有這兩個方面的優點,所以在實際應用中aggregation models都有很好的表現。 ![這里寫圖片描述](https://img.kancloud.cn/ef/3f/ef3f14d2294412c4de5e233eac5f5bd2_565x366.jpg) ### **總結** 本節課主要介紹了Gradient Boosted Decision Tree。首先講如何將AdaBoost與Decision Tree結合起來,即通過sampling和pruning的方法得到AdaBoost-D Tree模型。然后,我們從optimization的角度來看AdaBoost,找到好的hypothesis也就是找到一個好的方向,找到權重![](https://img.kancloud.cn/38/9a/389a9983ea24ad0b3af0559c2aca381b_11x8.gif)也就是找到合適的步進長度。接著,我們從binary classification的0/1 error推廣到其它的error function,從Gradient Boosting角度推導了regression的squared error形式。Gradient Boosting其實就是不斷迭代,做residual fitting。并將其與Decision Tree算法結合,得到了經典的GBDT算法。最后,我們將所有的aggregation models做了總結和概括,這些模型有的能防止欠擬合有的能防止過擬合,應用十分廣泛。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
                  <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>

                              哎呀哎呀视频在线观看