机器学习笔记三：SVM支持向量机

铺垫

线性可分：

$$\text{点集}D_0,D_1,\text{对任意一点$x$有}:\\ \begin{aligned} &\omega^Tx+b\lt0,\quad x\in D_0\\ &\omega^Tx+b\gt0,\quad x\in D_1\\ \end{aligned}$$

称两个集合线性可分

最大间隔超平面：

能将两个线性可分的集合正确划分开的平面就是超平面：$\omega^Tx+b=0$

为了使这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。

• 两类样本分别分割在该超平面的两侧；
• 两侧距离超平面最近的样本点到超平面的距离被最大化了。

支持向量（Support Vector）：

样本中距离超平面最近的一些点，这些点叫做支持向量。

SVM最优化问题

找到一个最优超平面划分两类样本$y\in{1,-1}$。

对任意超平面：

$$\omega^Tx+b=0$$

任一点$x$到其上的距离为：

$$l=\frac{|\omega^Tx+b|}{||\omega||}$$

设支持向量到超平面的距离为$d$（为了便于区分），对样本集${x,y}$有：

$$\begin{cases} \frac{\omega^Tx+b}{||\omega||}\ge d,\quad y=1\\ \frac{\omega^Tx+b}{||\omega||}\le -d,\quad y=-1\\ \end{cases}$$

也就是

$$\Leftrightarrow\quad\frac{y(\omega^Tx+b)}{||\omega||}\ge d\\ \Leftrightarrow\quad\frac{y(\omega^Tx+b)}{d||\omega||}\ge 1\\$$

对支持向量${x’,y’}$有：

$$\frac{y'(\omega^Tx'+b)}{||\omega||}=d$$

我们的目标是在样本集中，选取最大的$d$，即

$$\max{d}$$

在此我们做一些处理：

$$\text{令$\omega'=\frac{\omega}{d||\omega||},b'=\frac{b}{d||\omega||}$}\\$$

探究一下距离会如何变换：

