「支持向量机」支持向量机（SVM）详细推导及理解（1）

支持向量机

（1）线性可分支持向量机：当训练数据线性可分时，可通过硬间隔最大化，学习一个线性的分类器，叫线性可分支持向量机，也称硬间隔支持向量机

（2）线性支持向量机：当训练数据近似线性可分时，可通过软间隔最大化，也学习一个线性的分类器，叫线性支持向量机，也称为软间隔支持向量机

（3）非线性支持向量机：当训练数据线性不可分时，通过使用核函数技巧及软间隔最大化，学习一个非线性的支持向量机

线性可分的数据就是代表这些数据能够用一条直线分开（二分类），如下图所示：

近似线性可分的数据如下图所示，即绝大多数的样本都能被准确分类，只有少数样本出现错误：

所以对软间隔和硬间隔的理解：当训练数据是线性可分的，能够找到一个平面百分百的将数据分类正确，此时训练数据到超平面的距离就叫做硬间隔（粗俗的讲就是实打实的距离）；如果训练数据近似线性可分，同样可以找到一个超平面能够将绝大部分的数据分类正确，只有少数的样本分类错误，如果能容忍这种错误的存在，此时训练数据到超平面的距离就是软间隔（粗俗理解就是不在意这些细节）。简言之，硬间隔就是不能容忍错误分类点的存在，软间隔就是允许错误分类点的存在。

线性可分支持向量机

定义：给定线性可分训练数据集，由数据集训练得到超平面为

$\large {w^ * }\cdot x + {b^ * } = 0$

决策函数为

$\large f(x) = sign({w^ * }x + {b^ * })$

成为线性支持向量机。

点到直线的距离：

有直线 Ax + By + C = 0 ，点（ x_0 ， y_0 ）到该直线的距离为：

$d = \frac{{\left| {A{x_0} + B{y_0} + C} \right|}}{{\sqrt {{A^2} + {B^2}} }}$ （1）

即：

$d = \frac{{|(A,B)\left( {\begin{array}{*{20}{c}} {x0}\\ {y0} \end{array}} \right) + C|}}{{\left\| {(A,B)} \right\|}}$ （2）

如果数据是n 维时，此时直线就变成了平面，用 $\large w$ 表示平面的法向量得：

$\large d = \frac{{ |w \cdot x + b|}}{{\left\| { w } \right\|}}$ （3）

线性可分支持向量机建立超平面：

给定训练数据集 $\large D = ({x_1},{y_1}),({x_2},{y_2})....({x_n},{y_n}),y = \{ - 1, + 1\}$ ， $\large y$ 是标签，因为是二分类，取值只有-1，+1。

假设数据分布如上图所示，我们想找一条直线能够把数据分开，有无数条直线可以做到，但是这么多直线中选哪一个最好呢？

线性支持向量机的原理就是几何间隔最大化，从而确定这条直线，即上图中粗的黑线。

于SVM的超平面定义为： $\large w\cdot x + b = 0$ ，其中 $\large w$ 是超平面的法向量， $\large x$ 为训练数据，由上文（3）式可知数据点到超平面的距离为（此处公式标号依然为3）：

$\large d = \frac{{ |w \cdot x + b|}}{{\left\| { w } \right\|}}$ （3）

函数间隔：

如果此时我们想比较两个点 $\large x_1$ ， $\large x_2$ 到超平面的距离，把 $\large x_1$ ， $\large x_2$ 带入（3）式后发现分母都是相同的，所以想要比较两个点到平面的距离时，只需要比较分子就可以了，所以 $\large |w\cdot x + b|$ 能够相对表示点到平面的远近，而 $\large w\cdot x + b$ 的符号与类别标签的符号是否一致表示了分类正确与否（因为在做分类时，带入数据点计算 $\large f=sign(w\cdot x + b)$ ，当 $\large w\cdot x + b$ 为正时 $\large f$ 也为正，然后跟 $\large x$ 对应的标签 $\large y$ 对比，如果 $\large f$ 和 $\large y$ 的符号相同说明分类正确，否则分类错误）。所以可以用 $\large y(w\cdot x + b)$ 来表示分类的正确性，我们把 $\large y(w\cdot x + b)$ 称为函数间隔。

定义样本点 $\large (x_i, y_i)$ 到超平面 $\large (w,b)$ 的函数间隔为：

$\large {\widehat \gamma _i} = {y_i}(w\cdot {x_i} + b)$ （4）

而对于整个数据集 $\large D$ ，我们选取所有样本点中最小的函数间隔作为整个数据集到超平面的函数间隔，即

$\large \widehat \gamma = \mathop {\min }\limits_{i = 1,...,n} {\widehat \gamma _i}$

几何间隔：

函数间隔衡量的是点到超平面的远近，但是无法决定所要选择的超平面是哪一个。因为当我们把 $\large w$ 和 $\large b$ 都扩大2倍，那么函数间隔也会跟着扩大2倍，但是超平面并没有发生改变，还是原来的超平面。所以需要对法向量加某些约束，对 $\large w$ 使用L2范数进行规范化，使得间隔是确定的。

