【机器学习】支持向量机(SVM)——硬间隔+对偶+KKT条件+拉格朗日乘子(理论+图解+公式推导)

简介: 【机器学习】支持向量机(SVM)——硬间隔+对偶+KKT条件+拉格朗日乘子(理论+图解+公式推导)

2021人工智能领域新星创作者,带你从入门到精通,该博客每天更新,逐渐完善机器学习各个知识体系的文章,帮助大家更高效学习。


一、概述

本篇文章将讲解机器学习中的一个非常强的算法——支持向量机(SVM),一听到它的名字就会感到这个算法非常的厉害,确实是这样,在神经网络还没有发展起来的一段时间,它确实称霸了很久,而且也具有较高的能力。

支持向量机最开始是一个简单的二分类模型,后面不断发展引入了核函数、非线性因子等将其精度变得更加精准,能够适应更加复杂的数据。

它的算法原理就是,假设我们的数据样本分布在二维平面,有两个分类,支持向量机的做法就是要找到一条直线可以将所有的样本进行区分,这里假设线性可分,如果不可分需要引入核函数,之后的文章会进行讲解,本篇侧重讲解线性可分的二分类数据。

我们可以看到上面的图片,存在3条直线可以将我们的样本进行区分,但是我们可以发现A线是最好的,为什么?因为A线的鲁棒性最好,什么是鲁棒性?你可以理解为模型的牛逼程度,如果鲁棒性越强,模型越健壮,抗烦扰能力越强,如果此时有一个新的样本点在靠近C线或者B线的边缘,模型很有可能会将其进行误分类,而A却能很好的进行区分,因为A线对于所有的样本点的距离都很远,误分类的几率很低,这个分类边界有个很响亮的名字叫做最大间隔分类超平面。

这个平面有两条性质:

  • 能够将两个类别的数据分到平面两端
  • 距离两个类别样本最近的样本最远

其中图中最边缘的两条直线包含了距离分类平面最近的样本,它们被称作支持向量,而我们的目的是要使两条直线之间的距离最大。

这里解释一下,可能很多地方讲的最大化距离不太一样,有的是最大化上面两条直线之间的距离,有的是最大化所有样本到超平面的距离,还有的是最大化所有样本到分类界面的距离当中最小的距离。

其实没有关系,上面只是不同角度理解,不会影响结果的,从不同的角度引出待优化的目标,最终经过转换都是会转化成同一个优化函数的。

二、相关概念

1.超平面

所谓的超平面就是我们的决策边界,能够将我们数据进行区分的一个面,如果在二维是一条直线,三维是一个平面,在高维中可能是别的维度空间的一种形状,所以叫做超平面,总是n-1个维度。

这里假设还是以二维平面进行讲解,假设我们的超平面为 w T x + b = 0 w^Tx+b=0wTx+b=0 ,其中 w ww 为平面的法向量,例如:w 1 x 1 + w 2 x 2 + b = 0 w_1x_1+w_2x_2+b=0w1x1+w2x2+b=0 ,其中的 w 1 , w 2 w_1,w_2w1,w2 就为该平面的法向量,b为平面的偏移量,至于为什么另外两条直线为 w T x + b = 1 ( − 1 ) w^Tx+b=1(-1)wTx+b=1(1) ,我们下面会讲。

因为是二分类问题,假设两个分类为 − 1 , 1 {-1,1}11 ,如果样本处于左上方就是+1类,与之对应-1类,这也就对应着:

w T x + b ≥ 1 , y = + 1 w^Tx+b\geq1,y=+1wTx+b1,y=+1

w T x + b ≤ 1 , y = − 1 w^Tx+b\leq1,y=-1wTx+b1,y=1

然而这两个式子我们可以将其进行合并,成为 :y ( w T x + b ) ≥ 1 y(w^Tx+b)\geq 1y(wTx+b)1

2.优化目标

我们引出优化函数的方式有三种,分别进行讲解

2.1方法一

我们上面说到了为了要使两条直线间的间隔最大,即我们的优化目标为:m a x 2 ∣ ∣ w ∣ ∣ max \frac{2}{||w||}maxw2 ,这可以用空间直线与直线之间的距离公式得出,所以现在就是:

m a x w , b 2 ∣ ∣ w ∣ ∣ max_{w,b} \frac{2}{||w||}maxw,bw2

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m)s.t.yi(wTxi+b)1,(i=1,2,...m)

