# SVM 支持向量机(Support Vector Machine)(Part 1) -- 潘登同学的Machine Learning笔记

SVM 支持向量机

支持向量机(Support Vector Machine, SVM)本身是一个二元分类算法，是对感知器算法 模型的一种扩展，现在的 SVM 算法支持线性分类和非线性分类的分类应用，并且也能够直 接将 SVM 应用于回归应用中，同时通过 OvR 或者 OvO 的方式我们也可以将 SVM 应用在 多元分类领域中。在不考虑集成学习算法，不考虑特定的数据集的时候，在分类算法中 SVM 可以说是特别优秀的。

感知器模型

感知器模型寻找的就是一个超平面，能够把所有的二元类别分割开。感知器模型 的前提是：数据是线性可分的;

对于 m 个样本，每个样本 n 维特征以及一个二元类别输出 y

找到一个超平面

$$\theta_0 + \theta_1x_1 + \ldots + \theta_nx_n = 0\\ 即 \theta X = 0$$

• 使得这个超平面能把样本分为两类
  $$y= sign(\theta X)=\begin{cases} +1, \theta X > 0\\ -1, \theta X < 0 \end{cases}$$

构建Loss函数

根据上面的模型, 可以定义

正确分类 : $y\times\theta X>0$

错误分类 ：$y\times\theta X<0$

则可以定义Loss函数为: 期望使分类错误的所有样本到超平面的距离之和最小(MLR
也是类似的, 使残差平方和最小; 而logistics也是找一个超平面， 但是是用sigmoid来将线性结果映射到0-1赋予概率含义)；

• 计算样本到超平面的距离

二维平面的点到直线的距离公式:
$$d(x_i, y_i) = \frac{|ax_i+by_i+c|}{\sqrt{a^2+b^2}}$$

推广到高维：
$$d(X) = \frac{|w^TX+b|}{\lVert w \rVert_2}=\frac{|w^TX+b|}{\sqrt{w^Tw}}$$

注意： 这个$\lVert w \rVert_2$表示的是w的二范数(向量的模长), 就是各个分量平方求和再开方;

几何距离和函数距离

• 对于那些分类正确的点(y0与$w^TX+b$同号)

可以将距离表示为
$$d(X) = \frac{y(w^TX+b)}{\lVert w \rVert_2}$$

这个称为某点到平面的几何距离；

分子部分称为某点到平面的函数距离;

• 对于那些分类错误的点(y0与$w^TX+b$异号), 根据Loss函数，可表示为
  $$Loss = \sum_{i=1}^{m}\frac{-y_i\theta x_i}{\lVert \theta \rVert_2}$$

而根据线性代数，这不就是向量单位化嘛，用单位化后的向量代替$\theta$:
$$\theta' =\frac{\theta}{\lVert \theta \rVert_2}$$

• Loss函数改写成
  $$Loss = -\sum_{i=1}^{m}y_i\theta' x_i$$
• 对Loss求导, 梯度下降求解
  $$\frac{\partial{Loss}}{\partial{\theta}} = -\sum_{i=1}^{m}y_i x_i$$

注意：由于这里的 m 是分类错误的样本点集合，不是固定的，所以我们不能使用批量梯度下降法(BGD)求解，只能使用随机梯度下降 (SGD)或者小批量梯度下降(MBGD)；一般在感知器模型中使用 SGD 来求解

SVM 算法思想

• 总目标：分类

SVM 也是通过寻找超平面，用于解决二分类问题的分类算法

• 模型：与感知机相同
  $$y= sign(\theta X)=\begin{cases} +1, \theta X > 0\\ -1, \theta X < 0 \end{cases}$$

感知机是通过判错的点寻找超平面，逻辑回归是通过最大似然寻找超平面，SVM 是通过支持向量寻找超平面

• 优化目标

感知机和逻辑回归是直接最小化损失函数来得到θ，或者叫 W 和 b
SVM 有两种求解 方式，一种是直接最小化损失函数来得到θ，另一种先寻找支持向量，找到支持向量超平面就自然找到了

