支持向量機(jī)及其應(yīng)用

1、Page 1數(shù)學(xué)與計(jì)算機(jī)學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院 彭宏彭宏支持向量機(jī)及其應(yīng)用支持向量機(jī)及其應(yīng)用Support Vector Machines and its Application智能算法講座（一）智能算法講座（一） Page 2目錄目錄u 線性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī)u 線性支持向量（分類）機(jī)線性支持向量（分類）機(jī)u 支持向量（分類）機(jī)支持向量（分類）機(jī)u 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī)u 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)u

2、最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 3SVM的描述的描述u SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的模式識(shí)別方是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的模式識(shí)別方法，它是由法，它是由Boser,Guyon,Vapnik在在COLT-92上上首次提出，從此迅速的發(fā)展起來，現(xiàn)在已經(jīng)首次提出，從此迅速的發(fā)展起來，現(xiàn)在已經(jīng)在許多領(lǐng)域（生物信息學(xué)，文本，圖像處理，在許多領(lǐng)域（生物信息學(xué)，文本，圖像處理，語言信號(hào)處理和手寫識(shí)別等）都取得了成功語言信號(hào)處理和手寫識(shí)別等）都取得了成功的應(yīng)用的應(yīng)用uCOLT(Computational Learning Theory)Page 4S

