SVM公式详尽推导,没有思维跳跃。

假定数据集(T={(x_1,y_1),(x_2,y_2),...,(x_n,y_n)},x_n in R_k, y_n in {1,-1})线性可分,SVM的优化目标是:

优化一个超平面的参数,使得这个超平面,能够正确划分两类数据,并且,距离(动词),两类数据最近的那个点,的距离最大。



tip: 优化一个超平面的参数指的是:调整超平面的参数值。

写成数学公式为:

使得这个超平面,能够正确划分两类数据[1]

[y(w·x+b) > 0 tag{1} label{1}
]

距离(动词),两类数据最近的那个点,的距离最大。[2]

[max(min(yfrac{w·x+b}{||w||})) tag{2} label{2}
]

假设在所有((w,b) in {(w_1,b_1),(w_2,b_2),cdots})中,最优解为((w^*,b^*)),该最优解对应的,离这个超平面最近的点为((w_k,y_k)),我们现在改写(eqref{2}),但是毕竟是需要优化的,我们就不把最优解放到里面去,那么(eqref{2})可以改写为:

[max(y_kfrac{w·x_k+b}{||w||})
]

如果要写进去,那么就可以写成:

[max(y_kfrac{w·x_k+b}{||w||}) = y_kfrac{w^*·x_k+b^*}{||w^*||}
]

我们继续在上面的假设内,我们看到离超平面((w^*,b^*))最近的点,到该超平面的距离为(y_kfrac{w^*·x_k+b^*}{||w^*||}),那么公式(eqref{1})可以改写为:

[frac{y(w^*·x+b^*)}{||w^*||} geq frac{y_k(w^*·x_k+b^*)}{||w^*||}
]

现在让我们假设(注意,我现在已经在上面的假设上又假设了一次,相当于if语句里面又来了个if语句,我现在还没有说明对应的两个else语句,只有说明了两个else语句,所有情况才算全部讨论到),我们找到了((w^*,b^*)),但是让我们来看看这个解((2w^*,2b^*))。首先,其满足(eqref{2}),另外:

[max(y_kfrac{w·x_k+b}{||w||}) = y_kfrac{w^*·x_k+b^*}{||w^*||}=y_kfrac{2w^*·x_k+2b^*}{||2w^*||},\
||2w^*||=sqrt{(sum{(2w_i)^2})}=sqrt{(4sum{w_i^2})}=2sqrt{(sum{w_i^2})}=2||w^*||
]

我们再来看更一般的:

[max(min(yfrac{w·x+b}{||w||})) =max(min(yfrac{kw·x+kb}{||kw||})),k neq 0
]

tip: 我这里假设了(k neq 0),其实这不是假设,而是必然的结果,因为如果(k=0),那么超平面((kw^*,kb^*)=(0,0)),这是不满足(eqref{1})的(把(w)(b)均设为0,然后看看左边是否都大于0),既然不满足(eqref{1})((0,0))就不是解,那么(k=0)就不在我们的讨论范围内,所以(k neq 0)(k neq 0)的原因是其不在我们的讨论范围内,而不是简单的,听到已经麻木了的"分母不能为0,所以(k neq 0)"。另外,通过穷举可以看出$ k in R space and neq 0$。

从上面的一个式子可以看出,就算我们找到了一个最优解((w^*,b^*))(或者我们找到的是((2w^*,2b^*)),但是我们可以把((kw^*,kb^*))记作((w^*,b^*))),我们可以通过给予(w)(b)一个非零参数(k),诞生出另一个解,但实际上集合({(w^*,b^*),(2.2w^*,2.2b^*),(3w^*,3b^*),...})都是同一个向量(如果(w)是一个n维向量,那么((w,b)),可以看作一个n+1维向量。),另外,因为(k in R space and neq 0),(y(w·x+b) > 0)(因为(yfrac{w·x+b}{||w||})为点((x,y))到超平面((w,b))的距离,数据集T是线性可分的,那么该距离大于0,从而分子大于0),所以

[y(kw·x+kb) > 0
]

那么优化目标可以改写为[3]

