第八章

高級(jí)人工智能1/30/2021Chap8

SVM

Zhongzhi

Shi1史忠植中國科學(xué)院計(jì)算技術(shù)研究所支持向量機(jī)Support

Vector

Machines內(nèi)容提要1/30/2021Chap8

SVM

Zhongzhi

Shi2統(tǒng)計(jì)學(xué)習(xí)方法概述統(tǒng)計(jì)學(xué)習(xí)問題學(xué)習(xí)過程的泛化能力支持向量機(jī)SVM尋優(yōu)算法應(yīng)用統(tǒng)計(jì)學(xué)習(xí)方法概述1/30/2021Chap8

SVM

Zhongzhi

Shi3統(tǒng)計(jì)方法是從事物的外在數(shù)量上的表現(xiàn)去推斷該事物可能的規(guī)律性?？茖W(xué)規(guī)律性的東西一般總是隱藏得比較深,最初總是從其數(shù)量表現(xiàn)上通過統(tǒng)計(jì)分析看出一些線索,然后提出一定的假說或?qū)W說,作進(jìn)一步深入的理論研究。當(dāng)理論研究提出一定的結(jié)論時(shí),往往還需要在實(shí)踐中加以驗(yàn)證。就是說,觀測(cè)一些自然現(xiàn)象或?qū)ｉT安排的實(shí)驗(yàn)所得資料,是否與理論相符、在多大的程度上相符、偏離可能是朝哪個(gè)方向等等問題,都需要用統(tǒng)計(jì)分析的方法處理。統(tǒng)計(jì)學(xué)習(xí)方法概述1/30/2021Chap8

SVM

Zhongzhi

Shi4近百年來，統(tǒng)計(jì)學(xué)得到極大的發(fā)展。我們可用下面的框架粗略地刻劃統(tǒng)計(jì)學(xué)發(fā)展的過程:1900-19201920-19401940-1960數(shù)據(jù)描述統(tǒng)計(jì)模型的曙光數(shù)理統(tǒng)計(jì)時(shí)代隨機(jī)模型假設(shè)的挑戰(zhàn)松弛結(jié)構(gòu)模型假設(shè)1990-1999

建模復(fù)雜的數(shù)據(jù)結(jié)構(gòu)統(tǒng)計(jì)學(xué)習(xí)方法概述1/30/2021Chap8

SVM

Zhongzhi

Shi5從1960年至1980年間，統(tǒng)計(jì)學(xué)領(lǐng)域出現(xiàn)了一場(chǎng)革命要從觀測(cè)數(shù)據(jù)對(duì)依賴關(guān)系進(jìn)行估計(jì)，只要知道未知依賴關(guān)系所屬的函數(shù)集的某些一般的性質(zhì)就足夠了引導(dǎo)這一革命的是60年代的四項(xiàng)發(fā)現(xiàn): Tikhonov,Ivanov和Philips發(fā)現(xiàn)的關(guān)于解決不適問題的正則化原則； Parzen,Rosenblatt 和Chentsov發(fā)現(xiàn)的非參數(shù)統(tǒng)學(xué)； Vapnik和Chervonenkis發(fā)現(xiàn)的在泛函數(shù)空間的大定律，以及它與學(xué)習(xí)過程的關(guān)系； Kolmogorov,Solomonoff 和Chaitin發(fā)現(xiàn)的算法復(fù)雜性及其與歸納推理的關(guān)系。這四項(xiàng)發(fā)現(xiàn)也成為人們對(duì)學(xué)習(xí)過程研究的重要基礎(chǔ)。統(tǒng)計(jì)學(xué)習(xí)方法概述1/30/2021Chap8

SVM

Zhongzhi

Shi6統(tǒng)計(jì)學(xué)習(xí)方法: 傳統(tǒng)方法:統(tǒng)計(jì)學(xué)在解決機(jī)器學(xué)習(xí)問題中起著基礎(chǔ)性的作用。傳統(tǒng)的統(tǒng)計(jì)學(xué)所研究的主要是漸近理論即當(dāng)樣本趨向于無窮多時(shí)的統(tǒng)計(jì)性質(zhì)。統(tǒng)計(jì)方法主要考慮測(cè)試預(yù)想的假設(shè)和數(shù)據(jù)模型擬合。它依賴于顯式的基本概率模型。模糊集粗糙集支持向量機(jī)統(tǒng)計(jì)學(xué)習(xí)方法概述1/30/2021Chap8

SVM

Zhongzhi