3、VM的描述的描述u目標(biāo)：目標(biāo)：找到一個(gè)超平面，使得它能夠盡可能多找到一個(gè)超平面，使得它能夠盡可能多的將兩類數(shù)據(jù)點(diǎn)正確的分開，同時(shí)使分開的兩的將兩類數(shù)據(jù)點(diǎn)正確的分開，同時(shí)使分開的兩類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。u解決方法：解決方法：構(gòu)造一個(gè)在約束條件下的優(yōu)化問題，構(gòu)造一個(gè)在約束條件下的優(yōu)化問題，具體的說是一個(gè)約束二次規(guī)劃問題具體的說是一個(gè)約束二次規(guī)劃問題(constrained quadratic programing), ,求解該問題，得到分類器。求解該問題，得到分類器。Page 5模式識(shí)別問題的一般描述模式識(shí)別問題的一般描述u 已知：已知：n個(gè)觀測(cè)樣本，個(gè)觀測(cè)樣本，(x1,

4、y1), , (x2,y2) (xn,yn)u 求：最優(yōu)函數(shù)求：最優(yōu)函數(shù)y= f(x,w)u 滿足條件：期望風(fēng)險(xiǎn)最小滿足條件：期望風(fēng)險(xiǎn)最小u 損失函數(shù)損失函數(shù)),(),(,()(yxdFwxfyLwR),(1),(0),(,(wxfywxfywxfyLPage 6SVM的描述的描述u 期望風(fēng)險(xiǎn)期望風(fēng)險(xiǎn)R(w)要依賴聯(lián)合概率要依賴聯(lián)合概率F(x,y)的信息，的信息，實(shí)際問題中無法計(jì)算。實(shí)際問題中無法計(jì)算。u 一般用經(jīng)驗(yàn)風(fēng)險(xiǎn)一般用經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)代替期望風(fēng)險(xiǎn)代替期望風(fēng)險(xiǎn)R(w)nwxfyLnwRniiiemp錯(cuò)分?jǐn)?shù)1),(,(1)(Page 7一般模式識(shí)別方法的問題一般模式識(shí)別方法的問題u

5、經(jīng)驗(yàn)風(fēng)險(xiǎn)最小不等于期望風(fēng)險(xiǎn)最小，不能保證經(jīng)驗(yàn)風(fēng)險(xiǎn)最小不等于期望風(fēng)險(xiǎn)最小，不能保證分類器的推廣能力分類器的推廣能力. .u 經(jīng)驗(yàn)風(fēng)險(xiǎn)只有在樣本數(shù)無窮大趨近于期望風(fēng)險(xiǎn)，經(jīng)驗(yàn)風(fēng)險(xiǎn)只有在樣本數(shù)無窮大趨近于期望風(fēng)險(xiǎn)，需要非常多的樣本才能保證分類器的性能。需要非常多的樣本才能保證分類器的性能。u 需要找到經(jīng)驗(yàn)風(fēng)險(xiǎn)最小和推廣能力最大的平衡需要找到經(jīng)驗(yàn)風(fēng)險(xiǎn)最小和推廣能力最大的平衡點(diǎn)。點(diǎn)。Page 8一、線性可分的支持向量(分類)機(jī)),( ,),(),(2211nnyxyxyxD，niyRXximi, 1,1, 1,0)(bxw首先考慮線性可分情況。設(shè)有如下兩類樣本的訓(xùn)練集：首先考慮線性可分情況。設(shè)有如下兩類樣

6、本的訓(xùn)練集：線性可分情況意味著存在線性可分情況意味著存在超平面超平面使訓(xùn)練點(diǎn)中的正類和使訓(xùn)練點(diǎn)中的正類和負(fù)類樣本分別位于該超平面的兩側(cè)。負(fù)類樣本分別位于該超平面的兩側(cè)。如果能確定這樣的參數(shù)對(duì)（如果能確定這樣的參數(shù)對(duì)（w,bw,b）的話的話, ,就可以構(gòu)造就可以構(gòu)造決策函數(shù)決策函數(shù)來進(jìn)行來進(jìn)行識(shí)別新樣本。識(shí)別新樣本。)sgn()(bxwxfPage 9線性可分的支持向量(分類)機(jī)nibxwytswiibw, 1, 1)(. .21min2,問題是問題是：這樣的參數(shù)對(duì)（：這樣的參數(shù)對(duì)（w,bw,b）有許多。）有許多。 解決的方法是采用最大間隔原則。解決的方法是采用最大間隔原則。最大間隔原則最大間隔

7、原則：選擇使得訓(xùn)練集：選擇使得訓(xùn)練集D D對(duì)于線性函數(shù)對(duì)于線性函數(shù)(wx)+b的幾何間隔取最大值的參數(shù)對(duì)的幾何間隔取最大值的參數(shù)對(duì)(w,b)(w,b)，并，并由此構(gòu)造決策函數(shù)。由此構(gòu)造決策函數(shù)。在規(guī)范化下，超平面的幾何間隔為在規(guī)范化下，超平面的幾何間隔為于是，找最大于是，找最大幾何間隔的超平面幾何間隔的超平面表述成如下的最優(yōu)化問題：表述成如下的最優(yōu)化問題：w1(1)(1)Page 10線性可分的支持向量(分類)機(jī)niiiibxwywbwL12) 1)(21),(nTnR),(210),(, 0),(bwLbwLwb 為求解問題為求解問題(1),(1),使用使用Lagrange乘子法乘子法將其轉(zhuǎn)

8、化為對(duì)偶問題。將其轉(zhuǎn)化為對(duì)偶問題。于是引入于是引入Lagrange函數(shù)函數(shù)：其中，其中， 稱為稱為L(zhǎng)agrange乘子。乘子。首先求首先求Lagrange函數(shù)關(guān)于函數(shù)關(guān)于w,bw,b的極小值。由的極小值。由極值條件有：極值條件有：niiiy10niiiixyw1得到：得到：(2)(2)(3)(3)(4)(4)Page 11線性可分的支持向量(分類)機(jī)niytsxxyyiniiininjjnjjijiji, 1, 0, 0. .)(21min1111niiiixyw1niiiixyw1*將將(3)(3)式代入式代入Lagrange函數(shù)，并利用函數(shù)，并利用(4)(4)式，則原始的優(yōu)化問題式，則原始

9、的優(yōu)化問題轉(zhuǎn)化為如下的轉(zhuǎn)化為如下的對(duì)偶問題對(duì)偶問題( (使用極小形式使用極小形式) )：這是一個(gè)凸二這是一個(gè)凸二次規(guī)劃問題次規(guī)劃問題有唯一的最優(yōu)有唯一的最優(yōu)解解(5)(5)求解問題求解問題(5)(5)，得，得 。則參數(shù)對(duì)。則參數(shù)對(duì)(w,b)(w,b)可由下式計(jì)算：可由下式計(jì)算：nyiniiiixwb1*1*2Page 12線性可分的支持向量(分類)機(jī)0) 1)(*bxwyiii支持向量：支持向量：稱訓(xùn)練集稱訓(xùn)練集D中的樣本中的樣本xi為支持向量，如為支持向量，如 果它對(duì)應(yīng)的果它對(duì)應(yīng)的i*0。根據(jù)原始最優(yōu)化問題的根據(jù)原始最優(yōu)化問題的KKTKKT條件，有條件，有于是，支持向量正好在間隔邊界上于是，

10、支持向量正好在間隔邊界上。于是，得到如下的決策函數(shù)：于是，得到如下的決策函數(shù)：niiiibxxyxf1*)(sgn)(Page 13目錄目錄u 線性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī)u 線性支持向量（分類）機(jī)線性支持向量（分類）機(jī)u 支持向量（分類）機(jī)支持向量（分類）機(jī)u 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī)u 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page

