支持向量机SVM

Introduction

支持向量机（Support Vector Machine，SVM）是定义在特征空间中的最大间隔线性分类器，对于非线性可分的数据，SVM引入核方法（kernel trick）使它实质上成为非线性分类器。本文主要分为两大部分，1）求解间隔最大的分类平面，这种情况可以转化为一个求解凸二次规划的问题，这部分将包括求解算法 SMO； 2）Hinge Loss，通过经验风险最小化，采取 Hinge Loss 来求得损失函数，最终对损失函数求极值即可。下面将分章节对两大部分进行讨论讨论。

1. 最大化间隔解释

1.1 线性可分

给定N个数据的集合 $\left \{ (x_i,y_i)\right \}_{i=1}^N $, 其中 $x_i \in \mathbb{R}^n$ 为样本点， $y \in \mathbb{R}$为类标签, 每个 $(x_i,y_i)$ 的组合为一个训练样例，线性可分意味着即存在一个超平面 $w \cdot x +b= 0$，可以将这两类数据分开，使得超平面一边的数据点所对应的标签 $y$ 全是+1 ，另一边对应的标签 $y$ 全为-1.

注意，当训练数据线性可分时，存在无穷多超平面可以将两类数据正确分开，SVM 的思想是利用几何间隔最大来求解最优分类超平面，这个解是唯一的。

1.2 最大化几何间隔

一般来说，训练样本距离分类超平面的远近可以表示分类预测的确信程度，下图中点C的类别 = -1 确信程度要明显高于点A。

该确信程度可以用样本到超平面的距离来表示，该距离便是常说的几何距离（点到直线的距离）。样本点 $x_i$  到分类平面 $w \cdot x +b= 0$ 的几何距离如下所示：                 

\[\gamma_i = \frac{|w \cdot x +b|}{||w||}\]

其中分子为取绝对值，分母为 $L_2$ 范数， 且有 $||w|| = \sqrt{w_1^2 + w_2^2+...+w_n^2}$,进一步观察，对于正负训练样例， $w \cdot x_i +b> 0$  ,则标签 有 $y_i = 1$ ， 反之，若 $w \cdot x_i +b< 0$ ，则有 $y_i =-1$ ，所以可以去掉绝对值,便得到以下常见的几何间隔的表达式:

\[\gamma_i = y_i \left (\frac{w \cdot x }{||w||}+\frac{b }{||w||}\right )\]

对于整个个训练集的几何距离，可表示为所有N个训练样本中的最小的几何距离：

\[ \gamma = min_i \gamma_i\]

现在有了训练数据的几何间隔，根据SVM的核心思想：寻找最大间隔分类超平面，可以得到以下约束最优化问题：                                                           

\begin{aligned}
&\max_{w,b}\gamma \\
&s.t. \ \ y_i\left ( \frac{w}{||w||}\cdot x_i + \frac{b}{||w||} \right ) \ge \gamma , \ \ i = 1,2,...,N
\end{aligned}

这里约束条件的意思是使得训练集合中所有样本的几何间隔至少要大于最小的几何间隔. 这里在引入一个逻辑概念，叫做函数间隔。

\[\gamma_i = y_i \left (w \cdot x_i+b \right )\]

整个数据集的函数间隔为：

\[\widehat{\gamma} = \min_{i=1...N} \widehat{\gamma}_i\]

与几何间隔的关系分别由以下两个公式给出: 

\[\gamma_i = \frac{\widehat{\gamma}_i}{||w||}, \gamma = \frac{\widehat{\gamma} }{||w||}\]

根据以上函数间隔，可以对SVM优化公式做进一步化简：

\begin{aligned}
&\max_{w,b} \frac{\widehat{\gamma }}{||w||} \\
&s.t. \ \ y_i\left ( w\cdot x_i + b \right ) \ge \widehat{\gamma }, \ \ i = 1,2,...,N
\end{aligned}

