支持向量机 (support vector machine，SVM)，是一种常用的判别方法，本文概述其来源和思想 。

简介

• SVM （Support Vector Machines） 在机器学习领域是一个有监督的 两类分类模型 ，通常用来进行模型识别，分类，回归分析以及异常值检测。
• 其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略（分割原则）便是间隔最大化，最终可转换为一个凸二次规划问题的求解。

主要思想

• SVM的主要思想可以概括为两点：

1. 带入原式它是针对线性可分情况进行分析，对于线性不可分情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。
2. 它是基于结果风险最小化理论之上在特征空间中构建最优超平面，使得学习器得到全局最优化，并且在整个样本空间的期望以某个概率满足一定上界。

分类类型

支持向量机是在所有知名的数据挖掘算法中最健壮，最准确的方法之一，它属于二分类算法，可以支持线性和非线性的分类。发展到今天，SVM已经可以支持多分类了。

• 线性分类

  给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于他们落在间隔的哪一侧来预测所属类别。

• 非线性分类

  除了进行线性分类之外，SVM还可以使用所谓的核技巧有效的进行非线性分类，将其输入隐式映射到高维特征空间中。当数据未被标记时，不能进行监督式学习，需要用非监督式学习，它会尝试找出数据到簇的自然聚类，并将新数据映射到这些已形成的簇。将支持向量机改进的聚类算法被称为支持向量聚类，当数据未被标记或者仅一些数据被标记时，支持向量聚类经常在工业应用中用作分类步骤的预处理。

SVM 起源

• 我们看一个例子：

• 上图中，画了三条线，这三条都能分开，但是这三条线那条更好呢？
• 用SVM的思想来说，就是什么样的决策边界才是最好的呢？更进一步，当数据特征更加复杂，本身如果很难分，怎么办呢？那特征复杂后，计算复杂度如何呢？那SVM能实际应用吗？

Logistic 回归

• 给定一些数据点，他们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。如果用 $x$ 表示数据点，用 $y$ 表示类别（$y$ 可以取1或者-1，代表两个不同的类），一个线性分类器的学习目标便是要在 $n$ 维的数据空间中找到一个超平面（hyper plane），这个超平面的方程可以表示为：

$$
w^{T} x+b=0
$$

• Logistic 回归的目的是从特征学习出一个二分类模型，而这个模型是将特征的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。

• 因此，使用 Logistic 函数（或者也称为 Sigmoid 函数）将自变量映射到 $(0, 1)$ 上，映射后的值被认为是属于 $y=1$ 的概率。

• 假设函数如下：

$$
h _ { \theta } ( x ) = g ( \theta ^ { T } x ) = \frac { 1 } { 1 + e ^ { - \theta ^ { \prime } x } }
$$

• 其中 $x$ 是 $n$ 维特征向量，函数 $g$ 就是Logistic函数，我们令 $z = \theta^Tx$ ，则 $ g(z)$ 为：

$$
g ( z ) = \frac { 1 } { 1 + e ^ { - z } }
$$

• 其图像为：

• 而我们假设的 $h_\theta (x)$ 就是特征属于 y=1的概率：

$$ \begin{aligned} P(y=1 \mid x ; \theta) &=h_{\theta}(x) \\ P(y=0 \mid x ; \theta) &=1-h_{\theta}(x) \end{aligned} $$

• 当我们要判别一个新来的特征属于那个类的时候，只需要求出 $h_\theta (x)$ 即可，若 $h_\theta (x)$ 大于 0.5 就是 $y=1$的类，反之属于 $ y=0$ 的类。
• 此外， $h_\theta (x)$ 只和 $\theta^Tx$ 有关， $\theta^Tx >0$ ，那么 $\theta^Tx >0.5$，而 $g(z)$ 只是用来映射，真实的类别决定权还是在于 $\theta^Tx$ 。
• Logistic回归就是要学习得到 $θ$，使得正例的特征远大于0，负例的特征远小于0，而且要在全部训练实例上达到这个目标。

变形 Logistic 回归

• 接下来，尝试把 Logistic 回归做个变形。首先，将使用的结果标签 $y=0$ 和 $y=1$ 替换为 $y = -1, y=1$，然后将下面公式的 $θ_0$ 替换为 $b$。

$$ \theta^T{x} =\theta_{0}+\theta_{1} x_{1}+\theta_{2} x_{2}+\cdots+\theta_{n} x_{n} $$

• 最后将后面的 一串替换为 $W^Tx$，即下面一串被替换：

$$
\theta^{T} x=w^{T} x+\mathrm{b}
$$

• 也就是说除了将 $y$ 由 $y=0$ 变为 $y=-1$ 外，线性分类函数跟 logistic 回归的形式化 g 表示函数没有区别，下面是 Logistic 回归的形式化表示函数：

$$
h_{\theta}(\mathrm{x})=g\left(\theta^{T} x\right)=\mathrm{g}\left(w^{T} x+\mathrm{b}\right)
$$

• 对于逻辑回归我们先说到这里，下面看线性分类和逻辑回归的比较。

• SVM和Logistic虽然说都是寻找一个线性分类界限，但出发点不同。SVM是以训练集两个类的边界（支持向量）来考虑划分，而Logistic是从训练集的全局来考虑划分。这也就是为什么Logistic受噪声和离群点的影响比较大。当出现一个离群点时，Logistic划定的边界很有可能会改变。而SVM这边划分的边界却可能丝毫不动（因为离群点并不影响我支持向量）。

线性分类的一个例子

线性可分的二分类模型

什么是线性可分呢？如果一个线性函数能够将样本分开，称这些数据样本是线性可分的。那么什么是线性函数呢？在二维空间中就是一条直线，在三维空间中就是一个平面，依次类推，如果不考虑空位维度，这样的线性函数就统称为超平面。我们一般所说的线性可分支持向量机就对应着能将数据正确划分并且间隔最大的直线。

• 线性二分类模型的目标就是找到一组合适的参数 $(w, b)$，使得：

$$
\forall i . y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{x}_{i}+b\right)>0
$$

即：线性二分类模型希望在特征空间找到一个划分超平面，将属于不同标记的样本分开。

• 我们下面举个简单的例子。如下图所示，现在有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的 y 全是 -1 ，另一边所对应的 y 全是1。

• 上面的超平面可以用分类函数 $f(x)$ 表示，$f(x)$ 如下：

$$
f(x)=w^{T} x+b
$$

• 当 $f(x)=0$ 的时候，$x$ 便是位于超平面上的点，而 $f(x) > 0$ 的点对应 $ y=1$ 的数据点，$f(x) < 0$ 的点对应 $y = -1$ 的点，如下图所示：

• 问题是，如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分类两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着c最大间隔的超平面。这个问题，我们先搁置一下，下面说一下线性可分支持向量机。

线性可分支持向量机

线性可分支持向量机（SVM）也是一种线性二分类模型，也需要找到满足二分类目标约束的划分超平面，即 $(w, b)$，由于能将样本分开的超平面可能有很多，SVM进一步希望找到离个样本都比较远的划分超平面。

