<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 功能強大 支持多語言、二開方便! 廣告
                # 3 -- Kernel Support Vector Machine 上節課我們主要介紹了SVM的對偶形式,即dual SVM。Dual SVM也是一個二次規劃問題,可以用QP來進行求解。之所以要推導SVM的對偶形式是因為:首先,它展示了SVM的幾何意義;然后,從計算上,求解過程“好像”與所在維度![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)無關,規避了![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)很大時難以求解的情況。但是,上節課的最后,我們也提到dual SVM的計算過程其實跟![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)還是有關系的。那么,能不能完全擺脫對![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的依賴,從而減少SVM計算量呢?這就是我們本節課所要講的主要內容。 ### **Kernel Trick** 我們上節課推導的dual SVM是如下形式: ![這里寫圖片描述](https://img.kancloud.cn/f8/3d/f83d19dc007d88d3785ddced32295330_582x198.jpg) 其中![](https://img.kancloud.cn/38/9a/389a9983ea24ad0b3af0559c2aca381b_11x8.gif)是拉格朗日因子,共N個,這是我們要求解的,而條件共有N+1個。我們來看向量![](https://img.kancloud.cn/a4/40/a44019d660c0f6396c74f2640a75b215_25x16.jpg)中的![](https://img.kancloud.cn/5b/06/5b06daaec74914ea56876d5428c773d7_133x22.jpg),看似這個計算與![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)無關,但是![](https://img.kancloud.cn/34/7c/347cabcc2fe40fb23d292aa386e4f2cf_39x21.jpg)的內積中不得不引入![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)。也就是說,如果![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)很大,計算![](https://img.kancloud.cn/34/7c/347cabcc2fe40fb23d292aa386e4f2cf_39x21.jpg)的復雜度也會很高,同樣會影響QP問題的計算效率。可以說,![](https://img.kancloud.cn/5b/06/5b06daaec74914ea56876d5428c773d7_133x22.jpg)這一步是計算的瓶頸所在。 其實問題的關鍵在于![](https://img.kancloud.cn/34/7c/347cabcc2fe40fb23d292aa386e4f2cf_39x21.jpg)內積求解上。我們知道,z是由x經過特征轉換而來: ![](https://img.kancloud.cn/8a/9a/8a9ae25a70ec631e309994534303a394_158x21.jpg) 如果從x空間來看的話,![](https://img.kancloud.cn/34/7c/347cabcc2fe40fb23d292aa386e4f2cf_39x21.jpg)分為兩個步驟:1\. 進行特征轉換![](https://img.kancloud.cn/dd/74/dd74e21cc06008e7129be53fa8c5102a_45x18.jpg)和![](https://img.kancloud.cn/87/6f/876f387f0d5a251820496115d04342d8_48x18.jpg);2\. 計算![](https://img.kancloud.cn/dd/74/dd74e21cc06008e7129be53fa8c5102a_45x18.jpg)與![](https://img.kancloud.cn/87/6f/876f387f0d5a251820496115d04342d8_48x18.jpg)的內積。這種先轉換再計算內積的方式,必然會引入![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)參數,從而在![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)很大的時候影響計算速度。那么,若把這兩個步驟聯合起來,是否可以有效地減小計算量,提高計算速度呢? 我們先來看一個簡單的例子,對于二階多項式轉換,各種排列組合為: ![這里寫圖片描述](https://img.kancloud.cn/32/ee/32ee0171026c8bbf45ce497ea249fdf5_578x112.jpg) 這里提一下,為了簡單起見,我們把![](https://img.kancloud.cn/2a/ce/2ace80aac57cd2c0877e83c1ef61f3b0_50x15.jpg)包含進來,同時將二次項![](https://img.kancloud.cn/e2/b2/e2b27e2f0b8528d1d061a3189a5428ab_34x12.gif)和![](https://img.kancloud.cn/d9/0d/d90de0bdef32fe07f61870ecd59b6bb1_34x12.jpg)也包含進來。轉換之后再做內積并進行推導,得到: ![這里寫圖片描述](https://img.kancloud.cn/92/50/9250b99692850b0a752a826bb859a903_577x171.jpg) 其中![](https://img.kancloud.cn/1d/28/1d2866629cd7de7fda32ba326dc41297_34x16.jpg)是x空間中特征向量的內積。所以,![](https://img.kancloud.cn/d2/23/d2239c867c2e06b195ae37ac3cd36149_43x18.jpg)與![](https://img.kancloud.cn/e0/52/e052a069d8844b80ba9b5dc02658e45a_48x18.jpg)的內積的復雜度由原來的![](https://img.kancloud.cn/31/f8/31f806224409055b5e1e93725f11ab44_44x20.jpg)變成![](https://img.kancloud.cn/6a/a4/6aa4498440ca535eb5814ef1122ead70_36x18.jpg),只與x空間的維度d有關,而與z空間的維度![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)無關,這正是我們想要的! 至此,我們發現如果把特征轉換和z空間計算內積這兩個步驟合并起來,有可能會簡化計算。因為我們只是推導了二階多項式會提高運算速度,這個特例并不具有一般推論性。但是,我們還是看到了希望。 我們把合并特征轉換和計算內積這兩個步驟的操作叫做Kernel Function,用大寫字母K表示。例如剛剛講的二階多項式例子,它的kernel function為: ![](https://img.kancloud.cn/f8/48/f8481a51a58ecad98f76f825365de047_183x20.jpg) ![](https://img.kancloud.cn/31/49/31490c4bcb99a6a85dfca8ae083899ab_259x21.jpg) 有了kernel function之后,我們來看看它在SVM里面如何使用。在dual SVM中,二次項系數![](https://img.kancloud.cn/21/1a/211aa08a250fdda37535ddca3be89bc4_32x14.jpg)中有z的內積計算,就可以用kernel function替換: ![](https://img.kancloud.cn/f8/ed/f8edd8b2ae3ced0d028c92d7f15a168a_275x22.jpg) 所以,直接計算出![](https://img.kancloud.cn/b5/03/b5035b70847af39c2a8e0ca46b23d8d8_79x18.jpg),再代入上式,就能得到![](https://img.kancloud.cn/21/1a/211aa08a250fdda37535ddca3be89bc4_32x14.jpg)的值。 ![](https://img.kancloud.cn/21/1a/211aa08a250fdda37535ddca3be89bc4_32x14.jpg)值計算之后,就能通過QP得到拉格朗日因子![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)。然后,下一步就是計算b(取![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0的點,即SV),b的表達式中包含z,可以作如下推導: ![](https://img.kancloud.cn/18/78/1878721aa7fe8d66454aa4384b7a10e9_508x54.jpg) 這樣得到的b就可以用kernel function表示,而與z空間無關。 最終我們要求的矩![](https://img.kancloud.cn/71/eb/71ebdd2458daf1fd3283f6fd3671960b_42x12.jpg)可以作如下推導: ![](https://img.kancloud.cn/c4/c8/c4c8742b1964ef7fffa657a0f74f2229_685x74.jpg) 至此,dual SVM中我們所有需要求解的參數都已經得到了,而且整個計算過程中都沒有在z空間作內積,即與z無關。我們把這個過程稱為kernel trick,也就是把特征轉換和計算內積兩個步驟結合起來,用kernel function來避免計算過程中受![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的影響,從而提高運算速度。 ![這里寫圖片描述](https://img.kancloud.cn/1f/f3/1ff3fb600735f1c21ca1456f27fa322d_577x243.jpg) 那么總結一下,引入kernel funtion后,SVM算法變成: ![這里寫圖片描述](https://img.kancloud.cn/47/47/47471deafe2516e8a33ed28abeaa6974_580x208.jpg) 分析每個步驟的時間復雜度為: ![這里寫圖片描述](https://img.kancloud.cn/4a/88/4a8820cacb4d52670f8cec1e30ef3d5c_577x105.jpg) 我們把這種引入kernel function的SVM稱為kernel SVM,它是基于dual SVM推導而來的。kernel SVM同樣只用SV(![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)&gt;0)就能得到最佳分類面,而且整個計算過程中擺脫了![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的影響,大大提高了計算速度。 ### **Polynomial Kernel** 我們剛剛通過一個特殊的二次多項式導出了相對應的kernel,其實二次多項式的kernel形式是多種的。例如,相應系數的放縮構成完全平方公式等。下面列舉了幾種常用的二次多項式kernel形式: ![這里寫圖片描述](https://img.kancloud.cn/a3/9b/a39bcd6d08802366ed670fac46511749_577x127.jpg) 比較一下,第一種![](https://img.kancloud.cn/d2/23/d2239c867c2e06b195ae37ac3cd36149_43x18.jpg)(藍色標記)和第三種![](https://img.kancloud.cn/d2/23/d2239c867c2e06b195ae37ac3cd36149_43x18.jpg)(綠色標記)從某種角度來說是一樣的,因為都是二次轉換,對應到同一個z空間。但是,它們系數不同,內積就會有差異,那么就代表有不同的距離,最終可能會得到不同的SVM margin。所以,系數不同,可能會得到不同的SVM分界線。通常情況下,第三種![](https://img.kancloud.cn/d2/23/d2239c867c2e06b195ae37ac3cd36149_43x18.jpg)(綠色標記)簡單一些,更加常用。 ![這里寫圖片描述](https://img.kancloud.cn/eb/db/ebdb712c2bdde3650dca608e4b5965d2_578x121.jpg) 不同的轉換,對應到不同的幾何距離,得到不同的距離,這是什么意思呢?舉個例子,對于我們之前介紹的一般的二次多項式kernel,它的SVM margin和對應的SV如下圖(中)所示。對于上面介紹的完全平方公式形式,自由度![](https://img.kancloud.cn/12/f7/12f7d999d4aadae6a45e6ff88efe9a9e_75x16.jpg),它的SVM margin和對應的SV如下圖(左)所示。比較發現,這種SVM margin比較簡單一些。對于自由度![](https://img.kancloud.cn/f4/fe/f4fe684a21936c5f100c37a2e48c4bf9_71x16.jpg),它的SVM margin和對應的SV如下圖(右)所示。與前兩種比較,margin和SV都有所不同。 ![這里寫圖片描述](https://img.kancloud.cn/ce/ca/cecaeca543c018c788f20bfcb432111a_567x201.jpg) 通過改變不同的系數,得到不同的SVM margin和SV,如何選擇正確的kernel,非常重要。 歸納一下,引入![](https://img.kancloud.cn/b8/ba/b8ba7f5be41fb98b4ab6208db3d9dea4_43x16.jpg)和![](https://img.kancloud.cn/3d/e0/3de0480133ab8171313346cfc96b13c4_44x16.jpg),對于Q次多項式一般的kernel形式可表示為: ![這里寫圖片描述](https://img.kancloud.cn/a4/e2/a4e268a2ae7bb46a3854ab95f9bcce2c_577x133.jpg) 所以,使用高階的多項式kernel有兩個優點: * **得到最大SVM margin,SV數量不會太多,分類面不會太復雜,防止過擬合,減少復雜度** * **計算過程避免了對![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的依賴,大大簡化了計算量。** ![這里寫圖片描述](https://img.kancloud.cn/1f/e5/1fe5137edbb06f3a4b3ceb01090c86d5_587x225.jpg) 順便提一下,當多項式階數Q=1時,那么對應的kernel就是線性的,即本系列課程第一節課所介紹的內容。對于linear kernel,計算方法是簡單的,而且也是我們解決SVM問題的首選。還記得機器學習基石課程中介紹的奧卡姆剃刀定律(Occam’s Razor)嗎? ### **Gaussian Kernel** 剛剛我們介紹的Q階多項式kernel的階數是有限的,即特征轉換的![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)是有限的。但是,如果是無限多維的轉換![](https://img.kancloud.cn/14/10/141069974357dc052c30231e17897586_36x18.jpg),是否還能通過kernel的思想,來簡化SVM的計算呢?答案是肯定的。 先舉個例子,簡單起見,假設原空間是一維的,只有一個特征x,我們構造一個kernel function為高斯函數: ![](https://img.kancloud.cn/c4/49/c44940cd56688fe01a10b76def0c64c1_149x22.jpg) 構造的過程正好與二次多項式kernel的相反,利用反推法,先將上式分解并做泰勒展開: ![這里寫圖片描述](https://img.kancloud.cn/5d/00/5d00b7a19ab6e03be6e0198d468c0e85_579x248.jpg) 將構造的K(x,x’)推導展開為兩個![](https://img.kancloud.cn/14/10/141069974357dc052c30231e17897586_36x18.jpg)和![](https://img.kancloud.cn/b7/23/b72388bbc0a77dc4fdb441346f858e46_40x18.jpg)的乘積,其中: ![](https://img.kancloud.cn/ad/d4/add48700dc9e79412e4a22df05f9d56a_279x45.jpg) 通過反推,我們得到了![](https://img.kancloud.cn/14/10/141069974357dc052c30231e17897586_36x18.jpg),![](https://img.kancloud.cn/14/10/141069974357dc052c30231e17897586_36x18.jpg)是無限多維的,它就可以當成特征轉換的函數,且![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)是無限的。這種![](https://img.kancloud.cn/14/10/141069974357dc052c30231e17897586_36x18.jpg)得到的核函數即為Gaussian kernel。 更一般地,對于原空間不止一維的情況(d&gt;1),引入縮放因子![](https://img.kancloud.cn/3d/e0/3de0480133ab8171313346cfc96b13c4_44x16.jpg),它對應的Gaussian kernel表達式為: ![](https://img.kancloud.cn/e4/71/e47167f11169bff07afbcbdcaa9a3e4a_162x21.jpg) 那么引入了高斯核函數,將有限維度的特征轉換拓展到無限的特征轉換中。根據本節課上一小節的內容,由K,計算得到![](https://img.kancloud.cn/96/42/964237caf2be6185a33aa601075d68fb_19x11.jpg)和b,進而得到矩![](https://img.kancloud.cn/71/eb/71ebdd2458daf1fd3283f6fd3671960b_42x12.jpg)。將其中的核函數K用高斯核函數代替,得到: ![](https://img.kancloud.cn/3d/a7/3da770499b3f96306edfa5dacc7c6ca4_560x40.jpg) 通過上式可以看出,![](https://img.kancloud.cn/71/eb/71ebdd2458daf1fd3283f6fd3671960b_42x12.jpg)有n個高斯函數線性組合而成,其中n是SV的個數。而且,每個高斯函數的中心都是對應的SV。通常我們也把高斯核函數稱為徑向基函數(Radial Basis Function, RBF)。 ![這里寫圖片描述](https://img.kancloud.cn/cb/85/cb85f01cf78a8ae5316ab5123a9f99f8_571x219.jpg) 總結一下,kernel SVM可以獲得large-margin的hyperplanes,并且可以通過高階的特征轉換使![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)盡可能地小。kernel的引入大大簡化了dual SVM的計算量。而且,Gaussian kernel能將特征轉換擴展到無限維,并使用有限個SV數量的高斯函數構造出矩![](https://img.kancloud.cn/71/eb/71ebdd2458daf1fd3283f6fd3671960b_42x12.jpg)。 ![這里寫圖片描述](https://img.kancloud.cn/94/71/9471f82fd0886a0a87906fe6d9ea56b6_581x192.jpg) 值得注意的是,縮放因子![](https://img.kancloud.cn/8c/8b/8c8b9dbbd1e6b0fac772d9589e2d0ca2_10x12.jpg)取值不同,會得到不同的高斯核函數,hyperplanes不同,分類效果也有很大的差異。舉個例子,![](https://img.kancloud.cn/8c/8b/8c8b9dbbd1e6b0fac772d9589e2d0ca2_10x12.jpg)分別取1, 10, 100時對應的分類效果如下: ![這里寫圖片描述](https://img.kancloud.cn/8c/91/8c91f966325e05ac60691fc370f39fa5_565x203.jpg) 從圖中可以看出,當![](https://img.kancloud.cn/8c/8b/8c8b9dbbd1e6b0fac772d9589e2d0ca2_10x12.jpg)比較小的時候,分類線比較光滑,當![](https://img.kancloud.cn/8c/8b/8c8b9dbbd1e6b0fac772d9589e2d0ca2_10x12.jpg)越來越大的時候,分類線變得越來越復雜和扭曲,直到最后,分類線變成一個個獨立的小區域,像小島一樣將每個樣本單獨包起來了。為什么會出現這種區別呢?這是因為![](https://img.kancloud.cn/8c/8b/8c8b9dbbd1e6b0fac772d9589e2d0ca2_10x12.jpg)越大,其對應的高斯核函數越尖瘦,那么有限個高斯核函數的線性組合就比較離散,分類效果并不好。所以,SVM也會出現過擬合現象,![](https://img.kancloud.cn/8c/8b/8c8b9dbbd1e6b0fac772d9589e2d0ca2_10x12.jpg)的正確選擇尤為重要,不能太大。 ### **Comparison of Kernels** 目前為止,我們已經介紹了幾種kernel,下面來對幾種kernel進行比較。 首先,Linear Kernel是最簡單最基本的核,平面上對應一條直線,三維空間里對應一個平面。Linear Kernel可以使用上一節課介紹的Dual SVM中的QP直接計算得到。 ![這里寫圖片描述](https://img.kancloud.cn/59/80/59803f4e8e3aedb0349af3066254cb10_421x131.jpg) Linear Kernel的優點是計算簡單、快速,可以直接使用QP快速得到參數值,而且從視覺上分類效果非常直觀,便于理解;缺點是如果數據不是線性可分的情況,Linear Kernel就不能使用了。 ![這里寫圖片描述](https://img.kancloud.cn/a5/26/a526a262d98ea3f5d9c20b59830159ad_564x182.jpg) 然后,Polynomial Kernel的hyperplanes是由多項式曲線構成。 ![這里寫圖片描述](https://img.kancloud.cn/b8/7f/b87fe55f5eebd198e6b5e5d9d2612dd0_429x126.jpg) Polynomial Kernel的優點是階數Q可以靈活設置,相比linear kernel限制更少,更貼近實際樣本分布;缺點是當Q很大時,K的數值范圍波動很大,而且參數個數較多,難以選擇合適的值。 ![這里寫圖片描述](https://img.kancloud.cn/43/5d/435df27427a7a93e545e56f290dd915d_561x170.jpg) 對于Gaussian Kernel,表示為高斯函數形式。 ![這里寫圖片描述](https://img.kancloud.cn/7e/c0/7ec08896106f8484fe134333c41f4cc3_457x126.jpg) Gaussian Kernel的優點是邊界更加復雜多樣,能最準確地區分數據樣本,數值計算K值波動較小,而且只有一個參數,容易選擇;缺點是由于特征轉換到無限維度中,w沒有求解出來,計算速度要低于linear kernel,而且可能會發生過擬合。 ![這里寫圖片描述](https://img.kancloud.cn/87/7a/877ab1560186d171e930b1f2c73bff8d_563x217.jpg) 除了這三種kernel之外,我們還可以使用其它形式的kernel。首先,我們考慮kernel是什么?實際上kernel代表的是兩筆資料x和x’,特征變換后的相似性即內積。但是不能說任何計算相似性的函數都可以是kernel。有效的kernel還需滿足幾個條件: * **K是對稱的** * **K是半正定的** 這兩個條件不僅是必要條件,同時也是充分條件。所以,只要我們構造的K同時滿足這兩個條件,那它就是一個有效的kernel。這被稱為Mercer 定理。事實上,構造一個有效的kernel是比較困難的。 ![這里寫圖片描述](https://img.kancloud.cn/e5/01/e50142198679fd893fbd2548fd8e8a59_579x304.jpg) ### **總結** 本節課主要介紹了Kernel Support Vector Machine。首先,我們將特征轉換和計算內積的操作合并到一起,消除了![](https://img.kancloud.cn/c9/ed/c9eda98a39228f13bb32152950bf36b7_10x17.jpg)的影響,提高了計算速度。然后,分別推導了Polynomial Kernel和Gaussian Kernel,并列舉了各自的優缺點并做了比較。對于不同的問題,應該選擇合適的核函數進行求解,以達到最佳的分類效果。 **_注明:_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
                  <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>

                              哎呀哎呀视频在线观看