Shi7統(tǒng)計(jì)方法處理過程可以分為三個(gè)階段:（1）搜集數(shù)據(jù):采樣、實(shí)驗(yàn)設(shè)計(jì)（2）分析數(shù)據(jù):建模、知識(shí)發(fā)現(xiàn)、可視化（3）進(jìn)行推理:預(yù)測(cè)、分類常見的統(tǒng)計(jì)方法有:回歸分析（多元回歸、自回歸等）判別分析（貝葉斯判別、費(fèi)歇爾判別、非參數(shù)判別等）聚類分析（系統(tǒng)聚類、動(dòng)態(tài)聚類等）探索性分析（主元分析法、相關(guān)分析法等）等。COLT(Computational

Learning

Theory)支持向量機(jī) SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法,它是由Boser,Guyon,Vapnik在COLT-92上首次提出,從此迅速發(fā)展起來 VapnikVN.1995.TheNatureofStatisticalLearningTheory.SpringeVerlag,NewYork VapnikVN.1998.StatisticalLearninTheory.Wiley-IntersciencePublicatiJohnWiley&Sons,Inc 目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用。1/30/2021Chap8

SVM

Zhongzhi

Shi8統(tǒng)計(jì)學(xué)習(xí)理論1/30/2021Chap8

SVM

Zhongzhi

Shi9 統(tǒng)計(jì)學(xué)習(xí)理論是小樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)學(xué)習(xí)的最佳理論。 假設(shè)輸出變量Y與輸入變量X之間存在某種對(duì)應(yīng)的依賴關(guān)系,即一未知概率分布P(X,Y),P(X,Y)反映了某種知識(shí)。學(xué)習(xí)問題可以概括為:根據(jù)l個(gè)獨(dú)立同分布(independentlydrawnandidenticallydistributed)的觀測(cè)樣本trainset,(x1,y1),(x2,y2),…,(xn,yn)函數(shù)估計(jì)模型學(xué)習(xí)樣本的函數(shù):

產(chǎn)生器

(G)

generates

observations

x(typically

in

Rn),

independentlydrawn

from

some

fixed

distributionF(x)

訓(xùn)練器Supervisor

(S)

labels

eachinput

x

with

an

output

value

yaccording

to

some

fixed

distributionF(y|x) 學(xué)習(xí)機(jī)Learning Machine (LM) “l(fā)earnsfromani.i.d.l-sampleof(x,y)-pairsoutputfromGandS,bychoosingafunctionthatbestapproximatesSfromaparameterisedfunctionclassf(x, ),where isintheparameterset關(guān)鍵概念:F(x,y),ani.i.d.l-sampleonF,functionsf(x,)andtheequivalentrepresentationofeachfusingitsindexGSLMxy^y1/30/2021Chap8

SVM

Zhongzhi