11、14二、線性支持向量(分類)機(jī)1)(bxwyiinibxwyiii, 1,1)(現(xiàn)在考慮現(xiàn)在考慮線性不可分情況線性不可分情況。對(duì)于訓(xùn)練集。對(duì)于訓(xùn)練集D D，不存在這樣，不存在這樣的超平面，使訓(xùn)練集關(guān)于該超平面的幾何間隔取正值。的超平面，使訓(xùn)練集關(guān)于該超平面的幾何間隔取正值。如果要用超平面來劃分的話，必然有錯(cuò)分的點(diǎn)。如果要用超平面來劃分的話，必然有錯(cuò)分的點(diǎn)。但我們?nèi)蜗Ｍ褂贸矫孢M(jìn)行分劃，這時(shí)應(yīng)但我們?nèi)蜗Ｍ褂贸矫孢M(jìn)行分劃，這時(shí)應(yīng)“軟化軟化”對(duì)間隔的要求，即容許不滿足約束條件的樣本點(diǎn)存在。對(duì)間隔的要求，即容許不滿足約束條件的樣本點(diǎn)存在。為此，引入松弛變量為此，引入松弛變量并并“軟化軟化”約束條

12、件：約束條件：i0iPage 15線性支持向量(分類)機(jī)為了避免為了避免 i i取太大的值，需要在目標(biāo)函數(shù)中對(duì)它們進(jìn)行取太大的值，需要在目標(biāo)函數(shù)中對(duì)它們進(jìn)行懲罰。于是懲罰。于是原始優(yōu)化問題原始優(yōu)化問題變?yōu)椋鹤優(yōu)椋簄inibxwytsCwiiiiniibw, 1, 0, 1,1)(. .21min12,其中其中C0C0稱為稱為懲罰因子。懲罰因子。(6)(6)Page 16線性支持向量(分類)機(jī)niiiniiiiiniirbxwyCwrbwL1112)1)(21),(類似前面，通過引入如下的類似前面，通過引入如下的Lagrange函數(shù)：函數(shù)：得到如下的對(duì)偶問題：得到如下的對(duì)偶問題：niCytsxx

13、yyiniiininjjnjjijiji, 1,0, 0. .)(21min1111(7)(7)Page 17線性支持向量(分類)機(jī)求解對(duì)偶問題求解對(duì)偶問題(7),(7),可得如下決策函數(shù)：可得如下決策函數(shù)：niiiibxxyxf1*)(sgn)(支持向量有下列性質(zhì)：支持向量有下列性質(zhì)：(1)(1)界內(nèi)支持向量一定位于間隔邊界上界內(nèi)支持向量一定位于間隔邊界上 的正確劃分區(qū)；的正確劃分區(qū)；(2)(2)支持向量不會(huì)出現(xiàn)在間隔以外的支持向量不會(huì)出現(xiàn)在間隔以外的 正確劃分區(qū)；正確劃分區(qū)；(3)(3)非支持向量一定位于帶間隔的正確劃分區(qū)。非支持向量一定位于帶間隔的正確劃分區(qū)。Page 18目錄目錄u 線

14、性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī)u 線性支持向量（分類）機(jī)線性支持向量（分類）機(jī)u 支持向量（分類）機(jī)支持向量（分類）機(jī)u 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī)u 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 19三、支持向量(分類)機(jī)對(duì)于一般的對(duì)于一般的非線性可分情況非線性可分情況。對(duì)于訓(xùn)練集。對(duì)于訓(xùn)練集D D，無法尋找，無法尋找到來如前的超平面來劃分