• 当面对样本的随机扰动时，离每个样本都比较远的划分超平面对扰动的容忍能力比较强，即不容易因为样本的随机扰动使得样本穿越到划分超平面的另外一侧而产生分类错误。因此这样的划分超平面对样本比较稳健，不容易过拟合。另一方面，离各样本都比较远的划分超平面不仅可以把正负样本都分开，还可以比较大的确信度将所有样本分开，包括难分的样本，即离划分超平面近的样本。

• 分类学习最基本的思想就是基于训练集 $D$ 在样本空间中找到一个划分超平面，将不同类别的样本分开，但是能将训练样本分开的划分超平面可能有很多，所有我们应该去找位于两类训练样本“正中间”的划分超平面。因为该划分超平面对训练样本局部扰动的“容忍”性最好，例如，由于训练集的局限性或者噪声的因素，训练集外的样本可能比正中间的训练样本更接近于两个类的分割界，这将使得许多划分超平面出现错误。而正中间的超平面影响最小，所以这个划分超平面所产生的结果是鲁棒的。

• 所以问题就变为哪一个分类超平面是最优的？而要算最优超平面，肯定先算出间隔，只有间隔最大化，才能找出最优超平面，所以下面学习函数间隔。

点到平面间隔距离的计算

函数间隔

• 间隔（margin）：每个训练观测点到超平面距离中的最小值。

• 我们的划分超平面可以用如下线性方程来描述：

$$
w^{T} x+b=0
$$

• 其中 $W$ 为法向量，决定了超平面的方向，$b$ 为位移量，决定了超平面与原点的距离。
• 假设超平面能将训练样本正确的分类，即对训练样本 $(x_i, y_i)$，满足以下公式：

$$ \begin{array}{ll}w^{T} x_{i}+b \geq+1 & y_{i}=+1 \\ w^{T} x_{i}+b \leq-1 & y_{i}=-1\end{array} $$

• 该公式称为最大间隔假设，$y_i = +1$ 表示样本为正样本，$y_i = -1$ 表示样本为负样本，式子前面选择 $>= +1， <= -1$ 只是为了方便计算，原则上可是任意常数，但无论是多少，都可以通过对 $w$ 的变换使其为 +1 和 -1，实际上公式等价于：

$$ y_{i}\left(w^{T} x_{i}+b\right) \geq+1 $$

• 在超平面 $wx+b=0$ 确定的情况下， $| wx+b |$ 能够表示点 $x$ 到距离超平面的远近，而通过观察 $wx+b$ 的符号与类标记 $y$ 的符号是否一致可以判断分类是否正确，所以，可以用 $y (wx+b)$ 的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。
• 一般的，当样本点被分类正确时，定义函数间隔（用 $\hat{γ }$ 表示）为：

$$ \hat{\gamma}=y\left(w^{T} x+b\right)=y f(x) $$

几何间隔

• 而超平面 $(w, b)$ 关于训练数据集 $T$ 中所有样本点 $(x_i , y_i)$ 的函数间隔最小值（其中，$x$ 是特征，$y$ 是结果标签，$i$ 表示第 $i$ 个样本），便为超平面 $ (w, b)$ 关于训练数据集 $T$ 的函数间隔（即训练观测与超平面的间隔）：

$$ \hat{\gamma}=\min \hat{\gamma} _i(i=1, \ldots n) $$

• 但这样定义的函数间隔有问题，即如果成比例的改变 $w$ 和 $b$ （假设将他们改为 $2w$ 和 $2b$），则函数间隔的值 $f(x)$ 却变成了原来的 2 倍（虽然此时超平面没有改变），所以引出真正定义点到超平面的距离——几何间距（geometrical margin）的概念。
• 假定对于一个点 x，令其垂直投影到超平面上的对应点为 x0， w是垂直于超平面的一个向量，γ 为样本 x 到超平面的距离，如下图所示：

• 根据平面几何知识，有：

$$
x=x_{0}+\gamma \frac{w}{|w|}
$$

• 其中 $||w||$ 为 $w$ 的模长，$w / ||w||$ 是单位向量（一个向量除以它的模称之为单位向量）。
• 又由于 $x_0$ 是超平面的点，满足 $f(x_0) = 0$，代入超平面的方程 $w^Tx+b=0$ ，可得 $w^Tx_0+b=0$，即 $w^Tx_0 = -b$。随即让上式（平面几何所得公式）的两边同时乘以 $W^T$，然后根据 $w^Tx_0 = -b$ 和 $w^Tw = ||w||^2$，即可算出 $γ$ ：

$$ \gamma=\frac{w^{T} x+b}{\|w\|}=\frac{f(x)}{\|w\|} $$

• 为了得到 $γ$ 的绝对值，令 $γ$ 乘上对应的类别 $y$，即可得出几何间隔 （用 $\tilde{\gamma}$ 表示）的定义：

$$
\tilde{\gamma}=y \gamma=\frac{\hat{\gamma}}{|w|}
$$

• 从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以 $||w||$，而且函数间隔 $y (w^Tx+b) = y f(x)$ 实际上就是 $| f(x) |$，只是人为定义的一个间隔度量，而且几何间隔 $| f(x) | / || w || $ 才是直观上的点到超平面的距离。

点到超平面的距离

• 这里补充一下点到超平面的距离的概念。设二维空间存在一个超平面实现二类可分如下图所示：

• 图中的斜线表示超平面 $g(X) = w^TX + b = 0$，二维平面上一点 $X$ 在超平面的距离投影为 $X’$，则二者关系可表示为 $X = X’ + λ w$（$w$ 表示超平面的梯度向量），将 $X$ 代入到 $g(X)$ 得：

$$ \begin{aligned} g(X) &=w \cdot X+b \\ &=w \cdot\left(X^{\prime}+\lambda w\right)+b \\ &=w \cdot X^{\prime}+b+\lambda w \cdot w \\ &=0+\lambda w \cdot w=\lambda w \cdot w \end{aligned} $$

• 点到超平面的距离即是 $X$ 与 $X’$ 之间的距离：

$$ \left\|X-X^{\prime}\right\|=\|\lambda w\|=\frac{|g(X)|}{w \cdot w} \cdot\|w\|=\frac{|g(X)|}{\|w\|} $$

• 该公式为点到平面的距离公式，只不过这里点和平面表达式的系数都用向量表示。

最大间隔分类器

• 最大间隔超平面：间隔最大的超平面，即使得训练观测到分割超平面的间隔达到最大。

• 支持向量：样本点中与分离超平面距离最近的样本点的实例

• 最大间隔超平面的选取只与支持向量有关。

• 对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是下面的 Gap 的一半。

