Least Squares Support Vector

最小二乘支持向量机

LeastSquaresSupportVectorMachines

JohanSuykens

K.U.LeuvenESAT-SCD-SISTA

KasteelparkArenberg10

B-3001Leuven(Heverlee),Belgium

Tel:32/16/321802-Fax:32/16/321970

Email:johan.suykens@esat.kuleuven.ac.be

http://www.esat.kuleuven.ac.be/sista/members/suykens.htmlNATO-ASILearningTheoryandPracticeLeuvenJuly2002

http://www.esat.kuleuven.ac.be/sista/natoasi/ltp2002.html

最小二乘支持向量机

Mainreference:

J.A.K.Suykens,T.VanGestel,J.DeBrabanter,B.DeMoor,J.Vandewalle,LeastSquaresSupportVectorMa-chines,WorldScienti c,inpress(ISBN981-238-151-1)

RelatedsoftwareLS-SVMlab(Matlab/Ctoolbox):

http://www.esat.kuleuven.ac.be/sista/lssvmlab/

(software+publications)

...withthankstoKristiaanPelckmans,BartHamers,Lukas,LucHoe-gaerts,ChuanLu,LievekeAmeye,SabineVanHu el,GertLanckriet,TijlDeBieandmanyothers

最小二乘支持向量机

Interdisciplinarychallenges

LS-SVMmathematics

Oneoftheoriginaldreamsintheneuralnetworksareaistomakeauniversalclassofmodels(suchasMLPs)generallyapplicabletoawiderangeofapplications.

Presently,standardSVMsaremainlyavailableonlyforclassi ca-tion,functionestimationanddensityestimation.However,severalextensionsarepossibleintermsofleastsquaresandequalitycon-straints(andexploitingprimal-dualinterpretations).

最小二乘支持向量机

Overviewofthistalk

LS-SVMforclassi cationandlinkwithkernelFisherdiscrimi-nantanalysis

LinkstoregularizationnetworksandGaussianprocesses BayesianinferenceforLS-SVMs

Sparsenessandrobustness

Largescalemethods:FixedSizeLS-SVM

Extensionstocommitteenetworks

NewformulationstokernelPCA,kernelCCA,kernelPLS ExtensionsofLS-SVMtorecurrentnetworksandoptimalcon-trol

最小二乘支持向量机

Vapnik’sSVMclassi er

Givenatrainingset{xk,yk}Nk=1Inputpatternsxk∈Rn

Classlabelsyk∈Rwhereyk∈{ 1,+1}

Classi er:y(x)=sign[wT (x)+b]

with (·):Rn→Rnhmappingtohighdimensionalfeaturespace(canbein nitedimensional)

Forseparabledata,assume Tw (xk)+b≥+1,

wT (xk)+b≤ 1,

whichisequivalenttoifyk=+1ifyk= 1

yk[wT (xk)+b]≥1,k=1,...,N

Optimizationproblem(non-separablecase):

1TminJ(w,ξ)=ww+cw,ξ2

subjectto N k=1ξk

yk[wT (xk)+b]≥1 ξk,k=1,...,N

ξk≥0,k=1,...,N.

最小二乘支持向量机

ConstructLagrangian:

L(w,b,ξ;α,ν)=J(w,ξk)

SolutiongivenbysaddlepointofLagrangian:maxminL(w,b,ξ;α,ν)α,νw,b,ξ

N k=1withLagrangemultipliersαk≥0,νk≥0(k=1,...,N).N k=1αk{yk[wT (xk)+b] 1+ξk} N k=1νkξkOneobtains =0→w=N k=1αkyk (xk) L=0→αkyk=0

k=0→0≤αk≤c,k=1,...,N

Quadraticprogrammingproblem(Dualproblem):

k,l=1

suchthatNN 1maxQ(α)= ykylK(xk,xl)αkαl+αkαk2k=1 N αkyk=0 k=1

0≤αk≤c,k=1,...,N.

最小二乘支持向量机

Note:wand (xk)arenotcalculated.