之所以引入函数间隔，是因为其可以自由缩放的，比如对于分类超平面 $w \cdot x +b= 0$ , 若左右同时扩大 $\lambda$ 倍，$\lambda w \cdot x +\lambda b= 0$ ，平面不会发生任何改变，对于点 $x_i$ 根据函数间隔公式：

\[\gamma_i = y_i \left (w \cdot x_i+b \right )\]

于是可得：

\[\lambda \gamma_i =\lambda  y_i \left (w \cdot x_i+b \right )\]

也就是说函数间隔也扩大了 \lambda   倍，但是此时超平面与几何间隔不会产生任何变化，所以并不会对我们的优化函数产生一丝影响，因为优化目标是最小化几何间的，也就是说这里可以分类超平面参数的缩放不会对最终的结果产生影响，所以可以令数据集的函数间隔 = 1. 最终只需极大化：

\begin{aligned}
&\max_{w,b} \frac{ 1 }{||w||} \\
&s.t. \ \ y_i\left ( w\cdot x_i + b \right ) \ge 1, \ \ i = 1,2,...,N
\end{aligned}

把极大改为极小就是一个带有不等式约束的凸二次规划形式了：

\begin{aligned}
&\min_{w,b} \frac{ 1 }{2}||w||^2 \\
&s.t. \ \ y_i\left ( w\cdot x_i + b \right ) \ge 1, \ \ i = 1,2,...,N
\end{aligned}

综上，提炼出线性可分情况下SVM的学习算法，算法1.1：

线性可分数据集 $\left \{ (x_i,y_i)\right \}_{i=1}^N$ ,

　　（1）构造约束最优化问题：

\begin{aligned}
&\min_{w,b} \frac{ 1 }{2}||w||^2 \\
&s.t. \ \ y_i\left ( w\cdot x_i + b \right ) \ge 1, \ \ i = 1,2,...,N
\end{aligned}

　　（2）求解得到$w^*,b^*$，分类超平面即为 $w* x+b^* = 0$

　　（3）对于新的观测数据 $x$  ，  根据 $f(x) = sign(w^* \cdot  x+b^*)$ 判断其类别  $y$ 即可.

SVM中一个关键的因素就是 支持向量 ，  支持向量是什么样的点呢？

根据算法1.1中的约束条件  $w_i(w \cdot x_i +b) –1 \ge 0$可知，数据集中的点都满足如上约束，等式成立时的点 $x_i$ 支 持向量，即满足 $w_i(w \cdot x_i +b) =1 $ .支持向量还满足以下几个性质：

• 到分类超平面的距离为 $1/|w||$，因为之前我们在不影响结果的情况下，人为设定函数间隔 \widehat{\gamma} 为 1；
• 支持向量分别位于两条线  $w \cdot x_i + b = \pm 1$ 上，具体哪条线视类别而定；
• 决定超平面时，只有支持向量起作用，即SVM是由很少的“重要”的 支持向量样本决定，所以SVM对异常值是十分敏感的。

1.3 转化为对偶问题

本小节主要讲解如何求解算法1.1中的不等式约束二次规划问题，是一个凸优化问题，这里有两篇参考文献，只要这两篇搞懂，SVM 就是浮云，本节许多结论来自这两篇文章。

• 约束优化方法之拉格朗日乘子法与KKT条件
• 拉格朗日对偶

关于对于偶问题与 KKT 条件在这里真的非常重要，不熟悉先看明白以上两篇文章即可，而且在SVM中引入对偶的好处为：

• 对偶问题有良好的性质；

1. 对偶问题必为凸优化问题.
2. 对偶问题是原始问题的下界，当满足一定条件，两者等价.

• 可以自然而然的引入核函数。

现在回到之前的优化目标，也即原始问题：

　\begin{aligned}
&\min_{w,b} \frac{ 1 }{2}||w||^2 \tag{primal problem} \\
&s.t. \ \ - y_i\left ( w\cdot x_i + b \right ) -1\le 0, \ \ i = 1,2,...,N
\end{aligned}

