本文格式為Word版，下載可任意編輯——機(jī)器學(xué)習(xí)作業(yè)渤海大學(xué)研究生機(jī)器學(xué)習(xí)課程考核論文

院（系、部）：信息科學(xué)與技術(shù)學(xué)院年級(jí)：一專業(yè)：計(jì)算機(jī)軟件與理論

姓名：馬健學(xué)號(hào)：2023100002密封線

任課教師：秦玉平一、命題部分

二、評(píng)分標(biāo)準(zhǔn)

三、教師評(píng)語

請(qǐng)根據(jù)您確定的評(píng)分標(biāo)準(zhǔn)詳細(xì)評(píng)分，給定成績，填入“成績〞部分。

閱卷教師評(píng)語成績?cè)u(píng)閱教師簽字：200年月日____________________________注1：本頁由學(xué)生填寫卷頭和“任課教師〞部分，其余由教師填寫。其中藍(lán)色字體部分請(qǐng)教師在命題時(shí)刪

除。提交試卷時(shí)含本頁。學(xué)生從其次頁開始寫作，要求見藍(lán)色字體部分。

注2：“閱卷教師評(píng)語〞部分請(qǐng)教師用紅色或黑色碳素筆填寫，不可用電子版。無“評(píng)語〞視為不合規(guī)范。注3：試題、評(píng)分標(biāo)準(zhǔn)、評(píng)語盡量控制在本頁。注4：不符合規(guī)范試卷需修改規(guī)范后提交。

第1頁共11頁

密封線

基于支持向量機(jī)的機(jī)器學(xué)習(xí)研究

馬健

摘要:基于數(shù)據(jù)的機(jī)器學(xué)習(xí)，研究的實(shí)質(zhì)是從觀測數(shù)據(jù)出發(fā)尋覓規(guī)律，利用這些規(guī)律對(duì)未來數(shù)據(jù)

或無法觀測的數(shù)據(jù)進(jìn)行分類、研究、處理。支持向量機(jī)是基于統(tǒng)計(jì)學(xué)習(xí)理論的一種新的機(jī)器學(xué)習(xí)方法，因其卓越的學(xué)習(xí)性能在國內(nèi)為學(xué)術(shù)界引起了日益廣泛的重視。本文對(duì)機(jī)器學(xué)習(xí)、支持向量機(jī)的研究現(xiàn)狀進(jìn)行了綜述，闡述了機(jī)器學(xué)習(xí)和支持向量機(jī)的基本概念和支持向量機(jī)的訓(xùn)練算法。

關(guān)鍵字：機(jī)器學(xué)習(xí)支持向量機(jī)統(tǒng)計(jì)學(xué)習(xí)理論0引言

學(xué)習(xí)是一起智能系統(tǒng)最根本的特征。機(jī)器學(xué)習(xí)是人工智能最具智能特征、最前沿的研究領(lǐng)域之一。機(jī)器學(xué)習(xí)就是要使計(jì)算機(jī)模擬人的學(xué)習(xí)行為，自動(dòng)地通過學(xué)習(xí)獲取知識(shí)和技能，不斷改善性能，實(shí)現(xiàn)自我完善。

與傳統(tǒng)統(tǒng)計(jì)學(xué)比較，統(tǒng)計(jì)學(xué)習(xí)理論是一種專門研究有限樣本狀況下機(jī)器學(xué)習(xí)規(guī)律的理論。V.Vapinik等人從上世紀(jì)六、七十年代開始致力于此方面研究，到九十年代中期，其理論不斷發(fā)展和成熟。統(tǒng)計(jì)學(xué)習(xí)理論是建立在一套較堅(jiān)實(shí)的理論基礎(chǔ)之上的，為解決有限樣本學(xué)習(xí)問題提供了一個(gè)統(tǒng)一的框架，它能將好多現(xiàn)有方法納入其中，同時(shí)，在這一理論基礎(chǔ)上發(fā)展了一種新的通用的學(xué)習(xí)方法支持向量機(jī)（SupportVectorMachine或SVM),它已初步表現(xiàn)出好多優(yōu)于已有方法的性能。目前，SLT和SVM已成為國際上機(jī)器學(xué)習(xí)新的研究熱點(diǎn)問題。