• 通过由前面的分析可知：函数间隔不适合用来最大化间隔值，因为在超平面固定以后，可以等比例地缩放 $w$ 的长度和 $b$ 的值，这样可以使得 $f(x) = w^Tx + b$ 的值任意大，亦即函数间隔 $\hat γ $ 可以在超平面保持不变的情况下被取得任意大。
• 但几何间隔因为除上了 $||w||$，使得在缩放 $w$ 和 $b$ 的时候几何间隔是不会改变的，它只随着超平面的变动而变动。因此，这是更加合适的一个间隔。换言之，这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。
• 于是最大间隔分类器（maximum margin classifier）的目标函数可以定义为： $\max \hat γ $
• 同时需要满足一些条件，根据间隔的定义，有（下面两个式子是等价的）：

$$ \begin{array}{lc} & y_{i}\left(w^{T} x_{i}+b\right)=\hat{\gamma}_{i} \geq \hat{\gamma}, \quad i=1, \ldots, n \\ \max _{w, b} & \gamma \\ \text { s.t. } & y_{i}\left(\frac{w^{T}}{\|w\|} \cdot x_{i}+\frac{b}{\|w\|}\right) \geq \gamma, \quad i=1,2, \ldots N\end{array} $$

• 我们希望最大化超平面关于训练集的间隔 $ γ$ ，约束条件表示的是超平面关于每个训练样本点的间隔至少是 $γ$。
• 回顾一下几何间隔的定义：

$$
\tilde{\gamma}=y \gamma=\frac{\hat{\gamma}}{|w|}
$$

• 考虑距离平面最近的点的函数间隔 $ \hat γ$ ，该间隔会随着 $w$ 的倍数变化而变化，此时平面没有变，而我们的目的是找到特定的平面，因此不妨固定 $w$ 的倍率，以消除一个自由度，那么既然可以随便设置，怎么设方怎么来。那么索性就设置 $w$ 的倍率使得最近点的函数间隔 $ \hat γ$ 等于 1 吧，则有最近点距离平面的几何距离 $\tilde{\gamma} = 1 / || w ||$ 且：

$$
y_{i}\left(w^{T} x_{i}+b\right) \geq1,i=1,…,n
$$

• 从而上述目标函数转换成了（即线性可分支持向量机模型的最优化问题）：

$$
\max \frac{1}{|w|}, \quad s.t. , y_{i}\left(w^{T} x_{i}+b\right) \geq 1, i=1, \ldots, n
$$

• 相当于在相应的约束条件下，最大化这个 $1 / ||w||$ 值，而 $1 / ||w||$ 便是几何间隔 $ \tilde{\gamma}$。

• 如下图所示，中间的实线便是寻找到的最优超平面（optimal Hyper Plane），其到两条虚线边界的距离相等，这个距离便是几何间隔 $\tilde{\gamma}$，两条虚线间隔边界之间的距离等于 $2\tilde{\gamma}$ ，而虚线间隔边界上的点则是支持向量。

• 由于这些支持向量刚好在虚线间隔边界上，所以他们满足 $y( w^Tx + b) = 1$，而对于所有不是支持向量的点，则显然有 $y( w^Tx + b) > 1$。

• 所以线性可分支持向量机模型的最优化问题：

$$ \begin{array}{l} \min _{w, b} \quad \frac{1}{2}\|w\|^{2} \\ s.t. \quad y_{i}\left(w^{T} \cdot x_{i}+b\right)-1 \geq 0, \quad i=1,2, \ldots N \end{array} $$

• 这是一个凸二次规划问题，若能求出该优化问题的解 $w$， $b$，那么就可以得到最大间隔超平面 $w^Tx + b = 0$ 及分类函数:

$$
f(x)=\operatorname{sign}\left(w^{T} x+b\right)
$$

从线性可分到线性不可分

支持向量机是一种二分类模型，他的目的是寻找一个超平面对样本进行分割，分割的原则是间隔最大化，最终转换为一个凸二次规划问题来求解，而由简至繁的模型包括：

1. 当训练样本线性可分时，通过硬间隔最大化，学习一个线性可分支持向量机

2. 当训练样本近似线性可分时，通过软间隔最大化，学习一个线性支持向量机

3. 当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性支持向量机

• 接着从之前的目标函数说：

$$ \max \frac{1}{\|w\|} \quad s.t., y_{i}\left(w^{T} x_{i}+b\right) \geq 1, i=1, \ldots, n $$

• 由于求 $1 / ||w||$ 的最大值相当于求 $1 /2 ||w||^2$ 的最小值，所以上述目标函数等价于（$w$ 由分母变为分子，从而也由原来的 max 问题变为 min 问题，很明显，两者问题等价）：

$$
\min \frac{1}{2}|w|^{2} \quad s.t., y_{i}\left(w^{T} x_{i}+b\right) \geq 1, i=1, \ldots, n
$$

• 现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。

• 此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量（dual variable）的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法。

• 这样做的优点在于：

  1. 对偶问题往往更容易求解；
  2. 可以自然的引入核函数，进而推广到非线性分类问题。

从原始问题到对偶问题的求解

原始问题

• 拉格朗日对偶性 简单来说，通过对每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier）$α$，然后定义出拉格朗日函数：

$$ \mathcal{L}(w, b, \alpha)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{n} \alpha_{i}\left(y_{i}\left(w^{T} x_{i}+b\right)-1\right) $$

• 然后令：

$$ \theta(w)=\max _{\alpha_{i} \geq 0} \mathcal{L}(w, b, \alpha) $$

• 当所有约束条件都满足时，则最优值为：

$$
\theta(w)=\frac{1}{2}|w|^{2}
$$

• 上式最优值即最初要最小化的量，所以在要求约束条件得到满足的情况下最小化$ 1 /2 ||w||^2$ ，实际上等价于直接最小化 $\theta(w)$ 。
• 具体写出来，目标函数变成了：

$$ \min _{w, b} \theta(w)=\min _{w, b} \max _{\alpha_{i} \geq 0} \mathcal{L}(w, b, \alpha)=p^{*} $$

对偶问题

• 这里用 $P^*$ 表示这个问题的最优解，且和最初的问题是等价的。如果直接求解，那么一上来便得面对 $w$ 和 $b$ 这两个参数，而 $α_i$ 又是不等式约束，这个求解过程不好做。不妨把最小和最大的位置交换一下，变成：

$$
\max _{\alpha _i \geq 0} \min _{w, b} \mathcal{L}(w, b, \alpha)=d^{*}
$$

• 交换以后的新问题是原始问题的对偶问题，这个新问题的最优值用 $d^$ 来表示。而且有 $d^ \le p^*$，在满足某些条件的情况下，这二者等价，这时候就可以通过求解对偶问题来间接地求解原始问题。
• 换言之，之所以从 $\min \max$ 的原始问题 $p^$，转换为 $\max \min$ 的对偶问题 $d^$，一者是因为 $d^$ 是 $p^$ 的近似解，二者转换为对偶问题后，更容易求解。
• 上面提到了 $d^* \le p^*$ 在满足某些条件的情况下，二者等价，而要让两者等价需满足 strong duality（强对偶），而后有学者在强对偶下提出了KKT条件，且KKT条件的成立要满足 constraint qualifications，而 constraint qualifications 之一就是 Slater条件。
• 所谓的Slater条件是指：凸优化问题，如果存在一个点 $x$，使得所有等式约束都成立，并且所有不等式约束都严格成立（即取严格不等号，而非等号），则满足Slater条件。对于此处，Slater条件成立，所以 $d^* \le p^*$ 可以取等号。
• 一般的，一个最优化数学模型能够表示成下列标准形式：