这里把不等式约束优化写成了常见的 $g(x) \le 0$ 的形式，接下来首先构造拉格朗日函数：

\[L(w,b,a) = \frac{1}{2} ||w||^2 - \sum_{i=1}^Na_i(y_i(w \cdot x_i+b) - 1)\]

这个拉格朗日函数是很有意思的，首先是一定满足 $a_i \ge 0$ 的，其次是满足松弛互补条件，这就是支持向量的由来，即始终有：

\[\sum_i a_i(y_i(w \cdot x_i + b) -1) = 0\]

对于 $a_i > 0$ 的点便为支持向量了， 接下来转换为对偶问题求解，首先根据拉格朗日函数写出一个原始问题，之后再转换为对偶问题求解，这样做的目的，参考这篇文章即可，原始问题的构造如下：

\[ \max_{w,b}L(w,b,a) = \frac{1}{2}||w||^2\]

因为满足约束时，拉格朗日函数的第二项是为 0 的，因此 SVM 的求解的原始问题与原始问题的最优解 $p^*$ 为 ：

\[p^* = \min_{a_i \ge 0} \max_{w,b}L(w,b,a)\]

对偶为题的形式与最优解 $d^*$ 为：

\[d^* =  \max_{w,b} \min_{a_i \ge 0}L(w,b,a) \]

在对偶理论中，对偶问题为原始问题的下界，即 $p^* \ge d^*$，原始问题是满足 Salter 条件的，也就是说：存在 $w^*,b^*,a^*$ 分别是原始问题与对偶问题的解, 使得：

\[p^* = d^* = L(w^*,b^*,a^*)\]

由于满足 Salter 条件（即满足强对偶），可知每对满足原始问题与对偶问题的解都满足 KKT 条件，即：

\begin{aligned}
&\nabla_wL(w^*,b^*,a^*) =w^* -\sum_{i=1}^Na_i^*y_ix_i =0 \\
&\nabla_bL(w^*,b^*,a^*) =-\sum_{i=1}^N a_i^*y_i =0 \\
&a_i^*(y_i(w^* \cdot x +b^*) -1) \ge 0 \\
&y_i(w^* \cdot x +b^*) -1 \ge 0 \\
&a_i \ge 0 , \ i = 1,2,...,N
\end{aligned}

根据这些条件，可求得：

\begin{aligned}
w^* &= \sum_{i=1} ^N a_i^* y_ix_i \\
b^* &= y_j - \sum_{i=1}^N a_i^* y_i(x_i \cdot x_j) \\
\end{aligned}

最后来理清思路，首先构造对偶问题，根据原始问题满足 Slater 条件可知强对偶性成立且原始问题与对偶问题有共同的最优解，根据强对偶性成立可知每对原始问题与对偶问题的最优解是满足 KKT 条件的，所以要先从对偶问题下手，对偶问题是 max min 型的，先看极小部分：

1）min部分 ：假定 为定值，求解 的极小值，直接对 $w,b$ 求偏导即可：

\begin{aligned}
\frac{\partial L(w,b,a)}{\partial w} &= 0 \Rightarrow w - \sum_{i=1}^N a_iy_ix_i = 0 \\
\frac{\partial L(w,b,a)}{\partial b} &= 0 \Rightarrow  - \sum_{i=1}^N a_iy_i = 0
\end{aligned}

注意上式相当于产生一个约束条件 $\sum_i a_i y_i = 0$ ,将以上结果带入L(w,b,a) ，会有：

2)max部分 ： min 部分得到解之后，现在求关于 $a$ 的极大即可, 即现在的待优化函数 变为：

\begin{aligned}
&\max_{a_i \ge 0} \ -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Na_i a_jy_iy_j (x_i \cdot x_j) + \sum _{i=1}^Na_i\\
& \ s.t. \ \ \ \sum_{i=1}^N a_iy_i = 0
\end{aligned}