Shi10期望風(fēng)險(xiǎn)學(xué)習(xí)到一個(gè)假設(shè)H=f(x,w)作為預(yù)測(cè)函數(shù),其中w是廣義參數(shù).它對(duì)F(X,Y)的期望風(fēng)險(xiǎn)R(w)是(即統(tǒng)計(jì)學(xué)習(xí)的實(shí)際風(fēng)險(xiǎn)):其中,{f(x,w)}稱作預(yù)測(cè)函數(shù)集,w為函數(shù)的廣義參數(shù)。{f(x,w)}可以表示任何函數(shù)集。L(y,f(x,w為由于用f(x,w)對(duì)y進(jìn)行預(yù)測(cè)而造成的損失。不同類型的學(xué)習(xí)問題有不同形式的損失函數(shù)。1/30/2021Chap8

SVM

Zhongzhi

Shi11而對(duì)train

set上產(chǎn)生的風(fēng)險(xiǎn)Remp(w)被稱為經(jīng)驗(yàn)風(fēng)險(xiǎn)(學(xué)習(xí)的訓(xùn)練誤差):首先Remp(w)和R(w)都是w的函數(shù),傳統(tǒng)概率論中的定理只說明了(在一定條件下)當(dāng)樣本趨于無窮多時(shí)Remp(w)將在概率意義上趨近于R(w),卻沒有保證使Remp(w)最小的點(diǎn)也能夠使R(w)最小(同步最小)。1/30/2021Chap8

SVM

Zhongzhi

Shi12經(jīng)驗(yàn)風(fēng)險(xiǎn)根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論中關(guān)于函數(shù)集的推廣性的界的結(jié)論,對(duì)于兩類分類問題中的指示函數(shù)集f(x,w)的所有函數(shù)(當(dāng)然也包括使經(jīng)驗(yàn)風(fēng)險(xiǎn)員小的函數(shù)),經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)和實(shí)際風(fēng)險(xiǎn)R(w)之間至少以不下于1-η(0≤η≤1)的概率存在這樣的關(guān)系:經(jīng)驗(yàn)風(fēng)險(xiǎn)1/30/2021Chap8

SVM

Zhongzhi

Shi13h是函數(shù)H=f(x,w)的VC維,l是樣本數(shù).1/30/2021Chap8

SVM

Zhongzhi

Shi14VC維(Vapnik-ChervonenkisDimension)。模式識(shí)別方法中VC維的直觀定義是:對(duì)一個(gè)指示函數(shù)集，如果存在h個(gè)樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個(gè)樣本打散。函數(shù)集的VC維就是它能打散的最大樣本數(shù)目h。VC維一般的學(xué)習(xí)方法(如神經(jīng)網(wǎng)絡(luò))是基于Remp(w)最小,滿足對(duì)已有訓(xùn)練數(shù)據(jù)的最佳擬和,在理論上可以通過增加算法（如神經(jīng)網(wǎng)絡(luò)）的規(guī)模使得Remp(w)不斷降低以至為0。但是,這樣使得算法（神經(jīng)網(wǎng)絡(luò)）的復(fù)雜度增加,VC維h增加,從而φ(h/l)增大,導(dǎo)致實(shí)際風(fēng)險(xiǎn)R(w)增加,這就是學(xué)習(xí)算法的過擬合(Overfitting).1/30/2021Chap8

SVM

Zhongzhi

Shi15過學(xué)習(xí)過學(xué)習(xí)Overfitting

and

underfittiProblem:

how

rich

class

of

classifications

q(x;θ)

to

use.underfitting good

fit

overfittingProblem

of

generalization:

a

small

emprical

risk

Remp

does

noimply

small

true

expected

risk

R.1/30/2021Chap8

SVM

Zhongzhi

Shi16學(xué)習(xí)理論的四個(gè)部分1/30/2021Chap8

SVM

Zhongzhi

Shi17學(xué)習(xí)過程的一致性理論What

are

(necessary

and

sufficient)

conditions

for

consistency(convergence

of

Remp

to

R)

of

a

learning

process

based

on

the

ERMPrinciple?學(xué)習(xí)過程收斂速度的非漸近理論How

fast

is

the

rate

of

convergence

of

a

learning

proces控制學(xué)習(xí)過程的泛化能力理論How

can

one

control

the

rate

of

convergence

(thegeneralization

ability)

of

a

learning

process?構(gòu)造學(xué)習(xí)算法的理論How

can

one

construct

algorithms

that

can

control

thegeneralization

ability?結(jié)構(gòu)風(fēng)險(xiǎn)最小化歸納原則(SRM)1/30/2021Chap8

SVM

Zhongzhi

Shi18

ERM

is

intended

for

relatively

largesamples

(large

l/h)Large

l/h

induces

a

smallwhichdecreases

the

the

upper

bound

on

risk

Small

samples?

Small

empirical

riskdoesn’t

guarantee

anything!…we

need

to

minimise

both

terms

of

theRHS

of

the

risk

boundsThe

empirical

risk

of

the

chosenAn

expression

depending

on

the

VC

dimension

of結(jié)構(gòu)風(fēng)險(xiǎn)最小化歸納原則(SRM)1/30/2021Chap8

SVM

Zhongzhi

Shi19

The

Structural

Risk

Minimisation

(SRM)PrincipleLet

S

=

{Q(z,),}.

An

admissiblestructure

S1S2…Sn

…

S:For

each

k,

the

VC

dimension

hk

of

Sk

is

finite

anh1≤h2≤…≤hn≤…≤hS

Every

Sk

is

either

is

non-negative

bounded,

orsatisfies

for

some

(p,

k)Forgivenz1,…,zlandanadmissiblestructureS1 S2…Sn…S,SRMchoosesfunctionQ(z,minimisingRempinSkforwhichtheguaranteedrisk(riskupper-bound)isminimal Thusmanagestheunavoidabletrade-offofqualityofapproximationplexityofapproximationS11/30/2021Chap8

SVM

Zhongzhi

Shi20S2Snhh1The

SRM

Principle

continuedhnh*結(jié)構(gòu)風(fēng)險(xiǎn)最小化歸納原則(SRM)Sn風(fēng)險(xiǎn)界限Bound

on

the

ris置信范圍Confidence

intervh*經(jīng)驗(yàn)風(fēng)險(xiǎn)Empirical

riskhn

hh1S*S1

S*Sn結(jié)構(gòu)風(fēng)險(xiǎn)最小化歸納原則(SRM)1/30/2021Chap8

SVM

Zhongzhi

Shi21支持向量機(jī)SVM1/30/2021Chap8

SVM

Zhongzhi

Shi22SVMs

are

learning

systems

thatuse

a

hyperplane

of

linear

functionsin

a

high

dimensional

feature

space

—

Kernel

funct

trained

with

a

learning

algorithm

from

optimizationtheory

—

Lagrange

Implements

a

learning

bias

derived

from

statisticallearning

theory

—

Generalisation

SVM

is

a

classifiderived

from

statistical

learning

theory

by

VapnikChervonenkis線性分類器ayestxff(x,w,b)=sign(w.x-b)denotes

+1denotes

-1How

would

youclassify

this

data?1/30/2021Chap8

SVM

Zhongzhi

Shi23f線性分類器xayestdenotes

+1denotes

-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8

SVM

Zhongzhi

Shi24How

would

youclassify

this

data?f線性分類器xayestdenotes

+1denotes

-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8

SVM

Zhongzhi

Shi25Copyright?2001,2003,AndrewW.MooreHow

would

youclassify

this

data?f線性分類器xayestdenotes

+1denotes

-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8

SVM

Zhongzhi

Shi26Copyright?2001,2003,AndrewW.MooreHow

would

youclassify

this

data?f線性分類器xayestdenotes

+1denotes

-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8

SVM

Zhongzhi

Shi27Copyright?2001,2003,AndrewW.MooreHow

would

youclassify

this

data?最大間隔fxayestdenotes

+1denotes

-1f(x,w,b)=sign(w.x-b)The

maximummargin

linearclassifier

is

thelinear

classifierwith

the

maximummargin.This

is

the

simplekind

of

SVM(Called

an

LSVM)Linear

SVM1/30/2021Chap8

SVM

Zhongzhi

Shi28Copyright?2001,2003,AndrewW.Moore分類超平面Training

set:

(xi,

yi),

i=1,2,…N;

yiHyperplane:

wx+b=0This

is

fully

determined

by

(w,b){+1,-1}1/30/2021Chap8

SVM

Zhongzhi

Shi29最大間隔According

to

a

theoremfrom

Learning

Theory,from

all

possible

lineardecision

functions

the

othat

maximises

the

margiof

the

training

set

willminimise

thegeneralisation

error.1/30/2021Chap8

SVM

Zhongzhi

Shi30最大間隔原則Note1:

decision

functions

(w,b)

and(cw,

cb)

are

the

sameNote2:

but

margins

as

measured

by

theoutputs

of

the

function

x

wx+bare

not

the

same

if

we

take

(cw,

cb)1/30/2021Chap8

SVM

Zhongzhi

Shi31Definition:

geometric

margin:

themargin

given

by

the

canonicaldecision

function,

which

is

whenc=1/||w||Strategy:we

need

to

maximise

thegeometric

margin!

(cf

result

fromlearning

theory)subject

to

the

constraint

thattraining

examples

are

classifiedcorrectlywwx+b=0wx+b>0wx+b<0AccordingtoNote1,wecandemandthefunctionoutputfthenearestpointstobe+1and–1onthetwosidesodecisionfunction.ThisremovesthescalingfreedomDenotinganearestpositiveexamplex+andanearestnegativeexamplex-,thisisComputingthegeometricmargin(thathastobemaximised):Andherearetheconstraints:最大間隔原則1/30/2021Chap8

SVM

Zhongzhi

Shi32wx+b=0wx+b=-1wx+b>1wx+b<1This

is

a

quadraticprogramming

problem

withlinear

inequality

constraiwx+b=1

There

are

well

knownMaximum

margin

–

summing

upGiven

a

linearly

separabletraining

set

(xi,

yi),i=1,2,…N;

yi

{+1,-1}Minimise

||w||2Subject

toprocedures

for

solving

it1/30/2021Chap8

SVM

Zhongzhi

Shi33支持向量The

training

pointsthat

are

nearest

to

theseparating

functionare

called

supportvectors.What

is

the

output

ofour

decision

functionfor

these

points?1/30/2021Chap8

SVM

Zhongzhi

Shi34分類問題的數(shù)學(xué)表示已知:訓(xùn)練集包含個(gè)樣本點(diǎn):說明: 是輸入指標(biāo)向量，或稱輸入，或稱模式，其分量稱為特征，或?qū)傩?，或輸入指?biāo)；是輸出指標(biāo)，或輸出.問題:對(duì)一個(gè)新的模式 ，推斷它所對(duì)應(yīng)的輸出 是1還是-1.實(shí)質(zhì):找到一個(gè)把 上的點(diǎn)分成兩部分的規(guī)則.2維空間上的分類問題) n維空間上的分類問題.1/30/2021Chap8