一个问题?

考虑下面的两个超平面, 哪个更好？

在感知器模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都离超平面尽可能的远，但是实际上离超平面足够远的点基本上都是被正确分类的， 所以这个是没有意义的；反而比较关心那些离超平面很近的点，这些点比较容易分错。

假设未来拿到的数据含有一部分噪声，那么不同的超平面对于噪声的容忍度是不同的， 最右边的线是最robust 的。

• 换一种角度考虑，找到最胖的超平面

所以我们总结一下, 让离超平面比较近的点尽可能的远离这个超平面；

几个概念

• 线性可分(Linearly Separable)

在数据集中，如果可以找出一个超平面，将两组数据分开，那么这个数据集叫做线性可分数据。

• 线性不可分(Linear Inseparable)

在数据集中，没法找出一个超平面，能够将两组数据分开，那么这个数据集就叫做线性不可分数据。分割超平面(Separating Hyperplane)：将数据集分割开来的直线/平面叫做分割 超平面。

• 间隔(Margin)

数据点到分割超平面的距离称为间隔。

• 支持向量(Support Vector)

离分割超平面最近的那些点叫做支持向量。

硬间隔SVM

• 前提：

数据线性可分

• 目标:
  • 硬间隔最大化
  • 能够完美分类正负例
  • 距离最近的点越远越好

转换成有约束的函数优化问题:

$$\max_{w,b}d_{min} = \frac{y_{min}(wx_{min}+b)}{\lVert w \rVert_2}(下标min表示距离最近的点--支撑向量)\\ s.t \qquad d_i = y_i(w^Tx_i+b) \geq \gamma' (\gamma是支撑向量的函数距离)$$

而对于该超平面:
$$b + w_1x_1 + w_2x_2 + \ldots + w_nx_n = 0$$

将w与b同时放缩, 整个超平面其实是不变的, 所以一个超平面对应无数组w,b；
我们现在设定一个标准， 就是把距离最近的点的函数距离设为1, 也就是

$$\gamma' = y_{min}(wx_{min}+b)=1$$

所以优化目标变为:
$$\max_{w}d_{min} = \frac{a}{\lVert w \rVert_2}\\ s.t \qquad d_i = y_i(w^Tx_i+b) \geq 1$$

等价为:
$$\min_{w} \frac{1}{2}\lVert w \rVert_2^2\\ s.t \qquad d_i = y_i(w^Tx_i+b) \geq 1$$

拉格朗日乘子法-求解有约束最优化问题

先介绍拉格朗日乘子法和对偶问题

拉格朗日乘子法

对于带约束问题的最优化问题
$$\min_{c\in \bf{R}^n} f(x)\\ \begin{aligned} s.t \qquad & c_i(x) \leq 0 , i=1,2, \ldots, k \\ & h_j(x) = 0 , j=1,2,\ldots, l \end{aligned}$$

定义原始最优化问题的拉格朗日函数为

$$L(x,\alpha,\beta) = f(x) + \sum_{i=1}^{k}\alpha_i c_i(x) + \sum_{i=1}^{k}\beta_j h_j(x)$$

其中$\alpha_i、\beta_j$都是拉格朗日乘子

• 令$\theta_p(x) = \max_{\alpha\geq 0,\beta}L(x,\alpha,\beta)$

若x不满足之前的约束条件：

• 如$h_j(x) \ne 0$
  那么只要$\beta$无穷大(且与h_j(x)同号), 那么结果就无穷大

• 如$c_i(x) > 0$
  那么只要$\alpha$无穷大, 那么结果就无穷大

若x满足之前的约束条件：
那么
$$\theta_p(x) = f(x) (因为h_j(x)=0不影响\theta_p(x)，而c_i(x)\leq0，只要\alpha=0也不影响\theta_p(x))$$

• 总的来说
  $$\theta_p(x)= \begin{cases} f(x), & x满足约束条件 \\ +\infin, & x不满足约束条件\\ \end{cases}$$

