第5章 支持向量機(jī)及其學(xué)習(xí)算法-2016

1、支持向量機(jī)及其應(yīng)用支持向量機(jī)及其應(yīng)用 Support Vector Machines and its Application 主要內(nèi)容主要內(nèi)容一、一、 歷史背景歷史背景二、二、 統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論三、三、 支持向量機(jī)支持向量機(jī)四、四、 支持向量機(jī)的分類學(xué)習(xí)算法支持向量機(jī)的分類學(xué)習(xí)算法 五、五、 用于函數(shù)擬合的支持向量機(jī)用于函數(shù)擬合的支持向量機(jī) 六、六、 支持向量機(jī)算法的研究與應(yīng)用支持向量機(jī)算法的研究與應(yīng)用 傳統(tǒng)統(tǒng)計(jì)學(xué)是一種漸進(jìn)理論漸進(jìn)理論，研究的是樣本數(shù)目趨于無窮大時(shí)的極限特性。 現(xiàn)有的學(xué)習(xí)方法多基于傳統(tǒng)統(tǒng)計(jì)學(xué)理論傳統(tǒng)統(tǒng)計(jì)學(xué)理論，但在實(shí)際應(yīng)用中，樣本往往是有限的，因此一些理論上很優(yōu)秀的學(xué)

2、習(xí)方法在實(shí)際中的表現(xiàn)卻不盡人意，存在著一些難以克服的問題，比如說如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過學(xué)習(xí)問題、局部極小值問題等，從本質(zhì)本質(zhì)上來說就是因?yàn)槔碚撋闲枰獰o窮樣本與實(shí)際中樣本有限的矛盾造成的。 與傳統(tǒng)統(tǒng)計(jì)學(xué)的方向不同，Vapnik等人提出了一個(gè)較完善的基于有限樣本的理論體系統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論。 統(tǒng)計(jì)學(xué)習(xí)理論是一種專門研究小樣本研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論，它從更本質(zhì)上研究機(jī)器學(xué)習(xí)問題，為解決有限樣本學(xué)習(xí)問題提供了一個(gè)統(tǒng)一的框架 。 支持向量機(jī)方法是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的通用學(xué)習(xí)方法，它具有全局優(yōu)化、適應(yīng)性強(qiáng)、理論完備、泛化性能好等優(yōu)點(diǎn) 。Return統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論

3、（ Statistical Learning Theory ，SLT） 機(jī)器學(xué)習(xí)的基本問題 統(tǒng)計(jì)學(xué)習(xí)理論機(jī)器學(xué)習(xí)問題的表示機(jī)器學(xué)習(xí)問題的表示 基于數(shù)據(jù)的機(jī)器學(xué)習(xí)是現(xiàn)有智能技術(shù)中的重要方面，其研究的實(shí)質(zhì)實(shí)質(zhì)是根據(jù)給定的訓(xùn)練樣本求出對系統(tǒng)輸入輸出之間依賴關(guān)系的估計(jì)，使它能對未知樣本的輸出做出盡可能準(zhǔn)確的預(yù)測。 定義期望風(fēng)險(xiǎn)： ,RLfdFyxx y,fx,Lfyx 預(yù)測函數(shù)集 廣義參數(shù) 損失函數(shù) （誤差函數(shù)）,F x y聯(lián)合概率分布 經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 （Empirical Risk Minimization ，ERM） 實(shí)際應(yīng)用中，一般根據(jù)概率論中的大數(shù)定理，即采用下式的算術(shù)平均來逼近

4、期望風(fēng)險(xiǎn)。 用對參數(shù) 求經(jīng)驗(yàn)風(fēng)險(xiǎn) 的最小值代替求期望風(fēng)險(xiǎn) 的最小值。 11,nempiiiRLfnyx empR R經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 從期望風(fēng)險(xiǎn)最小化到經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化沒有可靠的依據(jù),只是直觀上合理的想當(dāng)然。期望風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)都是w的函數(shù),概率論中的大數(shù)定理只說明了當(dāng)樣本趨于無窮多時(shí)經(jīng)驗(yàn)風(fēng)險(xiǎn)將在概率意義上趨近于期望風(fēng)險(xiǎn),并沒有保證兩個(gè)風(fēng)險(xiǎn)的w是同一點(diǎn),更不能保證經(jīng)驗(yàn)風(fēng)險(xiǎn)能夠趨近于期望風(fēng)險(xiǎn)。即使有辦法使這些條件在樣本數(shù)無窮大時(shí)得到保證, 也無法認(rèn)定在這些前提下得到的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化方法在樣本數(shù)有限時(shí)仍能得到好的結(jié)果。復(fù)雜性與推廣能力復(fù)雜性與推廣能力 學(xué)習(xí)機(jī)器對未來輸出進(jìn)行正確預(yù)測的能力稱