SVM

Zhongzhi

Shi35根據(jù)給定的訓(xùn)練集,尋找上的一個(gè)其中,實(shí)值函數(shù),用決策函數(shù)判斷任一模式 對(duì)應(yīng)的 值.可見,分類學(xué)習(xí)機(jī)——構(gòu)造決策函數(shù)的方法(算法),兩類分類問題線性分類學(xué)習(xí)機(jī)多類分類問題非線性分類學(xué)習(xí)機(jī)分類學(xué)習(xí)方法1/30/2021Chap8

SVM

Zhongzhi

Shi36分類學(xué)習(xí)方法SVM分類問題大致有三種:線性可分問題、近似線性可分問題、線性不可分問題。1/30/2021Chap8

SVM

Zhongzhi

Shi37考慮 上的線性可分的分類問題.這里有許多直線 能將兩類點(diǎn)正確分開.如何選取和？簡(jiǎn)單問題：設(shè)法方向 已選定，如何選取 ？解答：選定 平行直線 極端直線和取 和的中間線為分劃直線如何選取對(duì)應(yīng)一個(gè)？，有極端直線 ，稱和 之間的距離為“間隔”.顯然應(yīng)選使“間隔”最大的

。最大間隔法的直觀導(dǎo)出1/30/2021Chap8

SVM

Zhongzhi

Shi38數(shù)學(xué)語言描述調(diào)整 ,使得令,則兩式可以等價(jià)寫為與此相應(yīng)的分劃直線表達(dá)式:給定適當(dāng)?shù)姆ǚ较?/30/2021Chap8

SVM

Zhongzhi