$$ \begin{array}{l} &\min . f(\mathbf{x}) \\ &s.t. & h_{j}(\mathbf{x})=0, j=1, \ldots p \\&& g_{k}(\mathbf{x}) \leq 0, k=1, \ldots, q \\ &&\mathbf{x} \in \mathbf{X} \subset \mathfrak{R}^{n} \end{array} $$

• 其中 $f(x)$ 是需要最小化的函数，$h(x)$ 是等式约束，$g(x)$ 是不等式约束，$p$ 和 $q$ 分别为等式约束和不等式约束的数量。
• 同时，得明白以下两点：

1. 凸优化的概念: $ \mathcal{X} \subset \mathbb{R}^{n} $ 为一凸集， $ f: \mathcal{X} \rightarrow \mathbb{R} $ 为一凸函数。凸优化就是要找出一点 $ x^{*} \in \mathcal{X} $ ，使得每一 $ -x \in \mathcal{X} $ 满足 $ f\left(x^{*}\right) \leq f(x) $ 。
2. KKT条件的意义: 它是一个非线性规划 (Nonlinear Programming) 问题能有最优化解法的必要 和充分条件。

• 而KKT的条件就是指上面最优化数学模型的标准形式中的最小点 $x^*$ 必须满足下面的条件：

$$ \begin{array}{c} h_{j}\left(\mathbf{x}_{*}\right)=0, j=1, \ldots, p, g_{k}\left(\mathbf{x}_{*}\right) \leq 0, k=1, \ldots, q \\ \nabla f\left(\mathbf{x}_{.}\right)+\sum_{j=1}^{p} \lambda_{j} \nabla h_{j}\left(\mathbf{x}_{*}\right)+\sum_{k=1}^{q} \mu_{k} \nabla g_{k}\left(\mathbf{x}_{*}\right)=\mathbf{0} \\ \lambda_{j} \neq 0, \mu_{k} \geq 0, \mu_{k} g_{k}\left(\mathbf{x}_{*}\right)=0 \end{array} $$

• 经过论证，我们这里的问题是满足KKT条件的（首先已经满足Slater条件，再者 $f$ 和 $g_i$ 也都是可微的，即 $L$ 对 $w$ 和 $b$ 都可导），因此现在我们便转换为求解第二个问题。
• 也就是说原始问题通过满足KKT条件，已经转换成了对偶问题。而求解这个对偶学习问题，分为三个步骤：

1. 要让 $ L(w, b, a)$ 关于 $w$ 和 $b$ 最小化,

2. 求 $\min L$ 对 $α$ 的极大

3. 利用SMO算法求解对偶问题中的拉格朗日乘子

对偶问题求解的三个步骤

• 根据拉格朗日的对偶性，原始问题的对偶问题是极大极小问题，所以我们求解对偶问题的步骤如下：

1. 首先固定 α，要让 $L$ 关于 $w$ 和 $b$ 最小化，我们分别对 $w$， $b$ 求偏导数，即令 $∂L / ∂w$ 和 $∂L / ∂b$ 等于零：

$$ \begin{array}{c} \frac{\partial \mathcal{L}}{\partial w}=0 \Rightarrow w=\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i} \\ \frac{\partial \mathcal{L}}{\partial b}=0 \Rightarrow \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \end{array} $$

将求偏导数的结果，代入下式：

$$ \mathcal{L}(w, b, \alpha)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{n} \alpha_{i}\left(y_{i}\left(w^{T} x_{i}+b\right)-1\right) $$

得到：

$$ \begin{aligned} \mathcal{L}(w, b, \alpha) &=\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j}-\sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j}-b \sum_{i=1}^{n} \alpha_{i} y_{i}+\sum_{i=1}^{n} \alpha_{i} \\ &=\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} \end{aligned} $$

​ 推导过程如下：

$$ \begin{aligned} \mathcal{L}(\mathrm{w}, \mathrm{b}, \alpha) &=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{m} \alpha_{i}\left[y^{(i)}\left(w^{T} x^{(i)}+b\right)-1\right] \\ &=\frac{1}{2} \mathrm{w}^{T} \mathrm{w}-\sum_{i=1}^{m} \alpha_{i} y^{(i)} w^{T} x^{(i)}-\sum_{i=1}^{m} \alpha_{i} y^{(i)} b+\sum_{i=1}^{m} \alpha_{i} \\ &=\frac{1}{2} \mathrm{w}^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}-\sum_{i=1}^{m} \alpha_{i} y^{(i)} w^{T} x^{(i)}-\sum_{i=1}^{m} \alpha_{i} y^{(i)} b+\sum_{i=1}^{m} \alpha_{i} \\ &=\frac{1}{2} \mathrm{w}^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}-w^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}-\sum_{i=1}^{m} \alpha_{i} y^{(i)} b+\sum_{i=1}^{m} \alpha_{i} \\ &=-\frac{1}{2} \mathrm{w}^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}-\sum_{i=1}^{m} \alpha_{i} y^{(i)} b+\sum_{i=1}^{m} \alpha_{i}\\ & =-\frac{1}{2} \mathrm{w}^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}-b \sum_{i=1}^{m} \alpha_{i} y^{(i)}+\sum_{i=1}^{m} \alpha_{i} \\ & =-\frac{1}{2}\left(\sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}\right)^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}-b \sum_{i=1}^{m} \alpha_{i} y^{(i)}+\sum_{i=1}^{m} \alpha_{i} \\ & =-\frac{1}{2} \sum_{i=1}^{m} \alpha_{i} y^{(i)}\left(x^{(i)}\right)^{T} \sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}-b \sum_{i=1}^{m} \alpha_{i} y^{(i)}+\sum_{i=1}^{m} \alpha_{i} \\ & =-\frac{1}{2} \sum_{i=1, j=1}^{m} \alpha_{i} y^{(i)}\left(x^{(i)}\right)^{T} \alpha_{j} y^{(j)} x^{(j)}-b \sum_{i=1}^{m} \alpha_{i} y^{(i)}+\sum_{i=1}^{m} \alpha_{i} \end{aligned} $$

最后，得到：

$$ \begin{aligned} \mathcal{L}(w, b, \alpha) &=\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j}-\sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j}-b \sum_{i=1}^{n} \alpha_{i} y_{i}+\sum_{i=1}^{n} \alpha_{i} \\ &=\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} \end{aligned} $$

此时的拉格朗日函数只包含变量 $α_i$，求解 $\alpha$ 后便能求出 $w$ 和 $b$，由此可见，上面提出来的核心问题：分类函数 $f(x) = w^Tx + b$ 也可以轻而易举的求出来。