5、作推推廣能力（廣能力（也稱為“泛化能力泛化能力”）。）。 在某些情況下,訓(xùn)練誤差過小反而導(dǎo)致推廣能力的下降,這就是過學(xué)習(xí)過學(xué)習(xí)問題。 神經(jīng)網(wǎng)絡(luò)的過學(xué)習(xí)問題是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則失敗的一個(gè)典型例子。 事實(shí)上，從期望風(fēng)險(xiǎn)最小化到經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化并沒有可靠的理論依據(jù)，只是直觀上合理的想當(dāng)然做法。 經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則不成功的一個(gè)例子就是神經(jīng)網(wǎng)絡(luò)的過學(xué)習(xí)過學(xué)習(xí)問題:訓(xùn)練誤差（經(jīng)驗(yàn)風(fēng)險(xiǎn)）過小反而會導(dǎo)致推廣能力的下降，即真實(shí)誤差（期望風(fēng)險(xiǎn)）的增加。 出現(xiàn)過學(xué)習(xí)現(xiàn)象的原因主要是由于學(xué)習(xí)樣本不充分和學(xué)習(xí)機(jī)器設(shè)計(jì)不合理。 當(dāng)試圖用一個(gè)復(fù)雜的模型去擬合有限的樣本，必然會喪失推廣能力。由此可見，有限樣本下學(xué)習(xí)機(jī)器的復(fù)雜性

6、復(fù)雜性與推廣性推廣性之間存在矛盾。機(jī)器的復(fù)雜度高，必然會導(dǎo)致其推廣性差；反之，一個(gè)推廣性好的學(xué)習(xí)機(jī)器，其分類能力必然不夠強(qiáng)。 設(shè)計(jì)一個(gè)好的學(xué)習(xí)機(jī)器的目標(biāo)目標(biāo)就變成如何在學(xué)習(xí)能力和推廣性之間取得一個(gè)平衡，使得在滿足給定學(xué)習(xí)能力的前提下，提高其推廣性。 統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論（SLT） 統(tǒng)計(jì)學(xué)習(xí)理論被認(rèn)為是目前針對小樣本統(tǒng)計(jì)估計(jì)和預(yù)測學(xué)習(xí)的最佳理論。它從理論上較為系統(tǒng)的研究了經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則成立的條件、有限樣本下經(jīng)驗(yàn)風(fēng)險(xiǎn)與期望風(fēng)險(xiǎn)的關(guān)系以及如何利用這些理論找到新的學(xué)習(xí)原則和方法等問題。 其中，最有指導(dǎo)性的理論結(jié)果是推廣性的推廣性的界界的結(jié)論，和與此相關(guān)的一個(gè)核心概念是函數(shù)集的函數(shù)集的VC維維。

7、 函數(shù)集的函數(shù)集的VC維維 （Vapnik Chervonenkis Dimension ） 模式識別方法中VC維的直觀定義是：對于一個(gè)指標(biāo)函數(shù)集，如果存在n個(gè)樣本能夠被函數(shù)集中的函數(shù)按所有可能的 種形式分開， 則稱函數(shù)集能夠把n個(gè)樣本打散；函數(shù)集的VC維就是它能打散的最大樣本數(shù)目h。有界實(shí)函數(shù)的VC維可以通過用一定的閾值將其轉(zhuǎn)化為指示函數(shù)來定義。 VC維反映了函數(shù)集的學(xué)習(xí)能力，維反映了函數(shù)集的學(xué)習(xí)能力，VC維越維越大則學(xué)習(xí)機(jī)器越復(fù)雜（學(xué)習(xí)能力越強(qiáng)）。大則學(xué)習(xí)機(jī)器越復(fù)雜（學(xué)習(xí)能力越強(qiáng)）。2hVC維維(函數(shù)的多樣性函數(shù)的多樣性) 為了研究經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化函數(shù)集的學(xué)習(xí)一致收斂速度和推廣性，SLT定義

