浙江大學(xué)SVM(支持向量機(jī))PPT通用課件

1、浙江大學(xué)研究生浙江大學(xué)研究生人工智能引論人工智能引論課件課件徐從富徐從富(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. ChinaSeptember 11, 2003第一稿第一稿Oct. 16, 2006第三次修改稿第三次修改稿第八章 統(tǒng)計(jì)學(xué)習(xí)理論與SVM(Chapter8 SLT & SVM )目錄目錄n概述n統(tǒng)計(jì)學(xué)習(xí)理論中的基

2、本概念n統(tǒng)計(jì)學(xué)習(xí)理論的發(fā)展簡(jiǎn)況n統(tǒng)計(jì)學(xué)習(xí)理論的基本內(nèi)容n支持向量機(jī)概述n研究現(xiàn)狀n參考文獻(xiàn)8.1.1 SLT & SVM的地位和作用的地位和作用n是統(tǒng)計(jì)學(xué)習(xí)方法的優(yōu)秀代表n有嚴(yán)密的數(shù)學(xué)依據(jù)，得到了嚴(yán)格的數(shù)學(xué)證明n有力反駁 “復(fù)雜的理論是沒有用的，有用的是簡(jiǎn)單的算法”等錯(cuò)誤觀點(diǎn)n充分表明 “沒有什么比一個(gè)好的理論更實(shí)用沒有什么比一個(gè)好的理論更實(shí)用了了”等基本的科學(xué)原則8.1 概述概述8.1.2 SLT & SVM的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)概率論與數(shù)理統(tǒng)計(jì)泛函分析“For God so loved the world that he gave his one and only Son,

3、that whoever believes in him shall not perish but have eternal life. For God did not send his Son into the world to condemn the world, but to save the world through him.” from JOHN 3:16-17 NIV 8.1.3 SLT&SVM所堅(jiān)持的“基本信念”傳統(tǒng)的估計(jì)高維函數(shù)依賴關(guān)系的方法所堅(jiān)持的信傳統(tǒng)的估計(jì)高維函數(shù)依賴關(guān)系的方法所堅(jiān)持的信念念 實(shí)際問題中總存在較少數(shù)目的一些“強(qiáng)特征強(qiáng)特征”，用它們的簡(jiǎn)單函數(shù)（如線

4、性組合）就能較好地逼近未知函數(shù)。因此，需要仔細(xì)地選擇一個(gè)低仔細(xì)地選擇一個(gè)低維的特征空間維的特征空間，在這個(gè)空間中用常規(guī)的統(tǒng)計(jì)技術(shù)來求解一個(gè)逼近。SLT&SVM所堅(jiān)持的信念所堅(jiān)持的信念 實(shí)際問題中存在較大數(shù)目的一些“弱特征弱特征”，它們“巧妙的”線性組合可較好地逼近未知的依賴關(guān)系。因此，采用什么樣的“弱特征”并不十分重要，而形成“巧妙的”線性組合更為重要。8.1.4 SLT&SVM與傳統(tǒng)方法的區(qū)別要較好地實(shí)現(xiàn)傳統(tǒng)方法傳統(tǒng)方法，需要人工選擇（構(gòu)造）一些數(shù)目相對(duì)較少的“巧妙的特征”SVM方法方法則是自動(dòng)地選擇（構(gòu)造）一些數(shù)目較少的“巧妙的特征”在實(shí)際應(yīng)用中，可通過構(gòu)造兩層（或多層）構(gòu)

