李航《统计学习方法》第七章支持向量机习题答案

李航《统计学习⽅法》第七章⽀持向量机习题答案1.⽐较感知机的对偶形式和线性可分⽀持向量机的对偶性形式。感知机原始形式：∑minϵM(y(w⋅x+b))iw,bL(w,b)=−xiiM为误分点的集合。等价于N∑minw,bL(w,b)=i=1(−y(w⋅x+b))+ii对偶形式：w,b表⽰为x,y的线性组合的形式，求其系数（线性组合的系数）w=∑i=1αyx,b=∑NNαyi=1iiiiiiiN∑N∑N∑minminαw,bL(w,b)=L(α)=i=1(−y(j=1αjyxjj⋅x+j=1αjyj))+iiii线性可分⽀持向量机原始问题：1minw,b2∥w∥2s.t.y(w⋅x+b)−1≥0ii线性可分⽀持向量机对偶问题：NN∑∑N∑1minαααyyj(x⋅xj)−i=1αi2i=1j=1jiiiN∑s.t.i=1αy=0ii0≤α≤C,i=1,2,⋯,Ni∑i=1αjx∗=yj−iii,b∑i=1α(x⋅)N∗N∗最终w∗,b∗可以按照下⼠求出，w∗=xj。可以看出w,b实质也是将其表⽰为xi,xj的线性组合形式。ii2.已知正例点x1=(1,2)T,x2=(2,3)T,x3=(3,3)T，负例点x4=(2,1)T,x5=(3,2)T,试求最⼤间隔分离超平⾯和分类决策函数，并在图上画出分离超平⾯，间隔边界以及⽀持向量。

⼿动计算：根据题意，得到⽬标函数即约束条件122min2∥w+w∥12s.t.w1+2w2+b≥12w+3w+b≥1(1)(2)123w+3w+b≥112(3)−2w−w−b≥112(4)−3w−2w−b≥112(5)以w1.w2为坐标轴找到可⾏域，⽬标函数即求到原点距离最⼩的点，也就是w=[−1,2],对于正例点b≥−2，对于负例点b≤−2，所以b=−2。python实验验证：fromsklearnimportsvmx=[[1,2],[2,3],[3,3],[2,1],[3,2]]y=[1,1,1,-1,-1]clf=svm.SVC(kernel='linear',C=10000)clf.fit(x,)yprint(clf.coef_)print(ercept_)画图importmatplotlib.pyplotaspltimportnumpyasnpplt.scatter([i[0]foriinx],[i[1]foriinx],c=y)xaxis=np.linspace(0,3.5)w=clf.coef_[0]a=-w[0]/w[1]y_sep=a*xaxis-(ercept_[0])/w[1]b=clf.support_vectors_yy_down=a*xaxis+(b[1]-a*[b0])b=clf.support_vectors_[0][-1]yy_up=a*xaxis+(b[1]-a*[b0])plt.plot(xaxis,y_sep,'k-')plt.plot(xaxis,yy_down,'k--')plt.plot(xaxis,yy_up,'k--').scatter(clf.show()plt.support_vectors_[:,0],clf.support_vectors_[:,1],s=150,facecolors='none',edgecolors='k')plt3.线性⽀持向量机还可以定义为以下形式：∑N1minw,b,ξξ22∥w∥2+Ci=1is.t.y(w⋅x+b)≥1−ξ,i=1,2,⋯,Niiiξ≥0,i=1,2,⋯,Ni试求其对偶形式。ξμi根据⽀持向量机的对偶算法得到对偶形式，由于不能消去变量i的部分，所以拉格朗⽇因⼦也包含。4证明内积的正整数幂函数K(x,z)=(x⋅z)pp是正定核函数，这⾥是正整数，x,z∈Rn。根据书中内容需要证明K(X,Z)对应的Gram矩阵K=[K(x,xj)]m×n是半正定矩阵。i对任意的c1,c2,⋯,c∈R,有mm∑m∑i,j=1ccjK(x,xj)=i,j=1ccji(x⋅xj)piiim∑m∑=(i=1cx)(j=1cjxj)(x⋅xj)p−1iiim∑=∥(i=1c