现在大功告成，只要求解对偶问题得到 $a^*$ ，然后根据 KKT 条件得到 $w^* ,b^*$ ,就可以完美的解得原始问题的最优解了　　

经过以上两部，便得到了最终的线性可分支持向量机学习算法1.2

输入：线性可分数据集 $\left \{ (x_i,y_i) \right \}_{i=1}^N$ ,

　　（1）构造约束最优化问题：

\begin{aligned}
&\max_{a_i \ge 0} \ -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Na_i a_jy_iy_j (x_i \cdot x_j) + \sum _{i=1}^Na_i\\
& \ s.t. \ \ \ \sum_{i=1}^N a_iy_i = 0
\end{aligned}

　　（2）求解得到 $a^*= (a^*_1，a^*_1,…,a^*_N)^T$，求解一般采用SMO算法　　

　　（3）根据 $a^*$求解得到$w^*,b^*$,首先选择$a^*_j$ 的支持向量 $(x_i,y_i)$ ;

\begin{aligned}
w^* &= \sum_{i=1} ^N a_i^* y_ix_i \\
b^* &= y_j - \sum_{i=1}^N a_i^* y_i(x_i \cdot x_j) \\
\end{aligned}

　　（4）求得超平面 $w^* \cdot x +b^* = 0$, 对于新的观测数据 $x$ ，  根据 $f(x) = sign(w^* \cdot x +b^*)$ 判断其类别 $y$.

这里顺便明确给出支持向量的定义：根据KKT条件  $a_i^*(y_i(w^* \cdot x_i +b^*) -1) = 0$ ,训练数据集中 $a_i^* >0$ 的样本点 $(x_i,y_i)$ ，其中$y_i(w^* \cdot x_i +b^*) -1= 0$ ，输入 $x_i,y_i$ 即为支持向量 ，支持向量一定在间隔边界上，且有 $a_i^*(y_i(w^* \cdot x_i + b^*) -1) = 0$ 。而对于非支持向量，即 $y_i(w^* \cdot x_i+b^*) -1 >0$ ，一定有 $a_i = 0$. 至此，关于线性可分情况下的二分类SVM全部推到完成，但是有一个问题：当数据中存在一些异常值（outlier），去除这些 outlier 后数据是线性可分的，这种情况下要引入关于异常值的处理。

1.4 outlier 的处理

给定数据集  , ,  其中 为样本点，存在 时的样本并不是线性可分的，如下图左，还有一种情况是即使数据集是线性可分的，但是由于异常值的存在，导致分离超平面被挤压，如下图右。

      非线性可分        分离超平面受到挤压

以上情况意味着某些样本点   的函数间隔并不满足大于 1 的要求。为了解决这个问题，为每个样本引入一个松弛变量   , 使得函数间隔可以小于 1 ，即满足 ,这里显然 不能任意大，因为那会导致任意样本点 满足要求，所以要对优化目标做出改进：

  , 

  , 

求解此优化目标的方法同线性可分数据集的情况，首先构造拉格朗日函数：

拉格朗日函数中的乘子 均大于 0 ，很明显的有

因此优化目标又变为极小极大的形式，这是应用拉格朗日对偶与KKT条件，就会得到最终待优化的极大极小问题,  ，同样对该问题求解分为极大极小部分，先来 min 部分：

将以上结果带入 ，min 部分变为：

接下来便是 max 部分:

  ,（这里根据 与 消去了 ） 

至此，可以总结出带有异常值的线性可分SVM的算法1.3：

线性可分数据集, 数据集非线性可分，伴有异常值

　　（1）构造约束最优化问题：

，

　　（2）求解得到 ，求解一般采用SMO算法　　

　　（3）根据 求解得到,首先选择 的支持向量

　　（4）求得超平面 , 对于新的观测数据 ，  根据 判断其类别 = +1 或 = -1