15、。到來如前的超平面來劃分。Page 20支持向量(分類)機(jī)下面通過下面通過核技術(shù)核技術(shù)來處理。引入一個(gè)來處理。引入一個(gè)非線性映射非線性映射 把把輸入空間輸入空間映射到一個(gè)映射到一個(gè)( (高維的高維的) )Hilbert空間空間H, ,使數(shù)據(jù)在使數(shù)據(jù)在H中是線性可分中是線性可分或線性不可分：或線性不可分：)(:xzxHZRXm輸入空間輸入空間Xi Hilbert空間空間H線性線性可分可分線性線性不可分不可分Page 21在核映射下，在核映射下，D D對(duì)應(yīng)于對(duì)應(yīng)于Hilbert空間空間H的訓(xùn)練集為：的訓(xùn)練集為：支持向量(分類)機(jī)),( ,),),(),( ,),(1111nnnnyxyxyzyzD

16、于是在于是在Hilbert空間空間H中尋找使幾何間隔最大的超平中尋找使幾何間隔最大的超平面，其原始優(yōu)化問題面，其原始優(yōu)化問題為：為：ninibzwytsCwiiiiniibw, 1, 0, 1,1)(. .21min12,(8)(8)Page 22問題問題(8)(8)對(duì)應(yīng)的對(duì)偶問題為對(duì)應(yīng)的對(duì)偶問題為：支持向量(分類)機(jī)(9)(9)niCytsxxKyyiniiininjjnjjijiji, 1,0, 0. .)(21min1111求解對(duì)偶問題求解對(duì)偶問題(9),(9),可得如下決策函數(shù)：可得如下決策函數(shù)：niiiibxxKyxf1*)(sgn)(Page 23b*問的計(jì)算如下問的計(jì)算如下：支持

17、向量(分類)機(jī)選取選取的一個(gè)正分量的一個(gè)正分量0j*0或或j* 0來計(jì)算來計(jì)算b: :Page 40硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)bxwxfy)()(支持向量：支持向量：稱訓(xùn)練集稱訓(xùn)練集D中的樣本中的樣本xi為支持向量，為支持向量， 如果它對(duì)應(yīng)的如果它對(duì)應(yīng)的i*0或i0 。把把w的式子代入函數(shù)：的式子代入函數(shù)：于是，得到如下的回歸函數(shù)：于是，得到如下的回歸函數(shù)：niiiibxxxf1*)()(y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 41目錄目錄u 線性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī)u 線性支持向量（分類）機(jī)線性支持向量（分