Shi39后,這兩條極端直線可表示為如何計(jì)算分劃間隔？考慮2維空間中極端直線之間的間隔情況求出兩條極端直線的距離:1/30/2021Chap8

SVM

Zhongzhi

Shi40分劃直線表達(dá)式為“間隔”為的最優(yōu)化問,從而構(gòu)造分劃。說明:只要我們求得該問題的最優(yōu)解超平面 ，求出決策函數(shù)上述方法對(duì)一般 上的分類問題也適用.

極大化“間隔”的思想導(dǎo)致求解下列對(duì)變量

和題原始問題1/30/2021Chap8

SVM

Zhongzhi

Shi41Margin

=H1平面:H2平面:…..(2)1/30/2021Chap8

SVM

Zhongzhi

Shi42…..(1)求解原始問題為求解原始問題,根據(jù)最優(yōu)化理論,我們轉(zhuǎn)化為對(duì)偶問題來求解對(duì)偶問題為原始問題中與每個(gè)約束條件對(duì)應(yīng)的Lagrange乘子。這是一個(gè)不等式約束條件下的二次函數(shù)尋優(yōu)問題,存在唯一解1/30/2021Chap8

SVM

Zhongzhi

Shi43線性可分問題計(jì)算,選擇 的一個(gè)正分量 ,并據(jù)此計(jì)算事實(shí)上, 的每一個(gè)分量都與一個(gè)訓(xùn)練點(diǎn)相對(duì)應(yīng)。而分劃超平面僅僅依賴于 不為零的訓(xùn)練點(diǎn),而與對(duì)應(yīng)于 為零的那些訓(xùn)練點(diǎn)無關(guān)。稱 不為零的這些訓(xùn)練點(diǎn)的輸入

為支持向量(SV)構(gòu)造分劃超平面,決策函數(shù)根據(jù)最優(yōu)解1/30/2021Chap8

SVM

Zhongzhi

Shi44近似線性可分問題不要求所有訓(xùn)練點(diǎn)都滿足約束條件 ，為此對(duì)第 個(gè)訓(xùn)練點(diǎn) 引入松弛變量(SlackVariable) ,把約束條件放松到 。（即“軟化”約束條件體現(xiàn)了訓(xùn)練集被錯(cuò)分的情況，可采用 作為一種度量來描述錯(cuò)劃程度。兩個(gè)目標(biāo):1.間隔 盡可能大 2.錯(cuò)劃程度 盡可能小顯然，當(dāng) 充分大時(shí)，樣本點(diǎn) 總可以滿足以上約束條件。然而事實(shí)上應(yīng)避免 太大，所以需在目標(biāo)函數(shù)對(duì) 進(jìn)行懲罰1/30/2021Chap8

SVM

Zhongzhi

Shi45因此,引入一個(gè)懲罰參數(shù),新的目標(biāo)函數(shù)變?yōu)?體現(xiàn)了經(jīng)驗(yàn)風(fēng)險(xiǎn),而 則體現(xiàn)了表達(dá)能力。所以懲罰參數(shù) 實(shí)質(zhì)上是對(duì)經(jīng)驗(yàn)風(fēng)險(xiǎn)和表達(dá)能力匹配一個(gè)裁決。當(dāng) 時(shí),近似線性可分SVC的原始問題退化為線性可分SVC的原始問題。近似線性可分問題1/30/2021Chap8

SVM

Zhongzhi

Shi46(廣義)線性支持向量分類機(jī)算法1.設(shè)已知訓(xùn)練集 ,其中2.選擇適當(dāng)?shù)膽土P參數(shù),構(gòu)造并求解最優(yōu)化問題,選擇 的一個(gè)分量,并據(jù)此3.計(jì)算計(jì)算出4.構(gòu)造分劃超平面,決策函數(shù)求得1/30/2021Chap8

SVM

Zhongzhi

Shi47非線性分類例子:1/30/2021Chap8

SVM

Zhongzhi

Shi48Non-linear

ClassificationWhat

can

we

do

if

the

boundary

is

nonlinear

?Idea:1/30/2021Chap8

SVM

Zhongzhi

Shi49transform

the

data

vectors

to

aspace

where

the

separator

islinearNon-linear

ClassificationThe

transformation

many

times

is

made

to

an

infinitedimensional

space,

usually

a

function

space.Example:

x

cos(uTx)1/30/2021Chap8

SVM

Zhongzhi

Shi50Non-linear

SVMsTransform

x

(x)

The

linear

algorithm

depends

only

on

xxi,

hencetransformed

algorithm

depends

only

on

(x)