[max(min(yfrac{w·x+b}{||w||})) =max(min(yfrac{kw·x+kb}{||kw||}))=max(y_kfrac{kw·x_k+kb}{||kw||})=max(frac{1}{||k_1w||})=max(frac{1}{||w||}), \
s.t: frac{y(w·x+b)}{||w||} geq frac{y_k(w·x_k+b)}{||w||}=frac{1}{||k_1w||}=frac{1}{||w||},\k neq 0
]

注意:

[max(frac{1}{||w^*||}) iff min(||w^*||) iff min(frac{1}{2}||w^*||^2)
]

所以最终优化目标为(在上面的两个假设内):

[min(frac{1}{2}||w||^2),\
s.t spacespace y(w·x+b) geq 1
]

到这里为止,SVM的推导其实还未完,因为我们是做了两个假设才推出SVM的优化公式的,那万一假设不满足呢?
我们一共做了两个假设:

假设在所有((w,b) in {(w_1,b_1),(w_2,b_2),cdots})中,最优解为((w^*,b^*))

现在让我们假设,(xxx),我们找到了((w^*,b^*))

现在让我们讨论另外的情况:

  • 对应于假设”现在让我们假设,(xxx),我们找到了((w^*,b^*))“,如果找不到((w^*,b^*))怎么办,那就继续找嘛,因为大假设里面保证了最优解存在,所以((w^*,b^*))是一定能找到的。所以,第二个if对应的else语句就是continue,即一直找。(应该是的,既然存在,那么就可以找到)
  • 对应于假设”假设在所有((w,b) in {(w_1,b_1),(w_2,b_2),cdots})中,最优解为((w^*,b^*))“,如果((w,b) in {})怎么办?因为数据集线性可分,那么就存在((w,b))能够正确划分数据集,所以((w,b) in {})不成立,那么((w,b) in {(w_1,b_1),(w_2,b_2),cdots})一定成立,那么如果没有最优解怎么办?从最终的优化目标中可以看出,优化目标有下界(即值的变化范围存在一个最小值),那么最优解一定是存在的。所以,第一个if对应的else不用写,因为不会走else语句。

至此,SVM的推导才算真正完成。

注释:

线性可分:对于数据集(S),若存在一个超平面((w,b)),能够正确划分数据集,即对于任意样本((x,y)),如果(y=1),那么(w·x+b>0),否则(w·x+b,则(这个字对应前面的‘若’),超平面((w,b))可分数据集(S),数据集(S)线性可分。

超平面:满足某个等式(如(w·x-y+b=0))的高维度(即(x in R_k,k>2))点((x,y))(这里的(x)(y)对应前面一个括号里面的(x)(y)),的集合。【另外可以看这里】

[1]:公式(eqref{1})的解释,见线性可分,运算符号‘(·)’为向量的点积运算.

[2]:公式(eqref{2})最里面的公式为点到超平面的距离,见 文章:高维空间中,点的超平面的距离 .

[3]:

  • (max(min(yfrac{kw·x+kb}{||kw||}))=max(y_kfrac{kw·x_k+kb}{||kw||}))的解释:
    对于任意一个超平面((w,b))可行解,都存在一个点((x_k,y_k))(自己在三维空间中想一下,对于某个能完全正确划分数据集的平面((w,b)),都会有一个离其最近的点((x_k,y_k))),使得(min(yfrac{kw·x+kb}{||kw||}))=(y_kfrac{kw·x_k+kb}{||kw||}).
  • (max(y_kfrac{kw·x_k+kb}{||kw||})=max(frac{1}{||k_1w||}))的解释:
    因为(y(kw·x+kb)>0)取任何值,都会有分母对应其值,使其回到原来的值。另外可以这样理解:不管(y(w·x+b)>0)取什么值,都存在一个值(k_1)使得(y(k_1w·x+k_1b)=1),所以我们可以把(y(w·x+b))的值限制为1,至于为什么要这么做,应该是为了简化表达式,但是这样子(b)就没法优化了,后面的优化还没看。

可行解: 对于某个问题,如果某个结果满足其约束条件,那么该结果就是该问题的可行解。比如:
有以下问题:

[min space y,\
s.t:space y>= 1
]

那么(y=4)就是可行解,因为其满足约束条件。

文章来源于互联网:SVM公式详尽推导,没有思维跳跃。

THE END
分享
二维码