5、造兩層（或多層）SVM來選擇“巧妙的特征”SLT & SVM集以下模型于一身：結(jié)構(gòu)風(fēng)險(xiǎn)最小化（SRM）模型數(shù)據(jù)壓縮模型構(gòu)造復(fù)合特征的一個(gè)通用模型 在希爾伯特空間中的內(nèi)積回旋可以 看作是構(gòu)造特征的一種標(biāo)準(zhǔn)途徑。對(duì)實(shí)際數(shù)據(jù)的一種模型 一個(gè)小的支持向量集合可能足以對(duì)不同的機(jī)器代表整個(gè)訓(xùn)練集。8.2 SLT中的基本概念中的基本概念n統(tǒng)計(jì)方法統(tǒng)計(jì)方法 從觀測(cè)自然現(xiàn)象或者專門安排的實(shí)驗(yàn)所得到的數(shù)據(jù)去推斷該事務(wù)可能的規(guī)律性。n統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論 在研究小樣本小樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)的過程中發(fā)展起來的一種新興理論?！咀⒁庾⒁狻浚哼@里所說的“小樣本”是相對(duì)于無窮樣本而言的，故只要樣本數(shù)不是無窮，都可稱

6、為小樣本，更嚴(yán)格地說，應(yīng)該稱為“有限樣本有限樣本”。統(tǒng)計(jì)學(xué)習(xí)理論中的基本概念（續(xù)）n機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí) 主要研究從采集樣本出發(fā)得出目前尚不能通過原理分析得到的規(guī)律,并利用這些規(guī)律對(duì)未來數(shù)據(jù)或無法觀測(cè)的數(shù)據(jù)進(jìn)行預(yù)測(cè)。n模式識(shí)別模式識(shí)別 對(duì)表征事務(wù)或現(xiàn)象的各種形式(數(shù)值、文字及邏輯關(guān)系等)信息進(jìn)行處理和分析,以對(duì)事務(wù)或現(xiàn)象進(jìn)行描述、辨認(rèn)、分類和解釋的過程。n統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論 一種研究有限樣本估計(jì)和預(yù)測(cè)的數(shù)學(xué)理論8.3 統(tǒng)計(jì)學(xué)習(xí)理論的發(fā)展簡(jiǎn)況統(tǒng)計(jì)學(xué)習(xí)理論的發(fā)展簡(jiǎn)況n學(xué)習(xí)過程的數(shù)學(xué)研究F. Rosenblatt于1958,1962年把感知器作為一個(gè)學(xué)習(xí)機(jī)器模型n統(tǒng)計(jì)學(xué)習(xí)理論的開始Novikoff

7、(1962)證明了關(guān)于感知器的第一個(gè)定理n解決不適定問題的正則化原則的發(fā)現(xiàn)Tikhonov(1963), Ivanov(1962), Phillips(1962)nVanik和Chervonenkis(1968)提出了VC熵熵和VC維維的概念提出了統(tǒng)計(jì)學(xué)習(xí)理論的核心概念得到了關(guān)于收斂速度的非漸進(jìn)界的主要結(jié)論SLTSLT的發(fā)展簡(jiǎn)況的發(fā)展簡(jiǎn)況( (續(xù)續(xù)) )Vapnik和Chervonenkis(1974)提出了結(jié)構(gòu)風(fēng)結(jié)構(gòu)風(fēng)險(xiǎn)最小化（險(xiǎn)最小化（SRM）歸納原則歸納原則。Vapnik和Chervonenkis(1989)發(fā)現(xiàn)了經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化歸納原則和最大似然方法一致性的充分必要條件,完成了對(duì)經(jīng)驗(yàn)風(fēng)險(xiǎn)

8、最小化歸納推理的分析。90年代中期,有限樣本情況下的機(jī)器學(xué)習(xí)理論研究逐漸成熟起來,形成了較完善的理論體系統(tǒng)計(jì)學(xué)習(xí)理論(Statistical Learning Theory,簡(jiǎn)稱SLT)8.4 統(tǒng)計(jì)學(xué)習(xí)理論的基本內(nèi)容統(tǒng)計(jì)學(xué)習(xí)理論的基本內(nèi)容n機(jī)器學(xué)習(xí)的基本問題n統(tǒng)計(jì)學(xué)習(xí)理論的核心內(nèi)容8.4.1 機(jī)器學(xué)習(xí)的基本問題機(jī)器學(xué)習(xí)的基本問題n機(jī)器學(xué)習(xí)問題的表示GLMSX Xyy學(xué)習(xí)問題的表示學(xué)習(xí)問題的表示n產(chǎn)生器(G)，產(chǎn)生隨機(jī)向量x屬于Rn ,它們是從固定但未知的概率分布函數(shù)F(x)中獨(dú)立抽取的。n訓(xùn)練器(S)，對(duì)每個(gè)輸入向量x返回一個(gè)輸出值y，產(chǎn)生輸出的根據(jù)是同樣固定但未知的條件分布函數(shù) F(y|x)