(xi

Use

kernel

function

K(xi,xj)

such

that

K(xi,xj)=(xi)1/30/2021Chap8

SVM

Zhongzhi

Shi51設(shè)訓(xùn)練集假定可以用，其中平面上的二次曲線來分劃:現(xiàn)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線映射為6維空間上的一個(gè)超平面:非線性分類1/30/2021Chap8

SVM

Zhongzhi

Shi52可見，只要利用變換，把所在的2維空間的兩類輸入點(diǎn)映射到所在的6維空間，然后在這個(gè)6維空間中，使用線性學(xué)習(xí)機(jī)求出分劃超平面:最后得出原空間中的二次曲線:1/30/2021Chap8

SVM

Zhongzhi

Shi53怎樣求6維空間中的分劃超平面？(線性支持向量分類機(jī))非線性分類需要求解的最優(yōu)化問題其中非線性分類1/30/2021Chap8

SVM

Zhongzhi

Shi54在求得最優(yōu)化問題的解 后,得到分劃超平面其中最后得到?jīng)Q策函數(shù)或1/30/2021Chap8

SVM

Zhongzhi

Shi55線性分劃－>非線性分劃代價(jià):2維空間內(nèi)積－>6維空間內(nèi)積非線性分類為此,引進(jìn)函數(shù)有比較(2)和(3),可以發(fā)現(xiàn)這是一個(gè)重要的等式,提示6維空間中的內(nèi)積可以通過計(jì)算 中2維空間中的內(nèi)積得到。非線性分類1/30/2021Chap8

SVM

Zhongzhi

Shi56實(shí)現(xiàn)非線性分類的思想給定訓(xùn)練集后,決策函數(shù)僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法,則可以考慮選擇其它形式的函數(shù) ,一旦選定了函數(shù),就可以求解最優(yōu)化問題1/30得/2021,C而hap決8SV策M(jìn)Zh函ongz數(shù)hiShi57決策函數(shù)其中實(shí)現(xiàn)非線性分類的思想1/30/2021Chap8

SVM

Zhongzhi

Shi58設(shè) 是 中的一個(gè)子集。稱定義在是核函數(shù)(正定核或核),如果存在著從空間 的映射上的函數(shù)到某一個(gè)使得其中表示中的內(nèi)積核函數(shù)(核或正定核)定義1/30/2021Chap8

SVM

Zhongzhi

Shi59目前研究最多的核函數(shù)主要有三類:多項(xiàng)式內(nèi)核得到q階多項(xiàng)式分類器徑向基函數(shù)內(nèi)核RBF每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量,它們及輸出權(quán)值由算法自動(dòng)確定Sigmoind內(nèi)核包含一個(gè)隱層的多層感知器,隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定1/30/2021Chap8

SVM

Zhongzhi

Shi60核函數(shù)的選擇多項(xiàng)式內(nèi)核

The

kind

of

kernel

represents

the

innerproduct

of

two

vector(point)

in

a

featurespace

of

dimension.For

example1/30/2021Chap8

SVM

Zhongzhi

Shi61傳統(tǒng)的利用二次型優(yōu)化技術(shù)解決對(duì)偶問題時(shí):需要計(jì)算存儲(chǔ)核函數(shù)矩陣。當(dāng)樣本點(diǎn)數(shù)較大時(shí)，需要很大的存儲(chǔ)空間。例如:當(dāng)樣本點(diǎn)超過4000時(shí)，存儲(chǔ)核函數(shù)矩陣就需要多達(dá)128兆內(nèi)存；SVM在二次型尋優(yōu)過程中要進(jìn)行大量的矩陣運(yùn)算，通常尋優(yōu)算法占用了算法時(shí)間的主要部分?！觯璄dgarOsuna(Cambridge,MA)等人在IEEENNSP’97發(fā)表了AnImprovedTrainingAlgorithmforSupportVectorMachines,提出了SVM的分解算法，即將原問題分解為若干個(gè)子問題，按照某種迭代策略，通過反復(fù)求解子問題，最終使得結(jié)果收斂于原問題的最優(yōu)解。1/30/2021Chap8

SVM

Zhongzhi

Shi62SVM尋優(yōu)算法根據(jù)子問題的劃分和迭代策略的不同，大致分為:1.塊算法(ChunkingAlgorithm):考慮去掉Lagrange乘子等于零的訓(xùn)練樣本不會(huì)影響原問題的解，采用一部分樣本構(gòu)成工作樣本集進(jìn)行訓(xùn)練，移除其中的非支持向量，并把訓(xùn)練結(jié)果對(duì)剩余樣本進(jìn)行檢驗(yàn)，將不符合KKT條件的樣本與本次結(jié)果的支持向量合并成為一個(gè)新的工作集。然后重新訓(xùn)練，如此重復(fù)獲得最優(yōu)結(jié)果。例如:基于這種思路的 算法。SVM尋優(yōu)算法1/30/2021Chap8

SVM

Zhongzhi

Shi63塊算法(ChunkingAlgorithm):SMO使用了塊與分解技術(shù)，而SMO算法則將分解算法思想推向極致，每次迭代僅優(yōu)化兩個(gè)點(diǎn)的最小子集，其威力在于兩個(gè)數(shù)據(jù)點(diǎn)的優(yōu)化問題可以獲得解析解，從而不需要將二次規(guī)劃優(yōu)化算法作為算法一部分。盡管需要更多的迭代才收斂，但每個(gè)迭代需要很少的操作，因此算法在整體上的速度有數(shù)量級(jí)的提高。另外，算法其他的特征是沒有矩陣操作，不需要在內(nèi)存中存儲(chǔ)核矩陣。1/30/2021Chap8