1機(jī)器學(xué)習(xí)簡介

在人們對(duì)機(jī)器智能的研究中，希望能夠用計(jì)算機(jī)來模擬人的思考和推廣能力這種學(xué)習(xí)能力，

這就是我們所說的基于數(shù)據(jù)的機(jī)器學(xué)習(xí)問題，或者簡單地稱為機(jī)器學(xué)習(xí)（MachineLearning）問題。

1.1機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)

第2頁共11頁

密封線

一個(gè)學(xué)習(xí)系統(tǒng)一般應(yīng)當(dāng)由環(huán)境、學(xué)習(xí)、知識(shí)庫、執(zhí)行四個(gè)基本部分組成。如圖1所示

圖1機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)

環(huán)境向系統(tǒng)的學(xué)習(xí)部分提供某些信息；學(xué)習(xí)部分利用這些信息修改知識(shí)庫，以加強(qiáng)系統(tǒng)執(zhí)行部分完成任務(wù)的效能；執(zhí)行部分根據(jù)知識(shí)庫完成任務(wù)，同時(shí)把獲得的信息反饋給學(xué)習(xí)部分。在具體應(yīng)用中，環(huán)境、知識(shí)庫和執(zhí)行部分決定了具體的工作內(nèi)容，學(xué)習(xí)部分所需要解決的問題完全由上述三部分確定。

環(huán)境學(xué)習(xí)知識(shí)庫執(zhí)行1.2機(jī)器學(xué)習(xí)的主要策略

機(jī)器學(xué)習(xí)有好多優(yōu)秀的學(xué)習(xí)算法，基本上可以分為基于符號(hào)和基于非符號(hào)學(xué)習(xí)（連接學(xué)習(xí)）。其中比較好的策略有機(jī)械式學(xué)習(xí)、指導(dǎo)式學(xué)習(xí)、歸納學(xué)習(xí)、類比學(xué)習(xí)、基于解釋的學(xué)習(xí)、基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)、支持向量機(jī)、基于遺傳算法的學(xué)習(xí)、加強(qiáng)學(xué)習(xí)、多Agent學(xué)習(xí)。

1.3分類問題

機(jī)器學(xué)習(xí)主要關(guān)心分類問題，它是大量其他問題的基礎(chǔ)和核心。

分類是通過對(duì)具體類別標(biāo)記的實(shí)例（數(shù)據(jù)）進(jìn)行訓(xùn)練，得出一個(gè)能夠預(yù)計(jì)新實(shí)例類別的模型。設(shè)

D??d1...dm?,為訓(xùn)練的實(shí)例集合，每一個(gè)實(shí)例都有預(yù)先標(biāo)記好的類Ck,?Ck??C0。通過對(duì)這些數(shù)據(jù)的有

導(dǎo)師學(xué)習(xí)，產(chǎn)生一個(gè)稱為分類器的模型，它能對(duì)不知道類別標(biāo)記的實(shí)例預(yù)計(jì)其類別。預(yù)計(jì)的確鑿程度可以評(píng)價(jià)分類器的性能。

分類方法主要有貝葉斯分類、分治法、覆蓋算法、投票算法等。

2基于支持向量機(jī)的機(jī)器學(xué)習(xí)2.1支持向量機(jī)簡介

支持向量機(jī)（SupportVectorMachine）是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中有大量特有的優(yōu)勢，并能推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。

支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的繁雜性和學(xué)習(xí)能力之間尋求最正確折衷，以期獲得最好的推廣能力。

第3頁共11頁

密封線

