支持向量机

机器学习之支持向量机

2019-02-20  本文已影响0人  Athenaearl

假设我们有两组数据都是只有两个特征：


数据

这两个特征分别成为一个坐标轴，那么每一个样本在图像中表现出来的都是坐标系中的一个点

超平面

如果这个分类不能在这个维度上用平面或者直线进行划分，那么就用高一维度的空间进行划分。
比如：


一维

我们不可能直接在一维用一个点将两种颜色的小球划分开
但是在二维


二维
我们很轻松的可以用一条直线将两者分开

这条直线就可以称为是超平面。如果读者认为将一条线称为是超平面有点难以理解。
那么一个二维的用一条直线不能很好划分的问题，可以在三维用一个平面来划分。这个平面也是一个超平面。

支持向量机的基本型

由以上的描述我们可以看出来，一切线性不可分问题都可以通过提高维度而变得线性可分
那么现在我们开始谈一谈线性的问题

我们希望用一个简化的形式来表现多维的线性方程
因此用矩阵的方式来完成，因此：
w^Tx+b = 0
w=[w_1, w_2, w_3,...]
x=[x_1, x_2, x_2,...]
相信大家高中都有学过，点到直线距离公式：
r = \frac{|kx+b|}{|k|}
这里更新为：
r = \frac{|w^Tx+b|}{||w||}
这里的w^Tx+b 在线的一侧为正，在线的另一侧为负
r = \frac{w^Tx+b}{||w||} 这样就同时表现了相对于直线的方向和距离
一条直线将空间分成了两类，因此类别y_i = 1 或者 -1 代表第i个样本是这一类还是另一类，至于为什么是1和-1 而不是 像以前一样的 0和-1 ，这是为了表达上的简洁，后期会说明为什么这样设定表达上会简洁
我们设定在w^Tx+b>0这一面的类别为1，w^Tx+b<0这一面的类别为-1, 即:
\begin{cases} w^Tx_i+b>0, & y_i = 1\\ w^Tx_i+b<0, & y_i = -1 \end{cases}
但并不是说只有一条直线可以将样本进行划分，就像开头的第一张图一样，会有两个支持面，而两个支持面正中央的线是最优的划分
假设 两个支持面之间的距离为2d, 即最优面到支持面之间的距离为d
那么，上面的式子可以进一步改写为：
\begin{cases} r_i\ge d, & y_i = 1\\ r_i\leq -d, & y_i = -1 \end{cases}
也就是：
\begin{cases} \frac{|w^Tx_i+b|}{||w||}\ge d, & y_i = 1\\ \frac{|w^Tx_i+b|}{||w||}\leq -d, & y_i = -1 \end{cases}
左右两边同除d
得到：
\begin{cases} w^T_{new}x_i+b_{new}\ge 1, & y_i = 1\\ w^T_{new}x_i+b_{new}\leq -1, & y_i = -1 \end{cases}
其中：
w^T_{new} = \frac{w^T}{||w||d}
b_{new} = \frac{b}{||w||d}

我们可以注意到,对于w^Tx+b = 0来说将w^T和 b用 w^T_{new} 和 b_{new} 对于原方程完全没有影响

因此后面所指的w^T 和 b 指的是w^T_{new} 和b_{new}
方程式为：w^Tx+b = 0
样本满足条件为：\begin{cases}w^Tx_i+b\ge 1, & y_i = 1\\ w^Tx_i+b \leq -1, & y_i = -1\end{cases}

这个时候就表现出了 分类时候用 -1 和 1 来表示的优势了
因为以上样本满足的条件可以写成为：
y_i(w^Tx_i+b)\ge 1

可以注意到以上的操作我们都是只是在一个确定方向上寻找最优面
但是我们怎样找到一个最优的方向呢

我们的想法是：在这个方向上的支持面距离越大，说明在这个方向上两个样本分得更"开"，也就说明这个方向的划分更优
因此使得两个支持面距离最大的方向就是最优方向
也就是说使得2d最大的方向就是最优方向
d是同方向上的最优面到支持面的距离，因此：
d = \frac{|w^Tx+b|}{||w||}
而由于我们以上的更新操作，可以看出，支持面上的样本满足:w^Tx+b = 1
因此d = \frac{1}{||w||}
我们想要 2d 最大，也就是想要 d 最大
也就是||w|| 最小
相信大家对于让某一个向量的模最小的处理方式已经不陌生了，一般都是做平方处理，同时，为便于求导，除以2
也就是支持向量机的基本型：
在满足y_i(w^Tx_i+b)\ge 1的情况下（i = 1, 2, 3,...,m），尽力让\frac{1}{2} ||w||^2达到最小
支持向量机的基本型是一个凸二次规划问题

凸二次规划问题

凸函数：
如果一个函数上任意两个点之间的连线上的中间点高于对应横坐标的函数上的点就称为凸函数：
数学表达：f(\frac{x_i+x_j}{2}) \leq \frac{f(x_i)+f(x_j)}{2}