定义样本点 $\large (x_i, y_i)$ 到超平面 $\large (w,b)$ 的几何间隔为：

$\large {\gamma _i} = {y_i}(\frac{w}{{\left\| w \right\|}}{x_i} + \frac{b}{{\left\| w \right\|}})$ （5）

而对于整个数据集 $\large D$ ，我们选取所有样本点中最小的几何间隔作为整个数据集到超平面的几何间隔，即

$\large \gamma = \mathop {\min }\limits_{i = 1,...,n} {\gamma _i}$

函数间隔和几何间隔的关系:

可以看出函数间隔和几何间隔的关系为：

$\large {\gamma } = \frac{{{{\widehat \gamma }}}}{{\left\| w \right\|}}$ （6）

上文说了，我们找到了这个几何间隔之后，因为几何间隔 $\large {\gamma }$ 是所有样本点中距离超平面最小的值，所有其他样本点距到超平面的距离肯定都不小于 $\large {\gamma }$ ，即 $\large {y_i}(\frac{w}{{\left\| w \right\|}}{x_i} + \frac{b}{{\left\| w \right\|}}) \ge \gamma$ 。

注：其实这些几何间隔为 $\large {\gamma }$ 就是支持向量。

同时我们希望能够找到一组 $\large w,b$ 使这个几何间隔最大，即 $\large \mathop {\max }\limits_{w,b} \gamma$

所以问题转化成：

（7）

$\large s.t$ 表示约束条件。

因为把（6）式带入（7）得：

（8）

由于函数间隔的取值对优化问题没有影响，因为无论函数间隔取值多少，最终我们想要找到的是 $\large w,b$ ，所以可以令函数间隔为1，即 $\large \widehat \gamma = 1$ 。注意到最大化 $\large \frac{1}{{\left\| w \right\|}}$ 就等于最小化 $\large \frac{1}{2}{\left\| w \right\|^2}$ ，所以优化问题转化成：

（9）

注：这里我们令 $\large \widehat \gamma = 1$ ，也就意味着到超平面的距离为1的点都是支持向量，即下图中画圈的点，如下图所示：

最终问题转化成了在一个线性约束下的二次优化问题，采用拉格朗日乘子法：

（10）

现在需要最大化 $\large L(w,b,\alpha )$ ，所以问题变成 $\large \mathop {\min }\limits_{w,b} \mathop {\max }\limits_\alpha L(w,b,\alpha )$ .

根据拉格朗日的对偶性，原始的极小极大问题变成了现在的极大极小问题 $\large \mathop {\max }\limits_\alpha \mathop {\min }\limits_{w,b} L(w,b,\alpha )$ .

(1) 求 $\large \mathop {\min }\limits_{w,b} L(w,b,\alpha )$ ：

让 $\large L(w,b,\alpha )$ 分别对 $\large w,b$ 求偏导，使导数为 0：

$\large \frac{{\partial L(w,b,\alpha )}}{{\partial w}} = w - \sum\limits_{i = 1}^n {{\alpha _i}{y_i}{x_i}} = 0$ 得 $\large w = \sum\limits_{i = 1}^n {{\alpha _i}{y_i}{x_i}}$ （11）

$\large \frac{{\partial L(w,b,\alpha )}}{{\partial b}} = \sum\limits_{i = 1}^n {{\alpha _i}{y_i}} = 0$ 得 $\large \sum\limits_{i = 1}^n {{\alpha _i}{y_i}} = 0$ （12）

把式（11），（12）带入式（10）得：

$\large L(w,b,\alpha ) = \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i}{x_j})} } - \sum\limits_{i = 1}^n {{\alpha _i}{y_i}[(\sum\limits_{j = 1}^n {{\alpha _j}{y_j}{x_j}} )\cdot {x_i} + b]}$ $\large + \sum\limits_{i = 1}^n {{\alpha _i}}$

$\large = \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i}{x_j})} } - \sum\limits_{i = 1}^n {{\alpha _i}{y_i}\sum\limits_{j = 1}^n {({\alpha _j}{y_j}{x_j}} )\cdot {x_i} - b\sum\limits_{i = 1}^n {{\alpha _i}{y_i}} }$ $\large + \sum\limits_{i = 1}^n {{\alpha _i}}$

$\large = \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i}{x_j})} } - \sum\limits_{i = 1}^n {{\alpha _i}{y_i}{x_i}\sum\limits_{j = 1}^n {{\alpha _j}{y_j}{x_j}} - 0} + \sum\limits_{i = 1}^n {{\alpha _i}}$

$\large = \sum\limits_{i = 1}^n {{\alpha _i}} - \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i}{x_j})} }$

