机器学习07 SVM

这一讲要开始讲SVM(Support Vector Machine)了，在深度学习流行以前，SVM占据着很重要的位置，它的理论推导是非常优美的。

SVM也是硬分类的一种，因为是直接给出具体分类的，并不是概率。

SVM一共可以分为三种 hard-margin SVM ，soft-margin SVM， kernel SVM，分别对应于线性可分，线性可分（存在一些错误点），非线性问题

Hard-margin SVM

首先定义数据集 $D = \{{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}\}， x_i\in R^p， y = \{+1, -1\}$

SVM和感知机一样，也是在寻找超平面进行分割， $f(x) = sign(w^Tx +b)$

但是和感知机不一样的地方在于，感知机找可分的超平面，只要实现可分即可，所以超平面有无限种可能（可分的前提下）

而SVM，是最大间隔分类器，即max margin(w,b)，margin的定义是所有样本点到超平面的最短距离

同时需要满足 $y_i(w^Tx_i+b) >0 \ for \ \forall \ i = 1,2,3,....,n$

样本点到超平面的最短距离 $margin(w,b) = min \ distance(w,b,x) = min \frac{1}{||w||} |w^Tx+b|$

我们希望这个最短距离最大，即

$max\ min \frac{1}{||w||} y_i (w^Tx_i +b) = max\ \frac{1}{||w||} min \ y_i(w^Tx_i+b)$

$s.t. \ y_i(w^Tx_i+b) > 0$ , 即 $\exists \ r >0, s.t. \ min\ y_i(w^Tx_i+b) = r$

所以 $max\ \frac{1}{||w||} min \ y_i(w^Tx_i+b) = max\ \frac{1}{||w||}\ r$

请注意一点，等比例放大和缩小w,b，超平面是同一个，但是会影响 $w^Tx_i+b$ 的值，即会影响r的值，所以我们不妨把r确定下来，假设r等于1，即 $min\ y_i(w^Tx_i+b) = 1$ ，这样问题就变成了

$max \frac{1}{||w||}$

$s.t.\ y_i(w^Tx_i+b) >=1 \ for \ \forall \ i = 1,2,3,....,n$

把最大化问题改成最小化问题，即

$\mathop{\min}_{w,b} \frac{1}{2}w^Tw$

$s.t.\ 1-y_i(w^Tx_i+b) \leq 0 \ for \ \forall \ i = 1,2,3,....,n$ （A）

目标函数是二次项，然后存在n个约束，是一个凸优化问题

使用拉格朗日乘子法， $L(w,b,\lambda) = \frac{1}{2} w^Tw + \sum_{i=1}^n \lambda _i(1- y_i(w^Tx_i+ b))$

问题就变成了 $\mathop{\min}_{w,b} \mathop{\max}_{\lambda}\ L(w,b,\lambda)$ , $s.t.\ \lambda_i \geq 0$ （B）

这边做一个逻辑上的解释，为什么新的问题（B），等价于原来的问题（A）呢

如果 $1- y_i(w^Tx_i+ b) > 0$ ，则 $\mathop{\max}_{\lambda}\ L(w,b,\lambda) = \infty$

如果 $1- y_i(w^Tx_i+ b) \leq 0$ , $\mathop{\max}_{\lambda}\ L(w,b,\lambda) = \frac{1}{2} w^Tw+0 = \frac{1}{2} w^Tw$ , $\mathop{\min}_{w,b} \mathop{\max}_{\lambda}\ L(w,b,\lambda) = \mathop{\min}_{w,b} \frac{1}{2}w^Tw$

所以 $\mathop{\min}_{w,b} \mathop{\max}_{\lambda}\ L(w,b,\lambda) = min(\infty, \frac{1}{2}w^Tw) = \frac{1}{2}w^Tw$ , 可以理解为丢弃了 $1- y_i(w^Tx_i+ b) > 0$ 的部分，相当于起到了原问题中的约束作用

至此，我们的问题就是 $\mathop{\min}_{w,b} \mathop{\max}_{\lambda}\ L(w,b,\lambda)$ ， $s.t.\ \lambda_i \geq 0$ ，我们称之为原问题

接下来，我们引入对偶问题的概念，原问题的对偶问题是 $\mathop{\max}_{\lambda} \mathop{\min}_{w,b} \ L(w,b,\lambda)$ ， $s.t.\ \lambda_i \geq 0$ （C）

我们针对这个问题再做一些简单的理解， $min\ max\ L \geq max\ min \ L$ （看到过一个哲学解释，min max是凤尾，max min是鸡头，凤尾还是要大于鸡头）

这是弱对偶关系，强对偶关系就是 $min\ max\ L = max\ min \ L$

现在我们来求对偶问题的解，先求 $\mathop{\min}_{w,b} \ L(w,b,\lambda)$

$\frac{\partial L}{\partial b} = \frac{\partial}{\partial b}[\sum_{i=1}^n \lambda _i - \sum_{i=1}^n\lambda _iy_i(w^Tx_i+b)] = - \sum_{i=1}^n\lambda _iy_i = 0$

将次这个结果带入L， $L(w,b,\lambda) = \frac{1}{2}w^Tw + \sum_{i=1}^n\lambda _i - \sum_{i=1}^n\lambda _iy_iw^Tx_i - \sum_{i=1}^n\lambda _iy_ib$

$= \frac{1}{2}w^Tw + \sum_{i=1}^n\lambda _i - \sum_{i=1}^n\lambda _iy_iw^Tx_i$

现在来求w，

$\frac{\partial L}{\partial w} = \frac{1}{2}*2*w - \sum_{i=1}^n\lambda_iy_ix_i = 0$ , 所以 $w = \sum_{i=1}^n\lambda_iy_ix_i$

现在把w再带入到L中， $L== \frac{1}{2}w^Tw + \sum_{i=1}^n\lambda _i - \sum_{i=1}^n\lambda _iy_iw^Tx_i = \frac{1}{2} (\sum_{i=1}^n\lambda_iy_ix_i)^T(\sum_{i=1}^n\lambda_iy_ix_i)$

$= \frac{1}{2} (\sum_{i=1}^n\lambda_iy_ix_i)^T(\sum_{i=1}^n\lambda_iy_ix_i) - \sum_{i=1}^n\lambda _iy_i(\sum_{j=1}^n \lambda _jy_jx_j)^Tx_i +\sum_{i=1}^n\lambda _i$

$= -\frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n\lambda_i \lambda_jy_iy_jx_i^Tx_j +\sum_{i=1}^n\lambda _i$

这个式子就是 $\mathop{\min}_{w,b} \ L(w,b,\lambda)$ 的结果，现在求剩下的 $\mathop{\max}_{\lambda} \mathop{\min}_{w,b} \ L(w,b,\lambda)$ ，即max部分

$\mathop{\max}_{\lambda} -\frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n\lambda_i \lambda_jy_iy_jx_i^Tx_j +\sum_{i=1}^n\lambda _i$ , $s.t.\ \lambda_i \geq 0, \sum_{i=1}^n\lambda _iy_i = 0$

老样子，max可以写成min，即

$\mathop{\min}_{\lambda} \frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n\lambda_i \lambda_jy_iy_jx_i^Tx_j -\sum_{i=1}^n\lambda _i$ ,

$s.t.\ \lambda_i \geq 0$ (D)

$\sum_{i=1}^n\lambda _iy_i = 0$

暂时先写到这边， SVM内容比较多，后续会慢慢补充。