FAFU机器学习08-1 Support Vector Machine课件VIP

FoundationsofMachineLearning

SupportVectorMachine（支持向量机）Top10algorithmsindataminingC4.5K-MeansSVMAprioriEM(MaximumLikelihood)PageRankAdaBoostKNNNaïveBayesCARTSupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-3BackgroundTheoriginalSVMalgorithmwasinventedby

VladimirN.Vapnik

and

AlexeyYa.Chervonenkis

in1963MaximalMarginClassifierIn1992,

BernhardE.Boser,

IsabelleM.GuyonandVladimirN.Vapniksuggestedawaytocreatenonlinearclassifiersbyapplyingthe

kerneltrick

tomaximum-marginhyperplanes.ThekernelizedversionusingtheKernelTrickThecurrentstandardincarnation(softmargin)wasproposedby

CorinnaCortes

andVapnikin1993andpublishedin1995.SoftMarginClassifierThesoft-marginkernelizedversion(whichcombine1,2and3)2023/11/4SupportVectorMachineLesson7-4BackgroundIn1996,Vapniketal.proposedaversionofSVMtoperformregressioninsteadofclassification.

SupportVectorRegression(SVR)In

machinelearning,

supportvectormachines

(SVMs,also

supportvectornetworks)are

supervisedlearning

modelswithassociatedlearning

algorithms

thatanalyzedatausedfor

classification

and

regressionanalysis.However,

itismostlyused

in

classificationproblems.SVMbecomespopularbecauseofitssuccessinhandwrittendigitrecognition2023/11/4SupportVectorMachineLesson7-5ProsKernel-basedframeworkisverypowerful,flexibleWorkverywellinpractice,evenwithverysmalltrainingsamplesizesSolutioncanbeformulatedasaquadraticprogrammingManypubliclyavailableSVMpackages:e.g.LIBSVM,LIBLINEAR,SVMLightConsCanbetrickytoselectbestkernelfunctionforaproblemComputation,memoryAttrainingtime,mustcomputekernelvaluesforallexamplepairsLearningcantakeaverylongtimeforlarge-scaleproblems2023/11/4SupportVectorMachineLesson7-6SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-7间隔与支持向量

2023/11/4SupportVectorMachineLesson7-8Whichisthebest?间隔与支持向量给定训练样本集D={(X1,Y1)，(X2

，Y2),...,(Xm,Ym)},Yi属于{-1，+1}，分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开.2023/11/4SupportVectorMachineLesson7-9Whichisthebest?间隔与支持向量给定训练样本集D={(X1,Y1)，(X2

，Y2),...,(Xm,Ym)},Yi属于{-1，+1}，分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面、将不同类别的样本分开.在样本空间中，划分超平面可通过如下线性方程来描述:样本空

间中任意点x

到超平面间的的距离可写为：2023/11/4SupportVectorMachineLesson7-10间隔与支持向量假设超平面(w,b)能将训练样本正确分类，即对于(xi,yi)inD,若yi=+1,则有wTxi+b>0;若yi=-1,则有wTxi+b<0.令：支持向量：使上式等号成立的训练样本点。间隔：两个异类支持向量到超平面的距离之和。2023/11/4SupportVectorMachineLesson7-11间隔与支持向量欲找到具有“最大间隔”(maximummargin)的划分超平面，也就是要找到能满足约束的参数w

和b

，使得

γ最大，即：为了最大化间隔，

仅需最大化||w||-1，这等价于最小化||w||2.于是:2023/11/4SupportVectorMachineLesson7-12SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-13对偶问题MaximizethemarginItisaconvexquadraticprogramming(QP)optimizationproblem.ConvexQPproblemshaveconvexobjectivefunctions.Theseproblemscanbesolvedeasilyandefficientlybygreedyalgorithms(becauseeverylocalminimumisaglobalminimum).Butwehavemoreeffectivemethodtosolveit.2023/11/4SupportVectorMachineLesson7-14对偶问题Maximizethemargin拉格朗日乘子法,定义拉格朗日函数:令L(w，b，α)对w

和b

的偏导为零可得:2023/11/4SupportVectorMachineLesson7-15对偶问题Maximizethemargin拉格朗日乘子法,定义拉格朗日函数:将L(ω

，b，α)中的ω

和b

消去，可得对偶问题:2023/11/4SupportVectorMachineLesson7-16解出α

后，求出ω

与b

即可得到模型：2023/11/4SupportVectorMachineLesson7-17SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-18核函数在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面，比如：2023/11/4SupportVectorMachineLesson7-19将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分.核函数令Φ(x)表示将x