8、了一些指標(biāo)來衡量函數(shù)集的性能，其中最重要的就是VC維(Vapnik-Chervonenkis Dimension)。 VC維維：對于一個(gè)指示函數(shù)集，如果存在h個(gè)樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個(gè)樣本打散，函數(shù)集的VC維就是能夠打散的最大樣本數(shù)目。 如果對任意的樣本數(shù)，總有函數(shù)能打散它們，則函數(shù)集的VC維就是無窮大。VC維（續(xù)）維（續(xù)） 一般而言,VC維越大, 學(xué)習(xí)能力就越強(qiáng),但學(xué)習(xí)機(jī)器也越復(fù)雜。 目前還沒有通用的關(guān)于計(jì)算任意函數(shù)集的VC維的理論,只有對一些特殊函數(shù)集的VC維可以準(zhǔn)確知道。 N維實(shí)數(shù)空間中線性分類器和線性實(shí)函數(shù)的VC維是n+1。 Sin(a

9、x)的VC維為無窮大。 VCVC維（續(xù)）維（續(xù)） Open problem: 對于給定的學(xué)習(xí)函數(shù)集,如何用理論或?qū)嶒?yàn)的方法計(jì)算其VC維是當(dāng)前統(tǒng)計(jì)學(xué)習(xí)理論研究中有待解決的一個(gè)難點(diǎn)問題。推廣性的界推廣性的界 統(tǒng)計(jì)學(xué)習(xí)理論系統(tǒng)地研究了各種類型函數(shù)集的經(jīng)驗(yàn)風(fēng)險(xiǎn)經(jīng)驗(yàn)風(fēng)險(xiǎn)（即訓(xùn)練誤差）（即訓(xùn)練誤差）和實(shí)際風(fēng)險(xiǎn)實(shí)際風(fēng)險(xiǎn)（即期望風(fēng)險(xiǎn)）（即期望風(fēng)險(xiǎn)）之間的關(guān)系，即推廣性的界。 關(guān)于兩類分類問題有如下結(jié)論：對指示函數(shù)集中的所有函數(shù)，經(jīng)驗(yàn)風(fēng)險(xiǎn)和實(shí)際風(fēng)險(xiǎn)之間至少以概率 滿足如下關(guān)系： 其中h是函數(shù)集的VC維，l是樣本數(shù)。 1 lhlhRRemp4ln12ln置信范圍置信范圍實(shí)際實(shí)際風(fēng)險(xiǎn)風(fēng)險(xiǎn)學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險(xiǎn)由兩部分組

10、成： 經(jīng)驗(yàn)風(fēng)險(xiǎn) ，即訓(xùn)練誤差； 置信范圍（Confidence Interval） 可以簡單的表示為： 它表明在有限樣本訓(xùn)練下，學(xué)習(xí)機(jī)VC維越高（機(jī)器的復(fù)雜性越高），則置信范圍越大，導(dǎo)致真實(shí)風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間可能的差別越大。這就是為什么出現(xiàn)過學(xué)習(xí)現(xiàn)象的原因。 empR lhRRemp結(jié)構(gòu)風(fēng)險(xiǎn)最小化結(jié)構(gòu)風(fēng)險(xiǎn)最小化 （Structural Risk Minimization，SRM） 經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則在樣本有限（即 較大）時(shí)是不合理的，此時(shí)一個(gè)小的經(jīng)驗(yàn)風(fēng)險(xiǎn)值并不能保證小的實(shí)際風(fēng)險(xiǎn)值。為解決此問題，就需要在保證分類精度（即減小經(jīng)驗(yàn)風(fēng)險(xiǎn)）的同時(shí)，降低學(xué)習(xí)機(jī)器的VC維，從而使得學(xué)習(xí)機(jī)器在整個(gè)樣本集上的