第一个式子是我们需要最大化的距离,第二个是需要满足的条件约束,就是要满足将所有样本正确分类的情况下求得使距离最大的w。

因为一般情况下,我们都是算最小化,所以需要将max进行转化,求它的最大值就是求分母的最小值,我们就是要分母最小,这时我们的优化函数就变成了:

m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 min_{w,b}\frac{1}{2}||w||^2minw,b21w2

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m)s.t.yi(wTxi+b)1,(i=1,2,...m)

我们可以看到从原来的L2范数直接加了平方,其实这是等价的,两个方程通解,加入1/2 的目的就是为了使之后的求导方便,直接消去2。

2.2 方法二

其实支持向量机是一种最大间隔分类器,意思就是要使我们所有样本到超平面的距离的最小值最大化,什么意思?就是每个样本到超平面都会有一个距离,肯定存在一个样本到该平面的距离最小,如果我们使得这个最小距离最大化的化,那么其它样本的距离也是会变大的,我们就是要最小的变大,从而使整体变大,那么我们就会引入一个式子:

m a r g i n ( w , b ) = m i n d i s t a n c e ( w , b , x i ) margin(w,b)=min\quad distance(w,b,x_i)margin(w,b)=mindistance(w,b,xi)

m i n 1 ∣ ∣ w ∣ ∣ ∣ w T x i + b ∣ min\frac{1}{||w||}|w^Tx_i+b|minw1wTxi+b

这个公式很容易理解,就是每个样本到超平面的距离。

那么我们的优化函数就变成了:

m a x m i n 1 ∣ ∣ w ∣ ∣ ∣ w T x i + b ∣ = m a x 1 ∣ ∣ w ∣ ∣ m i n ∣ w T x i + b ∣ max\quad min\frac{1}{||w||}|w^Tx_i+b|=max\frac{1}{||w||}min|w^Tx_i+b|maxminw1wTxi+b=maxw1minwTxi+b

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m)s.t.yi(wTxi+b)1,(i=1,2,...m)

那么根据第二个式子,我们可以得到 m i n   y i ( w T x i + b ) = 1 min\ y_i(w^Tx_i+b)=1minyi(wTxi+b)=1,由于第一个式子看起来较为复杂,尝试化简一下,首先要将绝对值去掉,怎么去呢?我们知道 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\geq1yi(wTxi+b)1,所以可以将 ∣ w T x i + b ∣ |w^Tx_i+b|wTxi+b 乘上个 y i y_iyi 将绝对值去掉,因为 y i y_iyi 的绝对值为1,不会造成影响,所以结果为 m i n   y i ( w T x i + b ) min\ y_i(w^Tx_i+b)minyi(wTxi+b),我们刚刚从第二个式子得到个结论就是该值的最小值为1,带入,那么第一个优化函数就变成了 m a x 1 ∣ ∣ w ∣ ∣ max\frac{1}{||w||}maxw1 ,这就和上面的一样,只不过上面的分子是2,这个是1,其实没有关系,我们注重的是分母,仍根据上面所说想要整体最大,则分母最小,那么优化函数仍为:

m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 min_{w,b}\frac{1}{2}||w||^2minw,b21w2

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m)s.t.yi(wTxi+b)1,(i=1,2,...m)

2.3 方法三

其实方法三和上面两种差不多,这里就不细致讲解了,感兴趣可以看看李航的统计学习那本书,我就简单说说。

它的原理就是我们同样和方法二要最大化每个样本到超平面的距离,但是服从的条件是我们所有的数据样本到该超平面的数据都大于我们要求的最大距离,就是说它保持所有样本到超平面的距离都大于我们要求的距离,这其实和方法二等价,即最大化最小的距离,方法三也是这样,每个样本距离都大于它,那么就说明我们优化的是所有样本中距离最小的,这里有个不一样的地方,就是引入了函数距离和几何距离,这里就不细讲了。

三、算法流程

整个算法流程为:

  • 获取优化目标函数
  • 将目标函数与约束条件结合进行拉格朗日乘子法
  • 强对偶性,转化求解问题
  • 二次规划求解 λ \lambdaλ
  • 获取最优解 w ∗ , b ∗ w^*,b^*w,b

1.获取优化函数

我们需要优化的函数就是上面推导出的,如果单是对第一个式子进行优化很容易求导,梯度下降,但是对于本问题来说,求解第一个式子的时候,会有m个约束条件,显然不能够直接进行计算,所以需要下面的几步进行转化成我们可以求解的目标函数,第一步就是要能不能将整个带有约束条件的函数转化为无约束的呢?肯定是能,这就引出了拉格朗日乘子法。