1）VC維

定義1.1(N(F,Zm))：設(shè)F是一個(gè)假設(shè)集，即由在記

X?Rn上取值為-1或

f1的若干函數(shù)組成的集合。

Zm={x1,x2,...,xm}為

f(

X中的ｍ個(gè)點(diǎn)組成的集合。考慮當(dāng)(

取遍F中的所有可能的假設(shè)時(shí)產(chǎn)生的m維

向量(

x1),f(

x2),…fxm))。定義N(F,Zm))為上述m維向量中不同的向量個(gè)數(shù)。

定義1.2（

Zm被

F打散）：設(shè)F是一個(gè)假設(shè)集，

Zm={x1,x2,...,xm}為

X中的m個(gè)點(diǎn)組成的集合。稱

Zm被

F打散，或F打散

Zm。

定義1.3（VC維）：設(shè)假設(shè)集F是一個(gè)由X上取值為-1或1的函數(shù)組成的集合。定義F的VC維為max{m|N(F,

Zm)=2m}.

VC維反映了函數(shù)集的學(xué)習(xí)能力。一般而言，VC維越大，學(xué)習(xí)機(jī)器越繁雜。但目前沒有通用的關(guān)于任意VC維計(jì)算的理論，只對(duì)一些特別函數(shù)集的VC維可以計(jì)算。如何利用理論和試驗(yàn)的方法計(jì)算VC維是當(dāng)前統(tǒng)計(jì)學(xué)習(xí)理論中一個(gè)待研究的問題[3]。2）結(jié)構(gòu)風(fēng)險(xiǎn)最小化

機(jī)器學(xué)習(xí)本質(zhì)上是一種對(duì)問題真實(shí)模型的迫近，由于真實(shí)世界的模型往往無法確切給出，我們給出的模型與真實(shí)模型就存在一個(gè)誤差，這個(gè)與真實(shí)模型之間的誤差積累就叫做風(fēng)險(xiǎn)。統(tǒng)計(jì)學(xué)習(xí)理論系統(tǒng)地研究了對(duì)于各種類型的函數(shù)集，經(jīng)驗(yàn)風(fēng)險(xiǎn)和實(shí)際風(fēng)險(xiǎn)之間的關(guān)系，即泛化誤差界。統(tǒng)計(jì)學(xué)習(xí)理論指出：經(jīng)驗(yàn)風(fēng)險(xiǎn)

Remp(w)和實(shí)際風(fēng)險(xiǎn)R(w)之間至少以

1-η的概率滿足如下關(guān)系

R(w)?Remp(w)?其中，l是樣本數(shù)，h是函數(shù)集的VC維。

h(ln(2l/h)?1)?ln(?/4)l

這一結(jié)論說明，統(tǒng)計(jì)學(xué)習(xí)的實(shí)際風(fēng)險(xiǎn)由兩部分組成：一個(gè)是經(jīng)驗(yàn)風(fēng)險(xiǎn)，另一個(gè)是置信風(fēng)險(xiǎn)。置信風(fēng)險(xiǎn)

反映了真實(shí)風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)差值的上確界，和VC維h記樣本數(shù)l有關(guān)。可簡單地表示為

R(w)?Remp(w)??(h/l)

在有限的訓(xùn)練樣本下，學(xué)習(xí)機(jī)器的繁雜性越高，VC維越大，置信風(fēng)險(xiǎn)就越大，就會(huì)導(dǎo)致真實(shí)風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)間的區(qū)別越大。如下圖

第4頁共11頁

密封線

這就解釋了為什么有些學(xué)習(xí)機(jī)器訓(xùn)練階段的確鑿率可以達(dá)到100%而泛化能力卻很差。結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則（StructuralRiskMinimization,SRM）就是為了取得經(jīng)驗(yàn)風(fēng)險(xiǎn)與置信風(fēng)險(xiǎn)的最小和。統(tǒng)計(jì)機(jī)器學(xué)習(xí)理論就是為了努力最小化結(jié)構(gòu)風(fēng)險(xiǎn)。即不僅要使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化，還要使VC維最小。

