SVM的推导(3)

前文介绍了硬间隔SVM的相关推导，本文将继续介绍软间隔SVM的数学推导，即在样本不是线性可分的情况下，允许一部分样本错误分类的SVM。软间隔SVM允许一部分样本不满足约束：yi(w⋅xi)≥0y_{i}(w\cdot x_{i})\ge 0

可以将优化目标写为：

minw,b12∣∣w∣∣2+C∑i=1mloss(yi(w⋅xi+b)−1)min_{w,b}\quad \frac{1}{2}||w||^{2}+C\sum_{i=1}^{m}loss(y_{i}(w\cdot x_{i}+b)-1)

其中 CC 是一个常数，用来衡量允许的不满足约束的程度，其中的 loss()loss() 函数可以使用 hinge()hinge() 函数，即 losshinge(z)=max(0,1−z)loss_{hinge}(z)=max(0,1-z)

那么可以将优化目标写为：

minw,b12∣∣w∣∣2+C∑i=1mmax(0,1−yi(w⋅xi+b))min_{w,b}\quad \frac{1}{2}||w||^{2}+C\sum_{i=1}^{m}max(0,1-y_{i}(w\cdot x_{i}+b))

引入“松弛变量” ξi≥0\xi_{i}\ge 0 ，可以将上式改写为

minw,b,ξi12∣∣w∣∣2+C∑i=1mξis.t.yi(w⋅xi+b)≥1−ξiξi≥0,i=1,2,...,m\begin{align*} min_{w,b,\xi_{i}}\quad& \frac{1}{2}||w||^{2}+C\sum_{i=1}^{m}\xi_{i}\\ s.t.\quad& y_{i}(w\cdot x_{i}+b)\ge1-\xi_{i}\\ &\xi_{i}\ge0,i=1,2,...,m \end{align*}

与硬间隔SVM类似，上述的问题也是个二次规划的问题，可以先用拉格朗日对偶性将其转换为对应的对偶问题，再用SMO算法求解。上面问题对应的拉格朗日函数为：

L(w,b,α,ξ,μ)=12∣∣w∣∣2+C∑i=1mξi+∑i=1mαi(1−ξi−yi(w⋅xi+b))−∑i=1mμiξiL(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^{2}+C\sum_{i=1}^{m}\xi_{i}\\+\sum_{i=1}^{m}\alpha_{i}(1-\xi_{i}-y_{i}(w\cdot x_{i}+b))-\sum_{i=1}^{m}\mu_{i}\xi_{i}

令 LL 对 w,b,αw,b,\alpha 的偏导为 00 可以得到

w=∑i=1mαiyixi0=∑i=1mαiyiC=αi+μiw=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i}\\ 0=\sum_{i=1}^{m}\alpha_{i}y_{i}\\ C=\alpha_{i}+\mu_{i}

代入 L(w,b,α,ξ,μ)L(w,b,\alpha,\xi,\mu) 即可以将原问题化成对偶问题：

minα12∑i=1m∑j=1mαiαjyiyjxi⋅xj−∑i=1mαis.t.∑i=1mαiyi=0C≥αi≥0i=1,2,...,m\begin{align*} min_ \alpha\quad &\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}\cdot x_{j}-\sum_{i=1}^{m}\alpha_{i}\\ s.t.\quad &\sum_{i=1}^{m}\alpha_{i}y_{i}=0\\ &C\ge \alpha_{i}\ge 0\\ &i=1,2,...,m \end{align*}

可以看出其与硬间隔SVM唯一的区别在于 αi≥0\alpha_{i}\ge 0变成了 C≥αi≥0C\ge \alpha_{i}\ge 0，同样可以用上文中提到的SMO算法很方便的求解，唯一的区别在于剪辑的时候需要考虑两个方向。

后面还会介绍SVM的核技巧以及常用核，To be continue…

#代码 & 数学