线性可分支持向量机

支持向量机系列导航

先验知识：

$a$ 向量在 $b$ 向量上的投影长度 $\frac{b\cdot a}{||b||}$
二次规划问题

模型引入

支持向量机是一种二类分类模型，基本模型是定义在特征空间上的“大间隔的分割超平面 ” (Large - Margin Separating Hyperplane)的线性分类器。什么意思呢？

以线性分类模型 PLA(感知机) 为例，其最终目标是找出一个超平面将所有的样本分割开（只要分开就行）。而支持向量机是在此基础上，保证离分割线最近的一些样本（ $x_n$ ）与超平面之间的距离（distance to closest $x_n$ ）尽量大。如下图，分别为PLA 和SVM学习得到的超分面

这使得对噪声的容忍度（amount of noise tolerance）更大，或者说该超平面鲁棒性（robustness of hyperplane）更强（more robust because of larger distance to closest x_n）

这样可以假设边界不是一条宽度不计的超平面，而是一个有宽度的胖超平面（fat hyperplane）如右图。这里的胖度实际上就相当于鲁棒性，即 $robustness ≡ fatness$

那么现在的目标就是找出那个最胖的一个超平面 $h(x)=w^Tx + b$ （fattest separating hyperplane）使得该超平面讲所有的大数据正确分类。如下公式描述

\begin{equation*}\begin{align*} \max _{\mathbf{w,b}}: &\text { fatness }(\mathbf{h})\\ \text { subject to} : \:&\mathbf{h}\text { classifies every }\left(\mathrm{x}_{n}, y_{n}\right) \text { correctly }\\ &\text { fatness }(\mathbf{h})=\min _{n=1, \ldots, N} \operatorname{distance}\left(\mathbf{x}_{n}, \mathbf{h}\right)\end{align*}\end{equation*}

所以就有两个问题：

如何定义超平面有多胖
如何定义该超平面能否正确分类

对于问题1，超平面有多胖就是看距离超平面最近的数据点到超平面有多近。对于问题2， $h(x_n)$ 与 $y_n$ 符号是否一致可以表示分类是否正确，所以可以用 $y_nh(x_n)>0$ 来表示分类的准确性。

至此将胖的超平面正式叫做间隔（margin），据此将上式改写为：

\begin{equation*}\begin{aligned}\max _{\mathbf{w,b}} &\;\; \operatorname{margin}(\mathbf{h}) \\\text { subject to} &\;\;\; y_{n} \mathbf{w}^{T} \mathbf{x}>0 \\&\;\; \operatorname{margin}(\mathbf{h})=\min _{n=1, .,, N} \operatorname{distance}\left(\mathbf{x}_{n}, \mathbf{w,b}\right)\end{aligned}\end{equation*}

转化为最优化问题

根据点到超平面的距离公式，可知

\text{distance}(x_n, w,b)) = \frac{|w^Tx_n+b|}{||w||}

基于超平面 h(x) ，若该超平面能正确分类，则所有的点均满足 $h(x_n)y_n =( w^Tx_n +b)y_n > 0$ , 所以 distance公式可以变换成如下：

\operatorname{distance}(x, b, w)=\frac{1}{\|w\|} y_{n}\left(w^{T} x_{n}+b\right)

注：此处本质原因是为了去掉距离公式的绝对值。可以直接乘 $y_n$ 一方面是因为二分类问题 $y_n$ 本来就等于正负1；另一方面原因是因为此处的距离乘上一个正数只是相当于起到了放缩作用，对最后结果不影响

此时，目标函数转换为如下：

\begin{aligned}\max _{b, \mathbf{w}} \;\;\;& \operatorname{margin}(b, \mathbf{w}) \\\text { subject to }\;\;\; & \text { every } y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right)>0 \\& \operatorname{margin}(b, \mathbf{w})=\min _{n=1, \ldots, N} \frac{1}{\|\mathbf{w}\|} y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right)\end{aligned}

缩放margin, 我们知道超平面 $w^Tx + b = 0$ 和 $3w^Tx + 3b = 0$ 是同一个超平面，也就是说，对 $w$ 和 $b$ 同时进行缩放还会得到同一超平面。

那么假设超平面距离最近的点之间的距离的分子 $y_n(w^Tx_n + b)=k$ ,此时可对等号两边同时缩小k倍。即我们将 $w$ 和 $b$ 进行缩放，令距离超平面最近的点满足 $y_n(w^Tx_n + b) = 1$ 。即