11、期望風(fēng)險(xiǎn)得到控制，這就是結(jié)構(gòu)風(fēng)險(xiǎn)最小化（SRM）原則的基本思想。 結(jié)構(gòu)風(fēng)險(xiǎn)最小化為我們提供了一種不同于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的更科學(xué)的學(xué)習(xí)機(jī)器設(shè)計(jì)原則，顯然，利用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的思想，就可以完美解決神經(jīng)網(wǎng)絡(luò)中的過學(xué)習(xí)問題。支持向量機(jī)方法實(shí)際上就是這種思想的具體實(shí)現(xiàn)。 lh風(fēng)險(xiǎn)欠學(xué)習(xí)過學(xué)習(xí)實(shí)際風(fēng)險(xiǎn)的界置信范圍經(jīng)驗(yàn)風(fēng)險(xiǎn)1S2S3Sh函數(shù)集子集： VC維： 結(jié)構(gòu)風(fēng)險(xiǎn)最小化示意圖 321SSS321hhh2022-5-1123支持向量機(jī)支持向量機(jī)SVMSVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由學(xué)習(xí)方法，它是由Boser,Guyon, Boser,Guyon, Vapni

12、kVapnik在在COLT-92COLT-92上首次提出，從此上首次提出，從此迅速發(fā)展起來迅速發(fā)展起來Vapnik V N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New York Vapnik V N. 1998. Statistical Vapnik V N. 1998. Statistical Learning Theory. Wiley-Learning Theory. Wiley-Interscience Publication, John Interscience Publication,

13、 John Wiley&Sons, IncWiley&Sons, Inc目前已經(jīng)在許多智能信息獲取與處理領(lǐng)目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用。域都取得了成功的應(yīng)用。 支持向量機(jī)支持向量機(jī) （Support Vector Machine，SVM） 90年代中期，在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上發(fā)展出了一種通用的學(xué)習(xí)方法支持向量機(jī)。它根據(jù)有限的樣本信息在模型的復(fù)雜它根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷，以獲得性和學(xué)習(xí)能力之間尋求最佳折衷，以獲得最好的泛化能力最好的泛化能力。 支持向量機(jī)在很多機(jī)器學(xué)習(xí)問題的應(yīng)用中已初步表現(xiàn)出很多優(yōu)于已有方法的性能。 支持向量機(jī)的理論最

14、初來自于對數(shù)據(jù)分類問題的處理。對于線性可分?jǐn)?shù)據(jù)的二值分類，如果采用多層前向網(wǎng)絡(luò)來實(shí)現(xiàn)，其機(jī)理可以簡單描述為：系統(tǒng)隨機(jī)的產(chǎn)生一個(gè)超平面并移動它，直到訓(xùn)練集合中屬于不同類別的點(diǎn)正好位于該超平面的不同側(cè)面，就完成了對網(wǎng)絡(luò)的設(shè)計(jì)要求。但是這種機(jī)理決定了不能保證最終所獲得的分割平面位于兩個(gè)類別的中心，這對于分類問題的容錯(cuò)性容錯(cuò)性是不利的。 保證最終所獲得的分割平面位于兩個(gè)類別的中心對于分類問題的實(shí)際應(yīng)用是很重要的。支持向量機(jī)方法很巧妙地解決了這一問題。 該方法的機(jī)理可以簡單描述為：尋找一個(gè)滿足分類要求的最優(yōu)分類超平面，使得該超平面在保證分類精度保證分類精度的同時(shí)，能夠使使超平面兩側(cè)的空白區(qū)域最大化超平面

15、兩側(cè)的空白區(qū)域最大化；從理論上來說，支持向量機(jī)能夠?qū)崿F(xiàn)對線性可分?jǐn)?shù)據(jù)的最優(yōu)分類。為了進(jìn)一步解決非線性問題，Vapnik等人通過引入核映射核映射方法轉(zhuǎn)化為高維空間的線性可分問題來解決。 最優(yōu)分類超平面最優(yōu)分類超平面 （Optimal Hyperplane ） 對于兩類線性可分兩類線性可分的情形，可以直接構(gòu)造最優(yōu)超平面，使得樣本集中的所有樣本滿足如下條件：（1）能被某一超平面正確劃分；（2）距該超平面最近的異類異類向量與超平面之間的距離最大，即分類間隔（margin ）最大； 以上兩個(gè)條件體現(xiàn)了結(jié)構(gòu)風(fēng)險(xiǎn)最小化（SRM）的原則。保證經(jīng)驗(yàn)風(fēng)險(xiǎn)最小保證置信范圍最小 設(shè)訓(xùn)練樣本輸入為 ， ， 對應(yīng)的期望輸