m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 min_{w,b}\frac{1}{2}||w||^2minw,b21w2

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m)s.t.yi(wTxi+b)1,(i=1,2,...m)

2.拉格朗日乘子法

我们高数中学过拉格朗日乘法,就是有一个函数 f ( x ) f(x)f(x),要求其极值我们可以直接进行求导,如果存在一定条件就要使用拉格朗日乘法,引入乘子变成 L = f ( x ) + λ g ( x ) L=f(x)+\lambda g(x)L=f(x)+λg(x),其中的 g ( x ) g(x)g(x) 就为约束条件,但是这只是针对等式约束条件,而上面我们遇到的是不等式约束条件,那么怎么弄呢?

这就引出了松弛变量这个概念, 松弛变量的引入常常是为了便于在更大的可行域内求解。我们可以尝试引入松弛变量将上面的不等式变成等式,具体怎么做?看!另:

m i n f ( w ) = m i n 1 2 ∣ ∣ w ∣ ∣ 2 minf(w)=min\frac{1}{2}||w||^2minf(w)=min21w2

g i ( w ) = 1 − y i ( w T x i + b ) ≤ 0 g_i(w)=1-y_i(w^Tx_i+b)\leq0gi(w)=1yi(wTxi+b)0

引入松弛变量后就变成了:

h i ( w , a i ) = g i ( w ) + a i 2 = 0 h_i(w,a_i)=g_i(w)+a_i^2=0hi(w,ai)=gi(w)+ai2=0

因为 g ( x ) g(x)g(x) 为小于等于0的,所以加上一个大于0的数,肯定是能够等于0的,这里 a i 2 a_i^2ai2 的作用就可以理解为一种动态调节因子,能够调节自身使上面的等式成立。那么这样就将原来的不等式转化成了等式,就可以使用拉格朗日乘子法了:

L ( w , b , λ , a ) = f ( w ) + ∑ i = 1 m λ i h i ( w ) = f ( w ) + ∑ i = 1 m λ i [ g i ( w ) + a i 2 ] L(w,b,\lambda,a)=f(w)+\sum_{i=1}^m\lambda_ih_i(w)=f(w)+\sum_{i=1}^m\lambda_i[g_i(w)+a_i^2]L(w,b,λ,a)=f(w)+i=1mλihi(w)=f(w)+i=1mλi[gi(w)+ai2]

我们的目标就是要对该式求极值:

{ ∂ L ∂ w i = ∂ f ∂ w i + ∑ i = 1 m λ i ∂ g i ∂ w i ∂ L ∂ a i = 2 λ i a i = 0 ∂ L ∂ λ i = g i ( w ) + a i 2 = 0 λ i ≥ 0

Lwi=fwi+mi=1λigiwiLai=2λiai=0Lλi=gi(w)+a2i=0λi0{∂L∂wi=∂f∂wi+∑i=1mλi∂gi∂wi∂L∂ai=2λiai=0∂L∂λi=gi(w)+ai2=0λi≥0

wiL=wif+i=1mλiwigiaiL=2λiai=0λiL=gi(w)+ai2=0λi0

这里解释一下为什么 λ \lambdaλ 要大于0:

根据第二个式子我们可以知道 λ \lambdaλa i a_iai 之间至少有一个为0,但不能同时为0,如果同时为0,那么我们上面的约束条件将对所有的样本不起作用,所以针对每个样本,二者其中有一个为0,所以产生两种情况:

1.λ i = 0 , a i ≠ 0 \lambda_i=0,a_i\neq0λi=0,ai=0

如果 λ i \lambda_iλi 为0的话,那么与之对应的样本将不会起到约束条件,同时根据第三个式子,因为 g ( w ) + a i 2 = 0 g(w)+a_i^2=0g(w)+ai2=0 ,又 a i ≠ 0 a_i\neq0ai=0 ,所以此时我们的 g ( w ) < 0 g(w)<0g(w)<0 ,那就对应 y i ( w T x i + b ) ≠ 1 y_i(w^Tx_i+b)\neq1yi(wTxi+b)=1 ,也就是此时对应的样本在两条直线的外侧。

2.λ i ≠ 0 , a i = 0 \lambda_i\neq0,a_i=0λi=0,ai=0

因为 a i a_iai 为0,根据第三个式子,则说明此时 g ( w ) = 0 g(w)=0g(w)=0 那么说明此时 y i ( w T x i + b ) = 1 y_i(w^Tx_i+b)=1yi(wTxi+b)=1 ,则此时样本落在两条直线上,同时 λ i ≠ 0 \lambda_i\neq0λi=0,那么此时与之对应的样本就会起到约束作用。

所以综上所述,真正起到作用的是 λ i ≠ 0 \lambda_i\neq0λi=0 对应的样本,也就是落在两条直线上的样本,它们叫做支持向量,所以整个算法的核心就是围绕支持向量,支持向量外的样本数据的分布是对模型没有影响的。

将这两点结合起来,就引出了KKT条件:

{ ∂ L ∂ w i = ∂ f ∂ w i + ∑ i = 1 m λ i ∂ g i ∂ w i λ i g i ( w ) = 0 g i ( w ) ≤ 0 λ i ≥ 0

Lwi=fwi+mi=1λigiwiλigi(w)=0gi(w)0λi0{∂L∂wi=∂f∂wi+∑i=1mλi∂gi∂wiλigi(w)=0gi(w)≤0λi≥0

wiL=wif+i=1mλiwigiλigi(w)=0gi(w)0λi0

其中更新的第二个式子和第三个式子就是根据上面得出的结论得到的。

也就是说对于支持向量满足 g ( w ) = 0 g(w)=0g(w)=0 ,即落在两条直线上,而且对应 λ i \lambda_iλi 不为0,对于其它的向量满足 g ( w ) < 0 g(w)<0g(w)<0 ,即对应除了支持向量之外的所有向量,此时 λ i = 0 \lambda_i=0λi=0 ,也就是没有任何作用。

所以我们之前求 m i n   1 2 w T w min\ \frac{1}{2}w^Twmin21wTw 就变为了 m i n   L ( w , b , λ , a ) min\ L(w,b,\lambda,a)minL(w,b,λ,a) ,但是此时又引入了a这个变量,尝试把它去掉,首先将拉格朗日函数进行展开:

L ( w , b , λ , a ) = f ( w ) + ∑ i = 1 m λ i [ g i ( w ) + a i 2 ] = f ( w ) + ∑ i = 1 m λ i g i ( w ) + ∑ i = 1 m λ i a i 2 L(w,b,\lambda,a)=f(w)+\sum_{i=1}^m\lambda_i[g_i(w)+a_i^2]=f(w)+\sum_{i=1}^m\lambda_ig_i(w)+\sum_{i=1}^m\lambda_ia_i^2L(w,b,λ,a)=f(w)+i=1mλi[gi(w)+ai2]=f(w)+i=1mλigi(w)+i=1mλiai2

因为之前求得 ∂ L ∂ a i = 2 λ i a i = 0 \frac{\partial L}{\partial a_i}=2\lambda_ia_i=0aiL=2λiai=0,所以二者得乘积为0,最后一项就消掉了,之后就变成了:

L ( w , b , λ ) = f ( w ) + ∑ i = 1 m λ i g i ( w ) L(w,b,\lambda)=f(w)+\sum_{i=1}^m\lambda_ig_i(w)L(w,b,λ)=f(w)+i=1mλigi(w)

所以此时待优化得就是 m i n L ( w , b , λ ) min L(w,b,\lambda)minL(w,b,λ) ,将其进一步转化

假设此时我们的 g ( w ) < = 0 g(w)<=0g(w)<=0 那么说明,m a x L ( w , b , λ ) maxL(w,b,\lambda)maxL(w,b,λ) 就变成了 f ( w ) + 0 f(w)+0f(w)+0 ,为什么是0,因为 λ \lambdaλ 大于0,而 g i ( w ) g_i(w)gi(w) 小于0,只有为0时才能取得最大值。

如果 g ( w ) > 0 g(w)>0g(w)>0 ,此时的 m a x L ( w , b , λ ) maxL(w,b,\lambda)maxL(w,b,λ) 就变成了 f ( w ) + ∞ f(w)+\inftyf(w)+,因为 λ \lambdaλ 是大于0的,而 g ( w ) g(w)g(w) 也是大于0的,那么最大值就会取到正无穷。

那么此时我们的优化函数又变为了:

m i n   m a x L ( w , b , λ ) min\ maxL(w,b,\lambda)minmaxL(w,b,λ)

又因为L的最大值肯定是 f ( w ) f(w)f(w) 那么就变成了,m i n f ( x ) = m i n 1 2 w T w min f(x)=min\frac{1}{2}w^Twminf(x)=min21wTw,而且此时是在 g ( w ) < = 0 g(w)<=0g(w)<=0 的条件下,因为在该条件下L的最大值才为 f ( x ) f(x)f(x) ,这也就对应最开始我们的函数,满足 y i ( w T x i + b ) > = 1 y_i(w^Tx_i+b)>=1yi(wTxi+b)>=1 的条件下进行优化 m i n 1 2 w T w min\frac{1}{2}w^Twmin21wTw

此时优化函数就是:

m i n   m a x L ( w , b , λ ) min\ maxL(w,b,\lambda)minmaxL(w,b,λ)

λ i > = 0 \lambda_i>=0λi>=0

3.强对偶性

我们上面得到了优化函数,但是求解起来不太方便,所以我们需要用到强对偶的方法,将其换个方式进行求解,针对于强对偶的两个方程是同解的。

这里解释下什么是弱对偶和强对偶。

如果针对一个函数 f ( x ) f(x)f(x) 我们存在:

m i n   m a x f ( x ) > = m a x m i n f ( x ) min\ maxf(x)>=max minf(x)minmaxf(x)>=maxminf(x)

那么则说明两者为弱对偶关系,怎么理解上面的不等式呢?

从大的里面挑出最小的要大于从小的里面挑出最大的,或者你可以理解为清华里的菜鸡要强于专科里的学霸,这个例子很好理解吧。

那么强对偶就是满足等号成立,即 m i n   m a x f ( x ) = m a x m i n f ( x ) min\ maxf(x)=max minf(x)minmaxf(x)=maxminf(x)

我们引出这个就是为个将上文获得的优化函数进行对偶转化,所以:

m i n   m a x L ( w , b , λ ) min\ maxL(w,b,\lambda)minmaxL(w,b,λ)

就变成了:

m a x   m i n L ( w , b , λ ) max\ minL(w,b,\lambda)maxminL(w,b,λ)

我们就可以优化新的方程式了,对偶的目的是将原来难以求解的问题转化为一个容易求解的问题,同时我们之前说的KKT条件就是强对偶性的充要条件。

这里因为我们的L是凸函数,所以可以直接确定能够进行强对偶。

4.二次规划求解 λ \lambdaλ

m a x   m i n L ( w , b , λ ) max\ minL(w,b,\lambda)maxminL(w,b,λ)

根据上文,我们最终优化函数是这个,首先将min和max分离,先计算内层min函数,因为是凸函数,所以可以直接进行求导,由于此时 λ \lambdaλ 为常数,所以只需对 w 、 b w、bwb 进行求导:

∂ L ∂ w = w − ∑ i = 1 m λ i x i y i = 0 \frac{\partial L}{\partial w}=w-\sum_{i=1}^m\lambda_ix_iy_i=0wL=wi=1mλixiyi=0

∂ L ∂ b = ∑ i = 1 m λ i y i = 0 \frac{\partial L}{\partial b}=\sum_{i=1}^m\lambda_iy_i=0bL=i=1mλiyi=0

我们可以获得 :w = ∑ i = 1 m λ i x i y i w=\sum_{i=1}^m\lambda_ix_iy_iw=i=1mλixiyi

我们将这两个式子带入到原式当中进行化简,由于是凸函数,所以导数为0的点就是其最小值,我们把w、b的值带入后就可以得到 m i n L ( w , b , λ ) minL(w,b,\lambda)minL(w,b,λ)

此时的 m i n L ( w , b , λ ) = ∑ j = 1 m λ i − 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j ( x i T x j ) minL(w,b,\lambda)=\sum_{j=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i^Tx_j)minL(w,b,λ)=j=1mλi21i=1mj=1mλiλjyiyj(xiTxj)

我们的优化函数就变成了:

m a x m i n L ( w , b , λ ) = m a x ∑ j = 1 m λ i − 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j ( x i T x j ) maxminL(w,b,\lambda)=max\sum_{j=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i^Tx_j)maxminL(w,b,λ)=maxj=1mλi21i=1mj=1mλiλjyiyj(xiTxj)

一般我们习惯优化最小值将上式加个符号就变成了:

m a x − ∑ j = 1 m λ i + 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j ( x i T x j ) max-\sum_{j=1}^m\lambda_i+\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i^Tx_j)maxj=1mλi+21i=1mj=1mλiλjyiyj(xiTxj)

∑ i = 1 m λ i y i = 0 \sum_{i=1}^m\lambda_iy_i=0i=1mλiyi=0

注意上面的这个条件不能丢,因为该优化函数满足的前提是对b的偏导为0得来的,为什么没有考虑对w的偏导,因为现在的优化函数与w参数没关系,所以不需要,而b的偏导为0的条件是 ∑ i = 1 m λ i y i = 0 \sum_{i=1}^m\lambda_iy_i=0i=1mλiyi=0 是对优化函数有影响的,需要保留。

接下来的问题就是如何求取满足最大值的 λ \lambdaλ

这里采用一种算法叫做SMO算法,其核心思想非常简单:每次只优化一个参数,其他参数先固定住,仅求当前这个优化参数的极值。

由于优化函数同时存在两个优化变量,所以需要根据约束条件消去一个。

由于有 ∑ i = 1 m λ i y i = 0 \sum_{i=1}^m\lambda_iy_i=0i=1mλiyi=0 ,所以存在:

λ i y i + λ j y j = c \lambda_iy_i+\lambda_jy_j=cλiyi+λjyj=c

其中 c = − ∑ k ≠ i , j λ k y k c=-\sum_{k\neq i,j}\lambda_ky_kc=k=i,jλkyk ,由此可以得出 λ j = c − λ i y i y j \lambda_j=\frac{c-\lambda_iy_i}{y_j}λj=yjcλiyi ,也就是我们可以利用 λ i \lambda_iλi 的表达式代替 λ j \lambda_jλj 。这就相当于把目标问题转化成了仅有一个约束条件的最优化问题,仅有的约束就剩下了 λ i > = 0 \lambda_i>=0λi>=0

对于单变量优化问题我们就可以使用梯度下降或者其它迭代算法进行求解。

5.求解最优解 w ∗ , b ∗ w^*,b^*w,b

说了这么这么多,到底怎么获得最终模型的参数和偏置呢?

我们之前对拉格朗日进行求导,获得:

w = ∑ i = 1 m λ i y i x i w=\sum_{i=1}^m\lambda_iy_ix_iw=i=1mλiyixi

由于我们在第四步,已经通过SMO算法求出了每个样本对应的 λ i \lambda_iλi ,所以可以直接带入上式,求出 w ∗ w^*w

那么如果求取 b ∗ b^*b 呢?

我们之前讲到我们的支持向量是满足 y i ( w T x i + b ) = 1 y_i(w^Tx_i+b)=1yi(wTxi+b)=1 的,也就是支持向量一定在该条直线上,所以说我们可以随便找个支持向量,然后带入就可以得到:

y k ( w T x k + b ) = 1 y_k(w^Tx_k+b)=1yk(wTxk+b)=1

其中(x_k,y_k)对应着支持向量的信息。

此时上式两边同时左乘 y k y_kyk ,得到:

y k 2 ( w T x k + b ) = y k y_k^2(w^Tx_k+b)=y_kyk2(wTxk+b)=yk

因为 y k y_kyk 只能为1或者-1,所以 y k 2 y_k^2yk2 的值为1,所以此时满足 w T x k + b = y k w^Tx_k+b=y_kwTxk+b=yk ,得到:

b ∗ = y k − w T x k b^*=y_k-w^Tx_kb=ykwTxk

又因为为了使我们的模型更加的稳定,鲁棒性更强,所以我们可以求得所有支持向量的均值:

b = 1 ∣ S ∣ ∑ s ∈ S ( y k − w T x k ) b=\frac{1}{|S|}\sum_{s\in S}(y_k-w^Tx_k)b=S1sS(ykwTxk)

其中 ∣ S ∣ |S|S 代表支持向量的个数。

这样我们就求出了模型最优解系数 w ∗ w^*w和偏置 b ∗ b^*b ,得到模型:

w ∗ T x + b ∗ = 0 {w^*}^Tx+b^*=0wTx+b=0

决策函数为:

f ( x ) = s i g n ( w ∗ T x + b ∗ ) f(x)=sign({w^*}^Tx+b^*)f(x)=sign(wTx+b)

其中的 s i g n ( . ) sign(.)sign(.) 为越阶函数:

s i g n ( x ) = { − 1 x < 0 0 x = 0 1 x > 0 sign(x)=

101x<0x=0x>0{−1x<00x=01x>0

sign(x)=101x<0x=0x>0

这样我们的支持向量机线性可分分类器就构建成功了,但是这只是针对线性可分的数据有用,如果我们的数据线性不可分,找不到一个超平面进行分割,那么那么我们的模型就会没用,进而引出了核函数和软间隔的概念,如何处理线性不可分数据,下篇文章再讲。

目录
相关文章
|
4月前
|
机器学习/深度学习 算法
【机器学习】SVM面试题:简单介绍一下SVM?支持向量机SVM、逻辑回归LR、决策树DT的直观对比和理论对比,该如何选择?SVM为什么采用间隔最大化?为什么要将求解SVM的原始问题转换为其对偶问题?
支持向量机(SVM)的介绍,包括其基本概念、与逻辑回归(LR)和决策树(DT)的直观和理论对比,如何选择这些算法,SVM为何采用间隔最大化,求解SVM时为何转换为对偶问题,核函数的引入原因,以及SVM对缺失数据的敏感性。
86 3
|
4月前
|
机器学习/深度学习 运维 算法
深入探索机器学习中的支持向量机(SVM)算法:原理、应用与Python代码示例全面解析
【8月更文挑战第6天】在机器学习领域,支持向量机(SVM)犹如璀璨明珠。它是一种强大的监督学习算法,在分类、回归及异常检测中表现出色。SVM通过在高维空间寻找最大间隔超平面来分隔不同类别的数据,提升模型泛化能力。为处理非线性问题,引入了核函数将数据映射到高维空间。SVM在文本分类、图像识别等多个领域有广泛应用,展现出高度灵活性和适应性。
198 2
|
4月前
|
机器学习/深度学习 算法
【机器学习】解释对偶的概念及SVM中的对偶算法?(面试回答)
解释了对偶的概念,指出对偶性在优化问题中的重要性,尤其是在强对偶性成立时可以提供主问题的最优下界,并且详细阐述了支持向量机(SVM)中对偶算法的应用,包括如何将原始的最大间隔优化问题转换为对偶问题来求解。
100 2
|
4月前
|
机器学习/深度学习 算法
【机器学习】支持向量机SVM、逻辑回归LR、决策树DT的直观对比和理论对比,该如何选择(面试回答)?
文章对支持向量机(SVM)、逻辑回归(LR)和决策树(DT)进行了直观和理论上的对比,并提供了在选择这些算法时的考虑因素,包括模型复杂度、损失函数、数据量需求、对缺失值的敏感度等。
71 1
|
6月前
|
机器学习/深度学习 算法 Windows
【阿旭机器学习实战】【34】使用SVM检测蘑菇是否有毒--支持向量机
【阿旭机器学习实战】【34】使用SVM检测蘑菇是否有毒--支持向量机
|
7月前
|
机器学习/深度学习 算法
探索机器学习中的支持向量机(SVM)算法
【5月更文挑战第31天】 在数据科学的广阔天地中,支持向量机(SVM)以其卓越的性能和强大的理论基础脱颖而出。本文将深入剖析SVM的工作原理、核心概念以及实际应用,旨在为读者提供一个清晰的理解视角,并通过实例演示其在分类问题中的有效性。我们将从线性可分的情况出发,逐步过渡到非线性问题的处理方法,并探讨如何通过调整参数来优化模型的性能。
304 0
|
7月前
|
机器学习/深度学习 人工智能 算法
探索机器学习中的支持向量机(SVM)算法
【5月更文挑战第28天】 在数据科学与人工智能的领域中,支持向量机(Support Vector Machines, SVM)是一种强大的监督学习模型,它基于统计学习理论中的VC维理论和结构风险最小化原则。本文将深入探讨SVM的数学原理、关键概念以及实际应用案例。我们将透过SVM的镜头,理解其在分类和回归问题中的应用,并讨论如何通过核技巧克服维度灾难,提高模型的泛化能力。文章还将展示使用SVM解决实际问题的步骤和注意事项,为读者提供一个清晰的SVM应用指南。
|
7月前
|
机器学习/深度学习 人工智能 算法
深入解析机器学习中的支持向量机(SVM)
深入解析机器学习中的支持向量机(SVM)
422 0
|
27天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
87 4
|
6天前
|
算法
PAI下面的gbdt、xgboost、ps-smart 算法如何优化?
设置gbdt 、xgboost等算法的样本和特征的采样率
22 2