2. $L$ 对 $α$ 的极大，即是关于对偶问题的最优化问题。经过上面第一个步骤的求 $w$ 和 $b$，得到的拉格朗日函数式子已经没有变量 $w$, $b$ ，只有 $α$ 。从上面的式子得到：

$$ \begin{array}{c} \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i} x_{j}\\ s.t., \alpha_{i} \geq 0, i=1, \ldots, n \\ \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \end{array} $$

这样，求出了 $α_i$ ，根据上面对 $w$ 求偏导的式子，我们可以求出 $w$。然后通过下面式子，可以求出 $b$，最终得到分离超平面和分类决策函数：

$$ \begin{array}{c} w^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i} \\ b^{*}=y_{j}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left(x_{i} \cdot x_{j}\right) \end{array} $$

3. 在求得 $L(w, b, a)$ 关于 $w$ 和 $b$ 最小化，以及对 $α$ 的极大值后，最后一步则可以利用 SMO 算法求解对偶问题中的拉格朗日乘子 $α$。

我们需要构造并求解对偶约束最优化问题

$$ \begin{array}{ll}\min _{\alpha} & \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i}, x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geq 0, i=1,2, \ldots, N\end{array} $$

上述式子要解决的是在参数 ${α_1, α_2, α_3,…α_n} $上求最大值 $W$ 的问题，至于 $x(i)$ 和 $y(i) $ 都是已知数。

拉格朗日乘子法求解梳理

梳理上述拉格朗日求解过程

• 拉格朗日乘子法解决带约束的优化问题：

$$ \begin{array}{c} \min _{x} f_{0}(x) \\ s.t. f_{i}(x) \leq 0, i=1, \ldots m \\ h_{i}(x)=0, i=1, \ldots q \end{array} $$

• 写成拉格朗日方程：

$$
\min L(x, \lambda, v)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{q} v_{i} h_{i}(x)
$$

• SVM 写成拉格朗日方程：

$$ \begin{array}{c} L(w, b, \alpha)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{n} \alpha_{i}\left(y_{i}\left(w^{T} \cdot \Phi\left(x_{i}\right)+b\right)-1\right) \\ s.t. y_{i}\left(w^{T} \cdot \Phi\left(x_{i}\right)+b\right) \geq 1 \end{array} $$

• 对偶问题：

$$
\min _{w, b} \max _{\alpha} L(w, b, \alpha) \rightarrow \max _{\alpha} \min _{w, b} L(w, b, \alpha)
$$

• 分别对 $w, b$ 求偏导

$$ \begin{array}{l} \frac{\partial L}{\partial w}=0 \Rightarrow w=\sum_{i=1}^{n} \alpha_{i} y_{i} \Phi\left(x_{n}\right) \\ \frac{\partial L}{\partial b}=0 \Rightarrow 0=\sum_{i=1}^{n} \alpha_{i} y_{i} \end{array} $$

• 带入原式，求解 $ \min _{w, b} L(w, b, \alpha) $:

$$ \begin{array}{l} &&w=\sum_{i=1}^{n} \alpha_{i} y_{i} \Phi\left(x_{n}\right) \quad 0=\sum_{i=1}^{n} \alpha_{i} y_{i} \\ L(w, b, \alpha)&=&\frac{1}{2} w^{T} w-w^{T} \sum_{i=1}^{n} \alpha_{i} y_{i} \Phi\left(x_{i}\right)-b \sum_{i=1}^{n} \alpha_{i} y_{i}+\sum_{i=1}^{n} \alpha_{i} \\ & =&\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2}\left(\sum_{i=1}^{n} \alpha_{i} y_{i} \Phi\left(x_{i}\right)\right)^{T} \sum_{i=1}^{n} \alpha_{i} y_{i} \Phi\left(x_{i}\right) \\ &=&\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} \Phi^{T}\left(x_{i}\right) \Phi\left(x_{j}\right) \end{array} $$

• 对 $\alpha$ 求极大值：

$$ \begin{array}{l} \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\Phi\left(x_{i}\right) \cdot \Phi\left(x_{j}\right)\right) \\ s.t. \sum_{i=1}^{n} \alpha_{i} y_{i}=0 , \alpha_{i} \geq 0 \end{array} $$

• 转换为极小值：

$$ \begin{array}{l} \min _{\alpha} \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\Phi\left(x_{i}\right) \cdot \Phi\left(x_{j}\right)\right)-\sum_{i=1}^{n} \alpha_{i}\\ s.t. \sum_{i=1}^{n} \alpha_{i} y_{i}=0 , \alpha_{i} \geq 0 \end{array} $$

从线性不可分到非线性问题

为了过渡到非线性分类情况，我们先看看上述推导过程中得到的一些有趣的形式。

• 首先就是关于我们的 hyper plane，对于一个数据点 $x$ 进行分类，实际上是通过把 $x$ 代入到 $f(x) = w^Tx + b$ 算出结果然后根据其正负号来进行类别划分的。而前面的推导，我们得出：

$$
w=\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}
$$

• 因此分类函数为：

$$ \begin{aligned} f(x) &=\left(\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}\right)^{T} x+b \\ &=\sum_{i=1}^{n} \alpha_{i} y_{i}\left\langle x_{i}, x\right\rangle+b \end{aligned} $$

• 这里的形式的有趣之处在于，对于新点 $x$ 的预测，只需要计算它与训练数据点的内积即可，这一点直观重要，是之后使用Kernel进行非线性推广的基本前提。此外，所谓 Supporting Vector 也在这里显示出来——事实上，所谓非 Supporting Vector所对应的系数 α 都是等于零的，因此对于新点的内积计算实际上只需要针对少量的“支持向量” 而不是所有的训练数据即可。
• 为什么非支持向量对应的 $α$ 等于零呢？直观上来看理解的话，就是这些“后方”的点——正如我们之前分析过一样，对超平面是没有影响的，由于分类完全由超平面决定，所以这些无关的点并不会参与分类问题的计算，因而也就不会产生任何影响了。
• 首先，我们看看通过 Lagrange multiplier 得到的目标函数：

$$ \max _{\alpha_{i} \geq 0} \mathcal{L}(w, b, \alpha)=\max _{\alpha_{i} \geq 0} \frac{1}{2}\|w\|^{2}-\sum_{i=1}^{n} \alpha_{i}\left(y_{i}\left(w^{T} x_{i}+b\right)-1\right) $$

• 注意到如果 $x_i$ 是支持向量的话，上式中 $ \left(y_{i}\left(w^{T} x_{i}+b\right)-1\right) $ 是等于 0 的（因为支持向量的 functional margin 等于1）
• 而对非支持向量来说，functional margin 会大于 1，因此 $ \left(y_{i}\left(w^{T} x_{i}+b\right)-1\right) $ 是大于零的，而 $α_i$ 又是非负的，为了满足最大化，$α_i$ 必须等于0。这也就是这些非 supporting vector 的局限性。
• 至此，我们便得到了一个 maximum margin hyper plane classifier，这就是所谓的支持向量机（Support Vector Machine）。当然，到目前为止，我们的 SVM 还比较弱，只能处理线性的情况，不过，在得到了对偶 dual 形式之后，通过 Kernel 推广到非线性的情况就变成了一件非常容易的事情了（我们之前说过：通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题）。