18、類）機(jī)u 支持向量（分類）機(jī)支持向量（分類）機(jī)u 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī)u 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 42軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)),( ,),(),(2211nnyxyxyxD，niRyRXximi, 1,考慮軟考慮軟 - -帶支持向量帶支持向量線性線性回歸回歸情況。設(shè)有如下兩類樣本的訓(xùn)練集情況。設(shè)有如下兩類樣本

19、的訓(xùn)練集：同樣希望使用一個(gè)線性函數(shù)來同樣希望使用一個(gè)線性函數(shù)來回歸回歸樣本點(diǎn)，且這種情況下，除了樣本點(diǎn)，且這種情況下，除了大量樣本點(diǎn)在大量樣本點(diǎn)在 - -帶內(nèi)，還有少量的樣本帶內(nèi)，還有少量的樣本落在落在 - -帶外。這時(shí)需要對(duì)帶外。這時(shí)需要對(duì)落在落在 - -帶外的樣本進(jìn)行懲罰。于是帶外的樣本進(jìn)行懲罰。于是原始優(yōu)化問題原始優(yōu)化問題為：為：ninibxwyniybxwtsnCwiiiiiiiniiibw, 1, 0, 1,)(, 1,)(. .)(121min(*)*1*2,(*)y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 43軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回

20、歸）機(jī)niiiiniiiiniiiiiniiibxwybxwynCwbwL1*11*1*2)()()()(21),(0, 0(*)(*)0(*)(*)(*)iinCL 為求解上述原始優(yōu)化問題為求解上述原始優(yōu)化問題, ,使用使用Lagrange乘子法乘子法將其轉(zhuǎn)化為對(duì)將其轉(zhuǎn)化為對(duì)偶問題。于是引入偶問題。于是引入Lagrange函數(shù)函數(shù)：其中，其中， 稱為稱為L(zhǎng)agrange乘子。乘子。首先求首先求Lagrange函數(shù)關(guān)于函數(shù)關(guān)于w,b,w,b, ( (* *) )的極小值。由的極小值。由極值條件有：極值條件有：niiibL1*0)(0)(1*niiiiwxwLPage 44軟軟 - -帶帶支持向

21、量（回歸）機(jī)支持向量（回歸）機(jī)ninCtsyxxiiniiiniiiininiiinjjijjii, 1,0, 0)(. .)()()()(21min*1*1*11*1*）（niiiixw1*)(將上式代入將上式代入Lagrange函數(shù)，則原始的優(yōu)化問題轉(zhuǎn)化為如下的函數(shù)，則原始的優(yōu)化問題轉(zhuǎn)化為如下的對(duì)偶問題對(duì)偶問題( (使用極小形式使用極小形式) )：求解上述對(duì)偶問題，得求解上述對(duì)偶問題，得 ( (* *) )。則參數(shù)對(duì)。則參數(shù)對(duì)(w,b)(w,b)可由下式計(jì)算：可由下式計(jì)算：b的計(jì)算（略）。的計(jì)算（略）。Page 45軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)bxwxfy)()(支

22、持向量：支持向量：稱訓(xùn)練集稱訓(xùn)練集D中的樣本中的樣本xi為支持向量，為支持向量， 如果它對(duì)應(yīng)的如果它對(duì)應(yīng)的i*0或i0 。把把w的式子代入函數(shù)：的式子代入函數(shù)：于是，得到如下的回歸函數(shù)：于是，得到如下的回歸函數(shù)：niiiibxxxf1*)()(y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 46目錄目錄u 線性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī)u 線性支持向量（分類）機(jī)線性支持向量（分類）機(jī)u 支持向量（分類）機(jī)支持向量（分類）機(jī)u 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī)u 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -

23、帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 47 - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)下面通過下面通過核技術(shù)核技術(shù)來處理。引入一個(gè)來處理。引入一個(gè)非線性映射非線性映射 把把輸入空間輸入空間映射到一個(gè)映射到一個(gè)( (高維的高維的) )Hilbert空間空間H, ,使在使在H中進(jìn)行線性回歸中進(jìn)行線性回歸（硬（硬 - -帶或軟帶或軟 - -帶）：帶）：)(:xzxHZRXm輸入空間輸入空間X Hilbert空間空間H硬硬 - -帶帶線性回歸線性回歸軟軟 -

24、 -帶帶線性回歸線性回歸Page 48在核映射下，在核映射下，D D對(duì)應(yīng)于對(duì)應(yīng)于Hilbert空間空間H的訓(xùn)練集為：的訓(xùn)練集為： - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)),( ,),),(),( ,),(1111nnnnyxyxyzyzD于是在于是在Hilbert空間空間H中進(jìn)行線性回歸，其原始優(yōu)化中進(jìn)行線性回歸，其原始優(yōu)化問題問題為：為：ninibzwyniybzwtsnCwiiiiiiiniiibw, 1, 0, 1,)(, 1,)(. .)(121min(*)*1*2,(*)Page 49上述問題的對(duì)偶問題為上述問題的對(duì)偶問題為： - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)求解對(duì)偶問