16、出為 如果訓(xùn)練集中的所有向量均能被某超平面正確劃分，并且距離平面最近的異類異類向量之間的距離最大（即邊緣margin最大化），則該超平面為最優(yōu)超平面（Optimal Hyperplane ） 。ix1, ,ildiRx1, 1iy最優(yōu)分類面示意圖最優(yōu)分類面示意圖 支持向量Support Vector 其中距離超平面最近的異類向量被稱為支持向量（Support Vector），一組支持向量可以唯一確定一個(gè)超平面。SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來，其超平面記為： 為使分類面對所有樣本正確分類并且具備分類間隔，就要求它滿足如下約束：0bxw1 110 1 1iiiiiibforyybbf

17、ory xwxwxw 可以計(jì)算出分類間隔為 ，因此構(gòu)造最優(yōu)超平面的問題就轉(zhuǎn)化為在約束式下求： 為了解決這個(gè)約束最優(yōu)化問題，引入下式所示的Lagrange函數(shù)： 其中 為Lagrange乘數(shù)。約束最優(yōu)化問題的解由Lagrange函數(shù)的鞍點(diǎn)決定。 2 w 211min 22www w21112lliiiiiiLybwxw 0i 利用Lagrange優(yōu)化方法可以將上述二次規(guī)劃問題轉(zhuǎn)化為其對偶問題對偶問題，即在約束條件： 下對 求解下列函數(shù)的最大值： 如果 為最優(yōu)解，那么： 選擇一個(gè)正分量并據(jù)此計(jì)算 liiiy10lii, 1,0i 1,112lliijijijii jWy yxxi1liiiiywx

18、*jlijiiijxxyyb1*).( 以上是在不等式約束下求二次函數(shù)極值問題，是一個(gè)二次規(guī)劃問題（Quadratic Programming，QP），），存在唯一解。根據(jù)最優(yōu)性條件Karush-Khn-Tucker條件（KKT條件），這個(gè)優(yōu)化問題的解必須滿足： 對多數(shù)樣本對多數(shù)樣本 將為零，取值不為零的將為零，取值不為零的 所對應(yīng)的樣本即為支持向量，它們通常所對應(yīng)的樣本即為支持向量，它們通常只是全體樣本中很少的一部分。只是全體樣本中很少的一部分。 10,1,iiib yilx wii 求解上述問題后得到的最優(yōu)分類函數(shù)是： 在通過訓(xùn)練得到最優(yōu)超平面后,對于給定的未知樣本x，只需計(jì)算f (x)即

19、可判斷x所屬的分類。 1sgnliiiifybxxx 若訓(xùn)練樣本集是線性不可分的，或事先不知道它是否線性可分，將允許存在一些誤分類的點(diǎn)，此時(shí)引入一個(gè)非負(fù)松弛變量非負(fù)松弛變量 ，約束條件變?yōu)? 目標(biāo)函數(shù)改為在以上約束條件下求： 即折衷考慮最小錯(cuò)分樣本和最大分類間隔。其中，C0 為懲罰因子 ，控制對錯(cuò)分樣本的懲罰程度 。0i1 0 1,iiiiybil w x，11min ,2liiCww w 線性不可分情況和線性可分情況的差別差別就在于可分模式中的約束條件中的 在不可分模式中換為了更嚴(yán)格的條件 。除了這一修正，線性不可分情況的約束最優(yōu)化問題中權(quán)值和閾值的最優(yōu)值的計(jì)算都和線性可分情況中的過程是相同