映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为：2023/11/4SupportVectorMachineLesson7-20核函数令Φ(x)表示将x映射后的特征向量，对偶问题：由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算Φ(xi)TΦ(xj)通常是困难的.为了避开这个障碍，可以设想这样一个函数:2023/11/4SupportVectorMachineLesson7-21核函数由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算Φ(xi)TΦ(xj)通常是困难的.为了避开这个障碍，可以设想这样一个函数:对偶问题可重写为：2023/11/4SupportVectorMachineLesson7-22核函数由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算Φ(xi)TΦ(xj)通常是困难的.为了避开这个障碍，可以设想这样一个函数:重写对偶问题求解对偶问题后即可得到2023/11/4SupportVectorMachineLesson7-23核函数核函数定理2023/11/4SupportVectorMachineLesson7-24核函数常用核函数2023/11/4SupportVectorMachineLesson7-25核函数常用核函数通过函数组合得到核函数若κ1和κ2为核函数，则对于任意正数ϒ1、ϒ2，其线性组合ϒ1*κ1+ϒ2*κ2也是核函数;若κ1和κ2为核函数，则核函数的直积κ1⊕κ2(x,z)=κ1(x,z)κ2(x,z)也是核函数；若κ1和κ2为核函数，则对于任意函数g(x)，κ(x,z)=g(x)κ1(x,z)g(z)也是核函数；2023/11/4SupportVectorMachineLesson7-26SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-27软间隔与正则化在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的?即存在一个超平面能将不同类的样本完全划分开.然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分;退一步说，即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的.缓解该问题的一个办法是允许支持向量机在一些样本上出错.为此，要引入“软间隔”(Softmargin)的概念.2023/11/4SupportVectorMachineLesson7-28软间隔与正则化“软间隔”(Softmargin)示意图.软间隔允许某些样本不满足约束2023/11/4SupportVectorMachineLesson7-29软间隔与正则化软间隔允许某些样本不满足约束,当然，在最大化间隔的同时，不满足约束的样本应尽可能少.于是，优化目标可写为:2023/11/4SupportVectorMachineLesson7-30软间隔与正则化然而，l0/1非凸、非连续，数学性质不太好,于是，人们通常用其他一些函数来代替l0/1，称为“替代损失”(surrogateloss).替代损失函数一般具有较好的数学性质，如它们通常是凸的连续函数且是l0/1的上界.三种常用的替代损失函数:2023/11/4SupportVectorMachineLesson7-31软间隔与正则化然而，l0/1非凸、非连续，数学性质不太好采用hinge损失失函数:引入"松弛变量"(slackvariables)ξi>=0这就是常用的"软间隔支持向量机"2023/11/4SupportVectorMachineLesson7-32软间隔与正则化然而，l0/1非凸、非连续，数学性质不太好我们还可以把0/1损失函数换成别的替代损失函数以得到其他学习模型，这些模型的性质与所用的替代函数直接相关，但它们具有一个共性:优化目标中的第一项用来描述划分超平面的“间隔”大小，另一项

用来表述训练集上的误差，可写为更一般的形式：结构风险：用于描述模型f的某些性质经验风险：用于描述模型与训练数据的契合程度C用于对二者进行折中可以把上式看着是“正则化”(regularization)问题，Ω(f)称为正则化项，C则称为正则化常数.2023/11/4SupportVectorMachineLesson7-33SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-34支持向量回归给定训练样本集D={(x1,y1)，(x2，y2),...,(xm,ym)},yi属于实数，希望学得一个形如式下式的回归模型，使得f(x)与y尽可能接近，ω和b是待确定的模型参数.对样本(x，y)，传统回归模型通常直接基于模型输出f(x)与真实输出y之间的差别来计算损失，当且仅当f(x)与y完全相同时，损失才为零.与此不同，支持向量回归(SupportVectorRegression，简称SVR)假设我们能容忍f(x)与y之间最多有ϵ的偏差，即仅当f(x)与y之间的差别绝对值大于ϵ

时才计算损失.这相当于以f(x)为中心构建了一个宽度为2ϵ的间隔带，若训练样本落入此间隔带，则认为是被预测正确的.2023/11/4SupportVectorMachineLesson7-35支持向量回归以f(x)为中心构建了一个宽度为2

ϵ的间隔带，若训练样本落入此间隔带，则认为是被预测正确的.2023/11/4SupportVectorMachineLesson7-36支持向量回归以f(x)为中心构建了一个宽度为2ϵ的间隔带，若训练样本落入此间隔带，则认为是被预测正确的.于是，SVR问题可形式化为:其中C为正则化常数，lϵ

