<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國際加速解決方案。 廣告
                # 2 -- Dual Support Vector Machine 上節課我們主要介紹了線性支持向量機(Linear Support Vector Machine)。Linear SVM的目標是找出最“胖”的分割線進行正負類的分離,方法是使用二次規劃來求出分類線。本節課將從另一個方面入手,研究對偶支持向量機(Dual Support Vector Machine),嘗試從新的角度計算得出分類線,推廣SVM的應用范圍。 ### **Motivation of Dual SVM** 首先,我們回顧一下,對于非線性SVM,我們通常可以使用非線性變換將變量從x域轉換到z域中。然后,在z域中,根據上一節課的內容,使用線性SVM解決問題即可。上一節課我們說過,使用SVM得到large-margin,減少了有效的VC Dimension,限制了模型復雜度;另一方面,使用特征轉換,目的是讓模型更復雜,減小![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)。所以說,非線性SVM是把這兩者目的結合起來,平衡這兩者的關系。那么,特征轉換下,求解QP問題在z域中的維度設為![](https://img.kancloud.cn/24/66/2466d0b5e92ac36c3835bccfb1c1ba01_40x19.jpg),如果模型越復雜,則![](https://img.kancloud.cn/24/66/2466d0b5e92ac36c3835bccfb1c1ba01_40x19.jpg)越大,相應求解這個QP問題也變得很困難。當![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)無限大的時候,問題將會變得難以求解,那么有沒有什么辦法可以解決這個問題呢?一種方法就是使SVM的求解過程不依賴![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg),這就是我們本節課所要討論的主要內容。 ![這里寫圖片描述](https://img.kancloud.cn/cb/9b/cb9b7ecb8cfa9e10eded2534d88ac3bb_578x219.jpg) 比較一下,我們上一節課所講的Original SVM二次規劃問題的變量個數是![](https://img.kancloud.cn/24/66/2466d0b5e92ac36c3835bccfb1c1ba01_40x19.jpg),有N個限制條件;而本節課,我們把問題轉化為對偶問題(’Equivalent’ SVM),同樣是二次規劃,只不過變量個數變成N個,有N+1個限制條件。這種對偶SVM的好處就是問題只跟N有關,與![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)無關,這樣就不存在上文提到的當![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)無限大時難以求解的情況。 ![這里寫圖片描述](https://img.kancloud.cn/62/ee/62ee76e5a4ad4bbad66de628e7ca7ae4_562x114.jpg) 如何把問題轉化為對偶問題(’Equivalent’ SVM),其中的數學推導非常復雜,本文不做詳細數學論證,但是會從概念和原理上進行簡單的推導。 還記得我們在《機器學習基石》課程中介紹的Regularization中,在最小化![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)的過程中,也添加了限制條件:![](https://img.kancloud.cn/9f/23/9f23c7d811876d26cb3739761398ff31_75x19.jpg)。我們的求解方法是引入拉格朗日因子![](https://img.kancloud.cn/99/d3/99d394e7d0b74248114405067e0ffd51_10x12.jpg),將有條件的最小化問題轉換為無條件的最小化問題:![](https://img.kancloud.cn/1f/e6/1fe6338ce9e26bb7b3c66ac24176b726_256x37.jpg),最終得到的w的最優化解為: ![](https://img.kancloud.cn/86/0a/860a5c37eecb88419b0b5ac0ed0b297e_160x37.jpg) 所以,在regularization問題中,![](https://img.kancloud.cn/99/d3/99d394e7d0b74248114405067e0ffd51_10x12.jpg)是已知常量,求解過程變得容易。那么,對于dual SVM問題,同樣可以引入![](https://img.kancloud.cn/99/d3/99d394e7d0b74248114405067e0ffd51_10x12.jpg),將條件問題轉換為非條件問題,只不過![](https://img.kancloud.cn/99/d3/99d394e7d0b74248114405067e0ffd51_10x12.jpg)是未知參數,且個數是N,需要對其進行求解。 ![這里寫圖片描述](https://img.kancloud.cn/79/6b/796b8aee99ffb3a033f6308f0e04c5df_601x303.jpg) 如何將條件問題轉換為非條件問題?上一節課我們介紹的SVM中,目標是:![](https://img.kancloud.cn/a6/34/a634056179e81cd951048000a7d43742_88x37.jpg),條件是:![](https://img.kancloud.cn/e8/6d/e86dc21a504398ffa3b117fd57be993f_303x20.jpg)。首先,我們令拉格朗日因子為![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)(區別于regularization),構造一個函數: ![](https://img.kancloud.cn/ea/55/ea558d0fc7a70023dc49922f22267df5_365x54.jpg) 這個函數右邊第一項是SVM的目標,第二項是SVM的條件和拉格朗日因子![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)的乘積。我們把這個函數稱為拉格朗日函數,其中包含三個參數:b,w,![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/19/34/19346d0809789e03e1eaa34e283de52d_578x183.jpg) 下面,我們利用拉格朗日函數,把SVM構造成一個非條件問題: ![這里寫圖片描述](https://img.kancloud.cn/ca/f6/caf64e8b4973d59c495144b622690a97_584x181.jpg) 該最小化問題中包含了最大化問題,怎么解釋呢?首先我們規定拉格朗日因子![](https://img.kancloud.cn/b5/f5/b5f51e0deae07262becef971a1b3e967_54x15.jpg),根據SVM的限定條件可得:![](https://img.kancloud.cn/f7/3a/f73aa4f0c7e9548cf1cf77cc4a0fb677_179x20.jpg),如果沒有達到最優解,即有不滿足![](https://img.kancloud.cn/f7/3a/f73aa4f0c7e9548cf1cf77cc4a0fb677_179x20.jpg)的情況,因為![](https://img.kancloud.cn/b5/f5/b5f51e0deae07262becef971a1b3e967_54x15.jpg),那么必然有![](https://img.kancloud.cn/f5/22/f522ebd228ab977fed978df5018cdaa5_228x38.jpg)。對于這種大于零的情況,其最大值是無解的。如果對于所有的點,均滿足![](https://img.kancloud.cn/f7/3a/f73aa4f0c7e9548cf1cf77cc4a0fb677_179x20.jpg),那么必然有![](https://img.kancloud.cn/38/da/38dae2db4ef4206d14596be0a5fa4ffe_228x38.jpg),則當![](https://img.kancloud.cn/8f/d0/8fd02a864a38b4cadb02151818847428_228x38.jpg)時,其有最大值,最大值就是我們SVM的目標:![](https://img.kancloud.cn/2e/0b/2e0bc9f87024e163c5d5f0e8a1f004ab_47x37.jpg)。因此,這種轉化為非條件的SVM構造函數的形式是可行的。 ### **Lagrange Dual SVM** 現在,我們已經將SVM問題轉化為與拉格朗日因子![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)有關的最大最小值形式。已知![](https://img.kancloud.cn/b5/f5/b5f51e0deae07262becef971a1b3e967_54x15.jpg),那么對于任何固定的![](https://img.kancloud.cn/27/21/2721304880bc953c5150ce330dd39876_16x14.jpg),且![](https://img.kancloud.cn/90/32/90326549e1884e5a3f0560738002fead_54x19.jpg),一定有如下不等式成立: ![這里寫圖片描述](https://img.kancloud.cn/e4/04/e404b90bb858b441ab88ce097a1827d2_672x117.jpg) 對上述不等式右邊取最大值,不等式同樣成立: ![這里寫圖片描述](https://img.kancloud.cn/93/70/9370a241135423682bbb54056c9c0504_644x147.jpg) 上述不等式表明,我們對SVM的min和max做了對調,滿足這樣的關系,這叫做Lagrange dual problem。不等式右邊是SVM問題的下界,我們接下來的目的就是求出這個下界。 已知![](https://img.kancloud.cn/33/5a/335afd255d70f490f73e2c524c6a5b8c_12x15.jpg)是一種弱對偶關系,在二次規劃QP問題中,如果滿足以下三個條件: * **函數是凸的(convex primal)** * **函數有解(feasible primal)** * **條件是線性的(linear constraints)** 那么,上述不等式關系就變成強對偶關系,![](https://img.kancloud.cn/33/5a/335afd255d70f490f73e2c524c6a5b8c_12x15.jpg)變成=,即一定存在滿足條件的解![](https://img.kancloud.cn/b1/79/b1794176b3bd398dcae5bf0baa19356d_61x18.jpg),使等式左邊和右邊都成立,SVM的解就轉化為右邊的形式。 經過推導,SVM對偶問題的解已經轉化為無條件形式: ![這里寫圖片描述](https://img.kancloud.cn/12/ab/12ab33342a72a4e34c4127ecbf77b629_650x159.jpg) 其中,上式括號里面的是對拉格朗日函數![](https://img.kancloud.cn/35/8f/358f56dc61167ef25a7324c767ec70a1_74x18.jpg)計算最小值。那么根據梯度下降算法思想:最小值位置滿足梯度為零。首先,令![](https://img.kancloud.cn/35/8f/358f56dc61167ef25a7324c767ec70a1_74x18.jpg)對參數b的梯度為零: ![](https://img.kancloud.cn/d4/6c/d46c3e2b8f65f210626cf4867285acc0_227x54.jpg) 也就是說,最優解一定滿足![](https://img.kancloud.cn/be/bf/bebf63f273fc57ac9f0b34f71b4663ab_99x54.jpg)。那么,我們把這個條件代入計算max條件中(與![](https://img.kancloud.cn/b5/f5/b5f51e0deae07262becef971a1b3e967_54x15.jpg)同為條件),并進行化簡: ![這里寫圖片描述](https://img.kancloud.cn/14/0a/140a7147179683b3d4266634d12cda03_645x85.jpg) 這樣,SVM表達式消去了b,問題化簡了一些。然后,再根據最小值思想,令![](https://img.kancloud.cn/35/8f/358f56dc61167ef25a7324c767ec70a1_74x18.jpg)對參數w的梯度為零: ![](https://img.kancloud.cn/3b/3f/3b3f077b55913b7f920a6330797cd2dd_255x54.jpg) 即得到: ![](https://img.kancloud.cn/69/7f/697f3951f299861336f447ed402ba84f_120x54.jpg) 也就是說,最優解一定滿足![](https://img.kancloud.cn/69/7f/697f3951f299861336f447ed402ba84f_120x54.jpg)。那么,同樣我們把這個條件代入并進行化簡: ![這里寫圖片描述](https://img.kancloud.cn/fb/38/fb38edcf567b9d76754d6da2d0c118bb_642x159.jpg) 這樣,SVM表達式消去了w,問題更加簡化了。這時候的條件有3個: * all ![](https://img.kancloud.cn/b5/f5/b5f51e0deae07262becef971a1b3e967_54x15.jpg) * ![](https://img.kancloud.cn/be/bf/bebf63f273fc57ac9f0b34f71b4663ab_99x54.jpg) * ![](https://img.kancloud.cn/69/7f/697f3951f299861336f447ed402ba84f_120x54.jpg) SVM簡化為只有![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)的最佳化問題,即計算滿足上述三個條件下,函數![](https://img.kancloud.cn/35/2a/352a541bc3bf7b6265f4844e30bff2f8_211x54.jpg)最小值時對應的![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)是多少。 總結一下,SVM最佳化形式轉化為只與![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)有關: ![這里寫圖片描述](https://img.kancloud.cn/d7/11/d711c1d1215fd8b2ead56f8b52e12616_524x81.jpg) 其中,滿足最佳化的條件稱之為Karush-Kuhn-Tucker(KKT): ![這里寫圖片描述](https://img.kancloud.cn/96/2c/962c325d798c68c192d5502298f8a79c_697x308.jpg) 在下一部分中,我們將利用KKT條件來計算最優化問題中的![](https://img.kancloud.cn/38/9a/389a9983ea24ad0b3af0559c2aca381b_11x8.gif),進而得到b和w。 ### **Solving Dual SVM** 上面我們已經得到了dual SVM的簡化版了,接下來,我們繼續對它進行一些優化。首先,將max問題轉化為min問題,再做一些條件整理和推導,得到: ![這里寫圖片描述](https://img.kancloud.cn/5f/1d/5f1de7b19c1ce69dca23199adfe09439_684x282.jpg) 顯然,這是一個convex的QP問題,且有N個變量![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg),限制條件有N+1個。則根據上一節課講的QP解法,找到Q,p,A,c對應的值,用軟件工具包進行求解即可。 ![這里寫圖片描述](https://img.kancloud.cn/47/8f/478f3aaa20f04cc49166d1b5c8816cf3_674x342.jpg) 求解過程很清晰,但是值得注意的是,![](https://img.kancloud.cn/5b/06/5b06daaec74914ea56876d5428c773d7_133x22.jpg),大部分值是非零的,稱為dense。當N很大的時候,例如N=30000,那么對應的![](https://img.kancloud.cn/a4/40/a44019d660c0f6396c74f2640a75b215_25x16.jpg)的計算量將會很大,存儲空間也很大。所以一般情況下,對dual SVM問題的矩陣![](https://img.kancloud.cn/a4/40/a44019d660c0f6396c74f2640a75b215_25x16.jpg),需要使用一些特殊的方法,這部分內容就不再贅述了。 ![這里寫圖片描述](https://img.kancloud.cn/ed/3e/ed3eda29bb0020d52ac56cf03445708c_582x164.jpg) 得到![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)之后,再根據之前的KKT條件,就可以計算出w和b了。首先利用條件![](https://img.kancloud.cn/1e/d7/1ed7b8d0f93efceb33aedc2a078898ee_120x26.jpg)得到w,然后利用條件![](https://img.kancloud.cn/6a/52/6a527475a5c593024eea5e94ecf5fa8a_200x20.jpg),取任一![](https://img.kancloud.cn/fa/b2/fab23ee6957e727e27bddf8b6405cd76_53x18.jpg)即![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0的點,得到![](https://img.kancloud.cn/e2/55/e255015d8c5e78834f68f1a1a2010f11_165x20.jpg),進而求得![](https://img.kancloud.cn/bb/45/bb45fb6266bc7f012a9538e86444be4e_111x20.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/18/bc/18bc4ae3c463ac15d824fc76aefd2c62_584x337.jpg) 值得注意的是,計算b值,![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0時,有![](https://img.kancloud.cn/e3/38/e338226fa144adc373be876bedbf09cd_133x20.jpg)成立。![](https://img.kancloud.cn/e3/38/e338226fa144adc373be876bedbf09cd_133x20.jpg)正好表示的是該點在SVM分類線上,即fat boundary。也就是說,滿足![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0的點一定落在fat boundary上,這些點就是Support Vector。這是一個非常有趣的特性。 ### **Messages behind Dual SVM** 回憶一下,上一節課中,我們把位于分類線邊界上的點稱為support vector(candidates)。本節課前面介紹了![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0的點一定落在分類線邊界上,這些點稱之為support vector(注意沒有candidates)。也就是說分類線上的點不一定都是支持向量,但是滿足![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0的點,一定是支持向量。 ![這里寫圖片描述](https://img.kancloud.cn/69/d2/69d232aea7161ce802380283001e3eef_578x182.jpg) SV只由![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0的點決定,根據上一部分推導的w和b的計算公式,我們發現,w和b僅由SV即![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0的點決定,簡化了計算量。這跟我們上一節課介紹的分類線只由“胖”邊界上的點所決定是一個道理。也就是說,樣本點可以分成兩類:一類是support vectors,通過support vectors可以求得fattest hyperplane;另一類不是support vectors,對我們求得fattest hyperplane沒有影響。 ![這里寫圖片描述](https://img.kancloud.cn/8d/47/8d47b29b03bc99a3a1db7806d21fc618_579x91.jpg) 回過頭來,我們來比較一下SVM和PLA的w公式: ![這里寫圖片描述](https://img.kancloud.cn/3b/64/3b64a3500c6718a5eb2ef75b0ad01155_562x156.jpg) 我們發現,二者在形式上是相似的。![](https://img.kancloud.cn/d8/da/d8daa4b11517d77897bdfd4347c1125e_46x11.jpg)由fattest hyperplane邊界上所有的SV決定,![](https://img.kancloud.cn/16/95/16950346c4f80168326d51a83ae17b29_42x11.jpg)由所有當前分類錯誤的點決定。![](https://img.kancloud.cn/d8/da/d8daa4b11517d77897bdfd4347c1125e_46x11.jpg)和![](https://img.kancloud.cn/16/95/16950346c4f80168326d51a83ae17b29_42x11.jpg)都是原始數據點![](https://img.kancloud.cn/f5/f8/f5f8a5fbc7323a4eb44909a10c882f0a_34x12.jpg)的線性組合形式,是原始數據的代表。 ![這里寫圖片描述](https://img.kancloud.cn/61/5d/615dd981b61ced706cdc20f51c99f204_584x122.jpg) 總結一下,本節課和上節課主要介紹了兩種形式的SVM,一種是Primal Hard-Margin SVM,另一種是Dual Hard_Margin SVM。Primal Hard-Margin SVM有![](https://img.kancloud.cn/24/66/2466d0b5e92ac36c3835bccfb1c1ba01_40x19.jpg)個參數,有N個限制條件。當![](https://img.kancloud.cn/24/66/2466d0b5e92ac36c3835bccfb1c1ba01_40x19.jpg)很大時,求解困難。而Dual Hard_Margin SVM有N個參數,有N+1個限制條件。當數據量N很大時,也同樣會增大計算難度。兩種形式都能得到w和b,求得fattest hyperplane。通常情況下,如果N不是很大,一般使用Dual SVM來解決問題。 ![這里寫圖片描述](https://img.kancloud.cn/26/86/26861bf33528cb91cbf9fe99b666127f_561x358.jpg) 這節課提出的Dual SVM的目的是為了避免計算過程中對![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的依賴,而只與N有關。但是,Dual SVM是否真的消除了對![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的依賴呢?其實并沒有。因為在計算![](https://img.kancloud.cn/5b/06/5b06daaec74914ea56876d5428c773d7_133x22.jpg)的過程中,由z向量引入了![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg),實際上復雜度已經隱藏在計算過程中了。所以,我們的目標并沒有實現。下一節課我們將繼續研究探討如何消除對![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的依賴。 ![這里寫圖片描述](https://img.kancloud.cn/e5/64/e5649f3be4052f4c7488ec3b9bb64a71_579x207.jpg) ### **總結** 本節課主要介紹了SVM的另一種形式:Dual SVM。我們這樣做的出發點是為了移除計算過程對![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的依賴。Dual SVM的推導過程是通過引入拉格朗日因子![](https://img.kancloud.cn/38/9a/389a9983ea24ad0b3af0559c2aca381b_11x8.gif),將SVM轉化為新的非條件形式。然后,利用QP,得到最佳解的拉格朗日因子![](https://img.kancloud.cn/38/9a/389a9983ea24ad0b3af0559c2aca381b_11x8.gif)。再通過KKT條件,計算得到對應的w和b。最終求得fattest hyperplane。下一節課,我們將解決Dual SVM計算過程中對![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的依賴問題。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
                  <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>

                              哎呀哎呀视频在线观看