SVM

Zhongzhi

Shi64SVM尋優(yōu)算法SMO算法每次迭代時(shí),在可行的區(qū)域內(nèi)選擇兩點(diǎn),最大化目標(biāo)函數(shù),從而優(yōu)化兩個(gè)點(diǎn)的最小子集。無論何時(shí),當(dāng)一個(gè)乘子被更新時(shí),調(diào)整另一個(gè)乘子來保證線性約束條件成立,保證解不離開可行區(qū)域。每步SMO選擇兩個(gè)參數(shù)優(yōu)化,其他參數(shù)固定,可以獲得解析解。盡管需要更多的迭代才收斂,但每個(gè)迭代需要很少的操作,因此算法在整體上的速度有數(shù)量級(jí)的提高。另外,算法其他的特征是沒有矩陣操作,不需要在內(nèi)存中存儲(chǔ)核矩陣。1/30/2021Chap8

SVM

Zhongzhi

Shi65SVM尋優(yōu)算法SVM尋優(yōu)算法1/30/2021Chap8

SVM

Zhongzhi

Shi66類別名稱測(cè)試樣本數(shù)錯(cuò)誤分類數(shù)準(zhǔn)確度（%）政治146497.26軍事830100經(jīng)濟(jì)137397.81法律32293.75農(nóng)業(yè)106298.11體育90198.89衛(wèi)生34197.06工業(yè)87297.70科技111298.20交通40197.50生活91198.90宗教30100天氣24291.67合計(jì)9842197.87SMO算法核緩存算法SMO算法在每次迭代只選擇兩個(gè)樣本向量?jī)?yōu)化目標(biāo)函數(shù),不需要核矩陣。雖然沒有核矩陣操作,但仍需要計(jì)算被選向量和訓(xùn)練集中所有樣本向量的核函數(shù),計(jì)算次數(shù)為2n（n為訓(xùn)練集中的樣本數(shù)）。如果訓(xùn)練集中的樣本選取有誤,在噪聲比較多的情況下,收斂會(huì)很慢,迭代次數(shù)很多,則核函數(shù)的計(jì)算量也是非常可觀的,SMO算法的優(yōu)點(diǎn)就完成失去了。同時(shí),考慮到文本分類的文本向量一般維數(shù)比較大,核函數(shù)的計(jì)算將會(huì)非常耗時(shí),尤其在高價(jià)多項(xiàng)式核和高斯核等核函數(shù)的計(jì)算中表現(xiàn)更加明顯。1/30/2021Chap8

SVM

Zhongzhi

Shi67SVM尋優(yōu)算法SMO算法核緩存算法在內(nèi)存中為SMO算法核函數(shù)開辟n行m列的核矩陣空間。其中:n為訓(xùn)練集中的樣本數(shù)；m是為可調(diào)節(jié)參數(shù)，根據(jù)實(shí)際的內(nèi)存大小進(jìn)行調(diào)整，每列存放訓(xùn)練集中某個(gè)樣本向量與訓(xùn)練集中所有樣本向量的核函數(shù)計(jì)算結(jié)果列表。在核矩陣列頭生成m個(gè)節(jié)點(diǎn)的雙向循環(huán)鏈表隊(duì)列，每個(gè)節(jié)點(diǎn)指向核矩陣的列，通過雙向循環(huán)鏈表隊(duì)列實(shí)現(xiàn)核矩陣中的核函數(shù)列喚入喚出操作。同時(shí)，為了實(shí)現(xiàn)樣本向量的核函數(shù)列的快速查找，為每個(gè)訓(xùn)練樣本向量設(shè)計(jì)了快速索引列表，通過索引列表判斷該訓(xùn)練樣本向量的核函數(shù)列是否在核矩陣中，并確定在哪1/一30/2列021

。SVM尋優(yōu)算法Chap8

SVM

Zhongzhi

Shi