为损失函数2023/11/4SupportVectorMachineLesson7-37SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-38SVMinsklearn2023/11/4SupportVectorMachineLesson7-39svm.LinearSVC([penalty,

loss,

dual,

tol,

C,

…])LinearSupportVectorClassification.svm.LinearSVR(*[,

epsilon,

tol,

C,

loss,

…])LinearSupportVectorRegression.svm.NuSVC(*[,

nu,

kernel,

degree,

gamma,

…])Nu-SupportVectorClassification.svm.NuSVR(*[,

nu,

C,

kernel,

degree,

gamma,

…])NuSupportVectorRegression.svm.OneClassSVM(*[,

kernel,

degree,

gamma,

…])UnsupervisedOutlierDetection.svm.SVC(*[,

C,

kernel,

degree,

gamma,

…])C-SupportVectorClassification.svm.SVR(*[,

kernel,

degree,

gamma,

coef0,

…])Epsilon-SupportVectorRegression.SVMinsklearn/stable/modules/svm.html#svm-classificationSVC,

NuSVC

and

LinearSVC

areclassescapableofperformingmulti-classclassificationonadataset.SVC

and

NuSVC

aresimilarmethods,butacceptslightlydifferentsetsofparametersandhavedifferentmathematicalformulations.Ontheotherhand,LinearSVCisanotherimplementationofSupportVectorClassificationforthecaseofalinearkernel.Notethat

LinearSVC

doesnotacceptkeyword

kernel,asthisisassumedtobelinear2023/11/4SupportVectorMachineLesson7-40SVMinsklearnclass

sklearn.svm.SVC(C=1.0,

kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

shrinking=True,

probability=False,

tol=0.001,

cache_size=200,

class_weight=None,

verbose=False,

max_iter=-1,

decision_function_shape=’ovr’,

random_state=None)2023/11/4SupportVectorMachineLesson7-41>>>import

numpy

as

np

>>>X=np.array([[-1,-1],[-2,-1],[1,1],[2,1]])>>>y=np.array([1,1,2,2])>>>from

sklearn.svm

importSVC>>>clf=SVC(gamma='auto')>>>clf.fit(X,y)#SVC(C=1.0,cache_size=200,class_weight=None,coef0=0.0,decision_function_shape='ovr',degree=3,gamma='auto',kernel='rbf',max_iter=-1,probability=False,random_state=None,shrinking=True,tol=0.001,verbose=False)>>>print(clf.predict([[-0.8,-1]]))2023/11/4SupportVectorMachineLesson7-42SVMinsklearnclass

sklearn.svm.NuSVC(nu=0.5,

kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

shrinking=True,

probability=False,

tol=0.001,

cache_size=200,

class_weight=None,

verbose=False,

max_iter=-1,

decision_function_shape=’ovr’,

random_state=None)Parameternu

:

float,optional(default=0.5)Anupperboundonthefractionoftrainingerrorsandalowerboundofthefractionofsupportvectors.Shouldbeintheinterval(0,1].2023/11/4SupportVectorMachineLesson7-43SVMinsklearnclass

sklearn.svm.LinearSVC(penalty=’l2’,

loss=’squared_hinge’,

dual=True,

tol=0.0001,

C=1.0,

multi_class=’ovr’,

fit_intercept=True,

intercept_scaling=1,

class_weight=None,

verbose=0,

random_state=None,

max_iter=1000)SimilartoSVCwithparameterkernel=’linear’,butimplementedintermsofliblinearratherthanlibsvm,soithasmoreflexibilityinthechoiceofpenaltiesandlossfunctionsandshouldscalebettertolargenumbersofsamples.Thisclasssupportsbothdenseandsparseinputandthemulticlasssupportishandledaccordingtoaone-vs-the-restscheme.2023/11/4SupportVectorMachineLesson7-44SVMinsklearnclass

sklearn.svm.SVR(kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

tol=0.001,

C=1.0,

epsilon=0.1,

shrinking=True,

cache_size=200,

verbose=False,

max_iter=-1)Epsilon-SupportVectorRegressionTheimplementationisbasedonlibsvm.2023/11/4SupportVectorMachineLesson7-45SVMinsklearnclass

sklearn.svm.NuSVR(nu=0.5,

C=1.0,

kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

shrinking=True,

tol=0.001,

cache_size=200,

verbose=False,

max_iter=-1)NuSupportVectorRegression.SimilartoNuSVC,forregression,usesaparameternutocontrolthenumberofsupportvectors.However,unlikeNuSVC,wherenureplacesC,herenureplacestheparameterepsilonofepsilon-SVR.Theimplementationisbasedon