支持向量机SVM——原理及相关数学推导系列一

2019-04-04 本文已影响0人 7NIC7

（一）前言

支持向量机比较适合于高维数据，可以减缓维数灾难问题；也非常适用于小样本，建模只需要“支持向量”即可。
支持向量机的思想非常简单，就是可以找到一个超平面使得不同类别的数据可以尽量分开，并且为了增加测试集分类的鲁棒性（robust），希望这个超平面与各类别距离最近的数据点均越远越好。

定义1.1：测试样本(x,y)的类别预测规则，如下：
$y=\begin{cases} 1 \ \ \ \ ,w^T x + b >0 \\ -1 \ ,w^T x + b <0 \end{cases}$
上面的式子可以统一为 $y(w^Tx+b) > 0$ .

（二）线性可分的SVM

基本原理

因为下面要计算点到超平面的距离，所以这里给出距离公式，假设超平面S为 $w^Tx + b = 0$ ，某个点p到S的距离定义如下。

定义2.1
$distance(p, S) = \frac{|w^Tx + b|} {||w||}$
根据SVM的思想：
1.在所有点的类都分对的条件下，即 $y_i(w^Tx_i + b) > 0$
2.希望每类中最近的点离分割面的距离越远越好。设这个最近的距离是C，那么SVM问题可以定义如下：
定义2.1：最大边缘分类器
$\begin{align*} &\max_{w,b}\ C \\ &s.t. y_i(w^Tx_i + b)/||w|| \geq C \end{align*}$
其中， $i=1,2, \dots,N$
对定义2.1中的不等式的左右均乘以 $||w||$ ，并且令 $C=1/||w||$ ，那么上述等式就可以转化为
定义2.2
$\begin{align*} &\max_{w,b} \ 1/||w|| \\ &s.t.y_i(w^Tx_i + b) \geq 1 \end{align*}$
其中， $i=1,2,\dots,N$
在数学中，带根号的式子不太好处理，并且处理最大化问题可以转化为处理最小化问题（定义2.2中需要最大化的式子是正数，所以与其等价的最小化问题即为其倒数），那么定义2.2可以重新定义为2.3.
定义2.3
$\begin{align*} &\min_{w,b} \ \frac{1}{2}w^Tw \\ &s.t. y_i(w^T x_i + b) \geq 1 \end{align*}$
其中， $i =1,2,\dots,N$

对偶问题

为了求解定义2.3中的未知参数，下面我们将改问题转化为其对偶形式。
首先，解释下定义2.3是如何和定义2.4等价的。在定义2.3中
1.当 $y_i (w^Tx_i + b) < 1$ 时，即点分类错误。那么 $1- y_i (w^Tx_i + b) > 0$ ，要想让定义2.4中的 $\alpha_i \geq 0$ 使得式子最大化，那么式子将变为无穷大，即无解。

2.当 $y_i (w^Tx_i + b) \geq 1$ 时，即点分类正确。那么 $1- y_i(w^T x_i + b) \leq 0$ ，此时，要想让定义2.4中的 $\alpha_i \geq 0$ 使得式子最大化，那么 $\alpha_i (1-y_i(w^Tx_i + b))$ 只能为零。即为最小化 $\frac{1}{2}w^T w$ 。
总结一下：定义2.4有解，就是在 $y_i(w^T x_i + b) \geq 1$ 时去最小化 $\frac{1}{2}w^T w$ 。是不是和定义2.3在处理同一个问题？

定义2.4
$\min_{w,b}\max_{\alpha_i \geq 0}L(w,b) = \min_{w,b}\max_{\alpha_i \geq 0}\frac{1}{2}w^T w + \sum_{i=1}^{N} \alpha_i(1-y_i(w^Tx_i + b))$
其中， $i =1,2,\dots,N$
那么在数学上，定义2.4有一个下限，我们可以通过这个下限去求解得到超平面。即 $\min_{w,b} \max_{\alpha_i \geq 0} L(w,b) \geq \max_{\alpha_i \geq 0}\min_{w,b}L(w,b,\alpha)$ 所以将我们的问题重新定义为2.5。
定义2.5
$\max_{\alpha_i \geq 0} \min_{w,b}L(w,b,\alpha)=\max_{\alpha_i \geq 0}\min_{w,b}\frac{1}{2}w^Tw + \sum_{i=1}^{N} \alpha_i(1-y_i(w^Tx_i + b))$
其中， $i =1,2,\dots,N$
定义2.5里面的最小化问题很好解，即为求 $||w||$ 和 $b$ 的偏导数，令其为零。
$\begin{align*} & \frac{\partial L(w,b,\alpha)}{\partial w} = w - \sum_{i=1}^{N}\alpha_iy_ix_i=0 \\ &\frac{\partial L(w,b,\alpha)}{\partial b} = -\sum_{i=1}^{N}\alpha_iy_i = 0 \end{align*}$
将解出的 $||w||$ 和 $b$ 代入到定义2.5中得到：
$\begin{align*} &\frac{1}{2}w^T w + \sum_{i=1}^{N}\alpha_i(1-y_i(w^Tx_i + b)) \\ =& \frac{1}{2}w^Tw - w^Tw +\sum_{i=1}^{N}\alpha_i + \sum_{i=1}^{N}\alpha_iy_i b \\ =&\sum_{i=1}^{N}\alpha_i - \frac{1}{2}w^T w \\ =& \sum_{i=1}^{N}\alpha_i - \frac{1}{2}\sum_{j=1}^{N}\sum_{i=1}^{N}\alpha_i y_i \alpha_j y_j x_i^T x_j \end{align*}$

终于推导完成了！！！最后再将最大化求解等价转化为最小化问题求解即为定义2.6。它是个关于 $\alpha$ 的函数，即为一个二次规划问题，推荐大家一个软件，在做规划的时候非常实用，这个软件就是lingo啦。

定义2.6
$\min_{\alpha \geq 0} \frac{1}{2} \sum_{j=1}^{N}\sum_{i=1}^{N}\alpha_i y_i \alpha_j y_j x_i^T x_j - \sum_{i=1}^{N}\alpha_i$
细心的你应该发现了，上述推导过程中有一系列条件，来保证有解。这些条件合在一起即为KKT条件：

1. $y_i(w^T x_i + b) \geq1$
2. $\alpha \geq0$
3. $w= \sum_{i=1}^{N} \alpha_i y_ix_i$ , $\sum_{i=1}^{N}\alpha_iy_i =0$
4. $\alpha_i (1 - y_i(w^T x_i + b)) = 0$

超平面求解以及支持向量的解释

根据上面得到的 $\alpha$ ，我们可以反代回偏导数为0的式子中，求解 $| |w||$ 和 $b$ 即
$w= \sum_{i=1}^{N}\alpha_iy_ix_i$ ，其中 $b$ 的求解需要用到KKT条件中的第4个条件，当 $\alpha_i > 0$ 时，则 $b = y_i - w^T x_i$ ，对于不同的 $\alpha_i$ 会有不同的 $b$ 的估计值，所以一般最后对于 $b$ 的估计，会取这些估计值的平均值。
那么也就是说，在求解 $b$ 时，我们只用到了 $\alpha_i > 0$ 的那些点，而根据KKT条件，当 $\alpha_i > 0$ 时， $1 - y_i(w^T x_i + b)=0$ ，这些点均在分割线上，而这些点正是支持向量。