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

技术分享 2年前 (2022-09-25) 0 999+

关注

假定数据集(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<0),则（这个字对应前面的‘若’），超平面((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)就没法优化了，后面的优化还没看。