2.2線性分類器

線性分類器是最簡單也是很有效的分類器形式，SVM就是是從線性可分狀況下的最優(yōu)分類面發(fā)展而來的。

1）線性可分

當(dāng)一個(gè)線性函數(shù)能將樣本完全正確地分開時(shí)，此時(shí)這些樣本就是線性可分的。否則就稱為非線性可分

的。線性函數(shù)指形如f(x)=wx+b的一次函數(shù)，此函數(shù)值為0時(shí)確定了一個(gè)n維空間的超平面(HyperPlane)。w、x為n維向量，b為常數(shù)。

2）廣義最優(yōu)分類面

第5頁共11頁

密封線

方形和圓形為兩類樣本，H為分類線，H1,H2分別為過各類分類線最近的樣本，且與分類線平行，他

們之間的距離margin稱為分類間隔。當(dāng)分類線H不但能將兩類正確分開，而且使分類間隔最大時(shí)，此分類線稱為最優(yōu)分類線。對(duì)分類線方程wx+b=0進(jìn)行歸一化處理，使得對(duì)線性可分的樣本集

(xi,yi),i?1,...,n,x?Rd,y?{?1,?1}，滿足

yi[(w?xi)?b]?1?0,i?1,,n.

此時(shí)分類間隔等于

2/w，使間隔最大等價(jià)于使

w2最小。滿足上述條件的分類面就叫最優(yōu)分類面，

H1,H2上的訓(xùn)練樣本點(diǎn)就稱作支持向量。

使分類間隔最大實(shí)際上就是對(duì)推廣能力的控制，這是SVM的核心思想之一。統(tǒng)計(jì)學(xué)習(xí)理論指出，在N

維空間中，設(shè)樣本分布在一個(gè)半徑為R的超球范圍內(nèi)，則滿足條件集

w?A的正則超平面構(gòu)成的指示函數(shù)

f(x,w,b)?sgn{(w?x)?b}（sgn()為符號(hào)函數(shù)）的

VC維滿足下面的界

h?min([R2A2],N)?1

因此，使

w2最小就是使VC維的上界最小，從而實(shí)現(xiàn)SRM準(zhǔn)則中對(duì)函數(shù)繁雜性的選擇。

于是問題就轉(zhuǎn)換成一個(gè)有約束的非線性規(guī)劃問題：

minw,b1w22

s.t.yi(w?xi?b)?1,i?1,2,,l

稱上二式組成的最優(yōu)化問題為原始優(yōu)化問題。由于此為凸二次尋優(yōu)問題，根據(jù)最優(yōu)化理論，這個(gè)問題存在唯一全局最小解。其Lagrange函數(shù)為：

第6頁共11頁

密封線

l12L?w???i[1?yi(w?xi?b)]

2i?1其中，?i

?0是約束yi(w?xi?b)?1的

Lagrange乘子。

根據(jù)KKT條件（Karush-Kuhn-Tucker）有：

ll?L?w???iyixi?0?w???iyixi?wi?1i?1l?L???iyi?0?bi?1根據(jù)wolf對(duì)偶理論，經(jīng)運(yùn)算將原始優(yōu)化問題轉(zhuǎn)為

max?l1lw(?)???i???i?jyiyj(xi?xj)

2i,j?1i?1ls.t.??i?1iyi?0,?i?0,i?1,2,...,l.

解此最優(yōu)化問題，可確定最優(yōu)超平面。且尋常只有一小部分量。此時(shí)得到的最優(yōu)分類函數(shù)是

?i不為

0，這些非零解對(duì)應(yīng)的樣本就是支持向

f(x)?sgn{(w?x)?b}?sgn{??iyi(xi?x)?b*}