$$||\omega'||=\frac{||\omega||}{d||\omega||}=1/d\\ d'=\frac{y'(\omega'^Tx'+b')}{||\omega'||}=\frac{y'(\omega^Tx'+b)}{||\omega||}=d\\$$

发现并不影响距离。

那么我们可令：

$$d=\frac{1}{||\omega'||}$$

由此我们可以重写以上的优化问题：

$$\begin{cases} \max{\frac{1}{||\omega||}}\\ s.t\quad y(\omega^Tx+b)\ge 1\\ \end{cases}$$

其等价于

$$\begin{cases} \min{\frac{1}{2}||\omega||^2}\\ s.t.\quad y(\omega^Tx+b)\ge 1\\ \end{cases}$$

这就是最后我们要优化的约束问题。

拉格朗日数乘法

KKT条件

只看不等式的约束条件（无推导直接用）：

要优化：

$$\begin{cases} \min{f(x)}\\ s.t.\quad g_j(x)\le0,\quad j=1,2,\cdots,p(\text{不等式约束条件的个数})\\ h_k(x)=0,\quad k=1,2,\cdots,q(\text{等式约束条件的个数})\\ \end{cases}$$

KKT条件给出了判断$\pmb{x^*}$是否为最优解的必要条件，即：

$$L(x,\lambda,\mu)=f(x)+\sum_{j=1}^q{\mu_jg_j(x)}+\sum^p_{k=1}{\lambda_kh_k(x)}$$

若要求解上述优化问题，必须满足条件：

$$\begin{align} \frac{\partial L}{\partial\omega}|_{x=x^*}=0 \\ \lambda_j\neq0 \\ u_k\ge0 \\ u_kg_k(x^*)=0 \\ h_j(x^*)=0 \\ g_k(x^*)\le0 \\ \end{align}$$

其实都能解释的，只挑第四个必要条件解释，分两种情况：1：解在不等式约束条件外部，则可无视该不等式约束条件；2：解在不等式边界条件的边界上，此时不等式为0。

对偶化

$$\begin{cases} \min{\frac{1}{2}||\omega||^2}\\ s.t.\quad 1-y(\omega^Tx+b)\le 0\\ \end{cases}$$

假定有m个样本。

其拉格朗日数乘函数：

$$L(w,\mu)=\frac{1}{2}||\omega||^2+\sum^m_{k=1}\mu_k\left[1-y_k(\omega^Tx_k+b)\right]$$

要得：

$$\min_{\omega,b}{L}$$

可以先去go to

插入一个小插曲，其实很重要，但是可能会产生困扰，先在这打个标记

在这之前，插入一个对偶化，这一步可以暂时不看，推出超平面后可以回来看看。

我们记一个函数：

$$\Theta(\omega)=\max_{\mu}{L}$$

对任意点（不止是样本点）满足：

$$\begin{cases} \mu_k=\infty,\quad&1-y(\omega^Tx+b)>0\\ \mu_k\text{不变},\quad&1-y(\omega^Tx+b)\le0 \end{cases}$$

则

$$\Theta(\omega)=\max_{\mu}{L}= \begin{cases} \infty,\quad&1-y(\omega^Tx+b)>0\\ \frac{1}{2}||\omega||^2,\quad&1-y(\omega^Tx+b)\le0\\ \end{cases}$$

那么：

$$\min_{\omega}(\max_{\mu}{L})=\frac{1}{2}||\omega||^2$$

与我们的优化目标相同。

一般而言，有：

$$\min(\max)\ge\max(\min)$$

如果问题是凸优化问题，则有强对偶关系：

$$\min(\max)=\max(\min)$$

由此我们的优化问题可为：

$$\max_{\mu}(\min_{\omega,b}{L})$$

go to

由KKT条件：

$$\begin{cases} \frac{\partial L}{\partial\omega}=0\\ \frac{\partial L}{\partial b}=0\\ \end{cases}$$

又有：

$$\begin{aligned} \frac{\partial L}{\partial\omega}&=\omega-\sum^m_{k=1}\mu_ky_kx_k\\ \frac{\partial L}{\partial b}&=-\sum^m_{k=1}\mu_ky_k\\ \end{aligned}$$

解得：

$$\omega=\sum^m_{k=1}\mu_ky_kx_k\\ \sum^m_{k=1}\mu_ky_k=0\\$$

注意$\omega\in R^n$以及$x_i\in R^n$

有：

$$\begin{aligned} L&=\frac{1}{2}\omega^T\omega+\sum^m_{i=1}\mu_i\left[1-y_i(\omega^Tx_i+b)\right]\\ &=\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\mu_i\mu_jx_j^Tx_iy_iy_j+\sum^m_{i=1}\mu_i\left[1-y_i(\sum^m_{j=1}\mu_jy_jx_j^Tx_i+b)\right]\\ &=\sum^m_{i=1}\mu_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\mu_i\mu_jx_j^Tx_iy_iy_j \end{aligned}$$

还有未知系数$\mu_i$，此时可以回看小插曲。

有：

$$\max_{\mu}\left(\sum^m_{i=1}\mu_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\mu_i\mu_jx_j^Tx_iy_iy_j\right)\\ s.t.\quad\sum^m_{i=1}\mu_iy_i=0\\ \mu_i\ge0\\$$

好了只要解决最后这个问题就可以了。

SMO(Sequential Minimal Optimization) 算法求解

1. 选择需要更新的两个参数

   $$\mu_i,\mu_j$$

2. 固定其他参数，由等式约束条件解得

   $$\mu_iy_i+\mu_jy_j=c=-\sum^m_{k=1}\mu_ky_k=0(k\neq i,j)\\ \mu_j=\frac{c-\mu_iy_i}{y_j}$$

3. 对于仅有一个约束条件的最优化问题

   只要让对于其的导数为0即可，求出$\mu_i$

4. 多次迭代直至收敛。

最后可得：

$$\omega=\sum^m_{k=1}\mu_ky_kx_k\\$$

对任意一个支持向量$x_s$，都满足：

$$y_s(\omega^Tx_S+b)=1\\ b=y_s-\omega^Tx_s$$

当然，取均值最好。

决策

已经获得超平面，将其带入决策函数即可得样本的分类。

软间隔

实际中，完全线性可分的样本是很少的。那么我们可以允许一些样本落在隔离带内，即允许有部分样本：

$$1-y(\omega^Tx+b)>0$$

为了度量我们的松弛程度引入松弛变量

$$\xi_i\ge0$$

对每个样本：

$$1-y_i(\omega^Tx_i+b)-\xi_i\le0$$

由此，优化目标为：

$$\begin{cases} \min{\frac{1}{2}||\omega||^2}+C\sum^m_{i=1}\xi_i\\ s.t.\quad 1-y_i(\omega^Tx_i+b)-\xi_i\le0\\ \xi_i\ge0 \end{cases}$$

C为惩罚因子，越大对离群的样本惩罚就更大，也就是越不关注异常样本。

构造拉格朗日函数

由之前的强对偶化，可有：

$$\begin{aligned} \max_{\mu,\lambda}\left(\min_{\omega,b,\xi}\left\{\frac{1}{2}||\omega||^2+C\sum^m_{i=1}\xi_i+\sum^m_{i=1}\mu_i\left[1-y_i(\omega^Tx_i+b)-\xi_i\right])-\sum^m_{i=1}\lambda_i\xi_i\right\}\right) \end{aligned}$$

求导

有：

$$\omega=\sum^m_{k=1}\mu_ky_kx_k\\ \sum^m_{k=1}\mu_ky_k=0\\ C=\mu_i+\lambda_i$$

带回原函数

有：

$$\begin{aligned} L&=\sum^m_{i=1}\mu_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\mu_i\mu_jx_j^Tx_iy_iy_j+\sum^m_{i=1}(\mu_i+\lambda_i)\xi_i-\sum^m_{i=1}(\mu_i\xi_i+\lambda_i\xi_i)\\ &=\sum^m_{i=1}\mu_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\mu_i\mu_jx_j^Tx_iy_iy_j \end{aligned}$$

则无需最大化$\lambda$：

$$\max_{\mu}\left(\sum^m_{i=1}\mu_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\mu_i\mu_jx_j^Tx_iy_iy_j\right)\\ s.t.\quad\sum^m_{i=1}\mu_iy_i=0\\ \mu_i\ge0\\ C-\mu_i-\lambda_i=0\\$$

最后SMO优化即可

这边要注意一个问题，在间隔内的那部分样本点是不是支持向量？

我们可以由求参数$\omega=\sum^m_{i=1}\mu_iy_ix_i$ 的那个式子可看出，只要$\mu_i>0$ 的点都能够影响我们的超平面，因此都是支持向量。（？？）

核函数

我们刚刚讨论的硬间隔和软间隔都是在说样本的完全线性可分或者大部分样本点的线性可分。但我们可能会碰到的一种情况是样本点不是线性可分的。

把样本映射到高维空间去：

$$x'=\phi(x),y'=y$$

常见核函数

1. 线性核函数
2. 多项式核函数
3. 高斯核函数

优缺点

6.1 优点

• 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
• 能找出对任务至关重要的关键样本（即：支持向量）；
• 采用核技巧之后，可以处理非线性分类/回归任务；
• 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

6.2 缺点

• 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为$O(N^2)$ ，其中 N 为训练样本的数量；
• 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为$O(N^2)$ ；
• 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。

因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。

---

参考：
https://zhuanlan.zhihu.com/p/77750026