（應(yīng)用數(shù)學(xué)專(zhuān)業(yè)論文）非標(biāo)準(zhǔn)支持向量機(jī)分類(lèi)誤差分析.pdf

中文摘要 摘要 統(tǒng)計(jì)學(xué)習(xí)理論是由v a p o i k 等人提出的一種有效的樣本學(xué)習(xí)下的理論 支持向 j i 機(jī)是該理論的一個(gè)成功實(shí)現(xiàn) 學(xué)習(xí)理論中有限數(shù)f i 的觀測(cè)l p l jw l 練樣本是根據(jù)樣 本空間中的未知概率分布隨機(jī)獨(dú)立抽取的 然后 對(duì)損失函數(shù)在該分布下取期望 值 這就是標(biāo)準(zhǔn)支持向量機(jī)的思想 然而許多實(shí)際問(wèn)題中往往需要處理非標(biāo)準(zhǔn)情 形的問(wèn)題 因此將學(xué)習(xí)算法推廣到非標(biāo)準(zhǔn)的情形具有重要的實(shí)際意義 本文基于分類(lèi)問(wèn)題研究了非標(biāo)準(zhǔn)支持向量機(jī)學(xué)習(xí)算法的收斂性 得到了較為 滿意的結(jié)果 針對(duì)兩分類(lèi)問(wèn)題 重點(diǎn)分析了非標(biāo)準(zhǔn)支持向量機(jī)基于t d r h o n o v 正則 化學(xué)習(xí)算法的一致收斂性和相對(duì)一致收斂性及其推廣性誤差的界 第一部分主要介紹了非標(biāo)準(zhǔn)支持向i i 機(jī)的背景知識(shí)及支持向j i 機(jī)的預(yù)備知識(shí) 第二部分闡述了支持向量機(jī)的基本思想及相關(guān)內(nèi)容 第三部分著重研究了在礬b 0 v 正則化意義下的非標(biāo)準(zhǔn)支持向量機(jī)1 范效軟間 隔分類(lèi)器的分類(lèi)誤差 并給出了其推廣誤差的界 并進(jìn)一步分析了其相對(duì)一致收 斂性 得到了較好的結(jié)果 第四部分將非標(biāo)準(zhǔn)支持向量機(jī)推廣到多類(lèi)分類(lèi)問(wèn)題 第五部分分析了前面得到的主要結(jié)果 并對(duì)未來(lái)進(jìn)一步的研究方向進(jìn)行了展望 關(guān)鍵詞 非標(biāo)準(zhǔn)支持向量機(jī) 正則化 相對(duì)一致收斂性 核方法 再生核希爾伯特 空間 湖北大學(xué)碩士學(xué)位論文 a b s t r a c t 1 1 地s t a t i s t i c a ll e a r n i n gt h e o r yp r o p o s e db yv a p n i ke ta 1 i sa l le f f e c t i v el e a r n i n gt h e o r y r 1 1 忙s u p p o r tv e c t o rm a c h i n e s s v m s li st h es u c c e s s f u lr e a l i z a t i o no ft h i st h e o r y 1 1 t r a i n i n gd a t e si nt h el e a r n i n gt h e o r ya l ei n d e p e n d e n ta n di d e n t i c a l l yd i s t r i b u t e d d r a w e ra c c o r d i n gt oau n k n o w np r o b a b i l i t yd i s t r i b u t i o n t h e nt ot h el o s sf u n c t i o na n d e rt h i sd i s t r i b u t i o nt a r et h ee x p e c t e dv a l u e 1 1 l i si st h ei d e ao ft h es t a n d a r ds u p p o r t v e c t o rm a c h i n e s m a n yr e a lw o r l ds i t u a t i o n s h o w e v e r a r en o n s t a n d a r d i nt h a tm o d e l i sn o tv a l i df o rt h o s es i t u a t i o n s i ti se s s e n t i a lt op r o m o t et h el e a r n i n ga l g o r i t h mt ot h e n o n s t a n d a r ds i t u a t i o n s i nt h i sa r t i c l e w es t u d yt h ec o n v e r g e n c eo ft h el e a r n i n ga l g o r i t h mb a s eo nt h e c l a s s i f i c a t i o np r o b l e mi nt h en o n s t a n d a r ds i t u a t i o n s s p e c i a l ly w ea n a l y z et h eu n i f o r m c o n v e r g e n c ea n dt h er e l a t i v eu n i f o r mc o n v e r g e n c eo ft h en o n s t a n d a r ds u p p o r tv e c t o r m a c h i n e sb yi i 他a l r so ft h et t k h o n o vr e g u l a r i z a t i o na l g o f i t h ma n do b t a i nt h eg e n e r a l i z a o o nb o u n d sf o c u so nb i n a r yc l a s s i f i c a t i o np r o b l e m s i n t h e f i r s t p a r t w e b r i e f t h e b a s i c t h e o r y o f n o n s t a n d a r ds u p p o r t v e o t o r m a c h i n e s a n d0 u n i n et h eb a s i so fs v m i n t h es e c o n d p a n w e b r i e f t h e b a s i s o f t h es u p p o r t v c c t o r m a c h i n e s 1 1 t h i r dp a r ti st h ei m p o r t a n c eo ft h i sa r t i c l e i nt h i sp a r t w es t u o yt h ec o n v e r g e n c eo ft h er e g u l a r i z a t i o na l g o r i t h mb a s eo nt h e t h ec l a s s i f i c a t i o np r o b l e m a tf i r s t w es t u d yt h ee r r o ra n a l y s i so ft h es v m1 n o r ms o f tm a r g i nc l a s s i f i e ra n do b t a i nt h e b o u n do f i t sg e n e r a l i z a t i o ni 口 r o r i nt h es e c o n d w ef u r t h e rs t u d yo ni t sr e l a t i v eu n i f o r m c o n v e r g e n c e a n do b t a i ns a t i s f i e dr e s u l t t h e n i np a r tf o u r e x t e n s i o nt ot h en o n s t a n d a r dm u l t i e a t e g o r ys i t u a t i o n s f i n a l l y i np a r tf i v e w ca n a l y z et h em a i nr e s u l t sg o ti np r e v i o u sp a r t sa n dg i v ea p r o s p e c tf o rf l l n h e rr e s e a r c h k e yw o r d s n o n s t a n d a r ds u p p o r tv e c t o rm a c h i n e s r e g u l a r i z a t i o n r e l a t i v et m i f o r mc o n v e r g e n c e k e r c e rm e t h o d r e p r o d u c i n gk e r n e lh i i b e r ts p a c e 一 湖北大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說(shuō)明 原創(chuàng)性聲明 本人鄭重聲明 所呈交的學(xué)位論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所 取得的研究成果 除了文中特別加以標(biāo)注引用的內(nèi)容外 本論文不包含任何其 他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)的成果作品 對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人 和集體 均已在文中以明確方式標(biāo)明 本人完全意識(shí)到本聲明的法律后果由本 人承擔(dān) 論文作者簽名 1 琵辛q 平 簽名日期 硐年鄉(xiāng)月f 6 日 學(xué)位論文使用授權(quán)說(shuō)明 本學(xué)位論文作者完全了解學(xué)校關(guān)于保留 使用學(xué)位論文的規(guī)定 即 按照學(xué)校要求提交學(xué)位論文的印刷本和電子版本 學(xué)校有權(quán)保存學(xué)位論文 的印刷本和電子版 并提供目錄檢索與閱覽服務(wù) 學(xué)?？梢圆捎糜坝?縮印 數(shù)字化或其它復(fù)制手段保存論文 在不以贏利為目的的前提下 學(xué)?？梢怨_(kāi) 學(xué)位論文的部分或全部?jī)?nèi)容 保密論文在解密后遵守此規(guī)定 論文作者簽名 岱鈾斗 簽名日期 問(wèn)夠月f g 日 導(dǎo)師簽名 簽名e t 期 柱隍 壚珀 貊 第一章引言 第一章引言 學(xué)習(xí)問(wèn)題是指依據(jù)經(jīng)驗(yàn)數(shù)據(jù)選取所期望的依賴關(guān)系的問(wèn)題 模式識(shí)別 函效 擬合以及概率估計(jì)等都屬于數(shù)據(jù)學(xué)習(xí)的問(wèn)題 傳統(tǒng)統(tǒng)計(jì)學(xué)研究的是樣本數(shù)目趨 向無(wú)窮大時(shí)的漸近理論 現(xiàn)有的學(xué)習(xí)方法也多是基于此假設(shè) 但在實(shí)際問(wèn)題中樣 本數(shù)目往往是有限的 因此一些理論上很優(yōu)秀的學(xué)習(xí)方法在解決實(shí)際問(wèn)題時(shí)的 表現(xiàn)卻可能不盡如人意 統(tǒng)計(jì)學(xué)習(xí)理論是f 1 日v a l m i k 等人提出的一種小樣本統(tǒng)計(jì)理 論 1 1 著重研究在小樣本情況下的統(tǒng)計(jì)規(guī)律以及學(xué)習(xí)方法性質(zhì) 統(tǒng)計(jì)學(xué)習(xí)理論為 機(jī)器學(xué)習(xí)問(wèn)題建立了一個(gè)較好的理論框架 也發(fā)展了一種通用學(xué)習(xí)算法 支持向 i 機(jī) 能夠較好的解決小樣本學(xué)習(xí)問(wèn)題 目前 統(tǒng)計(jì)學(xué)習(xí)理論和s v m 已經(jīng)成為機(jī) 器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn) 2 i 1 1 學(xué)習(xí)問(wèn)題簡(jiǎn)介 學(xué)習(xí)問(wèn)題中 最優(yōu)分類(lèi)器的優(yōu)化目標(biāo)函數(shù)是期望風(fēng)險(xiǎn) 但是由于我們可以利 用的信息只有有限的樣本 期望風(fēng)險(xiǎn)公式中的積分無(wú)法計(jì)算 因此傳統(tǒng)的學(xué)習(xí)方 法中采用經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 e r i v l i 拘準(zhǔn)則 并設(shè)計(jì)算法使其最小 事實(shí)上 用e r m 準(zhǔn) 則來(lái)代替期望風(fēng)險(xiǎn)最小并沒(méi)有經(jīng)過(guò)充分的理論論證 只是直觀上合理的做法 盡 管可以假定在樣本數(shù)目趨向于無(wú)窮大時(shí)經(jīng)驗(yàn)風(fēng)險(xiǎn)趨近于期望風(fēng)險(xiǎn) 但在解決真實(shí) 問(wèn)題時(shí)卻并非如此 此外 用經(jīng)驗(yàn)風(fēng)險(xiǎn)最小做為學(xué)習(xí)算法的目標(biāo)會(huì)帶來(lái)過(guò)學(xué)習(xí)的問(wèn)題 產(chǎn)生這一 問(wèn)題的原因有二個(gè) 一是樣本不充分 二是學(xué)習(xí)機(jī)器的設(shè)計(jì)不合理 而且這兩個(gè)問(wèn) 題是相互關(guān)聯(lián)的 為了使經(jīng)驗(yàn)最小 學(xué)習(xí)系統(tǒng)總可以找到一個(gè)足夠復(fù)雜的模型去 擬合巳知樣本 甚至使經(jīng)驗(yàn)風(fēng)險(xiǎn)為零 但是 過(guò)分復(fù)雜的模型極為依賴訓(xùn)練樣本 喪失了推廣能力 而且有限的訓(xùn)練樣本往往并不能充分反映真實(shí)總體分布 所以 對(duì)未知的測(cè)試樣本并不能作出較好的預(yù)測(cè) 可見(jiàn) 學(xué)習(xí)機(jī)器的復(fù)雜性與推廣性之 間存在這一個(gè)根本性的矛盾 研究經(jīng)驗(yàn)風(fēng)險(xiǎn)與真實(shí)風(fēng)險(xiǎn)的關(guān)系 以及判決風(fēng)險(xiǎn)與學(xué)習(xí)機(jī)器復(fù)雜性之間的關(guān) 系是統(tǒng)計(jì)學(xué)習(xí)理論的基本內(nèi)容 為了研究以上問(wèn)題 統(tǒng)計(jì)學(xué)習(xí)理論定義了一系列有關(guān)函數(shù)集學(xué)習(xí)能力的指 標(biāo) 其中最重要的是v c 維 函數(shù)集的v c 維被定義為它所能打散的最大樣本數(shù)目 所謂 打散 是指存在h 個(gè)樣本能夠被函數(shù)集中的函數(shù)按所有可能的2 種方式分 湖北大學(xué)碩士學(xué)位論文 開(kāi) v c 維反映了函數(shù)集的學(xué)習(xí)能力 v c 維越大則學(xué)習(xí)機(jī)器越復(fù)雜 統(tǒng)計(jì)學(xué)習(xí)理論中另一重要研究是分析了對(duì)于各種類(lèi)型函數(shù)集 經(jīng)驗(yàn)和實(shí)際風(fēng) 險(xiǎn)之間的關(guān)系 即推廣性的界 對(duì)于兩類(lèi)分類(lèi)的問(wèn)題 結(jié)論是 對(duì)指示函數(shù)集中的所有函數(shù) 經(jīng)驗(yàn)風(fēng) 險(xiǎn)r 和實(shí)際風(fēng)險(xiǎn)r 叫 之間至少1 一吁的概率滿足 r w 冠q 叫 圣 h n 其中 是函數(shù)集的v c 維 n 是樣本數(shù) 這一結(jié)論從理論上說(shuō)明了學(xué)習(xí)機(jī)器的實(shí) 際風(fēng)險(xiǎn)是由兩部分組成的 一是經(jīng)驗(yàn)風(fēng)險(xiǎn) 另一部分稱為置信范圍 它和學(xué)習(xí)機(jī) 器的v c 維以及訓(xùn)練樣本數(shù)有關(guān) 上式說(shuō)明 在有限樣本訓(xùn)練下 學(xué)習(xí)機(jī)器的v c 維 越高 復(fù)雜性越高 則置信范圍越大 導(dǎo)致真實(shí)風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間可能的差別越 大 這就解釋了為什么會(huì)出現(xiàn)過(guò)學(xué)習(xí)的現(xiàn)象 更有意義的是 上式說(shuō)明機(jī)器學(xué)習(xí)過(guò) 程中不但要使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小 還要使v c 維盡量小以縮小置信范圍 才能取得較小 的實(shí)際風(fēng)險(xiǎn) 即對(duì)未知樣本有較好的推廣性 從以上分析可知經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化準(zhǔn)則在樣本有限時(shí)是不合理的 統(tǒng)計(jì)學(xué)習(xí)理 論提出了一種被成為結(jié)構(gòu)風(fēng)險(xiǎn)最 n s r m 的思想來(lái)解決這一問(wèn)題 具體細(xì)節(jié)請(qǐng)參 考 l 在此不贅述 需要指出的是 實(shí)現(xiàn)s m r 的一種思路是設(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) 1 2 背景知識(shí) 支持向量機(jī)是統(tǒng)計(jì)學(xué)習(xí)理論中最年輕的內(nèi)容 也是最實(shí)用的部分 目前仍在 不斷發(fā)展之中 支持向j i 機(jī)是從線性可分情況下的最優(yōu)分類(lèi)面發(fā)展而來(lái)的 在這 一簡(jiǎn)單情況下 s v m 分類(lèi)器實(shí)際上是把一個(gè)正負(fù)樣本分離開(kāi)來(lái)的分界線 在多維 情況下是超平面 定義正負(fù)樣本到分類(lèi)線的最短距離為分類(lèi)間距m 所謂最優(yōu) 分類(lèi)就是要求分類(lèi)線不但能將兩類(lèi)樣本正確分開(kāi) 而且使分類(lèi)間距最大 如果定 義s v m 分類(lèi)器的輸出函數(shù)為 t 伽 z b 2 第一章引言 其中 z 是輸入向 i 伽是法向 i 6 是直線截距 則分類(lèi)線可表示為 塒 z b 0 由于同一條直線的表達(dá)形式不唯一 對(duì)分類(lèi)線方程歸一化 使得分類(lèi)間距處的正 負(fù)樣本滿足讓 l 一1 從而分類(lèi)間距是m 向 可知最優(yōu)分類(lèi)線應(yīng)當(dāng)滿足分 類(lèi)間距m 最大 所以目標(biāo)函數(shù)可以表示為 號(hào)摯 o 曠 t v i 璣 塒 而一6 l 1 1 其中弘是訓(xùn)練樣本的類(lèi)別標(biāo)簽 正樣本 1 負(fù)樣本 一1 由于s 分類(lèi)器的 輸出是u 加 z 一6 所以約束條件的實(shí)質(zhì)是要求對(duì)訓(xùn)練樣本都能正確分類(lèi) 一般的 采用拉各朗日優(yōu)化算法把上述最優(yōu)分類(lèi)面問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題其 目標(biāo)函數(shù)僅僅決定于拉各朗日乘子的集合啦 滿足約束 咤n 似 呼 1 j f f i l n剛岫h n 一萎啦 1 2 璣啦 o v i n m l 其中 為訓(xùn)練樣本個(gè)數(shù) 一旦通過(guò)訓(xùn)練算法得到 就可以計(jì)算出法向量加和截 距b b 衄 毛一們 v 啦 o 以上討論都是在線性可分的情況下展開(kāi)的 然而在通常情況下并不能找到一個(gè)平 面完全把正負(fù)樣本分離開(kāi)來(lái) v a p n i k 在1 9 9 5 年建議為目標(biāo)函數(shù) 1 1 添加松弛系數(shù)來(lái)解決上述問(wèn)題 3 修改 之后的目標(biāo)函數(shù)將容忍錯(cuò)分情況的發(fā)生 同時(shí)又對(duì)一個(gè)樣本點(diǎn)穿越分類(lèi)面的錯(cuò)誤 3 甄 馳 l 叫 湖北大學(xué)碩士學(xué)位論文 進(jìn)行不同程度的懲罰 新的目標(biāo)函數(shù)為 滿足約束 勃訓(xùn)z e n 啦 址 i 1 挑 伽 龜一b 1 6 v i 1 3 其中矗為松弛變量 其實(shí)質(zhì)為表示該對(duì)應(yīng)樣本點(diǎn)偏離分類(lèi)面的程度 c 為懲罰因 子 這一參數(shù)的選取體現(xiàn)了保持盡量寬的分類(lèi)間距和容忍一定數(shù)量的分類(lèi)錯(cuò)誤這 兩種選擇之間的折衷 同樣可以把 1 3 式轉(zhuǎn)為對(duì)偶形式 其與 1 2 的區(qū)別僅僅在 于約束條件改變?yōu)?0 啦 gv 啦 注意到目標(biāo)函數(shù) 1 2 中計(jì)算兩個(gè)樣本點(diǎn)之間的距離計(jì)算是采用內(nèi)積運(yùn)算 如 果此內(nèi)積是采用歐式空間的距離則得到線性分類(lèi)器 如果選取其他的內(nèi)積形式則 可以把s v m 分類(lèi)器進(jìn)一步推廣為非線性分離器 這種內(nèi)積經(jīng)常表示為 z f k 被稱為核函數(shù) 事實(shí)上 核函數(shù)表述的不是在樣本空間的距離關(guān)系 而是表示在 一高維空間中的距離關(guān)系 這樣的原因在于 在低維的樣本空間中的不可分總是 在某一個(gè)高維空間可分的 核函數(shù)是用原空間中的函數(shù)來(lái)表述在這個(gè)高維空間中 樣本之間的距離 同時(shí) 這種處理方法又避免了去直接求取那一個(gè)從低維到高維 映射的困難 典型的核函數(shù)包括多項(xiàng)式函數(shù)以及高斯函數(shù)等 另外 并不是每一種 函數(shù)都可以表示這種非線性距離關(guān)系 一般需要滿足m e r c e r 條件 4 引入核函數(shù)之后 s v m 分類(lèi)器的輸出可以表示為 4 6一 功 巧 喲鯽 問(wèn) u 第一章引言 目標(biāo)函數(shù)的對(duì)偶形式是 滿足約束 nnn 呼妒 口 2 呼 善 璣協(xié) 巧 啦喲一善啦 1 4 v i 0 啦 g 礬q o l 上式 1 4 目標(biāo)是一個(gè)二次優(yōu)化問(wèn)題 而k a n 雎l 卜豳l h i 卜1 l c k c f 訂 條件是二次優(yōu) 化問(wèn)題的充分必要條件 由此 1 4 o e 的約束條件可以改寫(xiě)為 瞄a 黧 由于k k t 條件每次只操作一個(gè)樣本點(diǎn) 所以有效的利用k k t 條件對(duì)于加 速s v m 分類(lèi)器訓(xùn)練過(guò)程是十分有意義的 由上可知 原來(lái)的s v m 算法優(yōu)化的目標(biāo)可以認(rèn)為是總的識(shí)別錯(cuò)誤率 對(duì)于錯(cuò) 誤接受和錯(cuò)誤拒絕兩種錯(cuò)誤率之間的關(guān)系并沒(méi)有加以約束 然而 在實(shí)際應(yīng)用中 兩類(lèi)錯(cuò)誤類(lèi)的關(guān)系是極為重要的 例如在身份認(rèn)證系統(tǒng)中一般認(rèn)為錯(cuò)誤接受比錯(cuò) 誤拒絕后果更為嚴(yán)重 錯(cuò)誤拒絕率略高只是為用戶使用帶來(lái)了一些不便 而錯(cuò)誤 率偏高則會(huì)使冒充者成功登錄 造成用戶數(shù)據(jù)的泄密 所以 盡管原來(lái)的s v m 訓(xùn) 練算法有著較好的推廣能力 卻與實(shí)際應(yīng)用中的許多問(wèn)題的特殊要求不相適應(yīng) 為此 我們用非標(biāo)準(zhǔn)s v m 來(lái)解決這一問(wèn)題 現(xiàn)實(shí)生活中的許多分類(lèi)問(wèn)題中不同類(lèi)別的錯(cuò)分誤差一般并不相等 主要有以 下幾個(gè)原因 一不同樣本點(diǎn)的損失 代價(jià) 不同 不同類(lèi)型的錯(cuò)分有不同的損失 二 存在采樣偏差 三樣本空間的分布與訓(xùn)練樣本的分布有差異 通常把在這三種情 形稱為非標(biāo)準(zhǔn)情形 近來(lái) i j ny i 等分析了前兩種非標(biāo)準(zhǔn)情形下貝葉斯決策規(guī)則的形式 證明了 其與標(biāo)準(zhǔn)情形下兩分類(lèi)問(wèn)題中貝葉斯規(guī)則的聯(lián)系 本文 在l i ny i 等給出的非標(biāo)準(zhǔn) 分類(lèi)情形的框架下 著重分析了錯(cuò)分代價(jià)不同時(shí)基于1 設(shè)h o n o v 正則化意義下的非 5 湖北大學(xué)碩士學(xué)位論文 標(biāo)準(zhǔn)s v i v l 的分類(lèi)誤差 并給出了其推廣誤差的界 對(duì)于口一范數(shù)支持向耐機(jī)及其特 例2 一范數(shù)支持向量機(jī)軟間隔分類(lèi)器的錯(cuò)分誤差 d i r o n gc h e n 等已經(jīng)給出了較好 的分析 這里只就1 一范數(shù)軟間隔分類(lèi)器的錯(cuò)分誤差進(jìn)行分析 得到了其一致收斂 性的界 為了對(duì)錯(cuò)分誤差進(jìn)行更為全面的分析 進(jìn)一步對(duì)其進(jìn)行了相對(duì)一致收斂 性的分析 得到了較為滿意的結(jié)果 同時(shí)考慮錯(cuò)分損失不同及存在采樣偏差情形 下的多類(lèi)分類(lèi)非標(biāo)準(zhǔn)支持向量機(jī) 1 3 預(yù)備知識(shí) 1 3 1 正則化方法 f g i r o s i 等研究表明 從樣本學(xué)習(xí)的問(wèn)題可被視為從稀疏數(shù)據(jù)進(jìn)行多變量的 函數(shù)逼近 這一問(wèn)題可表示為 依據(jù)某固定但未知的概率分布函數(shù)f z 暑 獨(dú)立抽 取樣本集 0 l 譏 z 2 暑1 2 x t 訛 由此樣本信息獲得未知函數(shù) 的最佳逼近 一般說(shuō)來(lái) 這是一個(gè)不適定問(wèn)題 于 是 a n t t k h o n o v 等人提出了解決不適定問(wèn)題的方法 一種方法是v v i v a n o v 提 出的擬解的方法 5 另一種是t l k h o n o v 提出的正則化方法 6 這兩種方法都對(duì)函 數(shù)集的容量進(jìn)行了控制 即這兩種方法都執(zhí)行了結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則 在2 0 世紀(jì)3 0 年代 當(dāng)r f i s h e r 提出他的理論體系時(shí) 不適定問(wèn)題的概念還沒(méi)有 發(fā)展起來(lái) 直n 2 0 世紀(jì)印年代才發(fā)展起來(lái) 不適定問(wèn)題理論中主要發(fā)現(xiàn)了這樣一 個(gè)事實(shí) 即存在很廣泛的一類(lèi)問(wèn)題 它們的形式化的解存在 卻不能用有限的資 源 計(jì)算機(jī)資源和信息資源 得到 如事件模型的辨識(shí)問(wèn)題屬于不適定問(wèn)題 這是 在快速計(jì)算機(jī)誕生的2 0 世紀(jì)6 0 年代被發(fā)現(xiàn)的 人們發(fā)現(xiàn) f i s h e r 的應(yīng)用統(tǒng)計(jì)學(xué)對(duì)于 解決高維問(wèn)題來(lái)說(shuō)不是一個(gè)合適的工具 因?yàn)樗嬖?雛數(shù)災(zāi)難 問(wèn)題 7 不適定問(wèn)題的數(shù)字語(yǔ)言表述為 對(duì)于算子方程 a f t f z 一6 1 5 第一章引言 如果方程右端f z f z 叩 發(fā)生微小變化 只會(huì)引起解的微小變化 即如果對(duì)任 意s 存在j e 使得只要不等式 p 易 f 扛 m f 扛 2 6 e 成立 不等式 p e x f t t j l l t 啦 一定成立 我們稱算子方程 1 5 髑解是穩(wěn)定的 其中歷和易表示距離分別定義在 度量空間局和b 中 算子方程 1 5 冬空間蜀中的函數(shù)映射到空間易中的函數(shù) 若方程 1 5 的解是存在的 唯一的且穩(wěn)定的 我們稱解算子方程 1 5 的問(wèn)題 在h a d a m a r d 意義下是適定的 8 1 如果方程的解至少有一條不滿足上述三條 則解 算子方程的問(wèn)題就是不適定的 在學(xué)習(xí)理論中 我們考慮算子方程的解存在 唯一 但不穩(wěn)定的這一類(lèi)不適定問(wèn)題 t i d m n o v 等于1 9 6 3 年提出了解決不適定問(wèn)題的方法一正則化方法1 9 1 0 1 1 1 假設(shè)要解 到 韻連續(xù)一對(duì)一映射算子j 4 定義的算子方程 a f f 1 d 并假設(shè)方程 1 妨的解存在 正則化泛函 是一個(gè)半連續(xù)的正泛函 且 c c o 是緊的 在定 義域d w i i f 泛函w 取非負(fù)實(shí)數(shù) 函數(shù)集f f 是方程的解域 i f 貝u 化的思想是將最小化某一泛函的一個(gè)元素作為方程 1 6 的解 該琵函不 是泛函 p 見(jiàn) a f 而是一個(gè)改進(jìn)的泛函 馬 f g a f f 7 a d 彤 1 7 其中正則化參數(shù)7 0 n k h o 腫v 已經(jīng)證明了最小化泛函 1 7 n 題是穩(wěn)定的 即對(duì) 于相鄰函數(shù)f 雨q f 6 其e e p 2 f f 6 s6 特別地在h n b e r t 空 n e 對(duì)于線性算子a 我們可以選擇泛函 等 fj f j 2 7 一 湖北大學(xué)碩士學(xué)位論文 常見(jiàn)的兩種正則化方法是同d l 徹o v 正則化方法和i v a n o v i f 貝j j 化方法 假設(shè)q 一冗 是定義在函數(shù)集合 t z f o 0 a 上的一個(gè)處罰泛函 于是 i v a n o v 三貝r j 化方法的定義為 島 z 1 0 a r g m 蚍i nl k p f o 約束條件為 a t z f o c c o 是常數(shù) t d d a o n o v 正則化方法的定義為 厶 z f o a r gr a 日 i n 冠 知 a q 0 一 1 8 其中a o 是一個(gè)常數(shù) 上述式 1 7 和 1 8 函數(shù)n z f o 被稱為正則化子 常數(shù)n 和a 被稱為正則 化參數(shù) 它們的取值依賴于樣本數(shù)目m c c m a a m 正則化方法的基本思想是 在i v a n o v 正則化方法中 當(dāng)g o o 時(shí) 島 z 一 是 z 如 的一個(gè)很好的逼近 在t t k h o n o v i f 貝l j 化方法中 當(dāng)a 一0 時(shí) 以 z f o 也是 2 允 的一個(gè)好的逼近 正則化方法中 正則化子n z f o 可以有不同的取法 若咒是由線性函數(shù)組 成的 正則化子通常取加權(quán)向量的范數(shù) 1 2 1 若爿是b 柚 h 或h i l b e f t 空間 正則化 子通常取他們的范數(shù)或范數(shù)的平方0 3 在核方法研究中 我們通常取 是再生和 希爾伯特空間 其中正則化參數(shù)a e 度量了關(guān)于正則化子q 的正則化方法輸 出函數(shù)的規(guī)律性 它的選取決定了正則化方法的性質(zhì) 由于解i v a n o v 正則化方法需要解最優(yōu)化問(wèn)題 故本文中 我們只考 慮n l d l o n o v 正則化方法 1 3 2 再生核希爾伯特空間 一個(gè)學(xué)習(xí)機(jī)器總是在一定函數(shù)集上實(shí)現(xiàn)某種算法的 函數(shù)集的類(lèi)型和性質(zhì)很 大程度上決定著算法實(shí)現(xiàn)的難易程度 給定的函數(shù)空間稱為假設(shè)空間 模型函數(shù) 集 其中的每個(gè)函數(shù)均稱為假設(shè) 核機(jī)器學(xué)習(xí)是現(xiàn)在比較流行的一種機(jī)器學(xué)習(xí)算 法 它的思想是將數(shù)據(jù)映射到高維的特征空間 尋找特征空間的線性學(xué)習(xí)機(jī)器 而 這種線性學(xué)習(xí)機(jī)器在對(duì)偶空間是以特征映射內(nèi)積的形式出現(xiàn)的 此時(shí)內(nèi)積對(duì)應(yīng)著 原始空間的核函數(shù) 通過(guò)選擇核函數(shù)來(lái)代替內(nèi)積后 就隱式地表示了特征映射 在 8 第一章引言 計(jì)算時(shí)只需計(jì)算核函數(shù)在成對(duì)出現(xiàn)的訓(xùn)練樣本上的值 s v m 屬于核機(jī)器學(xué)習(xí)的范疇 不過(guò)它選擇的核為再生核 它的假設(shè)空間是由 這個(gè)核導(dǎo)出的再生核希爾伯特空間 再生核希爾伯特空間在逼近和正則化理論中 扮演了重要角色 下面將給出定義 定義函數(shù) k xxx 冗 z t 一k x t 記j l t k z t 對(duì)每個(gè)固定z x j l 是x 上的函數(shù) 若k z t k t z 對(duì) 所有 z t x x 成立 則稱k 是對(duì)稱的 若 同時(shí)關(guān)于兩個(gè)變量連續(xù) 則 稱 而t 為核函數(shù) 定義1 1 設(shè)飩為 x 上函數(shù)碰l b e r t 空間 若核函數(shù)k 滿足 1 x 虹 咒 2 忱 x v 7 1 f x j l 則稱 為h 的再生核 由定義知 也 鮑 億 z z z 命題1 1 若函數(shù)琢l b e r t 空間咒存在再生核膏 則它是唯一的 證明假定咒存在另外的再生核露 則由k 和露的再生性 得 璉 一億 1 1 2 懈 一 k 一 a 配一忍 一 玩一忍 覓 恐 t 一元 t 一 虬 t 一億 t 0 因而 對(duì)所有z t x 有j 0 t 也 t 從而 z t 霞 z t 在k z x 上成 立 命題1 2 函數(shù)i f i l b e r t 空間咒存在再生核 的充分必要條件是 對(duì)每個(gè)衛(wèi) x 點(diǎn)泛函疋 z 是 上的連續(xù)泛函 9 湖北大學(xué)碩士學(xué)位論文 證明若咒上存在再生核函數(shù) 則由再生核性質(zhì) 1 6 z f i i 圳 l 霉 恐 t si l f l l i g t t z z 釧川 反之 若瓦是 上的連續(xù)泛函 由r i e s z 表示定理 存在如 咒使得 z 如 v f 7 稱k x t 如 t 則k 是咒的再生核 定義1 2 設(shè)函數(shù)k x x r 滿足條件 1 是對(duì)稱的 e p k x z k x 功忱 一 x 2 對(duì)任商b l z 2 x g r 鯽l 矩陣k k l 滿足z r j 白 0 則稱 為正定核 若k 是連續(xù)對(duì)稱正定的 則稱其為m e r e e r 核 m e r e e r 核具有下面兩個(gè)性質(zhì) 1 m e r c e r 核是非負(fù)的 2 u k u u k 口 定義1 3 設(shè)xc 為緊集 假定x 上函數(shù)碰l b e r t 空間爿存在再生核e 且j 厶 x 線性組合在 中稠密 即 s p a n k z x 則稱 為再生核希爾伯特空間 g e p r o d u c i n gk e r n e lh i l b e r ts p a c e 簡(jiǎn)寫(xiě)為 褂 i s 定理1 1 設(shè)函數(shù)k x x 一冗是m 鰍珂核 則存在定義在 x 上的連續(xù)函 數(shù)組成的希爾伯特空間w 滿足下列性質(zhì) v t x v 何 萑f(wàn) f x i 配 f 1 0 第一章引言 我們把這個(gè)性質(zhì)稱為再生性 滿足再生性的核被稱為再生核 不難得到m 餓盯核 為再生核 把咒 稱作由k 導(dǎo)出的再生核希爾伯特空間 下面考察咒 的結(jié)構(gòu) 令k xx x 一冗是m 朗嘟核 定義積分算子 t k lk b 固 q 令凡和氟 z 分別是 的特征值和特征函數(shù) 根據(jù)m 嘲定理有 令嘭 z 廊 z 則 k z z 7 包 z 奶 z j l r 他 q 奶 z j 1 在 中定義內(nèi)積 奶 z 如包 z 爿 勾屯 j lj 1j l 則 關(guān)于上面定義的內(nèi)積是一個(gè)r 璐 即 是由核 導(dǎo)出的再生核希爾伯特空 間咒肛不難驗(yàn)證再生性成立 z k x h 喲奶 z 包 一 奶 z h j 1j 1 q 奶 一 一 j l 對(duì)丁中的函數(shù) 功 囂l 喲包 若令 n 1 o n 妒 z 也 z 也 z 機(jī) z 湖北大學(xué)碩士學(xué)位論文 則 z 可以表示為 z u 妒 茁 的形式 把定義在x 上的映射 妒 妒 z 1 z 如 z 妒k z 稱為特征映射 把丁稱為特征空間 若q 1 m 九 z 此時(shí) n 扛 嘶奶 毛 奶o i 1t 1 n0 0 啦 九 卸 也 功 i f f i l i f f i l n 啦k 馬戤 即 z 可以寫(xiě)成 功 la k x 以 的表示形式 我們稱 z 的這種表示形式 為 的對(duì)偶表示 基于核的學(xué)習(xí)算法的思想是將原問(wèn)題轉(zhuǎn)化到對(duì)偶空間求解 從而講解轉(zhuǎn)化為對(duì)偶表示 這為計(jì)算提供了很大的方便 1 4 本論文的主要工作及內(nèi)容安排 本論文的主要工作是基于 l d l o n o v 正則化方法研究了兩分類(lèi)非標(biāo)準(zhǔn)支持向 苗機(jī)的分類(lèi)誤差 得到了其推廣誤差的界 文章的第一部分主要介紹了非標(biāo)準(zhǔn)支 持向 l 機(jī)的背景知識(shí) 及支持向艟機(jī)的預(yù)備知識(shí) 第二部分闡述了支持向 l 機(jī)的 基本思想 及支持向量機(jī)算法的研究現(xiàn)狀 第三部分是本文的重點(diǎn)部分 在q i 蛆g w u 1 4 1 的基礎(chǔ)上在t t k h o n o v 正則化意義下進(jìn)行了非標(biāo)準(zhǔn)支持向量機(jī)的兩分類(lèi)誤 差分析 得到了其一致收斂性的界 并進(jìn)一步研究了其相對(duì)一致收斂性 使得誤差 分析更趨于完善 第四部分研究了多分類(lèi)非標(biāo)準(zhǔn)支持向量機(jī) 應(yīng)用 一對(duì)余 支持 向量機(jī)方法 給出了非標(biāo)準(zhǔn)支持向量機(jī)在多分類(lèi)問(wèn)題中表現(xiàn)形式 最后 第五部分 分析了前面所得到的主要結(jié)果 并對(duì)未來(lái)進(jìn)一步的研究方向進(jìn)行了展望 1 2 第二章支持向量機(jī) 2 t 支持向量機(jī)簡(jiǎn)介 第二章支持向量機(jī) 支持向付機(jī)算法由貝爾實(shí)驗(yàn)室的v a m i k 及 其合作者提出的一類(lèi)基于統(tǒng)計(jì)學(xué) 習(xí)理論新型機(jī)器學(xué)習(xí)方法 l 它建立在統(tǒng)計(jì)學(xué)習(xí)理論的v c 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最 小化原則基礎(chǔ)上 根據(jù)有限樣本信息的模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折 衷以期獲得最好韻推廣能力 s v m 是統(tǒng)計(jì)學(xué)習(xí)理論的一種成功實(shí)現(xiàn) 其在模式識(shí) 別 函數(shù)逼近 信號(hào)預(yù)測(cè) 信息融合等領(lǐng)域 已得到了廣泛應(yīng)用 很多學(xué)者認(rèn)為 它 正成為繼模式識(shí)別和神經(jīng)網(wǎng)絡(luò)研究之后機(jī)器學(xué)習(xí)領(lǐng)域新的研究熱點(diǎn) 并將推動(dòng)機(jī) 器學(xué)習(xí)理論和技術(shù)豹重大發(fā)展 在2 0 世紀(jì)蚰年代后期支持向 i 機(jī)更是得到了全面深入的發(fā)展 現(xiàn)已成為機(jī)器 學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的標(biāo)準(zhǔn)工具 主要原因之一是s v m 是機(jī)器學(xué)習(xí)領(lǐng)域若干標(biāo) 準(zhǔn)技術(shù)的集大成者 它集成了最大間隔超平面 m e 虻盯核 凸二次優(yōu)化 稀疏解和 松弛變量等技術(shù) 在若干挑戰(zhàn)性的應(yīng)用中獲得了目前為止最好的性能 在美國(guó)科 學(xué)雜志上 s v m 及核方法被認(rèn)為是 機(jī)器學(xué)習(xí)領(lǐng)域非常流行的方法和成功的例子 并是一個(gè)令人矚目的發(fā)展方向 近年來(lái) v m 的理論已經(jīng)取得了重大進(jìn)展 其算 法實(shí)現(xiàn)策略及實(shí)際應(yīng)用也發(fā)展迅速 可以確信 該技術(shù)阿研究已發(fā)展成為機(jī)器學(xué) 習(xí)中一個(gè)獨(dú)立的領(lǐng)域 在理論和實(shí)踐兩方面都有著光明的前景 支持向j i 機(jī)方法的主要優(yōu)點(diǎn)有 1 它是專(zhuān)門(mén)針對(duì)有限樣本的情況的 其目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解而不 僅僅是樣本數(shù)趨于無(wú)窮大時(shí)的最優(yōu)解 2 算法最終將轉(zhuǎn)化為一個(gè)二次型尋優(yōu)問(wèn)題 從理論上說(shuō) 得到的將是全局最優(yōu) 點(diǎn) 解決了在神經(jīng)網(wǎng)絡(luò)方法中無(wú)法避免的局部極值問(wèn)題 3 算法將實(shí)際問(wèn)題通過(guò)非線性變換到高維的特征空間 在高維特征空間中構(gòu) 造線性判別函數(shù)來(lái)實(shí)現(xiàn)原空間的非線性判別函數(shù) 特殊性質(zhì)能保證機(jī)器有 較好的推廣能力 同時(shí)它又巧妙地解決了維數(shù)問(wèn)題 其算法復(fù)雜度與樣本維 數(shù)無(wú)關(guān) 在s v m 方法中 只要定義不同的內(nèi)積函數(shù) 就可以實(shí)現(xiàn)多項(xiàng)式逼近 貝葉斯 分類(lèi)器 徑向基函數(shù)方法 多層感知器網(wǎng)絡(luò)等許多現(xiàn)有學(xué)習(xí)算法 1 3 湖北大學(xué)碩士學(xué)位論文 2 2 支持向量機(jī)的思想 支持向量機(jī)實(shí)現(xiàn)了下列思想 通過(guò)事先選擇好的某一個(gè)非線性變換 將輸入 向量z 映射到高維空間z 在這一特征空間中構(gòu)造一個(gè)最優(yōu)分類(lèi)超平面 在上面的方法中會(huì)出現(xiàn)兩個(gè)問(wèn)題 一個(gè)概念性問(wèn)題和一個(gè)技術(shù)性問(wèn)題 1 如何找到一個(gè)推廣能力好的分類(lèi)超平面 概念性問(wèn)題 特征空間的維數(shù)是 非常高的 分開(kāi)訓(xùn)練數(shù)據(jù)的超平面不一定具有好的推廣能力 2 計(jì)算上如何處理如此高的高維空間 技術(shù)性問(wèn)題 為了在2 0 0 維空間中構(gòu)造 一個(gè)4 階或5 階多項(xiàng)式 必須在數(shù)億維空間中構(gòu)造超平面 如何才能克服 罐數(shù)災(zāi) 難 問(wèn)題呢 這一問(wèn)題的概念部分可以通過(guò)構(gòu)造最優(yōu)超平面來(lái)解決 根據(jù)最優(yōu)超平面的統(tǒng) 計(jì)性質(zhì) 如果我們能夠以訓(xùn)練樣本的最大范數(shù)和間隔的比值的平方的一個(gè)小的期 望或以支持向量數(shù)的一個(gè)小的期望來(lái)構(gòu)造最優(yōu)超平面 則所構(gòu)造的超平面的推廣 能力是好的 但是 即使最優(yōu)超平面具有好的推廣能力并可以從理論上找到它 如何處理 高維特征空間的技術(shù)問(wèn)題依然存在 然而 應(yīng)注意的是 對(duì)于特征空間z 中構(gòu)造最 優(yōu)分類(lèi)超平面 我們并不需要以顯式形式考慮特征空間 我們僅僅需要計(jì)算支持 向量與特征空間的向量之間的內(nèi)積 我們考慮 i i i b e r t 空間中內(nèi)積的一般性質(zhì) 假定 我們將向量z 艫映射到一 個(gè)i i i l l t 空間 其坐標(biāo)為 z l x z n 功 根據(jù)h i l b e t t s c h m i d t 理論 h i l b e r l 空間中的內(nèi)積有一個(gè)等價(jià)表達(dá)式 0 0 z l 忍 砷磊 z 1 磊 勛 骨k z l z 2 n r 0 r z l 其中 z l z 2 為滿足下列條件的對(duì)稱函數(shù) 定理2 1 為了保證一個(gè)連續(xù)對(duì)稱函數(shù)k t 在l 2 g 空間中有一個(gè)含有正系 數(shù)的釓 0 的展開(kāi)式 o o g u 口 口k 釓 u 魂 口 k 一 i 1 4 一 2 1 第二章 支持向量機(jī) 即x t t 描述了某一特征空問(wèn)的內(nèi)積 充分必要條件為 zz 腳 咖m d u d v 對(duì)于所有的g 島 c 丘y g l c 為艫的一個(gè)緊子集 可用于構(gòu)造支持向 i 機(jī)的t m b e n 空間中內(nèi)積結(jié)構(gòu)的好的性質(zhì)是 對(duì)于滿 足m 嘟條件的任何核函數(shù)k u 存在一個(gè)特征空間協(xié) 亂 缸 讓 在這 一空間的核函數(shù)生成內(nèi)積 2 1 2 3 構(gòu)造支持向量機(jī) 在 高維 特征空間中生成內(nèi)積允許我們構(gòu)造一些決策函數(shù) 它們?cè)谳斎肟臻g 中是非線性的 扛 口 喲n y a k x 而 6 2 2 s v 而它們?cè)谔卣骺臻gz l z o o i 釓0 中等價(jià)于線性決策函數(shù) o 口 s 哲n 肌醒 磊 戤 聾 z 6 wr f f i i 其中 z 盈 是生成特征空間中的內(nèi)積的核 因此 為了構(gòu)造分類(lèi)函數(shù) 2 2 我 們可以利用構(gòu)造線性分類(lèi)超平面的方法 其中 我們使用由核k z z t 來(lái)代替 由 z 戤 定義的內(nèi)積 i 為了在可分情況璣 而 n 1 下找出系數(shù)啦 充要條件是 找出泛函 n 啦一 啦喲鼽協(xié)k 盈 句 2 3 j i j 的最大值 約束條件為 口 20 i 1 2 1 1 5 o 璣 以 耐 湖北大學(xué)碩士學(xué)位論文 2 在不可分的情況下找出最優(yōu)軟間隔解 充分條件是 最大化泛函 2 3 約束 條件是 f 啦礬 0 0 啦 g 1 2 l i f f i l 3 最后 為了對(duì)給定的間隔1 a 找出最優(yōu)解 m 螄c 靄彘窯批c w 我們必須最大化泛函 約束條件為 l 啦執(zhí) o 0 啦 1 江1 2 z 1 構(gòu)造這一類(lèi)決策函敷的學(xué)習(xí)機(jī)器稱為支持向量機(jī) 2 4 最優(yōu)超平面 2 4 1 最優(yōu)超平面的概念 給定訓(xùn)練集 z 1 1 鋤 y t 緲 y 1 1 若挑 1 則稱墨屬 于i 類(lèi) 否則屬于i i 類(lèi) 稱集合 z 1 司 可被超平面z c 分離 若存在一個(gè)單 位向量鴝一個(gè)常數(shù)c 使得不等式組 毛 驢 c 妒 槲 再證唯一性 假定 妒 的最大值在兩個(gè)邊界點(diǎn)咖t 與如上達(dá)到 則由 妒 的凹 性 對(duì)處于這兩點(diǎn)連線上任一處的內(nèi)點(diǎn) p 的函數(shù)值不小于 妒1 我們的目的是尋求構(gòu)造最優(yōu)超平面的有效方法 為此考慮該問(wèn)題的等價(jià)形 式 尋找向量妒與常數(shù)6 使得 6 l 1 2 5 即 妒 b 1 若協(xié) 1 并且向量妒的范數(shù)i 訓(xùn)2 砂 妒具有最小值 定理2 3 在限制 2 5 下具有最小范數(shù)的向量妒與構(gòu)成最優(yōu)超平面的向量 具 有關(guān)系 妒 l 妒l 最優(yōu)超平面與分離向量之間的間隔p 咖 i l l i 證明在限制 2 5 下取得最小范數(shù)的砂是唯一的 假定 妒 6 1 與 仍 6 2 滿 足限制 2 5 并且兩個(gè)向量具有相同的最小的范數(shù)i 妒1 1 2 i 仍1 2 則對(duì)任意a 0 1 可知 a 妒1 t 1 一a 如 撕 1 一a 池 滿足 2 5 的限制 但j a 砂l(fā) i 1 一a 仍1 2 l l e l 構(gòu)造一個(gè)新向量礦 州p 糾 由假 設(shè)則有i 礦l z p o 由于最優(yōu)超平面與優(yōu)化問(wèn)題中的目標(biāo)函數(shù) 2 8 都不是依賴向量z 的維效而是 兩個(gè)向量的內(nèi)積 故我們可以在高維空間甚至是無(wú)窮維h i l l 犯r t 空間中構(gòu)造分類(lèi)超 平面 這正克服了所謂的維數(shù)災(zāi)難 1 5 j 應(yīng)該注意的 雖然最優(yōu)超平面是唯一的 即確定最優(yōu)超平面的向量妒與常 數(shù)6 是唯一的 但是1 f 關(guān)于支持向量的展式并不唯一 1 6 1 2 與支持向量機(jī)分類(lèi) 支持向量機(jī)是從線性可分情況下的最優(yōu)分類(lèi)面發(fā)展而來(lái)的 對(duì)于線性不可分 的二值分類(lèi)問(wèn)題 用s v m 方法也可以找到一個(gè)最優(yōu)分類(lèi)面 使得兩類(lèi)無(wú)錯(cuò)誤的分 開(kāi) 并使得兩類(lèi)的分類(lèi)間隔最大 設(shè)訓(xùn)練樣本集為 毛 璣 1 2 毋 式中 為輸入值 戤 艫 肌為輸出值 弘 2 f 為樣本數(shù) 最優(yōu)分類(lèi)面為 u 妒 z b 0 式中6 兄 u 為特征空間維數(shù) z 為內(nèi)積函數(shù) 將輸入樣本空間映射到高維線 性特征空間 1 9 湖北大學(xué)碩士學(xué)位論文 s v v l 將該最優(yōu)分類(lèi)面的求解轉(zhuǎn)化成一個(gè)二次規(guī)劃q p 問(wèn)題 其數(shù)學(xué)形式為 m i n r m l 2 c i l 豇t 們 u 盈 1 一靠 y i l i 矗 0 i 1 2 式中矗 為松弛變量 c 為懲罰參數(shù) c 0 g 越大表示對(duì)錯(cuò)誤分類(lèi)的懲罰越大 利用拉格朗日乘子法求解這個(gè)具有線性約束的二次優(yōu)化問(wèn)題 得到對(duì)偶最優(yōu) 化問(wèn)題為 f f m a x 啦一 啦喲弘鯽k 毛 巧 i f f i l i f f i lj 1 b t 0 m g 啦璣 o 式中啦為支持值 0 啦sc 時(shí) 對(duì)應(yīng)的z t 稱為支持向量 稱0 幽 c 所對(duì)應(yīng) 的以為標(biāo)準(zhǔn)支持向量n s v a 志 磊y 臚蓋q 倒蚋 式中 k w 為標(biāo)準(zhǔn)支持向i i 擻 分類(lèi)判別函數(shù)為 f m 咖 a i y i k x i 巧 6 l 其中 巧 稱為核函數(shù) 核函數(shù)的思想是把本來(lái)應(yīng)該在高維空間中做的操作 在輸入 低維 空間中就完成 這樣就解決了高的維數(shù)帶來(lái)麻煩 用于模式識(shí)別的s v m 方法在分類(lèi)問(wèn)題中 通過(guò)使間隔最大化 以期獲得較好 的推廣能力 該方法已經(jīng)被用來(lái)解決復(fù)雜的分類(lèi)問(wèn)題 成為一種強(qiáng)大的模式分類(lèi) 方法 2 0 第二章支持向量機(jī) 2 6 支持向量機(jī)回歸 支持向量機(jī)的方法也可以應(yīng)用到回歸問(wèn)題 即實(shí)值函數(shù)估計(jì) 中 仍保留最大 間隔算法的所有主要特征 非線性函數(shù)可以通過(guò)特征空間中的學(xué)習(xí)機(jī)器得到 同 時(shí)系統(tǒng)的容量由與特征空間維數(shù)不相關(guān)的參數(shù)控制 同分類(lèi)算法一樣 學(xué)習(xí)算法 要最小化一個(gè)凸函娩并且它的解是稀疏的 為估計(jì)實(shí)值函數(shù) 我們采用二次e 不敏感函數(shù)作為損失函數(shù)的定義 即 v o x 弘一 x i i 掣一 x i e 2 x 協(xié)一b x l s v m 凝 不敏感損失回歸定義為 其中 扛峨曲 忪曠 g 喜c 陽(yáng) s g 再 一弘 6 仂一l x d e 6 矗 o f o i 1 仇 這里引入了兩個(gè)松弛變量 一個(gè)是在目標(biāo)值之上超出 所設(shè) 另一個(gè)是在目標(biāo)值之 下超出e 所設(shè) 綜合前面六節(jié)的內(nèi)容 我們得到s v m 實(shí)現(xiàn)的就是如下的思想 通過(guò)某種事先 選擇的非線性映射將輸入向量映射到高維特征空間 再在這個(gè)空間中構(gòu)造優(yōu)化間 隔的超平面 一2 1 湖北大學(xué)碩士學(xué)位論文 第三章非標(biāo)準(zhǔn)支持向量機(jī)分類(lèi)誤差分析 支持向量機(jī)是建立在統(tǒng)計(jì)學(xué)習(xí)理論的v c 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化基礎(chǔ)上的 學(xué)習(xí)機(jī)器 它根據(jù)有限樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷 以期獲得好的推廣能力 已經(jīng)在模式識(shí)別的許多領(lǐng)域獲得了成功的應(yīng)用 例如文 本分類(lèi) 手寫(xiě)字符識(shí)別 生物序列分析等領(lǐng)域得到了快速發(fā)展 并表現(xiàn)出極好的性 能 因此 對(duì)支持向量機(jī)學(xué)習(xí)算法進(jìn)行分類(lèi)誤差分析 具有非常重要的理論和現(xiàn)實(shí) 意義 然而 支持向量機(jī)學(xué)習(xí)算法的嚴(yán)格數(shù)學(xué)分析還有待于進(jìn)一步探討與完善 且 需要構(gòu)造針對(duì)具體應(yīng)用問(wèn)題的支持向量機(jī)算法 支持向量機(jī)分類(lèi)算法具有四個(gè)顯 著特點(diǎn) 1 利用最大間隔的思想降低分類(lèi)器的v i 維 實(shí)現(xiàn)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則 控制 分類(lèi)器的推廣能力 2 利用m 部c e r 核實(shí)現(xiàn)線性算法的非線性化 3 稀疏性 即少量樣本 支持向量 的系數(shù)不為零 就推廣性而言 較少的支持向 量在統(tǒng)計(jì)意義上對(duì)應(yīng)好的推廣能力 從計(jì)算角度看 支持向量減少了核形式 判別式的計(jì)算 i 4 算法設(shè)計(jì)成凸二次規(guī)劃問(wèn)題 避免了多解性 至1 9 9 5 年以來(lái) 在實(shí)用算法研究 設(shè)計(jì)和實(shí)現(xiàn)方面已取得了豐碩的成果 可歸 結(jié)為幾個(gè)大的研究方向 1 提高s v m 的計(jì)算速度 以便于處理大的研究方向 如序列最小化方法 1 7 等 2 利用最優(yōu)化技術(shù)改進(jìn)或改造支持向量機(jī)形式 簡(jiǎn)化計(jì)算過(guò)程 如線 性s v m 8 l s s v m 1 9 等 3 依據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則和支持向 i 機(jī)的某些思想提出新的算法 如u s v m 2 0 廣義s v m 2 1 等算法 4 利用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則 核思想和正則化技術(shù)等改造傳統(tǒng)的線性算法 構(gòu) 造出相應(yīng)的核形式 如核主成分分析 2 2 等 s v m c a 于其出色的學(xué)習(xí)性能 應(yīng)用領(lǐng)域不斷擴(kuò)展 因而非標(biāo)準(zhǔn)支持向量機(jī)的 研究就顯得尤為重要 因?yàn)?在實(shí)際問(wèn)題中不同類(lèi)別的錯(cuò)分誤差一般并不相等 主 要有以下幾個(gè)原因 2 2 第三章非標(biāo)準(zhǔn)支持向量機(jī)分類(lèi)誤差分析 1 不同樣本點(diǎn)的損失不同 不同類(lèi)型的錯(cuò)分有不同的損失 一種類(lèi)型的的錯(cuò)分 往往要比另一種類(lèi)型的的錯(cuò)分更為嚴(yán)重 例如 醫(yī)生將一位癌癥患者診斷為 健康人所帶來(lái)的后果 要比將一個(gè)健康人診斷為患者的后果嚴(yán)重的多 2 存在采樣偏差 在某些情況下 從訓(xùn)練集中采樣得到的樣本不是完全隨機(jī) 的 對(duì)于兩類(lèi)分類(lèi)情形 從一類(lèi)中隨機(jī)抽取的樣本與從另一類(lèi)中隨機(jī)抽取的 樣本的比例與整個(gè)樣本空同中兩類(lèi)之間的比例有較大差異 例如患稀有疾 病的人的數(shù)目是很少的 若取樣時(shí)從所有人群中隨機(jī)取樣 則樣本中合有患 者的數(shù)目是很少的 實(shí)際中一個(gè)普通的方法是患者和健康人群中分別取樣 可按事先指定的數(shù)目從患者中隨機(jī)取樣 然后再?gòu)慕】等酥腥∫粋€(gè)數(shù)目與 前者不相上下的樣本 這樣我們得到的訓(xùn)練樣本包含上述兩部分 3 樣本空間的分布與訓(xùn)練樣本的分布有差異 通常把這三種情形稱為非標(biāo)準(zhǔn)情形 本文主要考慮前兩種情形下的非標(biāo)準(zhǔn)支 持向量機(jī) 3 1 非標(biāo)準(zhǔn)支持向量機(jī) 3 1 1 非標(biāo)準(zhǔn)支持向量機(jī)讕練算法 為了表述方便 重寫(xiě)標(biāo)準(zhǔn)s v m 訓(xùn)練的目標(biāo)函數(shù) 滿足約束 轉(zhuǎn)化為對(duì)偶問(wèn)題 知 i i z c 壹6 口 i 1 璣 塒 龜一 1 一島 v i 3 1 nnn 呼妒 n 呼i 萋萎璣協(xié)耳 啦 一 m 3 2 i l l i 1 2 3 湖北大學(xué)碩士學(xué)位論文 滿足約束 v i 0 s 啦 g 肫 o l 式中0 酬2 這一項(xiàng)與在線性可分情況下分界面間的最小距離有關(guān) 6 代表在線性不 可分的情況下的松弛量 即充許錯(cuò)分樣本點(diǎn)偏離分界面的程度 而常數(shù)e 則表述 對(duì)這種錯(cuò)分情況的懲罰因子 設(shè)c 是把正樣本錯(cuò)誤分