68SVM尋優(yōu)算法 選擇一個(gè)訓(xùn)練集，通過調(diào)整核緩沖參數(shù)的大小，記錄不同核緩存大小情況下訓(xùn)練時(shí)間，結(jié)果如下表:1核緩存大小(Mb)訓(xùn)練樣本數(shù)核矩陣迭代次數(shù)訓(xùn)練時(shí)間(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:564056245624*932407261:295056245624*1165407261:236056245624*1398407261:087056245624*1631407261:058056245624*1864407261:049056245624*2097407261:0710056245624*2330407261:37/2350/20215624

Chap5862S4V*M5Z6h2o4ngzhiS4h0i7261:12

69通過引入核緩存機(jī)制,有效的改進(jìn)了SMO算法,提高了文本分類的訓(xùn)練速度。在核緩存機(jī)制中采用簡(jiǎn)單的hash查找算法和隊(duì)列FILO算法,有效提高了核矩陣查找和喚入喚出操作的效率。設(shè)置核矩陣列參數(shù),通過調(diào)節(jié)列參數(shù),可以靈活的根據(jù)系統(tǒng)運(yùn)行情況調(diào)整訓(xùn)練的時(shí)間和空間開銷,避免因系統(tǒng)空間開銷過大使系統(tǒng)運(yùn)行效率下降,反而影響訓(xùn)練速度。1/30/2021Chap8

SVM

Zhongzhi

Shi70SVM尋優(yōu)算法活動(dòng)向量集選擇算法當(dāng)訓(xùn)練樣本數(shù)非常大的時(shí)候,如果系統(tǒng)能夠提供的核緩沖大小很有限,那么能夠同時(shí)保存在核緩沖中訓(xùn)練樣本的核函數(shù)數(shù)目在訓(xùn)練樣本數(shù)中所占比例將非常的小。在訓(xùn)練過程中,訓(xùn)練樣本在核緩沖中的核函數(shù)命中率將顯著下降,導(dǎo)致核緩沖中的核函數(shù)被頻繁的喚入喚出,而每執(zhí)行一次喚入喚出操作將引起系統(tǒng)重新計(jì)算訓(xùn)練樣本的核函數(shù),核緩存的作用被很大程度的削弱了。如果出現(xiàn)這樣的情況,要么增加系統(tǒng)的存儲(chǔ)空間；要么減少訓(xùn)練樣本數(shù),才能提高系統(tǒng)的訓(xùn)練速度。為解決訓(xùn)練樣本數(shù)多,系統(tǒng)內(nèi)存空間小的矛盾,本文通過活動(dòng)向量集選擇算法,比較好地解決了這個(gè)問題。1/30/2021Chap8

SVM

Zhongzhi

Shi71SVM尋優(yōu)算法活動(dòng)向量集選擇算法算法的主要思想是:定期檢查訓(xùn)練樣本集，在收斂前預(yù)先確定訓(xùn)練樣本集中一些邊界上的點(diǎn)（alpha=0，或者alpha=C）是否以后不再被啟發(fā)式選擇，或者不再被判定為最有可能違例，如果存在這樣的點(diǎn)，將它們從訓(xùn)練樣本集中剔除出去，減少參加訓(xùn)練的樣本數(shù)。該算法基于如下的認(rèn)識(shí):經(jīng)過多次迭代后，如果樣本的拉格朗日乘子一直為0該點(diǎn)被當(dāng)前估計(jì)的支持向量集所確定的超平面區(qū)分得很開，即使以后支持向量集發(fā)生變化，該點(diǎn)也不會(huì)是最靠近超平面的點(diǎn)，則可以確定該樣本不是支持向量；經(jīng)過多次迭代后，如果樣本的拉格朗日乘子一直為非常大的C常數(shù)，即使以后支持向量集發(fā)生變化，該點(diǎn)也不會(huì)遠(yuǎn)離超平面，則可以確定該樣本是上邊界處的支持向量1/30/2021Chap8

SVM

Zhongzhi

Shi72SVM尋優(yōu)算法活動(dòng)向量集選擇算法這樣就可以在SMO算法收斂前,提前將邊界上的點(diǎn)從訓(xùn)練樣本集中剔除,逐漸縮小參加訓(xùn)練的活動(dòng)樣本集,從而減少SMO算法對(duì)核緩存空間的要求,提高訓(xùn)練速度。訓(xùn)練開始前,訓(xùn)練活動(dòng)集樣本初始化為全部訓(xùn)練樣本。每經(jīng)過一定次數(shù)的迭代（比如迭代1000次）,如果算法還沒有收斂,應(yīng)檢查活動(dòng)集中的向量,檢查是否有訓(xùn)練樣本可以不參加迭代運(yùn)算。檢查完當(dāng)前活動(dòng)向量集中所有樣本后,產(chǎn)生了新的活動(dòng)向量集。如果新的活動(dòng)向量集的樣本數(shù)減少一成以上（含一成）,則可以收縮當(dāng)前活動(dòng)向量集,用新的活動(dòng)向量集替換當(dāng)前活動(dòng)向量集。當(dāng)活動(dòng)向量集的樣本數(shù)減少到一定的程度,對(duì)核緩存空間的要求不是很大的時(shí)候,繼續(xù)減少訓(xùn)練樣本對(duì)訓(xùn)練速度的提高就非常有限了,這時(shí)就沒有必要再1/3減0/20少21

訓(xùn)練樣本了。Chap8

SVM

Zhongzhi

ShiSVM尋優(yōu)算法73固定工作樣本集(Osunaetal.):將工作樣本集的大小固定在算法速度可以容忍的限度內(nèi)，迭代過程選擇一種合適的換入換出策略，將剩余樣本中的一部分與工作樣本集中的樣本進(jìn)行等量交換，即使支持向量的個(gè)數(shù)超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對(duì)支持向量中的一部分進(jìn)行優(yōu)化。例如: 算法SVM尋優(yōu)算法1/30/2021Chap8

SVM