1. 概述

最基本的支持向量机(Support Vector Machine SVM)用于解决线性可分数据的二分类问题.

对于二维平面上的点,可以用一条线来分隔不同分类的点.如下图所示.
对于三维空间中的点,可以用一个面来分隔不同分类的点,对于四维及以上维度的点,用超平面来分隔不同分类的点.这里为便于叙述,将二维中的分隔直线,三维中的分隔面也统一称为超平面.

由上图很容易看出,能把蓝色和橙色点分开的超平面(这里是直线)有无数个. 那么哪一个才是最优秀的呢? 由图,不难直观的看出中间的绿色的线是最优解.绿色两侧的红色和蓝色的线,对于A点和B点的分类划分来说显得信心不足,因为A点和B点里超平面太近了. 回头看看中间的绿色的线,发现它与最近点之间的距离是最大的.

那么如何求的这条绿色的超平面呢?这就是支持向量机要解决的问题.

观察上图可知,最优解会让离超平面最近的点到超平面的距离最大. 假设这个超平面方程为

$$g(x)=\vec{w}^{\mathrm{T}}\vec{x} + b \tag{1}$$

将输入$\vec{x}$带入超平面方程计算出$f(x)$的值.

另外,再考虑函数:
$$
y=f(g(x)) =
\begin{cases}
\quad 1, & \text{$f(x) \ge 0$} \\
\;-1, & \text{$f(x) \lt 0$}
\end{cases}
\tag{2}$$
算出$f(x)$后带入y=$g(f(x))$结果为1时属于分类A,结果为-1则属于分类B.

2. 支持向量机算法及原理推导

2.1. 支持向量,距离与间隔的定义

定义 1 支持向量是指离超平面最近的点.

定义2 点到超平面的距离Distance(同济六版高等数学下册42页)
$$D =\frac{1}{\lVert w \rVert} \lvert \vec{w}^{\mathrm{T}}\vec{x} + b \rvert \tag{3}$$

定义3 离超平面最近的点与超平面之间的间隔Margin,其中$i = 1 \cdots N$,$N$是训练数据的总行数(下文中的$i$都具有同样的含义)

$$M = \underset{1 \cdots N}{\min}{\left ( \frac{1}{\lVert w \rVert} \lvert \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \rvert \right )} \tag{4}$$

2.2. 算法原理推导与建立数学模型

根据上述定义,可将上面的表述–使得离超平面最近的点到超平面的距离最大,用数学语言描述出来:

$$
\begin{cases}
\underset{\vec{w},b}{\max} \left[ \underset{1 \cdots N}{\min}{\left ( \frac{1}{\lVert w \rVert} \lvert \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \rvert \right )} \right ] \\
s.t. \quad y_i \left ( \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \right ) \gt 0
\end{cases}
\tag{5}$$

(5)式用人话表述出来就是: 在$N$个样本点(N行训练数据)中找到一个离超平面最近的点,然后求这个超平面的参数$\vec{w}$和$b$的值,使得这个点和这个超平面之间的距离是最大的,因为超平面可能又无数的,现在要求的就是这个最优的超平面.同时,这个超平面要满足限制条件(subject to) $y_i \left ( \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \right )$. 注意,这里$y_i = f(g(x_i))$的值要么为-1,要么为+1.

上述(5)式中的约束条件中,因为$y_i$与$\left ( \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \right )$ 总是同取正或者同负,因此有:

$$y_i \left ( \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \right ) = \lvert \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \rvert \tag{6}$$

注意到,上面(5)式中的$\underset{1 \cdots N}{\min}$是只跟$i$相关的,也就是说,求$\underset{1 \cdots N}{\min}$是在$\vec{w}$和$b$都定下来的时候进行的(因为求解分类器过程中,每一轮迭代都是先选定一个$\vec{w}$和$b$,然后再算距离这个超平面(是由$\vec{w}$和$b$确定的)最近的点的),因此可以将$\frac{1}{\lVert w \rVert }$移到$\underset{1 \cdots N}{\min}$外面来,同时将(6)式带入(5)式后就有:

$$
\begin{cases}
\underset{\vec{w},b}{\max} \left ( \frac{1}{\lVert w \rVert} \underset{1 \cdots N}{\min}{ \left [y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \right ]} \right ) \\
s.t. \quad y_i \left ( \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \right ) \gt 0
\end{cases}
\tag{7}$$

考察(7)式中的$\underset{1 \cdots N}{\min}{ \left [y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \right ]}$. 因为$y_i \left ( \vec{w_i}^{\mathrm{T}}\vec{x_i} + b \right ) \gt 0$,所以$\exists \; \gamma=\underset{1 \cdots N}{\min}{\left [y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \right ]}$成立. 这里$\gamma$就是每一次迭代选定了$\vec{w}$和$b$之后,到超平面的最近的距离.通过缩放$\vec{w}$和$b$,总是可以让这个最短距离变成单位距离1,即:

$$\gamma=\underset{1 \cdots N}{\min}{\left [y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \right ]}=1 \tag{8}$$

而缩放前后的超平面是同一个超平面,所以对整式子没有影响.

于是,将(8)式带入(7)式,就有:

$$
\begin{cases}
\underset{\vec{w},b}{\max} \frac{1}{\lVert w \rVert} \\
s.t. \quad \underset{1 \cdots N}{\min}{\left [y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \right ]}=1
\end{cases}
\tag{9}
$$

考察(9)式第2个式子,假如$a$最小值为1,则$a \ge 1$,即 $1-a \le 0$,于是(9)式等价于:

$$
\begin{cases}
\underset{\vec{w},b}{\max} \frac{1}{\lVert w \rVert} \\
s.t. \quad 1 – y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \le 0,\quad \small{\small{i=1\cdots N}}
\end{cases}
\tag{10}
$$

注意,这里的$\underset{\vec{w},b}{\max}$是针对$\vec{w}$和$b$的,即需要调整$\vec{w}$和$b$以便取得最大值.

一般地,数学书将求最大值$\max$问题转化成求最小值$\min$问题,因此${\max} \frac{1}{\lVert w \rVert}$可以转化成求$\min{\lVert w \rVert}=\vec{w}^\mathrm{T} \cdot \vec{w}$.为简化计算,乘以系数$\frac{1}{2}$得到(10)的等价形式:

$$
\begin{cases}
\underset{\vec{w},b}{\min} \; { \frac{1}{2} \vec{w}^\mathrm{T} \vec{w} } \\
s.t. \quad 1 – y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \le 0,\quad \small{\small{i=1\cdots N}}
\end{cases}
\tag{11}
$$

式(11) 即是支持向量机问题的数学模型,可见问题已经转换为N个约束(不等式约束)条件下,求多元函数的最小值问题 (同济六版高等数学113页),就是传说中的条件极值,拉格朗日乘子问题.

下面讨论如何求解该模型.

3. 支持向量机模型求解

3.1. 问题简化

根据(11)式,可以写出对应的拉格朗日辅助函数:

$$L(\vec{w},b,\lambda_i) = \frac{1}{2} \vec{w}^\mathrm{T} \vec{w} + \sum_{i=1}^N{\lambda_i \left[ 1 – y_i\left( \vec{w}\vec{x_i} + b \right ) \right]} \tag{12}$$

(12)式中的$\lambda$就是传说中的拉格朗日乘子.

NOTE: (12)式中的$\lambda_i > 0$. 因为在求此类在限制条件$u(x) \le 0$时求$v(x)$得最小值问题时,设求得得极小值点为$x$,这个极值点有两种情 况 :

1. 在$u(x)$所决定的区域内部(不包含边界)取得,此时限制条件失去影响,或者说总是满足,只要满足$v(x)$在点$x$的偏导数为0