20、的。 0i0iC支持向量機(jī)支持向量機(jī) （Support Vector Machine，SVM） 在現(xiàn)實(shí)世界中，很多分類問題都是線性不可分的，即在原來的樣本空間中無法找到一個(gè)最優(yōu)的線性分類函數(shù)，這就使得支持向量機(jī)的應(yīng)用具有很大的局限性。但是可以設(shè)法通過非線性變換將原樣本空間的非通過非線性變換將原樣本空間的非線性問題轉(zhuǎn)化為另一個(gè)空間中的線性問線性問題轉(zhuǎn)化為另一個(gè)空間中的線性問題題。SVM就是基于這一思想的。首先將輸入向量通過非線性映射變換到一個(gè)高維的特征向量空間，在該特征空間中構(gòu)造最優(yōu)分類超平面。 由于在上面的二次規(guī)劃（QP）問題中，無論是目標(biāo)函數(shù)還是分類函數(shù)都只涉及內(nèi)積運(yùn)算，如果采用核函數(shù)(Ke

21、rnel Function)就可以避免在高維空間進(jìn)行復(fù)雜運(yùn)算，而通過原空間的函數(shù)來實(shí)現(xiàn)內(nèi)積運(yùn)算。因此，選擇合適的內(nèi)積核函數(shù)核函數(shù) 就可以實(shí)現(xiàn)某一非線性變換后的線性分類，而計(jì)算復(fù)雜度卻沒有增加多少 ，從而巧妙地解決了高維空間中計(jì)算帶來的“維數(shù)災(zāi)難”問題。 ,ijijK x xxx 此時(shí)，相應(yīng)的決策函數(shù)化為： 支持向量機(jī)求得的決策函數(shù)形式上類似于一個(gè)神經(jīng)網(wǎng)絡(luò)，其輸出是若干中間層節(jié)點(diǎn)的線性組合，而每一個(gè)中間層節(jié)點(diǎn)對應(yīng)于輸入樣本與一個(gè)支持向量的內(nèi)積，因此也被稱作是支持向量網(wǎng)絡(luò)。 1sgn,liiiifyKbxx x支持向量機(jī)示意圖支持向量機(jī)示意圖 選擇不同的核函數(shù) 可以生成不同的支持向量機(jī)，常有以下幾

22、種： （1）線性核函數(shù)： （2）多項(xiàng)式核函數(shù)： （3）Gauss核函數(shù)： （4）Sigmoid核函數(shù)： ,ijijK x xxx,iiKx xx x,1qiiKx xx x2( ,)exp2iiKxxx x,tanhiiKcx xx x一個(gè)具體核函數(shù)的例子一個(gè)具體核函數(shù)的例子 假設(shè)數(shù)據(jù)是位于 中的向量，選擇： 然后尋找滿足下述條件的空間H：使映射 從 映射到H且滿足： 可以選擇H=R3以及： 2R 2,ijijKx xxx2R 2 x yxy211 222( )2xx xxxx2x1z3z2z1用圖來表示該變換：用圖來表示該變換：SVM用于二維樣本分類用于二維樣本分類支持向量機(jī)的分類學(xué)習(xí)算法支

23、持向量機(jī)的分類學(xué)習(xí)算法 對于分類問題，用支持向量機(jī)方法進(jìn)行求解的學(xué)習(xí)算法過程為： 第一步第一步 給定一組輸入樣本 ， 及其對應(yīng)的期望輸出 ； 第二步第二步 選擇合適的核函數(shù) 及相關(guān)參數(shù)； 第三步第三步 在約束條件 和 下求解 得到最優(yōu)權(quán)值 ；ixli, 11, 1iy,ijijK x xxxliiiy100iC1,11max ( )(, )2lliijijiii jWy y K x xi 第四步 計(jì)算： ；選擇一個(gè) 計(jì)算 第五步 對于待分類向量x ，計(jì)算： 為1或1，決定x屬于哪一類。1()liiiiywx 1sgn,liiiifyKbxx xlijiiijxxKyyb1*)(，0*j用于函數(shù)

24、擬合的支持向量機(jī)用于函數(shù)擬合的支持向量機(jī) 假定數(shù)據(jù)集 。首先考慮用線性回歸函數(shù)線性回歸函數(shù) 擬合數(shù)據(jù)集X的問題。 所有訓(xùn)練數(shù)據(jù)在精度 下無誤差地用線性函數(shù)擬合，即： 考慮到允許擬合誤差存在的情況：(,)1,iiXyilx( )fbxw x 1,iiiiybilbyw xw x 1,iiiiiiybilbyw xw x 優(yōu)化目標(biāo)函數(shù)為： 對偶問題為：在約束條件 下求下式的最大值。 回歸函數(shù)為： 11min ( ,)()()2liiiiiC ww w11111(,)()()()()()2lllliiiiiiiiijjijiiijWy xx0, 1,iiCil 1( )()()liiiifbbxw

25、xx xPage 48 其它類型的支持向量機(jī)其它類型的支持向量機(jī) 線性可分的支持向量（分類）機(jī)線性可分的支持向量（分類）機(jī) 線性支持向量（分類）機(jī)線性支持向量（分類）機(jī) 支持向量（分類）機(jī)支持向量（分類）機(jī) 最小二乘支持向量（分類）機(jī)最小二乘支持向量（分類）機(jī) 硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī) 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī) - -支持向量（回歸）機(jī)支持向量（回歸）機(jī) 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī) 不確定支持向量機(jī)不確定支持向量機(jī) 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 49四、最小二乘支持向量(分類)機(jī)nkkkTempybxwn

