SVM，即 Support Vector Machine，中文名称为支持向量机。它是一种常用的二元分类器（binary classifier），由 Vapnik 等提出，它在解决小样本、非线性以及高维问题上有突出的表现。
SVM 的原理是构造一个的超平面（hyperplane），使得距离超平面最近的那些点，即支持向量与超平面之间的 margin 最大，从而将两个集合分开。下面我们分三种情况来讲解 SVM。
情况一：当训练样本线性可分时
在了解怎么训练一个线性 SVM 分类器之前，我们先来了解感知机分类器。
感知机分类器用来解决绝对线性可分的问题，其主要目的是为了训练得到一个超平面，这个超平面可用公式 \(w^Tx + b = 0\) 表示，训练结果就是为了得到一个可保证两个类别分居在超平面两侧、无一样本被错误分类的 \(w\) 和 \(b\)。我们可以用 \(+1\) 和 \(-1\) 来分别表示正类和负类，用 \((x_i, y_i)\) 表示样本 \(i\)。具体的训练方法主要有以下两种。
一种是传统的方法，只考虑 \(w\)，根据每一个误分类点调整 \(w\)。当负类样本被误分为正类样本的时候，有 \(w^Tx > 0\)，此时要减小 \(w\)，即 \(w = w - x_i\)，反之则为 \(w = w + x_i\)，综合两种情况，则可以得到 \(w\) 的更新公式：\(w = w + y_ix_i\)。
另一种是从优化损失函数的角度思考。如果样本被误分类，则有 \(-y_i(w^Tx_i + b) > 0\)。所以我们可以得到损失函数 \(L = -\sum_{x_i \in M}y_i(w^Tx_i + b)\)，其中 \(M\) 表示误分类集合。通过梯度下降算法优化损失函数，就可以得到满意的参数值。这里值得注意的是，由于这是完全线性可分的问题，所以要求最终 \(L = 0\)。
感知器分类器得到的超平面并不能最好地体现分类情况，因此 SVM 引入了硬间隔最大化的概念。
在超平面上任意取两点 \(x_1\)、\(x_2\)，易证 \(w^T(x_1 - x_2) = 0\)，从而我们可以知道 \(w\) 是超平面的法向量。设现在平面外有一点 \(x\)，我们可得距离 \(d = \frac{1}{\|w\|}(w^Tx + b)\)，由于保证距离非负，我们将其改为 \(d = \frac{1}{\|w\|}y_i(w^Tx_i + b)\)。这样子，我们的目标就是对于分类正确的样本，要求找到离超平面距离最近的点，这个点到超平面的距离就是 margin。由于超平面中的 \(w\) 和 \(b\) 可以进行缩放，所以我们直接令距离超平面最近的点满足 \(y_n(w^Tx_n + b) = 1\)，这样子有 \(margin = \frac{1}{\|w\|}\)。因此目标在 \(y_i(w^Tx_i + b) \geq 1\) 最大化 margin，即最小化 \(1/2\|w\|^2\)。这就是基本的 SVM 模型的优化目标。
现在的目标是在一个不等式 \(y_i(w^Tx_i + b) \geq 1\) 的约束下，最小化损失函数 \(1/2\|w\|^2\)，这里需要利用拉格朗日乘子法、对偶问题以及 KKT（Karush-Kuhn-Tucker）条件等知识点。
最优化往往会碰到三种情况：
-
无约束条件：对变量求导，令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可
-
等式约束条件：设目标函数为 \(f(x)\)，约束条件为 \(h_k(x)\)，具体形式如下：
\[min f(x) \\ s.t. \ \ h_k(x)=0 \ \ k=1,2,...,l\]\(s.t.\) 表示 subject to，即受限于的意思，l 表示约束条件的数目。
我们可以用拉格朗日乘子法来解决这个问题，首先构建拉格朗日函数：
\[F(x,\lambda)=f(x)+\sum_{k=1}^l{\lambda_kh_k(x)}\]其中 \(\lambda_k\) 是每个约束条件的待定系数。对函数求偏导，并令其为 0，则可以得到结果。关于拉格朗日的几何意义，可以见链接1、链接2。
-
不等式约束条件：设目标函数为 \(f(x)\)，不等式约束条件为 \(g_k(x)\)，等式约束条件为 \(h_j(x)\)，具体形式如下：
\[min f(x) \\ s.t. \ \ h_j(x)=0 \ \ j=1,2,...,p \\ \ \ g_k(x) \leq 0 \ \ k=1,2,...,q\]同样可以构建如下拉格朗日函数：
\[L(x,\lambda,\mu)=f(x)+\sum_{j=1}^p{\lambda_jh_j(x)}+\sum_{k=1}^q{\mu_kg_k(x)}\]与等式约束求解的方式不同，这里需要用到 KKT（Karush-Kuhn-Tucker）条件。KKT 条件给出了最优值需满足的条件：
\[L(x,\lambda,\mu) \ 对 \ x \ 求导为零 \\ h(x)=0 \\ \mu*g(x)=0 \\ g(x) \leq 0 \\ \mu \geq 0\]通过求取前三个等式即可得到最优解。求解 KKT 条件实际上是求解一个对偶问题。我们定义以下问题：
\[\theta(w)=\max_{a_i \geq 0}L(x,\lambda,\mu)\]观察此式，容易发现最优解也是 \(1/2\|w\|^2\)，等价于原始问题，因此可以得到
\[\min_{w,b}\theta(w)=\min_{w,b}\max_{a_i \geq 0}L(x,\lambda,\mu)=\max_{a_i \geq 0}\min_{w,b}L(x,\lambda,\mu)\]现在问题变成了原始问题的对偶问题，这个新问题的最优解就是原始问题的最优解。
之所以引入对偶问题来解决原始问题，一方面是将原始问题的约束转换为对偶问题中的等式约束，方便问题的求解，另一方面是方便核函数的引入。
情况二：当训练样本只是接近线性可分
由于现实中样本一般难以达到完全线性可分，而且即使做到线性可分，也很难判断这个结果是否是因为过拟合而导致的。所以我们需要引入松弛变量，通过软间隔最大化，来允许模型在一些样本上出错，从而得到线性 SVM。
硬间隔 SVM 的约束条件为 \(y_i(w^Tx_i + b) \geq 1\)，该条件严格要求所有点都需要被正确分类且在最大间隔外，但这在实际情况中是不一定能被满足的。因此我们引入一个松弛变量 \(\xi_i \geq 0\)，来允许部分点被错误分类或在间隔内，即约束条件变为：\(y_i(w^Tx_i + b) \geq 1 - \xi_i\)。与此同时，我们要给目标函数加上对应的损失，保证松弛变量尽可能小，则要最小化的目标函数变为 \(1/2\|w\|^2 + C\sum_{i=1}^N{\xi_i}\)，其中 \(C\) 为惩罚系数，其越大表示离群点越不被希望出现。
情况三：当训练样本线性不可分
需引入核函数将特征空间从低维映射到高维，使样本接近可分，从而通过软间隔最大化学习得到非线性 SVM。
SVM 也可以用来解决单分类问题和多分类问题。
单分类问题是指判断样本是否属于某一类，往往这一类的特征比较明显，容易判别，而当样本不属于这一类的时候，往往特征比较复杂，难以确定。对于单分类 SVM，其目标并不是确定最大 margin，而是确定唯一类别样本的边界。
SVM 可以从二元分类扩展到多元分类，其策略主要有以下两种：
- 一对多（one-against-rest）：对于 k 个类别，有 k 个 SVM。第 m 个 SVM 将第 m 类与其他类别分开。哪个分类器概率高，就说明是该分类
- 一对一（one-against-one）：对于任意两个类别构造一个 SVM，因为 k 个类别供需 k * (k - 1) / 2 个 SVM。通过所有分类器得到的投票判断最后分类结果