2. 在$u(x)$所决定的区域外(包含边界)取得,这时在迭代求解过程中,$v(x)$要求最小值,所以$x$会逐渐往函数值减小得方向移动,同时对于$u(x)$来说,必定是从内部往边缘移动,即沿着函数值增大方向移动(即由$u(x) \lt 0$ 向$u(x) = 0$方向移动)所以$v(x)$在满足$u(x)$并取得最小值得的点$x$,两个梯度$\nabla u(x)$和$\nabla v(x)$必定反向.而由拉格朗日辅助函数求的连个梯度可以相互线性表示,即$\nabla v(x) + \lambda \nabla u(x) = 0$,于是$\nabla v(x) = – \lambda \nabla u(x)$,已知$\nabla u(x)$和$\nabla v(x)$必定反向(-号表示反向),则$\lambda_i > 0$必定成立.
   如下图所示:
   

结合看(11)和(12)式,(11)式中可以转化为:

$$
\begin{cases}
\underset{\vec{w},b}{\min} \;\underset{\lambda}{max} \; L(\vec{w},b,\lambda_i) \\
s.t. \quad \lambda_i \ge 0
\end{cases}
\tag{13}
$$

可以推得(11)式和(13)式同解.

因为$\underset{\lambda}{max} \; L(\vec{w},b,\lambda_i)$这一部分是将$\vec{w},b$看成常数的(因为每一个$\lambda_i$的比较都是在$\vec{w},b$已经定下来的前提下的),要求使得$L(\vec{w},b,\lambda_i)$在$s.t. \;\lambda_i \ge 0$则$1 – y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \gt 0$的这一部分$\vec{w},b$不能使得$L(\vec{w},b,\lambda_i)$收敛.当取最大的$\lambda$时这一部分取值为$+\infty$,这样$L(\vec{w},b,\lambda_i)$无法取得最小值.
于是,拉格朗日辅助函数$L(\vec{w},b,\lambda_i)$只能在$1 – y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \lt 0$取得最小值,在$s.t. \quad \lambda_i \ge 0$的条件下.

这样(12)式的第二部分实际上是一个正数$\lambda_i$和一个非正数$1- y_i(\vec{w}\vec{x_i} + b)$ 乘积的最大值,那么这个最大值只能为0.于是(13)和(11)是同解的.

这样,通过(13)问题的约束变成了对$\lambda$的约束,而对$\vec{x},b$的约束解除了.参考大神的B站视频从6:30开始的解释.

所以(13)式在拉格朗日的帮助下,去掉了(11)中的关于$\vec{w},b$约束,但是结果集确是和(11)式一样的,这就是变形到现在的目的…,容我先擦把汗.

3.2. 对偶问题

下面继续看(13)式上面的式子是一个$\min \; \max$问题,那么它的对偶问题就是一个$\max \min$问题,如下所示:

$$
\begin{cases}
\underset{\lambda}{max} \; \underset{\vec{w},b}{\min} \; L(\vec{w},b,\lambda_i) \\
s.t. \quad \lambda_i \ge 0
\end{cases}
\tag{14}
$$

比较(13)和(14),先有结论:

$$ \underset{\vec{w},b}{\min} \;\underset{\lambda}{max} \; L \ge \underset{\lambda}{max} \; \underset{\vec{w},b}{\min} \; \tag{15} L$$

这里略去数学证明,只从直观上解释,凤尾 $\gt$ 鸡头,即$\underset{尾}{\min} \; \underset{凤}{\max} \ge \underset{头}{\max} \; \underset{鸡}{\min}$.

(15)式在数学中叫做弱对偶关系. 我们寻找的是强对偶关系,即将(15)式中的$\ge$直接换成$=$关系.之所以能够这么转换,是因为我们求解的优化问题是凸优化问题,并且约束条件是线性的,这种问题就可以转成强对偶关系. 这个结论这里仅做了解,不去证明.

因此,由强对偶关系,(14)式是与(13)同解的.

3.3. 进一步转化/简化问题

(14)式中,先将$\lambda_i$看成常数,求$\underset{\vec{w},b}{\min} \; L(\vec{w},b,\lambda_i)$.这是一个二元函数的极值问题,解法见同济六版高等数学109页.