从线性不可分到特征空间映射与核函数问题——线性不可分支持向量机

线性不可分

• 线性不可分示意图：

• 对于上图的二分类数据点，普通线性分类器不行，最大间隔超平面和软间隔超平面也无能为力。面对这样的线性不可分问题，通常的思路是找一个非线性分类边界（比如组合分类器）来实现分类，而SVM则另辟蹊径，将数据点从原始空间映射到特征空间，而数据在特征空间往往就能实现线性可分。

特征空间映射

对于非线性问题，线性可分支持向量机并不能有效解决，要使用非线性模型才能很好的分类。

• 一维空间向二维空间映射

下面我们考虑一维空间的二分类问题：

我们将它进行一个二次变换，换到二维空间，这里的变换为 $x \rightarrow x^2$。

从上面的例子，我们知道变换的核心思想就是：将原始输入空间的数据集映射到高维特征空间中，从而使得数据集可分。

• 二维空间向二维特征空间映射

上图中二维空间不可分，但是变换一下坐标空间，也能实现线性可分。

• 二维空间向三维空间的映射

二维空间的数据点不仅可以映射到二维空间，同样也可以映射到三维，如上所示，所以同样可以找到一个超平面能够实现在三维空间的线性可分。

首先将原始的输入特征通过函数 $h(x_i)$ 映射到高维空间，拉格朗日对偶有如下形式：
$$
L(w, b, \alpha)=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(h\left(x_{i}\right), h\left(x_{j}\right)\right)+\sum_{i=1}^{N} \alpha_{i}
$$
决策函数为：

$$
f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i} y_{i}\left(h\left(x_{i}\right), h(x)\right)+b^{*}\right)
$$

核函数

• 原始空间向特征空间的映射需要借助映射函数 $Ψ(x)$。例如对于数据点 $x_i$，映射到特征空间就变成了 $Ψ(x_i)$。而 SVM 的一大巧妙之处就是映射后的特征空间数据点内积的计算等价于低维空间数据点在映射函数对应的核函数中计算。这大大降低了运算量，因为有的时候高维空间的计算很复杂，下图是一个将 $m$ 维度向量的映射到特征空间的映射函数的例子：

$$ \Phi(x)=\left[\begin{array}{c}1 \\ \sqrt{2} x_{1} \\ \sqrt{2} x_{2} \\ \mathrm{...} \\ \sqrt{2} x_{m} \\ x_{1}^{2} \\ x_{2}^{2} \\ \mathrm{...} \\ x_{m}^{2} \\ \sqrt{2} x_{1} x_{2} \\ \sqrt{2} x_{1} x_{3} \\ \mathrm{...} \\ \sqrt{2} x_{1} x_{m} \\ \sqrt{2} x_{2} x_{3} \\ \mathrm{...} \\ \sqrt{2} x_{2} x_{m} \\ \mathrm{...} \\ \sqrt{2} x_{m-1} x_{m}\end{array}\right] $$ $$ C_{m+2}^{2}=\frac{(m+2)(m+1)}{2} \approx \frac{m^{2}}{2} $$

• 映射后的维度大概是 $m^2 / 2$维，则计算映射后的数据内积 $Ψ(x_i)^TΨ(x_j)$ 的时间复杂度为 $O(n^2)$。而如果使用核函数，则计算复杂度会降低为 $O(n)$，例如：

$$ K(a,b)=\left(a^{T} \cdot b+1\right)^{2}=\Phi(a)^{T} \cdot \Phi(b) $$

• 其中 $a$，$b$为 $m$ 维的向量，$Ψ(a)$ 为 $a$ 经过上面的映射函数后的 $m^2 / 2$维向量，可以看出核函数 $K(a, b) = (a^Tb + 1)^2$ 计算的时间复杂度为 $O(n)$。

核函数：设从输入空间 $Χ$ 到特征空间 $H$ 的一个映射 $h$，对任意 $x, z$ 属于 $X$，函数 $K(x, z)$ 满足 $K(x, z) = <h(x), h(z)>$，则称 $K$ 为核函数。

核技巧：在学习与预测中只定义核函数，而不显示的定义映射函数 $h$。

• 通常，直接计算 $K(x, z)$ 比较容易，而通过 $h(x)$ 和 $h(z)$ 计算 $K(x, z)$ 并不容易。

• 成为核函数的充要条件：设 $K$ 是对称函数，则 $K(x, z)$ 为核函数的充要条件是对输入空间中任意 $x_i$，$i=1,2,…m$，Gram 矩阵 $K = [K(x_i, x_j)] m^* m$ 是半正定矩阵。

• 对偶问题的目标函数：

$$
L(w, b, \alpha)=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} K\left(x_{i}, x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}
$$

• 决策函数的形式：

$$ f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} K\left(\left(x_{i}, x\right)\right)+b^{*}\right) $$

从线性不可分到软间隔问题——使用松弛变量处理 outliers（软间隔支持向量机）

软间隔（soft-margin）：有时候数据中有一些噪音点，如果我们考虑他们，那么我们的分割超平面就不太好了。

在之前讨论支持向量机的时候，我们就假定，数据是线性可分的，即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据，在下文使用 Kernel 方法对原来的线性 SVM 进行了推广，使得非线性的情况也能处理。虽然通过映射 $Φ(•)$ 将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。

例如可能并不是因为数据本身是非线性结构的，而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为 outlier，在我们原来的SVM模型里，outlier的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 support vector 组成的，如果这些 support vector里又存在 outliers 的话，其影响就很大了。例如下图：

用黑圈圈起来的那个蓝点是一个 outlier，它偏离了自己原本应该在的那个半空间，如果直接忽略掉它的话，原来的分割超平面还是挺好的，但是由于这个 outlier 的出现，导致分割超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。

为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的超平面蓝色间隔边界上，而不会使得超平面发生变形了。

也就是说，在有松弛的情况下 outline 点也属于支持向量SV，同时，对于不同的支持向量，拉格朗日参数的值也不同，如此篇论文 《Large Scale Machine Learning》中的下图所示：

对于远离分类平面的点值为 0；对于边缘上的点值在 $[0, 1/L]$，其中，$L$ 为训练数据集个数，即数据集大小；对于 outline 数据和内部的数据值为 $1/L$。