26、1bwR12)(),( SuykensSuykens等人等人在支持向量回歸機(jī)中引入如下的二次損失函數(shù)作在支持向量回歸機(jī)中引入如下的二次損失函數(shù)作為代價(jià)函數(shù)，并將其不等式約束改為等式約束：為代價(jià)函數(shù)，并將其不等式約束改為等式約束：nkkTeb,w,e21wwe)J(w,min1221且?guī)в腥缦碌仁郊s束條件：且?guī)в腥缦碌仁郊s束條件： nkebxwykkTk, 1,)(其中其中 bxxyeTi因此，把支持向量機(jī)的原始優(yōu)化問題轉(zhuǎn)變?yōu)槿缦聦ふ乙虼耍阎С窒蛄繖C(jī)的原始優(yōu)化問題轉(zhuǎn)變?yōu)槿缦聦ふ襴和和b的優(yōu)的優(yōu)化問題：化問題： nkebxwykkTk, 1,)(Page 50最小二乘支持向量(回歸)機(jī) 為了在對

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

28、)T, e=(e1,en)T, =(1, n)T。在上式中消去。在上式中消去w和和e后，得到如下后，得到如下線性方程組：線性方程組： yebwIxIIxInnTnnTn00001)(001000)(00ybInnTn01110其中其中kl=(xk)T(xl), k,l=1,.,n。 Page 52最小二乘支持向量(回歸)機(jī)根據(jù)根據(jù)Mercer定理，最小二乘支持向量分類器為：定理，最小二乘支持向量分類器為： 其中其中與與b通過求解上述方程組通過求解上述方程組得到。得到。 nkkkbxxKxf1),(sgn)(Page 53例子：最小二乘支持向量(分類)機(jī)Page 54目錄目錄u 線性可分的支持向

29、量（分類）機(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 55五、硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)1 1、一個(gè)簡單的回歸例子、一個(gè)簡單的回歸例子。 考慮兩個(gè)量考慮兩個(gè)量x x與與y y的關(guān)系。假設(shè)已

30、測得若干個(gè)數(shù)據(jù)構(gòu)成的數(shù)據(jù)的關(guān)系。假設(shè)已測得若干個(gè)數(shù)據(jù)構(gòu)成的數(shù)據(jù)集集D D：Page 56硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)Page 57五、硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)2 2、不敏感損失函數(shù)、不敏感損失函數(shù) 為了在回歸問題中使用結(jié)構(gòu)風(fēng)險(xiǎn)代替經(jīng)驗(yàn)風(fēng)險(xiǎn)來作為期望風(fēng)為了在回歸問題中使用結(jié)構(gòu)風(fēng)險(xiǎn)代替經(jīng)驗(yàn)風(fēng)險(xiǎn)來作為期望風(fēng)險(xiǎn)，以及保持在支持向量分類機(jī)的稀疏性質(zhì)，險(xiǎn)，以及保持在支持向量分類機(jī)的稀疏性質(zhì)，Vapnik引入了如引入了如下的下的不敏感損失函數(shù)不敏感損失函數(shù)：其中：其中：Page 58硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)Page 59硬硬 -