25、題求解對(duì)偶問題, ,可得如下回歸函數(shù)：可得如下回歸函數(shù)：ninCtsyxxKiiniiiniiiininiiinjjijjii, 1,0, 0)(. .)()()()(21min*1*1*11*1*）（niiiibxxKxf1*)()()(Page 50目錄目錄u 線性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī)u 線性支持向量（分類）機(jī)線性支持向量（分類）機(jī)u 支持向量（分類）機(jī)支持向量（分類）機(jī)u 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī)u 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回

26、歸）機(jī)支持向量（回歸）機(jī)u 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 51四、最小二乘支持向量(回歸)機(jī) 假定假定xXRd表示一個(gè)實(shí)值隨機(jī)輸入向量，表示一個(gè)實(shí)值隨機(jī)輸入向量，yYR表示一個(gè)實(shí)表示一個(gè)實(shí)值隨機(jī)輸出變量。記值隨機(jī)輸出變量。記RN表示一高維的特征空間，表示一高維的特征空間，為一非線性為一非線性映射映射: X，它映射隨機(jī)輸入向量到高維特征空間，它映射隨機(jī)輸入向量到高維特征空間。 支持向量方法的思想是在該高維特征空間支持向量方法的思想是在該高維特征空間中考慮如下線性中考慮如下線性函數(shù)集：函數(shù)集： RbRwXbxwxffFfnT,:;)(

27、)(: 我們考慮在函數(shù)表示式中含噪聲情形。給定一個(gè)由未知分我們考慮在函數(shù)表示式中含噪聲情形。給定一個(gè)由未知分布布FXY產(chǎn)生的、獨(dú)立同分布（產(chǎn)生的、獨(dú)立同分布（i.i.d.）的訓(xùn)練集：）的訓(xùn)練集： nkYyXxyxDkkkk, 1;,: ),(kkkexfy)(這里這里ekR假定為獨(dú)立同分布的隨機(jī)誤差，且假定為獨(dú)立同分布的隨機(jī)誤差，且E ek | X=xk = 0，Var ek = 2 ；m(x)F為一個(gè)未知的實(shí)值光滑函數(shù)，且為一個(gè)未知的實(shí)值光滑函數(shù)，且E yk | x=xk = f(xk)。 Page 52最小二乘支持向量(回歸)機(jī) 函數(shù)估計(jì)的目的是在約束函數(shù)估計(jì)的目的是在約束|w|a, aR

28、下通過最小化如下經(jīng)驗(yàn)下通過最小化如下經(jīng)驗(yàn)風(fēng)險(xiǎn)來尋找風(fēng)險(xiǎn)來尋找w和和b: : nkkkTempybxwn1bwR12)(),( 最小二乘支持向量回歸機(jī)最小二乘支持向量回歸機(jī)（LS-SVR）定義了與標(biāo)準(zhǔn)支持向定義了與標(biāo)準(zhǔn)支持向量機(jī)不同的代價(jià)函數(shù)，選用損失函數(shù)為誤差量機(jī)不同的代價(jià)函數(shù)，選用損失函數(shù)為誤差ek的二次項(xiàng)，并將的二次項(xiàng)，并將其不等式約束改為等式約束，因此尋找其不等式約束改為等式約束，因此尋找w和和b的優(yōu)化問題可以轉(zhuǎn)的優(yōu)化問題可以轉(zhuǎn)化為如下具有化為如下具有嶺回歸嶺回歸形式的優(yōu)化問題：形式的優(yōu)化問題： nkkTeb,w,e21wwe)J(w,min1221且?guī)в腥缦碌仁郊s束條件：且?guī)в腥缦碌仁?/p>