OK，继续回到问题，我们原来的约束条件为：
$$
y_{i}\left(w^{T} x_{i}+b\right) \geq 1, \quad i=1, \ldots, n
$$
​ 现在考虑到 outlier 问题，约束条件变成了：
$$
y_{i}\left(w^{T} x_{i}+b\right) \geq 1-\xi_{i}, \quad i=1, \ldots, n
$$
​ 其中，$ξ_i >= 0$ 称为松弛变量（slack variable），对应数据点 $x_i$ 允许偏离的 functional margin 的量。当然，如果我们运行 $ξ_i$ 任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些 $ξ_i$ 的总和也要最小，即软间隔支持向量机的学习问题如下（原始问题）：
$$
\min \frac{1}{2}|w|^{2}+C \sum_{i=1}^{n} \xi_{i}
$$
　 其中 $C$ 是惩罚系数，用于控制目标函数中两项（“寻找 margin 最大的超平面” 和 “保证数据点偏差量最小”）之间的权重。注意，其中 $ξ$ 是需要优化的变量（之一），而 C 是一个事先确定好的常量，C 值大时对误分类的惩罚增加（C趋于很大时，意味着分类严格不能有错误），C值小时对误分类的惩罚减小（C 趋于很小时，意味着可以有更大的错误容忍）。完整的写出来是这个样子：

$$ \begin{array}{l} \min \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{n} \xi_{i} \\ s.t., y_{i}\left(w^{T} x_{i}+b\right) \geq 1-\xi_{i}, i=1, \ldots, n \\ \xi_{i} \geq 0, i=1, \ldots, n \end{array} $$

所以上式包含两层含义，使 $||w||^2/2$ 尽量小即间隔尽量大，同时使误分类点的个数尽量小，$C$ 是调和两者的系数，有了上式，就可以和线性可分支持向量机一样考虑线性可分支持向量机一样考虑线性支持向量机的学习过程，此时，线性不可分支持向量机的学习问题可以变为之前的凸二次规划问题的求解。

用之前的方法将限制或约束条件加入到目标函数中，得到新的拉格朗日函数，如下所示：
$$
\mathcal{L}(w, b, \xi, \alpha, r)=\frac{1}{2}|w|^{2}+C \sum_{i=1}^{n} \xi_{i}-\sum_{i=1}^{n} \alpha_{i}\left(y_{i}\left(w^{T} x_{i}+b\right)-1+\xi_{i}\right)-\sum_{i=1}^{n} r_{i} \xi_{i}
$$
　　约束如下：

$$ \begin{array}{c} w=\sum_{i=1}^{n} \alpha_{i} y_{i} \phi\left(x_{n}\right) \\ 0=\sum_{i=1}^{n} \alpha_{i} y_{i} \\ C-\alpha_{i}-\mu_{i}=0 \\ \alpha_{i} \geq 0 \quad \mu_{i} \geq 0 \end{array} $$

​ 分析方法和前面一样，转换为另一个问题之后，解法类似，我们先让 $L$ 针对 $w, b$ 和 $ξ$ 最小化：

$$ \begin{aligned} \frac{\partial \mathcal{L}}{\partial w} &=0 \Rightarrow w=\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i} \\ \frac{\partial \mathcal{L}}{\partial b} &=0 \Rightarrow \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \\ \frac{\partial \mathcal{L}}{\partial \xi_{i}} &=0 \Rightarrow C-\alpha_{i}-r_{i}=0, \quad i=1, \ldots, n \end{aligned} $$

将 $w$ 带回 $L$ 并化简，得到和原来一样的目标函数：

$$ \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}\left\langle x_{i}, x_{j}\right\rangle $$

​ 不过由于我们得到 $C - α_i - r_i = 0$ 而 又有 $ r_i >= 0$ （作为 Lagrange multiplier 的条件），因此有 $α_i <= C$，所以整个 dual 问题现在写作：

$$ \begin{aligned} \max _{\alpha} & \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}\left\langle x_{i}, x_{j}\right\rangle \\ \text { s.t. }, & 0 \leq \alpha_{i} \leq C, i=1, \ldots, n \\ & \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \end{aligned} $$

​ 把前后的结果对比一下：

​ 可以看到唯一的区别就是现在 dual varibale $α$ 多了一个上限 $C$。而 Kernel 化的非线性形式也是一样的，只要把 $<x_i, x_j>$ 换成 $k(x_i, x_j)$即可。这样一来，一个完整的可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机就介绍完毕了。

所以可以做一个总结，不准确的说：SVM它本质上是一个分类方法，用 $WT+b$ 定义分类函数，于是求 $w$，$b$ 为寻最大间隔，引出 $1 / 2 || w || ^2$，继而引入拉格朗日因子，化为对拉格朗日乘子 $\alpha$ 的求解（求解过程中会设计一系列的最优化或凸二次规划等问题），如此，求 $w.b$ 与 求 $\alpha$ 等价，而 $\alpha$ 的求解可以用一种快速学习算法 SMO，至于核函数，是为了处理非线性问题，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。

支持向量机（SVM）的优缺点

支持向量机（SVM）是一组用于分类，回归和异常值检测的监督学习方法。

优点

• 在高维空间有效
• 在维度数量大于样本数量的情况下仍然有效
• 在决策功能（称为支持向量）中使用训练点的子集，因此他也是内存有效的
• 多功能：可以为决策功能指定不同的内核函数。提供通过内核，也可以指定自定义内核

缺点

• 如果特征数量远远大于样本数量，则该方法可能会导致交叉的性能
• 支持向量机不直接提供概率估计，这些是使用昂贵的五折交叉验证计算的

知识储备

凸优化

我们可以看到，上面线性可分支持向量机模型的最优化问题如下：

$$ \begin{array}{ll}\min _{w, b} & \frac{1}{2}\|w\|^{2} \\ \text { s.t. } & y_{i}\left(w^{T} \cdot x_{i}+b\right)-1 \geq 0, \quad i=1,2, \ldots N\end{array} $$

​ 上面的基本型目标函数是二次的，约束条件是线性的，这是一个凸二次规划问题。可以直接用现成的优化计算包求解。但若利用“对偶问题”来求解，会更高效。

啥是凸？什么是凸优化？

凸优化说的是这样一回事情：

• $ X \subset R^{n} $ 为一凸集， $ f: X \rightarrow R $ 为一凸函数，凸优化就是要找出一点 $ x^{*} \in X $, 使得任意 $ x \in X $, 都满足 $ f\left(x^{*}\right) \leq f(x) $.

凸优化可以想象成给我一个凸函数，我们需要找最低点。

为啥叫二次规划问题呢？

据了解。目标函数和约束条件都为变量的线性函数，叫做——线性规划问题。目标函数为变量的二次函数和约束条件为变量的线性函数，叫做二次规划问题。

• 拉格朗日函数

$$ L(w, b, \alpha)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N} \alpha_{i} y_{i}\left(w^{T} \cdot x_{i}+b\right)+\sum_{i=1}^{N} \alpha_{i} $$

拉格朗日对偶性，即通过给每一个约束条件加上一个拉格朗日乘子。然后定义出拉格朗日函数，通过拉格朗日函数将约束条件融合进目标函数中。目的是，只需要通过一个目标函数包含约束条件，便可以解释清楚问题。

有约束最优化问题的数学模型