31、 -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)),( ,),(),(2211nnyxyxyxD，niRyRXximi, 1,首先考慮硬首先考慮硬 - -帶支持向量帶支持向量線性線性回歸回歸情況。設(shè)有如下兩類樣本的訓(xùn)情況。設(shè)有如下兩類樣本的訓(xùn)練集：練集：即使用一個(gè)線性函數(shù)來即使用一個(gè)線性函數(shù)來回歸回歸（擬合擬合、逼近逼近）樣本點(diǎn)，且這種情）樣本點(diǎn)，且這種情況下，沒有樣本點(diǎn)落在況下，沒有樣本點(diǎn)落在 - -帶外。表示為如下的帶外。表示為如下的原始優(yōu)化問題原始優(yōu)化問題：nibxwyniybxwtswiiiibw, 1,)(, 1,)(. .21min2,y=(w.x)+b+y=(w.x)+b-y=(w.

32、x)+bPage 60硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)niiiiniiiibxwybxwywbwL1*12(*)()(21),(nTnnR2*22*11(*), ,(0),(, 0),(*)(*)bwLbwLwb 為求解上述原始優(yōu)化問題為求解上述原始優(yōu)化問題, ,使用使用Lagrange乘子法乘子法將其轉(zhuǎn)化為對將其轉(zhuǎn)化為對偶問題。于是引入偶問題。于是引入Lagrange函數(shù)函數(shù)：其中，其中， 稱為稱為Lagrange乘子。乘子。首先求首先求Lagrange函數(shù)關(guān)于函數(shù)關(guān)于w,bw,b的極小值。由的極小值。由極值條件有：極值條件有：niii1*0)(niiiixw1*)(得到

33、：得到：Page 61硬硬 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)nitsxxiniiininiiinjjijjii, 1, 0, 0)(. .)()()(21min(*)1*11*1*）（niiiixw1*)(將上式代入將上式代入Lagrange函數(shù)，則原始的優(yōu)化問題轉(zhuǎn)化為如下的函數(shù)，則原始的優(yōu)化問題轉(zhuǎn)化為如下的對偶問題對偶問題( (使用極小形式使用極小形式) )：求解上述對偶問題，得求解上述對偶問題，得 ( (* *) )。則參數(shù)對。則參數(shù)對(w,b)(w,b)可由下式計(jì)算：可由下式計(jì)算：)(jjxwyb選擇某個(gè)選擇某個(gè)j 0或或j* 0來計(jì)算來計(jì)算b: :Page 62硬硬 -

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

35、 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)u - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)u 最小二乘支持向量（回歸）機(jī)最小二乘支持向量（回歸）機(jī)u 支持向量機(jī)應(yīng)用支持向量機(jī)應(yīng)用Page 64軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)),( ,),(),(2211nnyxyxyxD，niRyRXximi, 1,考慮軟考慮軟 - -帶支持向量帶支持向量線性線性回歸回歸情況。設(shè)有如下兩類樣本的訓(xùn)練集情況。設(shè)有如下兩類樣本的訓(xùn)練集：同樣希望使用一個(gè)線性函數(shù)來同樣希望使用一個(gè)線性函數(shù)來回歸回歸樣本點(diǎn)，且這種情況下，除了樣本點(diǎn)，且這種

36、情況下，除了大量樣本點(diǎn)在大量樣本點(diǎn)在 - -帶內(nèi)，還有少量的樣本帶內(nèi)，還有少量的樣本落在落在 - -帶外。這時(shí)需要對帶外。這時(shí)需要對落在落在 - -帶外的樣本進(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 65軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)niiiiniiiiniiiiiniiibxwybxwynCwbwL1*11*1*2)()()()(21

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

38、 0)(. .)()()()(21min*1*1*11*1*）（niiiixw1*)(將上式代入將上式代入Lagrange函數(shù)，則原始的優(yōu)化問題轉(zhuǎn)化為如下的函數(shù)，則原始的優(yōu)化問題轉(zhuǎn)化為如下的對偶問題對偶問題( (使用極小形式使用極小形式) )：求解上述對偶問題，得求解上述對偶問題，得 ( (* *) )。則參數(shù)對。則參數(shù)對(w,b)(w,b)可由下式計(jì)算：可由下式計(jì)算：b的計(jì)算（略）。的計(jì)算（略）。Page 67軟軟 - -帶帶支持向量（回歸）機(jī)支持向量（回歸）機(jī)bxwxfy)()(支持向量：支持向量：稱訓(xùn)練集稱訓(xùn)練集D中的樣本中的樣本xi為支持向量，為支持向量， 如果它對應(yīng)的如果它對應(yīng)的i*

39、0或i0 。把把w的式子代入函數(shù)：的式子代入函數(shù)：于是，得到如下的回歸函數(shù)：于是，得到如下的回歸函數(shù)：niiiibxxxf1*)()(y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 68目錄目錄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 69 - -支持向量（回歸）機(jī)支持向量（回歸）機(jī)下面通過下面通過核技術(shù)核技術(shù)來處理。引入一個(gè)來處理。引入一個(gè)非線性映射非線性映射 把把輸入空間輸入空間映射到一個(gè)映射到一個(gè)( (高維的高維的) )Hilbert空間空間H, ,使在使在H中進(jìn)行線性回歸中進(jìn)行線性回歸（硬（硬 - -帶或軟