那么对$\theta_p(x)$进行极小化,将相当于对原始最优化问题进行极小化，
$$\min_x\theta_p(x) = \min_x\max_{\alpha\geq 0,\beta}L(x,\alpha,\beta)$$

定义原始问题最优解
$$P^* = \min_x\theta_p(x)$$

注意： 这里没有拉格朗日乘子法的详细解释和原理剖析, 详细的还得去百度百科

对偶问题

定义:
$$\theta_D(\alpha, \beta) = \min_x L(x,\alpha, \beta)$$

此时极大化$\theta_D$：
$$\max_{\alpha\geq 0,\beta}\theta_D(\alpha, \beta) = \max_{\alpha\geq 0,\beta}\min_x L(x,\alpha, \beta)$$

称为拉格朗日的极大极小问题，也称为原始问题的对偶问题;

定义对偶问题的最优解:
$$d^* = \max_{\alpha\geq 0,\beta}\theta_D(\alpha, \beta)$$

当$f(x)和C_i(x)函数为凸函数, h_j(x)为仿射函数时$, 有：
$$P^*=d^*=L(x^*,\alpha^*,\beta^*)$$

(也就是对偶问题与原问题的解一致)

• 仿射函数

从$\mathbb{R}^n到\mathbb{R}^m$的映射$x \mapsto\bf{A} x+b$,称为仿射映射， 其中A是一个$m\times n$ 矩阵，b 是一个 m 维向量， 当m为1时， 上述仿射变换为仿射函数；

• 如何求解上述的拉格朗日函数及他的对偶函数?

KKT条件
$$\begin{cases} \nabla_xL(x^*,\alpha^*,\beta^*)=0, & \alpha_i^*C_i(x^*)=0, i=1,2,\ldots, k \\ \nabla_{\alpha}L(x^*,\alpha^*,\beta^*)=0, & C_i(x^*)\leq0, i=1,2,\ldots, k \\ \nabla_{\beta}L(x^*,\alpha^*,\beta^*)=0, & \alpha_i(x^*)\geq0, i=1,2,\ldots, k \\ &h_j(x^*)=0, i=1,2,\ldots, l \\ \end{cases}$$

求解最优化问题-硬间隔

• 原始问题：
  $$\min_{w} \frac{1}{2}\lVert w \rVert_2^2\\ s.t \qquad d_i = y_i(w^Tx_i+b) \geq 1$$

• 构建拉格朗日函数：
  $$L(w,b, \alpha) = \frac{1}{2}\lVert w \rVert_2^2 - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b)-1] (\alpha_i\geq 0)$$

• 可将原始有约束的最优化问题转换为对拉格朗日函数进行无约束的最优化问题（也叫二次规划问题）
  $$\min_{w,b}\max_{\alpha\geq0}L(w,b, \alpha)$$

由于我们的原始问题满足 f(x)为凸函数，那么可以将原始问题的极小极大优化转换为对偶函 数的极大极小优化进行求解：

• 对偶函数为：
  $$\max_{\alpha\geq0}\min_{w,b}L(w,b, \alpha)$$

• 第一步求极小
  $$\min_{w,b}L(w,b, \alpha) = \min_{w,b} \frac{1}{2}\lVert w \rVert_2^2 - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b)-1]$$

• 对对偶函数分别求 w 和 b 的偏导：
  $$\frac{\partial{L}}{\partial{w}} = 0 \Rightarrow w = \sum_{i=1}^m\alpha_iy_ix_i \\ \frac{\partial{L}}{\partial{b}} = 0 \Rightarrow \sum_{i=1}^m\alpha_iy_i = 0 \\$$