9、。n學(xué)習(xí)機(jī)器(LM)，它能夠?qū)崿F(xiàn)一定的函數(shù)集f(x, a)，a屬于A，其中A是參數(shù)集合。8.4.2 機(jī)器學(xué)習(xí)的基本問題機(jī)器學(xué)習(xí)的基本問題n機(jī)器學(xué)習(xí)就是從給定的函數(shù)集f(x x,)(是參數(shù))中,選擇出能夠最好地逼近訓(xùn)練器響應(yīng)的函數(shù)。n機(jī)器學(xué)習(xí)的目的可以形式化地表示為：根據(jù)n個(gè)獨(dú)立同分布的觀測(cè)樣本 ，在一組函數(shù) 中求出一個(gè)最優(yōu)函數(shù) 對(duì)訓(xùn)練器的響應(yīng)進(jìn)行估計(jì),使期望風(fēng)險(xiǎn)最小 其中 是未知的,對(duì)于不同類型的機(jī)器學(xué)習(xí)問題有不同形式的損失函數(shù)。 1122( ,),(,),(,)nnx yxyxy ( , )f x0 ( , )f x( , )P x y( )( , ( , )( , )RL y f xdP

10、x y三類基本的機(jī)器學(xué)習(xí)問題三類基本的機(jī)器學(xué)習(xí)問題n模式識(shí)別n函數(shù)逼近（回歸估計(jì)）n概率密度估計(jì)【補(bǔ)充說明】：用有限數(shù)量信息解決問題的基基本原則本原則 在解決一個(gè)給定問題時(shí)，要設(shè)法在解決一個(gè)給定問題時(shí)，要設(shè)法避免把解決一個(gè)更為一般的問題作為其中間避免把解決一個(gè)更為一般的問題作為其中間步驟步驟。上述原則意味著，當(dāng)解決模式識(shí)別或回歸估計(jì)問題時(shí)，必須設(shè)法去必須設(shè)法去“直接直接”尋找待求的函數(shù)尋找待求的函數(shù)，而不是不是首先估計(jì)密度，然后用估計(jì)的密度來構(gòu)造待求的函數(shù)。密度估計(jì)密度估計(jì)是統(tǒng)計(jì)學(xué)中的一個(gè)全能問題，即知道了密度就可以解決各種問題。一般地，估計(jì)密度是一個(gè)不適定問題(ill-posed probl

11、em)，需要大量觀測(cè)才能較好地解決。實(shí)際上，需要解決的問題（如決策規(guī)則估計(jì)或回歸估計(jì)）是很特殊的，通常只需要有某一合理數(shù)通常只需要有某一合理數(shù)量的觀測(cè)就可以解決量的觀測(cè)就可以解決。經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則n對(duì)于未知的概率分布,最小化風(fēng)險(xiǎn)函數(shù), 只有樣本的信息可以利用,這導(dǎo)致了定義的期望風(fēng)險(xiǎn)是無法直接計(jì)算和最小化的。n根據(jù)概率論中大數(shù)定理,可用算術(shù)平均代替數(shù)據(jù)期望,于是定義了經(jīng)驗(yàn)風(fēng)險(xiǎn) 來逼近期望風(fēng)險(xiǎn)。n經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化(ERM)原則：使用對(duì)參數(shù)w求經(jīng)驗(yàn)風(fēng)險(xiǎn) 的最小值代替求期望風(fēng)險(xiǎn) 的最小值。11( )(,( ,)nempiiiRwL yf x wn( )empRw()R w經(jīng)驗(yàn)風(fēng)險(xiǎn)最小

12、化經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化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ù)雜性與推廣能力n學(xué)習(xí)機(jī)器對(duì)未來輸出進(jìn)行正確預(yù)測(cè)的能力稱作推推廣能力（廣能力（也稱為“泛化能力泛化能力”）。）。n在某些情況下,訓(xùn)練誤差過小反而導(dǎo)致推廣能力的下降,這就是過學(xué)習(xí)過學(xué)習(xí)問

13、題。n神經(jīng)網(wǎng)絡(luò)的過學(xué)習(xí)問題是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則失敗的一個(gè)典型例子。用三角函數(shù)擬合任意點(diǎn)用三角函數(shù)擬合任意點(diǎn)學(xué)習(xí)的示例學(xué)習(xí)的示例復(fù)雜性與推廣能力（續(xù)）復(fù)雜性與推廣能力（續(xù)）n在有限樣本情況下，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小并不一定意味著期望風(fēng)險(xiǎn)最??；學(xué)習(xí)機(jī)器的復(fù)雜性不但與所研究的系統(tǒng)有關(guān),而且要和有限的學(xué)習(xí)樣本相適應(yīng)；學(xué)習(xí)精度和推廣性之間似乎是一對(duì)不可調(diào)和的學(xué)習(xí)精度和推廣性之間似乎是一對(duì)不可調(diào)和的矛盾矛盾, ,采用復(fù)雜的學(xué)習(xí)機(jī)器雖然容易使得學(xué)習(xí)采用復(fù)雜的學(xué)習(xí)機(jī)器雖然容易使得學(xué)習(xí)誤差更小誤差更小, ,卻往往喪失推廣性；卻往往喪失推廣性；傳統(tǒng)的解決辦法（例如：采用正則化、模型選擇、噪聲干擾等方法以控制學(xué)習(xí)機(jī)器的復(fù)雜度

14、）缺乏堅(jiān)實(shí)的理論基礎(chǔ)。8.5 統(tǒng)計(jì)學(xué)習(xí)理論的核心內(nèi)容統(tǒng)計(jì)學(xué)習(xí)理論的核心內(nèi)容nSLT被認(rèn)為是目前針對(duì)有限樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)學(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í)原則和方法等問題。nSLT的主要內(nèi)容包括:基于經(jīng)驗(yàn)風(fēng)險(xiǎn)原則的統(tǒng)計(jì)學(xué)習(xí)過程的一致性理論學(xué)習(xí)過程收斂速度的非漸進(jìn)理論控制學(xué)習(xí)過程的推廣能力的理論構(gòu)造學(xué)習(xí)算法的理論VC維維(函數(shù)的多樣性函數(shù)的多樣性)n為了研究經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化函數(shù)集的學(xué)習(xí)一致收斂速度和推廣性，SLT定義了一些指標(biāo)來衡量函數(shù)集的性能，其中最重要的就是VC維(Vapnik-Chervon

15、enkis Dimension)。nVC維維：對(duì)于一個(gè)指示函數(shù)（即只有0和1兩種取值的函數(shù)）集，如果存在h個(gè)樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個(gè)樣本打散，函數(shù)集的VC維就是能夠打散的最大樣本數(shù)目。n如果對(duì)任意的樣本數(shù)，總有函數(shù)能打散它們，則函數(shù)集的VC維就是無窮大。VC維（續(xù)）維（續(xù)）n一般而言,VC維越大, 學(xué)習(xí)能力就越強(qiáng),但學(xué)習(xí)機(jī)器也越復(fù)雜。n目前還沒有通用的關(guān)于計(jì)算任意函數(shù)集的VC維的理論,只有對(duì)一些特殊函數(shù)集的VC維可以準(zhǔn)確知道。nN維實(shí)數(shù)空間中線性分類器和線性實(shí)函數(shù)的VC維是n+1。nSin(ax)的VC維為無窮大。nVCVC維（續(xù)）維（續(xù)） O