29、約束條件： nkebxwykkTk, 1,)(其中其中 bxxyeTiPage 53最小二乘支持向量(回歸)機(jī) 為了在對(duì)偶空間中求解上述優(yōu)化問題，定義如下的為了在對(duì)偶空間中求解上述優(yōu)化問題，定義如下的Lagrange泛函：泛函： nkkkkTkyebxw-e)J(w,)e,b,L(w,1)(其中其中kR為乘子（叫做支持向量）。為乘子（叫做支持向量）。 其優(yōu)化條件由下式給出：其優(yōu)化條件由下式給出： nkyebxwLnkeeLbLxwwLkkkTkkkknkknkkk, 1,)(0, 1,000)(011Page 54最小二乘支持向量(回歸)機(jī)上式能被直接表示為求解如下如下線性方程組：上式能被直接

30、表示為求解如下如下線性方程組： 其中其中y=(y1,yn)T, (x)=( (x1), (xn)T, 1n=(1,.,1)T, e=(e1,en)T, =(1, n)T。在上式中消去。在上式中消去w和和e后，得到如下后，得到如下線性方程組：線性方程組： yebwIxIIxInnTnnTn00001)(001000)(00ybInnTn01110其中其中kl=(xk)T(xl), k,l=1,.,n。 Page 55最小二乘支持向量(回歸)機(jī)根據(jù)根據(jù)Mercer定理，函數(shù)估計(jì)的最小二乘支持向量回歸模型為：定理，函數(shù)估計(jì)的最小二乘支持向量回歸模型為： 其中其中與與b通過求解上述方程組得到。通過求解

31、上述方程組得到。 nkkkbxxKxf1),()(Page 56目錄目錄u 線性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī)u 線性支持向量（分類）機(jī)線性支持向量（分類）機(jī)u 支持向量（分類）機(jī)支持向量（分類）機(jī)u 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī)u 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 57九、支持向量機(jī)應(yīng)用1 1、手寫體數(shù)字識(shí)別、手寫體數(shù)字識(shí)別。 SV

32、MSVM的第一個(gè)應(yīng)用是手寫字符識(shí)別問題。的第一個(gè)應(yīng)用是手寫字符識(shí)別問題。 VapnikVapnik、BurgesBurges、CortesCortes、ScholkopfScholkopf等研究了該問等研究了該問題。使用題。使用最大間隔最大間隔和和軟間隔軟間隔SVMSVM。使用。使用高斯核高斯核和和多項(xiàng)式多項(xiàng)式核核。 在兩個(gè)數(shù)據(jù)集在兩個(gè)數(shù)據(jù)集USPSUSPS( (美國(guó)郵政服務(wù)局美國(guó)郵政服務(wù)局) )和和NISTNIST( (國(guó)家標(biāo)國(guó)家標(biāo)準(zhǔn)技術(shù)局準(zhǔn)技術(shù)局) )。其中。其中USPSUSPS數(shù)據(jù)集包括數(shù)據(jù)集包括72917291個(gè)訓(xùn)練樣本，個(gè)訓(xùn)練樣本，20072007個(gè)測(cè)試樣本，用個(gè)測(cè)試樣本，用2562

33、56維的向量維的向量(16(161616矩陣矩陣) )表示，表示，每個(gè)點(diǎn)的灰度值每個(gè)點(diǎn)的灰度值0 0255255。 NISTNIST數(shù)據(jù)集包括數(shù)據(jù)集包括6000060000個(gè)訓(xùn)練樣本，個(gè)訓(xùn)練樣本，1000010000個(gè)測(cè)試樣本個(gè)測(cè)試樣本，圖像為，圖像為20202020矩陣表示。矩陣表示。 結(jié)果表明結(jié)果表明SVMSVM具有一定的優(yōu)勢(shì)。具有一定的優(yōu)勢(shì)。Page 58九、支持向量機(jī)應(yīng)用2 2、文本分類、文本分類。 根據(jù)文本的內(nèi)容自動(dòng)地把它歸類。比如郵件過濾、根據(jù)文本的內(nèi)容自動(dòng)地把它歸類。比如郵件過濾、網(wǎng)頁搜索、網(wǎng)頁搜索、WebWeb挖掘、信息檢索等。挖掘、信息檢索等。 JoachimsJoachim