• 将 w 反代回原来的拉格朗日函数中
  $$\begin{aligned} L &= \frac{1}{2}\lVert w \rVert_2^2 - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b)-1]\\ &= \frac{1}{2}w^Tw - \sum_{i=1}^m\alpha_iy_iw^Tx_i - \sum_{i=1}^m\alpha_iy_ib + \sum_{i=1}^m\alpha_i\\ &= \frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i - w^T\sum_{i=1}^m\alpha_iy_ix_i - \sum_{i=1}^m\alpha_iy_ib + \sum_{i=1}^m\alpha_i\\ &= -\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i - \sum_{i=1}^m\alpha_iy_ib + \sum_{i=1}^m\alpha_i\\ &= -\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i - b\sum_{i=1}^m\alpha_iy_i + \sum_{i=1}^m\alpha_i\\ &= -\frac{1}{2}(\sum_{i=1}^m\alpha_iy_ix_i)^T\sum_{i=1}^m\alpha_iy_ix_i + \sum_{i=1}^m\alpha_i\\ &= -\frac{1}{2}\sum_{i=1}^m\alpha_iy_ix_i^T\sum_{i=1}^m\alpha_iy_ix_i + \sum_{i=1}^m\alpha_i\\ &= -\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum_{i=1}^m\alpha_i\\ \end{aligned}$$

• 第二步求极大
  $$\max_{\alpha\geq0} -\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum_{i=1}^m\alpha_i\\ s.t \qquad \sum_{i=1}^{m}\alpha_iy_i = 0 \qquad(\alpha_i\geq0)$$

• 去掉负号求极小
  $$\min_{\alpha\geq0} \frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum_{i=1}^m\alpha_i\\ s.t \qquad \sum_{i=1}^{m}\alpha_iy_i = 0 \qquad(\alpha_i\geq0)$$

• 而上面的问题就是一个非线性规划, 我们用SMO算法求解

  求得一组$\alpha^*$使得函数最优化；

  • 则可以求得w:
    $$w^* = \sum_{i=1}^m\alpha_i^*y_ix_i$$
  • 则b可以通过支撑向量求解:
    $$y_{support}(w^Tx_{support}+b)=1$$
  • 那怎么找到支撑向量？回到拉格朗日函数的构造(*):
    $$a_i^*[y_i(w^Tx_i+b)-1] = 0$$
    只要后面的$y_i(w^Tx_i+b)-1=0$, 那么$a_i$是多少都可以, 那么$a_i\neq0$的那个对应的就是支撑向量；
  • 求 b 的过程:

  找到所有个支持向量带进去求出所有个$b$，然后求平均$b^*$

注意:(*)处的逻辑其实是这样： 构建拉格朗日函数前，有这样的约束$y_i(w^Tx_i+b) \geq 1$, 拉格朗日函数把这个约束乘上$\alpha_i$加到原函数上, 且原函数与拉格朗日函数保持一致, 那么就要求$a_i^*[y_i(w^Tx_i+b)-1] = 0$； 但是有的$y_i(w^Tx_i+b) > 1$， 那么$\alpha_i$就一定要为0, $\alpha_i$不为零就说明$y_i(w^Tx_i+b) = 1$， 那个点就是支撑向量!!!

• 这样我们就得到了分割超平面
  $$w^Tx + b^* = 0$$

硬间隔SVM总结

算法流程

• 1. 原始目标： 求得一组 w 和 b 使得分隔 margin 最大
• 2. 转换目标： 通过拉格朗日函数构造目标函数，问题由求得 n 个 w 和 1 个 b 转换为求得 m 个α
     $$\min_{\alpha\geq0} \frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum_{i=1}^m\alpha_i\\ s.t \qquad \sum_{i=1}^{m}\alpha_iy_i = 0 \qquad(\alpha_i\geq0)$$
• 3. 利用 smo 算法求得 m 个$\alpha^*$
• 4. 利用求得的 m 个$\alpha^*$求得 $w^*$和 $b^*$
     $$w^* = \sum_{i=1}^m \alpha_i^*y_ix_i\\ b_{support} = y_{support} - (w^{*})^Tx_{support}\\ b^* = \frac{1}{s}\sum_{support=1}^{s}b_{support}\\$$

SVM 支持向量机的硬间隔就是这样了, 继续下一章吧！pd的Machine Learning