16、pen problem: 對(duì)于給定的學(xué)習(xí)函數(shù)集,如何用理論或?qū)嶒?yàn)的方法計(jì)算其VC維是當(dāng)前統(tǒng)計(jì)學(xué)習(xí)理論研究中有待解決的一個(gè)難點(diǎn)問題。三個(gè)里程碑定理三個(gè)里程碑定理( )()(VC)lim0( )lim0( )lim0 xannxxH nnHnnG nn收斂的充分 必要 條件熵快收斂速度的充分條件 與概率測(cè)度無關(guān)的快收斂充要條件推廣性的界nSLT系統(tǒng)地研究了經(jīng)驗(yàn)風(fēng)險(xiǎn)和實(shí)際風(fēng)險(xiǎn)之間的關(guān)系,也即推廣性的界。n根據(jù)SLT中關(guān)于函數(shù)集推廣性界的理論,對(duì)于指示函數(shù)集中所有的函數(shù),經(jīng)驗(yàn)風(fēng)險(xiǎn) 和實(shí)際風(fēng)險(xiǎn) 之間至少以概率 滿足如下關(guān)系: 其中，h是函數(shù)集的VC維,n是樣本數(shù)。( )empRw()R w1(ln(2

17、/ ) 1) ln( /4)( )( )emphn hRRn 推廣性的界（續(xù)1）n學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險(xiǎn)由兩部分組成:訓(xùn)練樣本的經(jīng)驗(yàn)風(fēng)險(xiǎn)置信范圍(同置信水平 有關(guān),而且同學(xué)習(xí)機(jī)器的VC維和訓(xùn)練樣本數(shù)有關(guān)。n在訓(xùn)練樣本有限的情況下,學(xué)習(xí)機(jī)器的VC維越高,則置信范圍就越大,導(dǎo)致實(shí)際風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間可能的差就越大。(ln(2 / ) 1) ln( /4)( )( )emphn hRRn ( )( )()empnRRh 1推廣性的界（續(xù)2）n在設(shè)計(jì)分類器時(shí), 不但要使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化,還要使VC維盡量小,從而縮小置信范圍,使期望風(fēng)險(xiǎn)最小。n尋找反映學(xué)習(xí)機(jī)器的能力的更好參數(shù)，從而得到更好的界是SLT今后的重

18、要研究方向之一。結(jié)構(gòu)風(fēng)險(xiǎn)最小化n傳統(tǒng)機(jī)器學(xué)習(xí)方法中普遍采用的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則在樣本數(shù)目有限時(shí)是不合理的,因此，需要同時(shí)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍。n統(tǒng)計(jì)學(xué)習(xí)理論提出了一種新的策略,即把函數(shù)集構(gòu)造為一個(gè)函數(shù)子集序列,使各個(gè)子集按照VC維的大小排列;在每個(gè)子集中尋找最小經(jīng)驗(yàn)風(fēng)險(xiǎn),在子集間折衷考慮經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍,取得實(shí)際風(fēng)險(xiǎn)的最小。這種思想稱作結(jié)構(gòu)風(fēng)險(xiǎn)最小化(Structural Risk Minimization)，即SRM準(zhǔn)則。結(jié)構(gòu)風(fēng)險(xiǎn)最小化（續(xù)1）結(jié)構(gòu)風(fēng)險(xiǎn)最小化（續(xù)2）n實(shí)現(xiàn)SRM原則的兩種思路在每個(gè)子集中求最小經(jīng)驗(yàn)風(fēng)險(xiǎn),然后選擇使最小經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍之和最小的子集。設(shè)計(jì)函數(shù)集的某種結(jié)構(gòu)

19、使每個(gè)子集中都能取得最小的經(jīng)驗(yàn)風(fēng)險(xiǎn),然后只需選擇適當(dāng)?shù)淖蛹怪眯欧秶钚?則這個(gè)子集中使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的函數(shù)就是最優(yōu)函數(shù)。支持向量機(jī)方法實(shí)際上就是這種思路的實(shí)現(xiàn)。8.6 支持向量機(jī)概述n支持向量機(jī)概述n支持向量機(jī)理論n支持向量機(jī)n核函數(shù)n支持向量機(jī)實(shí)現(xiàn)8.6.1 支持向量機(jī)概述支持向量機(jī)概述n1963年，Vapnik在解決模式識(shí)別問題時(shí)提出了支持向量方法,這種方法從訓(xùn)練集中選擇一組特征子集,使得對(duì)特征子集的劃分等價(jià)于對(duì)整個(gè)數(shù)據(jù)集的劃分,這組特征子集就被稱為支持向量(SV)。n1971年，Kimeldorf提出使用線性不等約束重新構(gòu)造SV的核空間,解決了一部分線性不可分問題。n1990年，Grac