下图中实线为分离超平面，虚线为间隔边界，且有间隔边界与分离超平面的函数距离为1，几何距离为 1/||w||。在线性不可分的情况下，求借得到 的分量 对应的样本实例 中的 称为支持向量，这时的支持向量要比线性可分复杂一些，如下图的点，以下支持向量点到间隔边界的几何距离均已标注出为。这个几何距离是这样计算的，点 到分离超平面的函数距离为 , 而分离超平面与间隔边界的函数距离为 1 ，所以点   到间隔边界的距离为 ,几何距离只需除以 即可得到结果。

可见这时候的支持向量或者分布在间隔边界上，或者在间隔边界与超平面之间，或者在分离超平面误分的一侧。

首先考虑如下两个公式：

注意限制条件 ，若 ,  则 ,若   则  ，当 得到的向量均为支持向量，下面为支持向量的分类：

若 ，则       则   为支持向量，且恰好落在间隔边界上

　　根据 ，若   则    ，则 ，说明该点到分离超平面的函数距离为

若 ，   则分类正确 ， 落在间隔边界与分离超平面之间　

　　根据 ，若 ,  则 ，此时若 ，说明该点到分离超平面的函数距离为

若 ，         则 在分离超平面上

　　根据 ，若 ,  则 ，此时若 ，说明该点到分离超平面的函数距离为

若 ，         则 位于分离超平面误分的一侧

　　根据 ，若 ,  则 ，此时若 ，说明该点到分离超平面的函数距离为

综上所述，并且考虑 KKT 条件 ， 可以得到 支持向量 与 的关系：

至此，带有 的非线性可分的情况也解决了，但是还需要注意的是数据集是完全非线性可分的。这是便需要引入 了。核方法并不是 SVM 的专利，其可以解决一系列机器学习问题。下一节讲述的主要是核方法在 SVM 中的应用。

1.5

给定数据集  , ,  其中 为样本点，这时数据集是完全非线性可分的，如下图所示，此时只能找到一个超曲面，来将数据进行分类，这是的数据即为非线性可分的，非线性问题很难求解，转换为线性问题相对来说很简单（前边1.1-1.5已经给出求解方法），此时就需要引入 了。 即对原空间中非线性可分的样本点进行映射，使其到新的空间中变得线性可分。下图给出一个 的映射，原空间为 ,定义新空间 为 ，根据图可以看出映射后样本点的变化，此时样本便为线性可分的了，直接用 即可分开原来的样本点。

上图是一个 的映射，但一般情况下，特征空间的选取往往是很高维度的 ,如下为一个 的映射：

下面给核函数一个正式定义，设 为输入空间， 为特征空间，如果存在一个 到 的映射  ,对所有的 ,函数 满足 ,则称 为输入空间到特征空间的映射函数， 为核函数。

核函数常用的技巧是不计算映射函数 ，因为特征空间 通常是高维的，甚至无穷维，所以 计算并不容易，而计算核函数 却相对简单。映射 取法多种多样，可以取不同的特征空间，即使在同一特征空间也可以取不同的映射。映射后的样本一般是线性可分带有异常值的，这时考虑其优化目标：

，

由于在输入空间计算的是样本   的内积，所以经过映射后分别为 与 ，现在只需修改目标函数为 与 的内积即可，又由于   ，所以只需要定义便于计算的核函数，而不需要定义映射函数，这便是核技巧。所以线性不可分的数据集的优化目标变为：

，

现在即使线性不可分的数据经过映射函数 的映射得到新的特征空间，将 与 进行内积运算的，得到 ，在新的特征空间里学习线性可分的SVM。当映射函数为非线性函数时，此时得到的SVM为非线性模型。也就是说给定核函数 ，即可用求解线性分类问题的方法来求解非线性问题，核技巧的好处在于不需要显式的定义特征空间与映射函数，只需要选择一个合适的核函数即可。综上核函数是用来免去显式计算高维变换的，直接用低维度的参数带入核函数来等价计算高维度的向量的内积。