i?1n不難看出，式中的求和實(shí)際上只對(duì)支持向量進(jìn)行。一個(gè)樣本線性可分時(shí)的線性分類器。

b*可由任一支持向量回代求得。此時(shí)，我們就得到了

2.3核函數(shù)

線性可分的問題可以由上述的線性分類器求解，當(dāng)待分類樣本為非線性可分時(shí)，可以通過非線性變換轉(zhuǎn)化為某個(gè)高維空間中的線性問題，在變換空間求最優(yōu)分類面。如圖

第7頁共11頁

密封線

當(dāng)（a,b）范圍內(nèi)的樣本為一類，其余部分為一類時(shí)，在二維空間無法找到一個(gè)線性函數(shù)將其正確分開，但我們可以找到一條曲線，如

此時(shí)該函數(shù)表達(dá)式為

g(x)?c0x2?c1x?c2

新建一個(gè)向量

y?(y1,y2,y3)T?(x2,x,1)T,a?(a1,a2,a3)T?(c0,c1,c2)T

將g(x)轉(zhuǎn)化為

f(y)??a,y?，此時(shí)

f(y)與g(x)等價(jià)，且為四維空間中的線性函數(shù)。這樣，我們就將低

維的非線性可分問題轉(zhuǎn)化為了高維的線性可分問題。

但惋惜的是，目前還沒有一種系統(tǒng)地將低維向量映射到高維的方法。

第8頁共11頁

密封線

事實(shí)上，計(jì)算過程中我們只關(guān)心高維向量之間的內(nèi)積，只要找出一種方法可以求出此值就得到了我們想要的結(jié)果。

核函數(shù)（kernelfunction）正是為了求出低維空間的向量經(jīng)過變換后在高維空間的內(nèi)積而提出的。

并且由于其輸入為原空間中的低維向量，避開了高維變換計(jì)算問題，使得問題大大簡化了。

根據(jù)泛函的有關(guān)理論，只要一種核函數(shù)[6]。

Mercer條件：對(duì)任意的對(duì)稱函數(shù)意?(x)2??0，且??(x)dx??，有

K(xi,xj)滿足

Mercer條件，它就對(duì)應(yīng)某一變換空間中的內(nèi)積

K(x,x?),它是某個(gè)特征空間中的內(nèi)積運(yùn)算的充分必要條件是，對(duì)任

??K(x,x?)?(x)?(x?)dxdx??0

用核函數(shù)替換內(nèi)積函數(shù)后，此時(shí)的最優(yōu)分類目標(biāo)函數(shù)變?yōu)?/p>

f(x)?sgn{??iyiK(xi?x)?b*}

i?1n此時(shí)由于計(jì)算仍在原空間進(jìn)行，分類器的計(jì)算繁雜度沒有增加[4]。

目前，常用的核函數(shù)有以下幾種：線性核函數(shù)：

K(xi,xj)?xi?xj

多項(xiàng)式核函數(shù)：

K(xi,xj)?[(xi?xj)?1]d

徑向基函數(shù)（RBF）：

2K(xi,xj)?exp(??xi?xj)

Sigmoid函數(shù)：

K(xi,xj)?tanh(v(xi?xj)?c)

這時(shí)SVM實(shí)現(xiàn)的是包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定的，而且算法不存在困擾神經(jīng)網(wǎng)絡(luò)方法的局部微小點(diǎn)問題。3支持向量機(jī)目前研究現(xiàn)狀

由于支持向量機(jī)堅(jiān)實(shí)的理論基礎(chǔ)和它在好多領(lǐng)域表現(xiàn)出的良好的推廣性能，目前，國際上正在廣泛開

第9頁共11頁

密封線

展支持向量機(jī)的研究，包括算法本身的改進(jìn)和算法的實(shí)際應(yīng)用，都不斷提了出來。以下是其中主要的研究熱點(diǎn)。