20、e,Boser和Vapnik等人開始對(duì)SVM進(jìn)行研究。n1995年，Vapnik正式提出統(tǒng)計(jì)學(xué)習(xí)理論。8.6.2 支持向量機(jī)理論支持向量機(jī)理論nSVM從線性可分情況下的最優(yōu)分類面發(fā)展而來。n最優(yōu)分類面就是要求分類線不但能將兩類正確分開(訓(xùn)練錯(cuò)誤率為0),且使分類間隔最大。nSVM考慮尋找一個(gè)滿足分類要求的超平面,并且使訓(xùn)練集中的點(diǎn)距離分類面盡可能的遠(yuǎn),也就是尋找一個(gè)分類面使它兩側(cè)的空白區(qū)域(margin)最大。n過兩類樣本中離分類面最近的點(diǎn)且平行于最優(yōu)分類面的超平面上H1,H2的訓(xùn)練樣本就叫做支持向量。支持向量機(jī)理論（續(xù)1）廣義最優(yōu)分類面廣義最優(yōu)分類面（續(xù)1）n假定訓(xùn)練數(shù)據(jù)n可以被一個(gè)超平面分

21、開n我們進(jìn)行正歸化n此時(shí)分類間隔等于n使最大間隔最大等價(jià)于使 最小() 1,1,.,iiyw xbilRbRwbxwN, 0).(11( ,),.,( ,), 1, 1nllx yx yxR y 2w2w廣義最優(yōu)分類面（續(xù)2）n最優(yōu)分類面問題可以表示成約束優(yōu)化問題MinimizeSubject ton定義Lagrange函數(shù)211( )()22()1,1,.,iiwww wyw xbilliiiibwxywbwL1221) 1)(),(廣義最優(yōu)分類面（續(xù)3）nLagrange函數(shù)liiiibwxywbwL1221) 1)(),(0),(0),(bwLwbwLbiiliiiliixywya110

22、liiiiliiiililjijijijiibxxyxfyandlixxyyW1111,21)(sgn()(0,.,1, 0)()(一個(gè)簡(jiǎn)單的例子：4x3x2x1x2221234223341( ) ()(444)2Qx1 =(0, 0), y1 = +1x2 =(1, 0), y2 = +1x3 =(2, 0), y3 = -1x4 =(0, 2), y4 = -1可調(diào)用Matlab中的二次規(guī)劃程序，求得1, 2, 3, 4的值，進(jìn)而求得w和b的值。 123412013 / 41 / 41120312002144231113,02224()3220wbgxxx 8.6.3 支持向量機(jī)支持向量機(jī)

23、n很多情況下，訓(xùn)練數(shù)據(jù)集是線性不可分的，Vapnik等人提出了用廣義分類面（松弛子）來解決這一問題。n非線性問題通過非線性變換將它轉(zhuǎn)化為某個(gè)高維空間中的線性問題，在這個(gè)高維空間中尋找最優(yōu)分類面。高維空間中的最優(yōu)分類面n分類函數(shù)只涉及到訓(xùn)練樣本之間的內(nèi)積運(yùn)算(xixj) ,因此,在高維空間中只需進(jìn)行內(nèi)積運(yùn)算,這種內(nèi)積運(yùn)算可通過定義在原空間中的函數(shù)來實(shí)現(xiàn), 甚至不必知道變換的形式。nSLT指出,根據(jù)Hibert-Schmidt原理,只要一種運(yùn)算滿足Mercer條件,就可以作為內(nèi)積使用。Mercer條件2( , ),( )0( ),) ( ) ( )0K x xxx dxKxxx dxdx對(duì)于任意的

24、對(duì)稱函數(shù)它是某個(gè)特征空間中的內(nèi)積運(yùn)算的充要條件是,對(duì)于任意的且有(x,支持向量機(jī)n在最優(yōu)分類面中采用適當(dāng)?shù)膬?nèi)積函數(shù)就可以實(shí)現(xiàn)某一非線性變換后的線性分類,而計(jì)算復(fù)雜度卻沒有增加。支持向量機(jī)8.6.4 核函數(shù)核函數(shù)nSVM中不同的內(nèi)積核函數(shù)將形成不同的算法,主要的核函數(shù)有三類：n多項(xiàng)式核函數(shù)n徑向基函數(shù)nS形函數(shù)8.6.5 支持向量機(jī)實(shí)現(xiàn)支持向量機(jī)實(shí)現(xiàn)SVMlight - 2.private:/usr/local/binsvm_learn, svm_classifybsvm - 2.private:/usr/local/binsvm-train, svm-classify, svm-scaleli