Mercercondition:K(xk,xl)= (xk)T (xl)

N k=1 Obtainedclassi er:y(x)=sign[αkykK(x,xk)+b]

withαkpositiverealconstants,brealconstant,thatfollowassolutiontotheQPproblem.

Non-zeroαkarecalledsupportvaluesandthecorrespondingdatapointsarecalledsupportvectors.

ThebiastermbfollowsfromKKTconditions.

SomepossiblekernelsK(·,·):

K(x,xk)=xTkx(linearSVM)

dx+1)(polynomialSVMofdegreed)K(x,xk)=(xTk

2K(x,xk)=exp{ x xk 2/σ}(RBFSVM)2

K(x,xk)=tanh(κxTkx+θ)(MLPSVM)

InthecaseofRBFandMLPkernel,thenumberofhiddenunitscorrespondstothenumberofsupportvectors.

最小二乘支持向量机

Featurespaceandkerneltrick

Featurespace

=

K(x,z) (x)T

(z

最小二乘支持向量机

Primal-dualinterpretationsofSVMs

#sv

最小二乘支持向量机

LeastSquaresSVMclassi ers

LS-SVMclassi ers(Suykens,1999):closetoVapnik’sSVMformulationbutsolveslinearsysteminsteadofQPproblem. Optimizationproblem:

1TminJ(w,b,e)=ww+γw,b,e22

subjecttotheequalityconstraintsN 1k=1e2k

yk[wT (xk)+b]=1 ek,k=1,...,N.

Lagrangian

L(w,b,e;α)=J(w,b,e)

whereαkareLagrangemultipliers.

Conditionsforoptimality: N L αkyk (xk)=0→w= k=1 N αkyk=0=0→ k=1 =0→αk=γek,k=1,...,N k =0→y[wT (x)+b] 1+e=0,k=1,...,NkkkkN k=1αk{yk[wT (xk)+b] 1+ek}

最小二乘支持向量机

Setoflinearequations(insteadofQP): 0I00 ZTw 000 YT b 0 = I e 0 00γIZYI0α1

with

Z=[ (x1)Ty1;...; (xN)TyN]

Y=[y1;...;yN] 1=[1;...;1]

e=[e1;...;eN]

α=[α1;...;αN].

Aftereliminationofw,eoneobtains T00Yb=.Y +γIα1

where

=ZZT

andMercer’sconditionisapplied

kl=ykyl (xk)T (xl)

=ykylK(xk,xl).

Relatedwork:Saunders(1998),Smola&Sch¨olkopf(1998),Cristianini&Taylor(2000)

最小二乘支持向量机

LargescaleLS-SVMs

Forthebinaryclasscase:probleminvolvesmatrixofsize(N+1)×(N+1).

Largedatasets→iterativemethodsneeded(CG,SOR,...) Problem:solving

Ax=BA∈Rn×n,B∈Rn

byCGrequiresthatAissymmetricpositivede nite. Representtheoriginal 0problemYT ξof1 theform d1

YHξ2=d2

withH = +γ 1I,ξ1=b,ξ2=α,d1=0,d2

s0 ξ1 = 1as d1+YTH 1d2

0Hξ2+H 1Yξ1=d2

withs=YTH 1Y>0(H=HT>0).

Iterativemethodscanbeappliedtothelatterproblem. Convergence(henceitdependsofCGondependsγ,σ)onconditionnumber

最小二乘支持向量机

FisherDiscriminantAnalysis Projectionofdata:

z=f(x)=wTx+b

OptimizeRayleighquotient:wTΣwmaxJFD(w,b)=Tw,bwΣW

w

最小二乘支持向量机

最小二乘支持向量机

Atwospiralclassi cationproblem

Di cultproblemforMLPs,notforSVMorLS-SVMwithRBFkernel(buteasyinthesensethatthetwoclassesareseparable)

最小二乘支持向量机

Benchm …… 此处隐藏：3214字，全部文档内容请下载后查看。喜欢就下载吧 ……