\begin{align*} \min _{n=1, \cdots, N} y_{n}\left(\mathbf{w}^{T} \mathbf{x}+b\right)=1 \end{align*}

此时，对所有的数据点则会满足如下公式，亦为约束条件1

\begin{equation*}y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq 1 \text { for all } n\end{equation*}

缩放之后，约束条件2有如下转换：

\begin{align*}&\operatorname{margin}(b, \mathbf{w})=\min _{n=1, \ldots, N} \frac{1}{\|\mathbf{w}\|} y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right)\\ \implies& \\ &\text{margin(b,w)} = \frac{1}{||w||} \\ \end{align*}

至此，优化问题的目标函数转为

\text{max} \;\; \frac 1{\|w\|}

最终，优化问题可以转换为如下：

\begin{equation*}\begin{aligned}&\min _{b, w} \;\;\;\frac{1}{2} w^{T} w\\&\text { s.t. } \quad y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq 1 ,n=1,2,..,N\end{aligned}\end{equation*}

对上式可以有如下直观理解：

转换为二次规划问题

因为SVM的目标是关于 $w$ 的二次函数，约束是关于 $w$ 和 $b$ 的一次函数。这是一个典型的二次规划问题，即Quadratic Programming（QP）。通常可以使用软件自带的二次规划的库函数来求解。下图给出SVM与标准二次规划问题的参数对应关系，左边为SVM优化问题，右边为二次规划标准形式。

所以，线性SVM算法可以总结为三步：

计算对应的二次规划参数 $Q，p，A，c$
根据二次规划库函数，计算 $b，w$
将 $b$ 和w代入 $g_{SVM}$ ，得到最佳超平面

总结

对输入数据集 $T = \{ (x_1,y_1), (x_2, y_2),\cdots (x_N, y_N)\}$ , 其中 $x_i \in X=R^n, y_\in\ \{-1, +1\}, i=1,2,\cdots,N$ .如下图

SVM目标是找到一个超平面，该超平满足如下要求：

首先能正确的分来两类数据
其次是距离两类最近数据点的距离最大，可以理解为该超平面最胖

空间中超平面可以表示为

h(x) = w^Tx+b

空间中任意一点 $x_i$ 到该超平面的距离

\text{distance}(x_i, h) = \frac{|w^Tx_i + b|}{\|w\|}

根据上述对超平面的要求，可以转为如下优化问题：

\begin{equation*}\begin{aligned}\max _{\mathbf{w,b}} \;\;\;& \operatorname{margin}(\mathbf{w,b}) \\\text {s.t. } \;\;\;& y_{n} (\mathbf{w}^{T} \mathbf{x}+b)>0 \\& \operatorname{margin}(\mathbf{w,b})=\min _{n=1, .,, N}\frac{|w^Tx_n+b|}{\|w\|} \end{aligned}\end{equation*}

对约束2去绝对值可得

\begin{aligned}\max _{b, \mathbf{w}} \;\;\;& \operatorname{margin}(b, \mathbf{w}) \\\text { subject to }\;\;\; & \text { every } y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right)>0 \\& \operatorname{margin}(b, \mathbf{w})=\min _{n=1, \ldots, N} \frac{1}{\|\mathbf{w}\|} y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right)\end{aligned}

假设距离超平面最近的点 $x_k$ 满足 $y_k(w^Tx_k+b) = k$ ,此时对 $w,b$ 进行缩放，使得

\begin{align*}&y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq 1 \;\;\text{对所有的数据点} \\ &y_n\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) = 1 \;\;\text{对距超平面最近的数据点}\end{align*}

此时，

\text{margin}(w,b) = \frac1 {||w||}

因此优化问题可以转换为

\begin{equation*}\begin{aligned}&\min _{b, w} \;\;\;\frac{1}{2} w^{T} w\\&\text { s.t. } \quad y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \geq 1 \end{aligned}\end{equation*}

上述问题为凸二次规划问题。

📌

先从最大间隔出发，写出SVM的目标（间隔最大）及约束（能正确分类），然后对距离公式去绝对值，再然后对 $w,b$ 缩放使得边界上的点满足 $y_i(wTx_i)+ b = 1$ ，然后就可以简化优化问题为凸二次规划