凸二次规划问题：
用于表示一类问题：约束条件为线性不等式，求一个凸二次函数的最小值问题
一般形式为：
满足w^Tx \leq b的情况下
求\frac{1}{2}x^TQx+c^Tx的最小值
对于这种有约束条件的求极值问题：
有一种很好的解决手段：拉格朗日乘子法

拉格朗日乘子法与KKT条件

拉格朗日乘子法是一种处理有约束条件的极值问题非常常用的手段
等式约束条件：
约束条件: h(x_1, x_2,..) = 0
要求的极值：g(x_1, x_2,...)
那么L(x_1,x_2,...,\lambda) = g(x_1, x_2, ...) + \lambda h(x_1, x_2,...)
对于各个参数进行求导并让结果等于0：
\frac{\partial g(x_1, x_2,..)}{\partial x_1} + \lambda \frac{\partial h(x_1, x_2,...)}{\partial x_1} = 0
\frac{\partial g(x_1, x_2,..)}{\partial x_2} + \lambda \frac{\partial h(x_1, x_2,...)}{\partial x_2} = 0
....
且 \lambda \ge 0
所有条件这些条件最后能够求出结果
不等式约束条件：
这种情况就是我们在这里需要解决的情况
我们有很多的不等式约束h_i(x) \leq 0
也可以有等式约束：k(x) = 0
求 g(x) 的极值
解决方法还是使用拉格朗日乘子法：
L(w_1, w_2,..,a,x) = g(x) + w_1 h_1(x) + w_2 h_2(x)....a*k(x)
(w_1, w_2, w_3...\ge 0)
这个时候：最优解满足KKT条件
KKT条件：
L(w_1, w_2,...,x) 对 x 求导为0
w_i h_i(x) = 0
k(x) = 0
并且有 h_i(x) \leq 0 的已知条件
然后正常使用拉格朗日乘子法就可以解决问题

对偶问题:
对于不等式约束条件的处理方式正常来说，以上就可以解决问题了，但是有的时候，由于方程难解，就会利用对偶的性质
由L(w_1, w_2,..,a,x) = g(x) + w_1 h_1(x) + w_2 h_2(x)....ak(x)
易知：g(x) = max_{w_1,w_2,..a}(L(w_1, w_2, w_3, ..,a, x))
因为:
对于满足条件的x来说 h_i(x) \leq 0 且 w_i \ge 0 因此 w_i h_i(x) \leq 0 要想达到最大，只有让w_i = 0
而k(x) = 0, 因此 g(x) = max_{w_1,w_2,..a}(L(w_1, w_2, w_3, ..,a, x))

而不要忘了我们的目标是要求g(x)的最小值，即min_{x}(g(x))
也就是min_{x}(max_{w_1, w_2, w_3,...a}L(w_1, w_2, w_3,...a, x))

它的对偶性质在于 只要 L(w_1, w_2,...,a,x)满足KKT条件：
min_{x}(max_{w_1, w_2, w_3,...a}L(w_1, w_2, w_3,...a, x)) = max_{w_1, w_2, w_3,...a}(min_x(L(w_1, w_2, w_3, ...a,x)))

继续计算

有了以上的知识储备
我们回顾一下，支持向量机的基本型是：
在满足y_i(w^Tx_i+b)\ge 1的情况下（i = 1, 2, 3,...,m），尽力让\frac{1}{2} ||w||^2达到最小
在满足KKT条件的情况下，可以使用拉格朗日乘子法 可以使用对偶性质：
也就是说，我们可以从求
min_{w, b}(max_{\alpha}L(w,b,\alpha))
变成求：
max_{\alpha}(min_{w, b}L(w,b,\alpha))

先开始求min_{w, b}L(w,b,\alpha):
L(w,b,\alpha) = \frac{1}{2}||w||^2 + \sum_{i = 1}^{m}\alpha_i(1-y_i(w^Tx_i + b))
\frac{\partial L(w,b,\alpha)}{\partial w} = w - \sum_{i = 1}^{m}\alpha_iy_ix_i = 0
\frac{\partial L(w,b,\alpha)}{\partial b} = -\sum_{i = 1}^{m}\alpha_iy_i = 0
将w和b消掉，因数只有\alpha：
L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j（*）
并满足：\sum_{i = 1}^{m}\alpha_iy_i = 0

然后求max_{\alpha}L(\alpha):
由KKT条件可知：
\alpha_i(1- y_i(w^Tx_i+b)) = 0 (i = 1, 2, 3,....,m)
还有已知条件：
\alpha_i \ge 0
y_i(w^Tx_i + b) \leq 1

因此：
可以分为 \alpha_i = 0 和 1-y_i(w^Tx_i+b) = 0 两种情况
但显然，如果\alpha_i = 0 代表第i个样本没有起到约束作用
因此1-y_i(w^Tx_i+b) = 0
由\sum_{i = 1}^{m}\alpha_iy_i = 0
设 f(x_i) = w^Tx_i+b
那么 y_if(x_i) = 1
也就是说对于\alpha_i \ne 0 的样本来说，y_if(x_i) = 1
由此可见，只有在支持面上的样本才起到了约束作用