25、bsvm - 2.private:/usr/local/binsvm-train, svm-predict, svm-scale, svm-toymySVMMATLAB svm toolbox支持向量機(jī)實(shí)現(xiàn)8.7 8.7 研究現(xiàn)狀研究現(xiàn)狀n應(yīng)用研究n支持向量機(jī)研究n支持向量機(jī)算法研究8.7.1 應(yīng)用研究應(yīng)用研究nSVM的應(yīng)用主要于模式識(shí)別領(lǐng)域n貝爾實(shí)驗(yàn)室對(duì)美國(guó)郵政手寫數(shù)字庫(kù)進(jìn)行的實(shí)驗(yàn)分類器錯(cuò)誤率人工表現(xiàn)2.5%決策樹C4.516.2%最好的兩層神經(jīng)網(wǎng)絡(luò)5.9%SVM4.0%SVM與神經(jīng)網(wǎng)絡(luò)（NN）的對(duì)比SVM的理論基礎(chǔ)比NN更堅(jiān)實(shí)，更像一門嚴(yán)謹(jǐn)?shù)摹翱茖W(xué)科學(xué)”（三要素：?jiǎn)栴}的表示、問題的解決、證明）SVM 嚴(yán)格的數(shù)學(xué)推理NN 強(qiáng)烈依賴于工程技巧推廣能力推廣能力取決于“經(jīng)驗(yàn)風(fēng)險(xiǎn)值”和“置信范圍值”，NN不能控制兩者中的任何一個(gè)。NN設(shè)計(jì)者用高超的工程技巧彌補(bǔ)了數(shù)學(xué)上的缺陷設(shè)計(jì)特殊的結(jié)構(gòu)，利用啟發(fā)式算法，有時(shí)能得到出人意料的好結(jié)果。“我們必須從一開始就澄清一個(gè)觀點(diǎn)，就是如果某事不是科學(xué)，它并不一定不好。比如說，愛情就不是科學(xué)。因此，如果我們說某事不是科學(xué)，并不是如果我們說某事不是科學(xué)，并不是說它有什么不對(duì)，而只是說它不是科學(xué)說它有什么不對(duì)，而只是說它不是科學(xué)?！?by R. Feynman from The Fey