SVM 问题是一个不等式约束条件下的优化问题。绝大多数模式识别教程在讨论这个问题时都会加上优化算法的简介。

有约束优化问题的几何意向

约束条件一般分为等式约束和不等式约束，前者表示为 g(x) = 0 ；后者表示为 g(x) <= 0、

假设 x 属于 Rd（就是这个向量一共有 d 个标量组成），则 g(x) = 0 则是由 d-1 维的超平面。那么有约束优化问题就要求在这个 d-1 维的曲面或者超平面上找到能使得目标函数最小的点，这个 d-1 维的曲面就是“可行解区域”。

对于不等式约束条件， g(x) <= 0 ，则可行解区域 d-1 维曲面扩展成 d 维空间的一个子集。我们可以从 d=2 的二维空间进行比对理解。等式约束对应的可行解空间就是一条线；不等式约束对应的则是这条线以及线的某一侧对应的区域，就像下面的这幅图（图中的模板函数等高线其实就是等值线，在同一条等值线上的点对应的目标函数值相等）。

拉格朗日乘子法

尽管上面我们已经想象出有约束优化问题的几何意向。可是如何利用代数方法找到这个被约束了的最优解呢？这就需要用到拉格朗日乘子法。

首先定义原始目标函数 f(x)，拉格朗日乘子法的基本思想是把约束条件转换为新的目标函数 L(x, λ) 的一部分，从而使有约束优化问题变成我们习惯的无约束优化问题，那么该如何去改造原来的目标函数 f(x)，使得新的目标函数 L(x, λ) 的最优解恰好在可行解区域中呢？这就需要我们去分析可行解区域的最优解的特点。

KKT条件

• KKT条件是一个线性规划问题能有最优解的充分和必要条件。

• 对于不等式约束条件 $g(x) \le 0 $ 的情况，如下图所示，最优解所在的位置 $x^*$ 有两种可能，或者在边界曲线 $g(x)=0$ 上或者在可行解区域内部满足不等式 $g(x) < 0$ 的地方。

• 第一种情况：最优解在边界上，就相当于约束条件就是 $g(x) = 0$.参考下图，注意此时的目标函数 $f(x)$ 的最优解是在可行解区域外面，所以函数 $f(x)$ 在最优解 $x^ * $ 附加的变化趋势是“在可行解区域内侧较大而在区域外侧较小”，与之对应的是函数 $g(x)$ 在可行解区域内小于 0 ，在区域外大于零，所以在最优解 $x^ * $ 附加的变换趋势是内部较小而外部较大。这意味着目标函数 $f(x)$ 的梯度方向与约束条件函数 $g(x)$ 的梯度方向相反。因此根据下式，可以推断出参数 $λ > 0$。

$$
L(\boldsymbol{x}, \lambda)=f(\boldsymbol{x})+\lambda g(\boldsymbol{x})
$$

• 一般的，一个最优化数学模型可以表示成如下形式：

$$ \begin{array}{l} \min f(x) \\ s.t. h_{i}(x)=0, i=1,2, \ldots, p \\ g_{j}(x) \leq 0, j=1,2, \ldots, q \\ x \in X \in R^{n} \end{array} $$

• $h(x)$ 是等式约束，$g(x)$ 是不等式约束，$p$, $q$ 表示约束的数量。

而这个最优化数学模型的最优解 $x^*$ 需满足的条件（即KTT条件）为：

$$ \begin{array}{l} h_{i}\left(x^{*}\right)=0, i=1,2, \ldots, p \\ g_{j}\left(x^{*}\right)=0, j=1,2, \ldots, q \\ \nabla f\left(x^{*}\right)+\sum_{i=1}^{p} \lambda_{i} \nabla h_{i}\left(x^{*}\right)+\sum_{j=1}^{q} \mu_{k} \nabla g_{k}\left(x^{*}\right)=0 \\ \lambda_{i} \neq 0, \mu_{k} \geq 0, \mu_{k} g_{k}\left(x^{*}\right)=0 \end{array} $$

代入SVM中来看。

• 对于带等式和不等式的约束问题，在最优点处必须满足 KKT 条件，将KKT条件应用于SVM原问题的拉格朗日乘子函数，得到关于所有变量的方程，对于原问题中的两组不等式约束，根据KKT条件必须满足（和上面的一样）：

$$ \begin{array}{c} \alpha_{i}\left(y^{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right)-1+\xi_{i}\right)=0, i=1, \ldots, l \\ \beta_{i} \xi_{i}=0, i=1, \ldots, l \end{array} $$

• 对于第一个方程，**第一种情况：**如果 $α_i > 0$，则必须有：

$$ y^{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right)-1+\xi_{i}=0 $$

• 即：

$$ y^{i}\left(\mathrm{~W}^{\mathrm{T}} \mathrm{x}_{i}+b\right)=1-\xi_{i} $$

• 而由于 $ξ_i \geq 0$，因此必定有：

$$ y^{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \leq 1 $$

• 再来看第二种情况：如果 $α_i = 0$，则对 $ y^{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right)-1+\xi_{i}=0 $ 的值没有约束。由于有 $α_i + β_i = C$ 的约束，因此 $β_i = C$ ，又因为 $β_iξ_i = 0 $的限制，如果 $β_i >0$，则必须有 $ξ_i = 0$。由于原问题中有约束条件：

$$ y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \geq 1-\xi_{i} $$

而由于 $ξ_i = 0$，因此有
$$
y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \geq 1
$$

• **最后第三种情况：对于 $α_i >$ 0 的情况，我们又可以细分为 $α_i < C$ 和$α_i = C$ 的情况。**如果 $α_i < C$ ，由于有 $α_i + β_i = C$ 的约束，因此有 $β_i > 0$；因为有 $β_iξ_i = 0$ 的约束，因此有 $ξ_i = 0$。不等式约束：

$$ y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \geq 1-\xi_{i} $$

• 变为：

$$
y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \geq 1
$$

• 由于 $0 < α_i < C$ 时，既要满足：

$$
y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \le 1
$$

又要满足：
$$
y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \geq 1
$$

• 因此有：

$$
y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \geq 1
$$

• 将三种情况合并起来，在最优点，所有样本都必须满足：

$$ \begin{array}{c} \alpha_{i}=0 \Rightarrow y_{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right) \geq 1 \end{array} $$ $$ 0<\alpha_{i} < C \Rightarrow y^{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_{i}+b\right)=1 $$ $$ \alpha_{i}=C \Rightarrow y^{i}\left(\mathrm{w}^{\mathrm{T}} \mathrm{x}_ {i}+b\right) \le1 $$

• 上面第一种情况对应的是自由变量即非支持向量，第二种情况对应的是支持向量，第三种情况对应的是违反不等式约束的样本。在SMO算法求解中，会应用此条件来选择优化变量。

参考资料

• https://www.cnblogs.com/wj-1314/p/12899598.html

文章链接：
https://www.zywvvd.com/notes/study/machine-learning/about-svm/svm-summarize/svm-summarize/