所以 $\large \mathop {\min }\limits_{w,b} L(w,b,\alpha ) = - \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i}{x_j})} } + \sum\limits_{i = 1}^n {{\alpha _i}}$

(2) 求 $\large \mathop {\min }\limits_{w,b} L(w,b,\alpha )$ 对 $\large \alpha$ 的极大值：

问题变为： $\large \mathop {\max }\limits_\alpha \ \ - \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i}{x_j})} } + \sum\limits_{i = 1}^n {{\alpha _i}}$

约束条件为： $\large \sum\limits_{i = 1}^n {{\alpha _i}{y_i}} = 0$ ， $\large {\alpha _i} \ge 0,i = 1,2...n$

所以只要知道 $\large {\alpha }$ ， $\large w$ 也就知道了，假设最优解为 $\large {\alpha ^ * } = {(\alpha _1^ * ,\alpha _2^ * ....\alpha _n^ * )^T}$

由式（11）可知 $\large {w^ * } = \sum\limits_{i = 1}^n {\alpha _i^ * {y_i}{x_i}}$ ，假设此时得到的 $\large b$ 的最优解为 $\large {b^ * }$ ，根据KKT条件可以得到（KKT定理可以参考李航老师的《统计学习方法》）：

至少存在一个 $\large \alpha _i^ *>0$ 使：

$\large \alpha _i^ * ({y_i}({w^ * }\cdot {x_i} + {b^ * }) - 1) = 0$

反证法，假设 $\large \alpha ^ * =0$ ，由式（11）可知 $\large w^*=0$ ,而 $\large w^*=0$ 时，带入式（9）可得

$\large {y_i}b - 1 \ge 0$ （13）

因为 $\large y_i$ 的取值只有+1和-1，要使上式成立， $\large b$ 的取值是个不定值，说明超平面有多个，与原始问题矛盾，故至少存在一个 $\large \alpha _j^ *>0$ ，对此 $\large j$ 有：

$\large \alpha _j^ * ({y_j}({w^ * }\cdot {x_j} + {b^ * }) - 1) = 0\ ,j=1,2...n$ （14）

因为 $\large \alpha _j^ *>0$ ，所以可得：

$\large ({y_j}({w^ * }\cdot {x_j} + {b^ * }) - 1) = 0$ （15）

把式（11）带入式（15），因为 $\large {y_i} = \{ + 1, - 1\}$ ，所以 $\large \frac{1}{{{y_i}}} = {y_i}$ ，进而得到：

$\large {b^ * } = {y_j} - \sum\limits_{i = 1}^n {\alpha _i^ * {y_i}({x_i}\cdot {x_j})}$

至此 $\large w^*$ 和 $\large b^*$ 都已经得到，所以可以得到超平面： $\large {w^ * }\cdot x + {b^ * } = 0$ ，

分类决策函数为： $\large f(x) = sign({w^ * }x + {b^ * })$

注：其实由上面的式（15）可以看出，一定存在一些点使使（15）成立，即 $\large {y_j}({w^ * }{x_j} + {b^ * }) = 1$ ，这个式子不就是代表函数间隔为1嘛，就是一定会存在支持向量，有了支持向量才能支撑起超平面。

上面我们只是假设已经求得了 $\large {\alpha ^ * } = {(\alpha _1^ * ,\alpha _2^ * ....\alpha _n^ * )^T}$ ，所以关键问题就是如何求 $\large \alpha ^ *$ ，支持向量机中求 $\large \alpha ^ *$ 的方法是SMO（Sequential Minimal Optimization）即序列最小最优化，感觉SMO其实不属于支持向量机算法的一部分，只是一种优化方法，所以没怎么着重看（手动捂脸），下面是自己的理解。

SMO的思想是因为拉格朗日乘子由许多个，即 $\large \alpha$ 有许多个，每次只选择其中两个变量作为未知量，其他乘子作为已经量，将N个问题转变成两个变量的求解问题。比如对于线性可分支持向量机的目标函数：

$\large \mathop {\max }\limits_\alpha \ \ - \frac{1}{2}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i}{x_j})} } + \sum\limits_{i = 1}^n {{\alpha _i}}$

约束条件为： $\large \sum\limits_{i = 1}^n {{\alpha _i}{y_i}} = 0$ ， $\large {\alpha _i} \ge 0,i = 1,2...n$

一开始选取两个变量 $\large {\alpha _1},{\alpha _2}$ 作为未知量，其他因子 $\large {\alpha _i}(i = 3,4...n)$ 当作已经的来求目标函数的最小值，求出 $\large {\alpha _1},{\alpha _2}$ 再带入进去，再选取 $\large {\alpha _3},{\alpha _4}$ 求目标函数最小值，求出后继续带入，直到所有 $\large \alpha$ 都得到（中间过程其实挺复杂的，个人理解手动捂脸）。

参考：

1.李航《统计学习方法》

2.机器学习之深入理解SVM

支持向量机（SVM）详细推导及理解（1）