34、s，DumaisDumais等人進(jìn)行等人進(jìn)行SVMSVM對(duì)文本分類的研究工對(duì)文本分類的研究工作。作。 使用的數(shù)據(jù)集為路透社使用的數(shù)據(jù)集為路透社(Reuters)(Reuters)第第2157821578號(hào)新聞數(shù)號(hào)新聞數(shù)據(jù)庫。該數(shù)據(jù)庫共有據(jù)庫。該數(shù)據(jù)庫共有1290212902個(gè)文本，包括個(gè)文本，包括96039603個(gè)訓(xùn)練的個(gè)訓(xùn)練的文本和文本和32993299個(gè)測(cè)試樣本。每個(gè)文本大約包含個(gè)測(cè)試樣本。每個(gè)文本大約包含200200個(gè)單詞個(gè)單詞，分屬于，分屬于118118類，如金融、運(yùn)輸?shù)取ｎ?，如金融、運(yùn)輸?shù)取?主要使用線性核。主要使用線性核。 結(jié)果表明結(jié)果表明SVMSVM比其他的分類算法（如決策樹、比

35、其他的分類算法（如決策樹、K-K-近鄰近鄰算法等）具有良好的性能。算法等）具有良好的性能。Page 59九、支持向量機(jī)應(yīng)用3 3、圖像識(shí)別、圖像識(shí)別。(1)(1)視位無關(guān)的分類視位無關(guān)的分類 PontilPontil、VerriVerri研究了使用研究了使用SVMSVM于與視位無關(guān)的目標(biāo)于與視位無關(guān)的目標(biāo)識(shí)別。識(shí)別。Page 60九、支持向量機(jī)應(yīng)用(2)(2)基于顏色的分類基于顏色的分類 Oliver ChapelleOliver Chapelle及其合作者研究了僅使用顏色與及其合作者研究了僅使用顏色與光照信息下的光照信息下的SVMSVM目標(biāo)識(shí)別。目標(biāo)識(shí)別。Page 61九、支持向量機(jī)應(yīng)用(3

36、)(3)可視場(chǎng)景中的目標(biāo)檢測(cè)可視場(chǎng)景中的目標(biāo)檢測(cè) 人臉檢測(cè)人臉檢測(cè)：給定任意圖像作為輸入，檢測(cè)其中是否有人：給定任意圖像作為輸入，檢測(cè)其中是否有人臉存在，以及人臉的位置。臉存在，以及人臉的位置。 OsunaOsuna等人開發(fā)的系統(tǒng)，盡可能掃描像人臉的模式，等人開發(fā)的系統(tǒng)，盡可能掃描像人臉的模式，然后利用然后利用SVMSVM作為分類器，檢查一幅給定的圖像是否有作為分類器，檢查一幅給定的圖像是否有人臉。數(shù)據(jù)庫中包含臉與非臉的模式，圖像用人臉。數(shù)據(jù)庫中包含臉與非臉的模式，圖像用191919=36119=361個(gè)像素的向量表示，訓(xùn)練一個(gè)軟間隔分類器個(gè)像素的向量表示，訓(xùn)練一個(gè)軟間隔分類器，使用二階多項(xiàng)式核。，使用二階多項(xiàng)式核。汽車行進(jìn)的可視場(chǎng)景中的行人檢測(cè)汽車行進(jìn)的可視場(chǎng)景中的行人檢測(cè)： M.OrenM.Oren等人多項(xiàng)式核的等人多項(xiàng)式核的SVMSVM作為分類器，在之前端使作為分類器，在之前端使用小波作為特征提取的方法。用小波作為特征提取的方法。Page 62九、支持向量機(jī)應(yīng)