(12)式中,分别对$b,w$求偏导并令偏导$=0$可得:

$$\frac{\partial{L}}{\partial b} = -\sum_{i}^N \lambda_i y_i = 0 \Rightarrow \sum_{i}^N \lambda_i y_i = 0 \tag{16}$$

$$\frac{\partial L}{\partial w} = w – \sum_{i=1}^N \lambda_i y_i x_i = 0 \Rightarrow w = \sum_{i=1}^N \lambda_i y_i x_i \tag{17}$$

将(16)(17)式带入(12)式,可得$L$的最小值(省去中间过程):

$$\min L(\vec{w},b,\lambda) = – \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j x_i^\mathrm{T} x_j + \sum_{i=1}^N \lambda_i \tag{18}$$

将(18)带入(14)式,可得:
$$
\begin{cases}
\underset{\lambda}{max}\left ( – \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j x_i^\mathrm{T} x_j + \sum_{i=1}^N \lambda_i \right ) \\
s.t. \quad \lambda_i \ge 0, \; \sum_{i}^N \lambda_i y_i = 0
\end{cases}
\tag{19}
$$

去掉负号,进一步转换为$\min$问题有,
$$
\begin{cases}
\underset{\lambda}{min}\left ( \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j x_i^\mathrm{T} x_j – \sum_{i=1}^N \lambda_i \right ) \\
s.t. \quad \lambda_i \ge 0, \; \sum_{i}^N \lambda_i y_i = 0
\end{cases}
\tag{20}
$$

3.4. KKT条件

经过一步步推导换化,终于得到上面的(20)式, 要求解(20)式,还需要引入KKT条件.

简单来说,KKT条件是能解除函数$f(x)$在不等式约束$g(x) \le 0$下取得极小值时必须满足的条件(其中$L$是拉格朗日辅助函数),即:

$$
\begin{cases}
\nabla_x L = \nabla f + \lambda \nabla g = 0 \\
g(x) \le 0 \\
\lambda \gt 0 \\
\lambda g(x) = 0
\end{cases}
$$

可参考知乎上的解答.

NOTE: 原问题和对偶问题具有强对偶关系的充要条件是KKT条件同时成立.

回顾上面(12)式中支持向量机最优解的拉格朗日辅助函数,得到能求出最优解必须满足的KKT条件为:

$$
\begin{cases}
\frac{\partial L}{\partial \vec{w}} = 0,\; \frac{\partial L}{\partial b} = 0,\; \frac{\partial L}{\partial \lambda} = 0 \\
\lambda_i \left [ 1 – y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \right] = 0 \\
\lambda_i \ge 0 \\
1 – y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) \le 0
\end{cases}
\tag{21}
$$

有了上面的KKT条件,就可以求解$\vec{w}$和$b$了,实际上在(17)式中已经求出$\vec{w}$了.另外,根据(21)式中第二个条件(有个专门术语叫松弛互补条件slackness complementary)可求得$b$

(21)式中最后一个约束在求到极值时必定在边界上取得,所以不等式中的等号成立,于是可得:

$$
\begin{aligned}
&1 – y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) = 0 \\
&\Rightarrow y_i (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) = 1 \\
&\Rightarrow y_i^2 (\vec{w_i}^{\mathrm{T}}\vec{x_i} + b ) = y_i \\ & \because y_i^2 =1 \\
&\Rightarrow b = yi – \sum_{i=1}^N \lambda_i y_i x_i^\mathrm{T} x_i
\end{aligned}
$$

于是就得到

$$
\begin{cases}
w = \sum_{i=1}^N \lambda_i y_i x_i \\
b = y_i – \sum_{i=1}^N \lambda_i y_i x_i^\mathrm{T} x_i
\end{cases}
\tag{22}
$$

(22)式就是要求的最佳超平面的参数.

4. python实战代码

please stay tuned.

5. 参考

• 白板推导SVM

赞 赏

   微信赞赏  支付宝赞赏

本文固定链接: https://www.jack-yin.com/coding/ml/3145.html | 边城网事