介绍了基本的支持向量机模型。

问题背景

求解

记目标超平面为。考虑任意一点，容易推出其到的距离恰为¹：其中范数取。不妨假设存在完全分开这两类点。我们希望是尽量 robust 的，因此令所有点到的最小距离最大，即：不妨令，则：显然取得最优解时，必然满足。进一步我们将其写作：这就是 SVM 的标准形式。对于使得约束取等的点，我们将其称作 support vector 。写出上述优化问题的 Lagrangian ，得到：则原问题等价于：其 Lagrange dual 为：对偶问题与原问题取等时满足 KKT 条件，即：² 这样：代入 Lagrange dual ，并考虑对偶可行性与 Lagrange 条件得到：从技术上解这个凸优化即可。而通过 KKT 条件和 support vector ，我们可以解出和。

以上的问题被称作 Hard SVM ，顾名思义，因为强制要求了超平面必须分离两类点。如果不强制要求分离，我们考虑引入分类错误的惩罚函数。具体的，Hard SVM 的形式为：我们加入一个惩罚函数³，得到：重写得到：这就是带有 hinge loss 的 Soft SVM 。其处理方式和上述的 Hard SVM 基本相同，这里就不再演示了。

在很多情况下给定的点类不一定是适合用超平面划分的。一个好的思路是，我们可以通过选定某种特征映射，将中的点映射到高维空间（也称特征空间）中去，然后在高维空间中做线性划分。这样做的好处是，高维空间中的超平面在原先的中不一定是线性的，因此适应性会更好。具体的，考虑定义域为，值域为某个希尔伯特空间的映射，则 dual SVM 的形式为：而最终的分类模型为：然而有一个问题是我们很难表示高维空间的向量。注意到我们实际上只关注向量的内积，实际上只需考虑如何快速求内积即可，这种技巧称作 Kernel Trick 。我们将计算特征映射的内积的函数称作核函数，记作。一个简单的例子是多项式核函数，即，注意到低维的内积的幂等于高维中高次项构成的向量的内积。利用这种思路，可以构造出多项式核函数，其中，对应了维空间中的内积。⁴核函数有很多种类，这里就不一一列举了。

一个另外的问题是，给定一个函数，我们如何判定其可否用作核函数。一个简单的思路是，考虑内积的性质，我们只需验证对于任意的，核矩阵都是半正定的即可，这里就不提供详细证明了。

考虑用个超平面进行划分，第个超平面划分第类点以及其余所有的点，每一次划分采用标准的 SVM 方法。这样，我们将得到个决策函数。对于单个待决策的点，选择最优的决策函数对应的类即可。
以上的处理方式是对于每个超平面单独优化。我们也可以考虑同时对总共的个超平面进行优化，此时我们的处理方式将和原先产生显著的区别。具体的，我们会考虑直接对 primal SVM 进行优化，采取诸如 SGD 的数值方法，这里就不细讲了。

考虑使用个超平面进行所有点类的两两划分，每一次划分采用标准的 SVM 方法。这样，我们将得到个超平面。对于单个待决策的点，我们采用投票的方式决定其类别，即，对于每个超平面选择较优的一类投票，再选择总票数最高的类。