浙江大學(xué)svm(支持向量機(jī))(編輯修改稿)
2024-09-12 01:17 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 習(xí)算法的理論 VC維 (函數(shù)的多樣性 ) ? 為了研究經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化函數(shù)集的學(xué)習(xí)一致收斂速度和推廣性， SLT定義了一些指標(biāo)來(lái)衡量函數(shù)集的性能，其中最重要的就是 VC維 (VapnikChervonenkis Dimension)。 ? VC維 ：對(duì)于一個(gè)指示函數(shù)（即只有 0和 1兩種取值的函數(shù)）集，如果存在 h個(gè)樣本能夠被函數(shù)集里的函數(shù)按照所有可能的 2h種形式分開(kāi)，則稱(chēng)函數(shù)集能夠把 h個(gè)樣本打散，函數(shù)集的 VC維就是能夠打散的最大樣本數(shù)目。 ? 如果對(duì)任意的樣本數(shù)，總有函數(shù)能打散它們，則函數(shù)集的 VC維就是無(wú)窮大。 VC維（續(xù)） ? 一般而言 ,VC維越大 , 學(xué)習(xí)能力就越強(qiáng) ,但學(xué)習(xí)機(jī)器也越復(fù)雜。 ? 目前還沒(méi)有通用的關(guān)于計(jì)算任意函數(shù)集的VC維的理論 ,只有對(duì)一些特殊函數(shù)集的 VC維可以準(zhǔn)確知道。 ? N維實(shí)數(shù)空間中線性分類(lèi)器和線性實(shí)函數(shù)的VC維是 n+1。 ? Sin(ax)的 VC維為無(wú)窮大。 ? …… VC維（續(xù)） Open problem: 對(duì)于給定的學(xué)習(xí)函數(shù)集 ,如何用理論或?qū)嶒?yàn)的方法計(jì)算其 VC維是當(dāng)前統(tǒng)計(jì)學(xué)習(xí)理論研究中有待解決的一個(gè)難點(diǎn)問(wèn)題。 三個(gè)里程碑定理 ()( ) ( VC ) l i m 0()l i m 0()l i m 0xannxxHnnHnnGnn?????????收 斂 的 充 分 必 要 條 件 熵快 收 斂 速 度 的 充 分 條 件 與 概 率 測(cè) 度 無(wú) 關(guān) 的 快 收 斂 充 要 條 件推廣性的界 ? SLT系統(tǒng)地研究了經(jīng)驗(yàn)風(fēng)險(xiǎn)和實(shí)際風(fēng)險(xiǎn)之間的關(guā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()Rw 1 ??( l n ( 2 / ) 1 ) l n ( / 4 )( ) ( )e m ph n hRRn??? ????推廣性的界（續(xù) 1） ? 學(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)。 ? 在訓(xùn)練樣本有限的情況下 ,學(xué)習(xí)機(jī)器的 VC維越高 ,則置信范圍就越大 ,導(dǎo)致實(shí)際風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間可能的差就越大。 ( l n ( 2 / ) 1 ) l n ( / 4 )( ) ( )e m ph n hRRn??? ????( ) ( ) ( )e m p nRR h??? ? ?1 ??推廣性的界（續(xù) 2） ? 在設(shè)計(jì)分類(lèi)器時(shí) , 不但要使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 ,還要使 VC維盡量小 ,從而縮小置信范圍 ,使期望風(fēng)險(xiǎn)最小。 ? 尋找反映學(xué)習(xí)機(jī)器的能力的更好參數(shù)，從而得到更好的界是 SLT今后的重要研究方向之一。 結(jié)構(gòu)風(fēng)險(xiǎ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)和置信范圍。 ? 統(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)的最小。這種思想稱(chēng)作 結(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） ? 實(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)使每個(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)。 支持向量機(jī)概述 ?支持向量機(jī)概述 ?支持向量機(jī)理論 ?支持向量機(jī) ?核函數(shù) ?支持向量機(jī)實(shí)現(xiàn) 支持向量機(jī)概述 ? 1963年， Vapnik在解決模式識(shí)別問(wèn)題時(shí)提出了支持向量方法 ,這種方法從訓(xùn)練集中選擇一組特征子集 ,使得對(duì)特征子集的劃分等價(jià)于對(duì)整個(gè)數(shù)據(jù)集的劃分 ,這組特征子集就被稱(chēng)為支持向量 (SV)。 ? 1971年， Kimeldorf提出使用線性不等約束重新構(gòu)造 SV的核空間 ,解決了一部分線性不可分問(wèn)題。 ? 1990年， Grace,Boser和 Vapnik等人開(kāi)始對(duì) SVM進(jìn)行研究。 ? 1995年， Vapnik正式提出統(tǒng)計(jì)學(xué)習(xí)理論。 支持向量機(jī)理論 ? SVM從線性可分情況下的最優(yōu)分類(lèi)面發(fā)展而來(lái)。 ? 最優(yōu)分類(lèi)面就是要求分類(lèi)線不但能將兩類(lèi)正確分開(kāi) (訓(xùn)練錯(cuò)誤率為 0),且使分類(lèi)間隔最大。 ? SVM考慮尋找一個(gè)滿足分類(lèi)要求的超平面 ,并且使訓(xùn)練集中的點(diǎn)距離分類(lèi)面盡可能的遠(yuǎn) ,也就是尋找一個(gè)分類(lèi)面使它兩側(cè)的空白區(qū)域 (margin)最大。 ? 過(guò)兩類(lèi)樣本中離分類(lèi)面最近的點(diǎn)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1