3.1改進(jìn)訓(xùn)練算法

鑒于SVM對(duì)偶問題的求解過程相當(dāng)于解一個(gè)線性約束的二項(xiàng)規(guī)劃問題（QP），需要計(jì)算和存儲(chǔ)核函數(shù)矩陣，其大小與訓(xùn)練樣本的平方相關(guān)，因此，隨著樣本數(shù)目的增加，所需要的內(nèi)存也增大，例如，當(dāng)樣本數(shù)目超過4000時(shí)，存儲(chǔ)核函數(shù)矩陣需要多達(dá)128M內(nèi)存；其次，SVM在二次型尋優(yōu)過程中要進(jìn)行大量的矩陣運(yùn)算，多數(shù)狀況下，巡優(yōu)算法是占用算法時(shí)間的主要部分。尋常，訓(xùn)練算法改進(jìn)的思路是把要求解的問題分成大量子問題，然后通過反復(fù)求解子問題來求得最終的解，方法有如下幾種：

（1）塊處理算法（chunkingalgorithm）它的思想是將采樣本集分成工作樣本集合測試樣本集，每次對(duì)工作樣本集利用二項(xiàng)規(guī)劃求得最優(yōu)解，剔除其中的分支持向量，并用訓(xùn)練結(jié)果對(duì)剩余樣本進(jìn)行檢驗(yàn)，將不符合訓(xùn)練結(jié)果（一般是指違背KKT條件）的樣本（或其中的一部分）與本次結(jié)果的支持向量合并，成為一個(gè)新的工作樣本集，然后重新訓(xùn)練。如此重復(fù)下去，直到獲得最優(yōu)結(jié)果。其依據(jù)是去掉Lagrange乘子等于零的訓(xùn)練樣本不會(huì)影響原問題的解，塊算法的一個(gè)前提是：支持向量的數(shù)目比較少。然而假使支持向量的數(shù)目本身就比較多，那么隨著訓(xùn)練迭代次數(shù)的增加，工作樣本數(shù)也越來越大，就會(huì)導(dǎo)致算法無法實(shí)施。

（2）固定工作樣本集算法它使樣本數(shù)目固定在足以包含所有的支持向量，且算法速度在計(jì)算機(jī)可以容忍的限度內(nèi)。迭代過程中只是將剩余樣本中部分“狀況最糟的樣本‘與工作樣本集中的樣本進(jìn)行等量交換。即使支持向量的個(gè)數(shù)超過工作樣本集的規(guī)模。文獻(xiàn)[3]介紹了一種具體的算法，將樣本集分為B和N兩個(gè)集合，集合B作為子問題的工作樣本集進(jìn)行SVM訓(xùn)練，集合N中所有樣本的Lagrange乘子均置為零。顯然，假使把集合B中，對(duì)應(yīng)Lagrange乘子為零的樣本i(

ai?0,i?B)與集合

N的樣本j(既

aj?0,j?N)交換，不會(huì)改變子問題與原問題的可行性（既仍舊滿足約束條件）。于是可以依照以下步驟

迭代求解：1）選擇集合B,構(gòu)造子問題；2）求子問題最優(yōu)解

lai,i?B及b,并置aj?0,j?N;3)計(jì)算

g(xj)yj,j?N,找出其中g(shù)(xj)yj?1的樣子

j,(

g(xj)??apyp?1K(xj,xp)?b),與

B中滿足

ai?0的樣本i交換，構(gòu)成新的子問題，需要指出：假使集合

提出改變B的大小的策略，那么有可能得不到結(jié)果。

B不足以包括所有的支持向量，該算法沒有

第10頁共11頁

密封線

（3）SMO算法SMO是固定工作樣子集算法的一個(gè)極端狀況，其工作樣本數(shù)目為2.需要兩個(gè)樣子，是由于等式線性約束的存在使得同時(shí)至少有兩個(gè)Lagrange乘