【正文】 ；QPOPT（線性和二次規(guī)劃）； SQOPT（大規(guī)模線性和凸二次規(guī)劃）； SPRNLP（稀疏最小二乘 ,稀疏和稠密非線性規(guī)劃）； SYSFIT（非線性方程組的參數(shù)估計）；TENSOLVE（非線性方程組和最小二乘）等。 41 七、支持向量機(jī) ? 167。 1 支持向量機(jī)的基本思想 ? 對于線性可分?jǐn)?shù)據(jù)，隨機(jī)產(chǎn)生一個超平面并移動它，直到訓(xùn)練集中屬于不同類別的樣本點正好位于該超平面的兩側(cè)。顯然，這種方法能夠解決線性分類問題，但不能保證產(chǎn)生的超平面是最優(yōu)的。 ? 支持向量機(jī)建立的分類超平面能夠在保證分類精度的同時，使超平面兩側(cè)的空白區(qū)域最大化，從而實現(xiàn)對線性可分問題的最優(yōu)分類 。 42 七、支持向量機(jī) ? 167。 最優(yōu)超平面的概念 ? 考慮 P個線性可分樣本 對于任一輸入樣本 Xp，其期望輸出為 d p = ，分別代表兩類的類別標(biāo)識。用于分類的超平面方程為： 1 1 2 2{ ( , ) , ( , ) , , ( , ) , , ( , ) }p p P PX d X d X d X d1?0 ( 1 )TW X b??0 , 10 , 1T ppT ppWb dXWb dX? ? ? ?? ? ? ?當(dāng)當(dāng)式中， X為輸入向量， W為權(quán)值向量， b為偏置，則有 43 七、支持向量機(jī) ? 由式（ 1）定義的超平面與最近的樣本點之間的間隔稱為分離邊緣，用 表示， 支持向量機(jī)的目標(biāo)是 找到一個使分離邊緣最大的超平面，即最優(yōu)超平面。如下圖： 最優(yōu)超平面 支持向量 ??44 七、支持向量機(jī) ? 假設(shè)最優(yōu)超平面的方程為： ? 則樣本空間中任一點 X到最優(yōu)超平面的距離為： ? 從而有判別函數(shù)， g(X)=r||W0||= W0TX＋ b0 ? 將判別函數(shù)歸一化，使所有樣本滿足： 00 0T XWb??000T XWbrW??00001 , 11 , 1 1 , 2 , ( 2)TpppW b dXpPW b dX? ? ? ?? ? ? ? ? ?當(dāng)當(dāng)45 七、支持向量機(jī) ? 則對于離最優(yōu)超平面最近的特殊樣本 Xs滿足|g(Xs )|=1，稱為 支持向量 。 （ 2）式可表示為： ? 從支持向量到最優(yōu)超平面的代數(shù)距離為： ( ) 1 , 1 , 2 , , ( 3 )pT p b p PdW X ? ? ?0001, 1 ,W()1, 1 ,Ws sss sd Xg XrWd X?????? ?? ? ? ???在 最 優(yōu) 超 平 面 的 正 面在 最 優(yōu) 超 平 面 的 負(fù) 面46 七、支持向量機(jī) ? 因此，兩類之間的間隔可用分離邊緣表示為： （ 4）式表明，要使分離邊緣最大化等價于使權(quán)值向量的范數(shù) ||W|| 最小化。因此， 滿足（ 3）式的條件且使 ||W|| 最小的分類超平面就是最優(yōu)超平面。 02 ( 4 )W? ?47 七、支持向量機(jī) ? 167。 最優(yōu)超平面的構(gòu)建 ? 建立最優(yōu)線性分類超平面問題可以表示成如下的約束優(yōu)化問題。 采用 Lagrange系數(shù)方法解決此約束最優(yōu)化問題，引入 Lagrange函數(shù) 211m in ( ) ( 5 )22. . ( ) 1 1 , 2 , ,Tp T pW W W Ws t d W X b p P? ? ?? ? ?11( , , ) [ ( ) 1 ] ( 6 )2m in ( , , )PT p T pppL W b W W d W X bL W b? ???? ? ? ??求48 七、支持向量機(jī) L ( , , ) L ( , , ) L ( , , )000W b W b W bWb??????? ???? ? ?令得： 11( 7 )0( ) 1 ( )PppppPpppT p pW d XdW X b d?????? ????????? ????支 持 向 量將（ 6）式展開： 1 1 1111( , , )21212P P PT T p p pp p pp p pPTTppPTppL W b W W W d X d bW W W WWW? ? ? ???? ? ???? ? ? ?? ? ?? ? ? ?? ? ? ?49 七、支持向量機(jī) ? 將（ 7）式代入上式，則問題轉(zhuǎn)化為： 1 1 11m a x ( ) ( )2P P P p T jpjp p jp p jQ X Xdd? ? ? ?? ? ???? ? ?設(shè) Q（ )的最優(yōu)解為 0 1 0 2 0 0{ , , , , , }pP? ? ? ?則 最優(yōu)超平面的權(quán)向量為 ： 000 1P p p p ppppW d X d X??????? 所 有 支 持 向 量最優(yōu)分類判斷函數(shù)為 ： 0 01( ) s g n [ ( ) ]P p p Tppf X d X X b??????50 七、支持向量機(jī) ? 167。 2 支持向量機(jī)神經(jīng)網(wǎng)絡(luò) ? 支持向量機(jī)求解非線性可分模式分類的方法如下： ? 將輸入向量映射到一個高維特征向量空間，如果選用的映射函數(shù)適當(dāng)且特征空間的維數(shù)足夠高，則大多數(shù)非線性可分模式在特征空間中可以轉(zhuǎn)化為線性可分模式，因此可以在該特征空間構(gòu)造最優(yōu)超平面進(jìn)行模式分類。 51 七、支持向量機(jī) ? 設(shè) X為 N維輸入空間的向量，令 φ (X)=[φ1(X), φ2(X), …, φ m(X)]T表示從輸入空間到 M維特征空間的非線性變換，稱為輸入向量 X在特征空間誘導(dǎo)出的“像”。 ? 特征空間分類超平面的權(quán)向量為： 1()P ppppWXd?????52 七、支持向量機(jī) ? 超平面方程為： 01( ) ( ) 0P p T poppd X X b??? ? ? ??最優(yōu)分類判別函數(shù)為 001( ) s g n [ ( ) ( ) ]Pp T pppf X d X X b??? ? ? ??53 七、支持向量機(jī) ? 167。 3 支持向量機(jī)的學(xué)習(xí)算法 步驟如下： （ 1）通過非線性變換 將輸入向量映射到高維特征空間。 （ 2）在約束條件 ?10 , 0 ( 0 ) , 1 , 2 , ,P pp pppd C p P????? ? ? ? ?? 或 下 求 解 使 目 標(biāo) 函 數(shù)T01 1 11( ) ( ) ( )2P P P pjpjp p jp p jQ X Xdd??? ? ?? ? ?? ? ? ?? ? ? p最 大 化 的 。54 七、支持向量機(jī) ? （ 3）計算最優(yōu)權(quán)值 001()p ppppWXd?????（ 4）對于分類模式 X，計算分類判別函數(shù) 根據(jù) f(X)為 1或 1，決定 X的類別歸屬。 001( ) s g n [ ( ) ( ) ]Pp T pppf X d X X b??? ? ? ??55 七、支持向量機(jī) ? 167。 4 支持向量機(jī)處理 XOR問題 ? XOR問題： ? 4個樣本 1 1 2 2 3 3 4 41 1 1 1X , 1 , X , 1 , X , 1 , X , 11 1 1 1d d d d? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ???? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?如圖： 2 1 X2 1 2 2 1 x1 1 2 (1,1) (1,1) (1,1) (1,1) 56 七、支持向量機(jī) 221 2 1 2 12( ) [ 1 , 2 , 2 , 2 , , ] TX x x x x xx??選擇映射函數(shù) 1 0 1 2 2 1 0 1 2 (1 , 2 , 2 , 2 ,1 ,1 )??(1 , 2 , 2 , 2 ,1 ,1 )(1 , 2 , 2 , 2 ,1 ,1 )??(1 , 2 , 2 , 2 ,1 ,1 )??2122xx2?12x可將二維訓(xùn)練樣本映射到一個六維特征空間，這個六維空間在平面上的投影如下圖。 (1, 1) (1, 1) (1, 1) (1, 1) 57 七、支持向量機(jī) ? 可以看出分離邊緣 最優(yōu)超平面為 X1X2＝ 0。（推導(dǎo)過程略） 2? ?221 1 2 2 1 2( ) [ 1 , , 2 , , 2 , 2 ] TX x x x x x x??注： 也可選擇映射函數(shù)