修正

以上的一切推导我们都基于了一个想法：一切线性可分问题都是百分百的线性可分，但是大部分的实际情况，即使这个问题可以用线性的方式分类，即使我们找到了非常好的分割函数，我们仍然避免不了会有错误分类的样本，因此我们推导不得不对于这种情况表现出一定的容忍度。
因此，要对于以上的推导进行修正
引入参数：

也就是支持向量机的基本型更新为：
在满足y_i(w^Tx_i+b)+ \xi_i\ge 1和 \xi_i \ge 0的情况下（i = 1, 2, 3,...,m），尽力让\frac{1}{2} ||w||^2 + C\sum_{i = 1}^m \xi_i达到最小

那么:L(w, \alpha, b,\xi, \mu) = \frac{1}{2} ||w||^2 + C\sum_{i = 1}^m \xi_i + \sum_{i = 1}^m \alpha_i(1-(y_i(w^Tx_i+b)+ \xi_i))-\sum_{i =1}^m \mu_i \xi_i
同样的更新方法：
分别对w,b,\xi_i进行求导：
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(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j（*）
并满足：\sum_{i = 1}^{m}\alpha_iy_i = 0
但是不同于之前要求0 \leq \alpha_i 这里要求 0 \leq \alpha_i \leq C
根据KKT条件：
\alpha_i \ge 0, \mu_i \ge 0, \xi_i \ge 0
y_if(x_i) -1 + \xi_i \ge 0
\alpha_i(y_if(x_i) - 1 + \xi_i) = 0
\mu_i \xi_i = 0

对于第i个样本：
如果\alpha_i = 0 说明这个样本对于f(x) 没有任何影响
如果y_if(x_i) - 1 + \xi_i = 0 说明这个样本是支持向量

根据：C = \alpha_i + \mu_i
可知：
如果C > \alpha_i, \mu_i > 0 因此 \xi_i = 0 样本恰在最大分隔边界上
如果C = \alpha_i, \mu_i = 0 :

SMO算法

前面已经介绍过了什么是二次规划问题
因此我们可以看出，我们的后期推导出来的形式：
L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j（*）
并满足：\sum_{i = 1}^{m}\alpha_iy_i = 0
这种形式，仍然是一个二次规划问题

而SMO算法是一种解决二次优化问题的常用手段，基本思想是：先认为有两个参数是变量，并认为其他参数为常数值，对这两个变量做更新

下面我们就要用SMO算法解决问题：
由：\sum_{i = 1}^{m}\alpha_iy_i = 0 a_i' 和a_j' 为更新之后的结果
可以看出来，如果我们只认为一个参数\alpha_i为变量，其余都为常量的话，\alpha_i的值会被直接推导出来，而非给出一种关系
因此，我们会认为有两个变量\alpha_i和\alpha_j
由：\sum_{i = 1}^{m}\alpha_iy_i = 0
\alpha_i y_i + \alpha_j y_j = \zeta = \alpha_i'y_i + \alpha_j'y_j \zeta 代表常数
由上面的：0 \leq \alpha_i \leq C
另y_i 和 y_j分别为1 和-1
则\alpha_i' - \alpha_j'=\zeta
因此从这里计算得到-\zeta \leq \alpha_j' \leq C-\zeta
本身有的限制0 \leq \alpha_j' \leq C
因此下界为：max(0, -\zeta)
上界：min(C, C-\zeta)
因此取值范围如下：

图片来源自https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

同理：
如果y_i = 1, y_j = 1
取值范围如下

https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

因此：L 表示上界 H 表示下界
\begin{cases} L = max(0, \alpha_j-\alpha_i),& H = min(C, C + \alpha_i-\alpha_j), & y_i \ne y_j\\ L = max(0, \alpha_i+ \alpha_j - C), & H = min(C, \alpha_i + \alpha_j), & y_i = y_j \end{cases}

L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j（*）
并满足：\sum_{i = 1}^{m}\alpha_iy_i = 0
\alpha_r y_r + \alpha_o y_o = -\sum_{k \ne r, o}^{m} \alpha_k y_k(常数)
\alpha_r y_r y_o + \alpha_o y_o^2= 常数
\alpha_r y_o y_r + \alpha_o =常数

设s = y_i y_j
设s\alpha_r + \alpha_o =D（常数）
所以： \alpha_o = D - s \alpha_r

由：L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j（*）
将 \alpha_o = D - s \alpha_r 带入，并对\alpha_r 求偏导

为了以下的推导方便，以上选择的i和j，用o和r代替，\alpha_o 和 \alpha_r 为旧参数，\alpha_o' 和 \alpha_r' 为新参数

暂时更新到此

参考：

上一篇 下一篇

猜你喜欢

热点阅读