核函数的选择，什么样的函数 可以作为一个有效核函数呢？答案是只要满足 Mercer 定理 即可，即如果函数 是 上的映射（也就是从两个n维向量映射到实数域）。那么如果 是一个有效核函数（也称为Mercer核函数），那么当且仅当其训练样本 相应的核函数矩阵是对称半正定的。

这里先解释一下正定矩阵：

设 是 阶方阵，如果对任何非零向量 ，都有 ，其中 表示 的转置，就称 为正定矩阵。

正定矩阵性质如下：

1）正定矩阵一定是非奇异的。奇异矩阵的定义：若n阶矩阵A为奇异阵，则其行列式为零，即  。

2）正定矩阵的任一主子矩阵也是正定矩阵。

3）若 为 阶正定矩阵，则 为 阶可逆矩阵。

给定 N 个训练样本 ，每一个样本 对应一个训练样例。那么，我们可以将任意两个 和 带入核函数中，计算 。这样可以把 表示为一个 的矩阵（ 矩阵），即只要 矩阵为对称半正定的，则 即为一个有效的核函数。

显而易见，对称性是很好满足的：

下面看正定性，对于任意非零向量 ，

显然最后一项是大于零的，以上即核函数合法性的判定方法，最后给出一些常用的核函数。

1）线性核

　　线性核其实就是不采用非线性分类器，认为样本是线性可分的

1）多项式核

　　该核函数对应的是一个 次多项式的分类器，这时需要额外调节的参数为

2）高斯核 

　　该核函数对应的是高斯径向基分类器，该核函数甚至可以将特征空间映射为无穷维，这时需要额外调节的参数为 ，这里所说几句如果 选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果 选得很小，则可以将任意的数据映射为线性可分，当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数 ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。

综上，给出非线性可分支持向量机的学习算法1.4：

给定 ， 数据集完全非线性可分，即只有映射到高维空间后才有可能成为伴随异常值的线性可分的数据集。

　　（1）构造约束最优化问题：

，

　　（2）求解得到 ，求解一般采用SMO算法　　

　　（3）根据 求解得到首先选择 的支持向量

　　（4）求得超平面 , 对于新的观测数据

　　（5） 根据 判断其类别 = +1 或 = -1.

2.  Hinge Loss 解释

在经典的 Logistic 回归中，loss function 采用的-log损失函数

这里另   , 则 ， 的图形如下图的红色曲线（图中绿色的线为square loss，蓝色的线为 hinge loss），可见 越接近1 ， 的取值越小，即损失越小。

反之另，此时得到的图像应该为关于 对称的红色的线（没画出），此时 越接近-1， 的取值越小，即损失越小。

2.1 二分类问题

给定数据集 ， 要用这些数据做一个线性分类器，即求得最优分离超平面 来将样本分为正负两类，给定数据集后只需求得最优的参数 即可，首先做出如下线性映射关系 ，根据经验风险最小化原则， 每个训练样本二分类的 Hinge Loss 为 ，上图中对应的 ，所以SVM可以通过直接最小化如下损失函数二求得最优的分离超平面：

2.2 多分类问题

给定数据集 ， ,现在要用这些数据做一个类的线性分类器 ,现在需要优化的参数变为 ， 此时的 ，为一个 的矩阵， 为一个向量，现在的映射关系如下 ： ，此时， ， 中的每个分量代表分类器在该类别的得分，样本 的标签  , 这里若 属于类别 ，则 中除了第 个分量外其余元素全为 0 ，比如 5 分类问题，   属于第3类，则有 ,用 表示得分向量 中的第 个分量 ， 表示对应 的分量，在多分类的Hinge Loss可表示为：，所以k线性分类SVM 的 Hinge 损失函数为：

支持向量机SVM

原文：http://www.cnblogs.com/ooon/p/5750551.html