Support Vector Machine 3

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

可以将优化目标写为：

$$min_{w,b}\quad \frac{1}{2}||w||^{2}+C\sum_{i=1}^{m}loss(y_{i}(w\cdot x_{i}+b)-1)$$

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

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

$$min_{w,b}\quad \frac{1}{2}||w||^{2}+C\sum_{i=1}^{m}max(0,1-y_{i}(w\cdot x_{i}+b))$$

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

$$\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,\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}$$

令 $L$ 对 $w,b,\alpha$ 的偏导为 $0$ 可以得到

$$w=\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,\alpha,\xi,\mu)$ 即可以将原问题化成对偶问题：

$$\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 唯一的区别在于 $\alpha_{i}\ge 0$变成了 $C\ge \alpha_{i}\ge 0$，同样可以用上文中提到的 SMO 算法很方便的求解，唯一的区别在于剪辑的时候需要考虑两个方向。

后面还会介绍 SVM 的核技巧以及常用核