拉格朗日乘子法 - KKT条件 - 对偶问题 支持向量机 (一)： 线性可分类 svm 支持向量机 (二)： 软间隔 svm 与 核函数 支持向量机 (三)： 优化方法与支持向量回归
支持向量机（support vector machine， 以下简称 svm）是机器学习里的重要方法，特别适用于中小型样本、非线性、高维的分类和回归问题。本系列力图展现 svm 的核心思想和完整推导过程，以飨读者。
机器学习的一大任务就是分类（Classification）。如下图所示，假设一个二分类问题，给定一个数据集，里面所有的数据都事先被标记为两类，能很容易找到一个超平面（hyperplane）将其完美分类。
然而实际上可以找到无数个超平面将这两类分开，那么哪一个超平面是效果最好的呢？
要回答这个问题，首先就要定义什么叫做“效果好”？在面临机器学习问题的时候普遍不是很关心训练数据的分类正确与否，而是关心一个新数据出现时其能否被模型正确分类。如果新数据被分类的准确率高，可以认为是“效果好”，或者说有较好的泛化能力。因此这里的问题就转化为：上图中哪一个超平面对新数据的分类准确率最高？
然而令人沮丧的是，没人能确切地回答哪个超平面最好，因为没人能把真实世界中的所有数据都拿过来测试。从广义上来说，大部分的理论研究都是对真实情况的模拟，譬如我们用人均收入来衡量一个国家的人民生活水平，这里的人均收入甚至只是一个不太接近的近似，因为不可能把每个国家中所有人的收入都拿出来一一比较。我们的大脑善于把繁琐的细节组合起来并高度抽象化，形成模型和假设，来逼近真实情况。
所以，在这个问题上我们能做的，也只有提出假设，建立模型，验证假设。而在 svm 中，这个假设就是：拥有最大“间隔”的超平面效果最好。
间隔（margin）指的是所有数据点中到这个超平面的最小距离。如下图所示，实线为超平面，虚线为间隔边界，黑色箭头为间隔，即虚线上的点到超平面的距离。可以看出，虚线上的三个点（2蓝1红）到超平面的距离都是一样的，实际上只有这三个点共同决定了超平面的位置，因而它们被称为“支持向量（support vectors）”，而“支持向量机”也由此而得名。
于是我们来到了svm的核心思想 —— 寻找一个超平面，使其到数据点的间隔最大。原因主要是这样的超平面分类结果较为稳健（robust），对于最难分的数据点(即离超平面最近的点)也能有足够大的确信度将它们分开，因而泛化到新数据点效果较好。
比如上左图的红线和紫线虽然能将两类数据完美分类，但注意到这两个超平面本身非常靠近数据点。以紫线为例，圆点为测试数据，其正确分类为蓝色，但因为超平面到数据点的间隔太近，以至于被错分成了黄色。 而上右图中因为间隔较大，圆点即使比所有蓝点更靠近超平面，最终也能被正确分类。
给定一组数据 \(\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}\)， 其中 \(\boldsymbol{x}_i \in \mathbb{R}^d\)， \(y_i \in \{-1, +1\}\) 。如果两类样本线性可分，即存在一个超平面 \(\boldsymbol{w}^{\top} \boldsymbol{x}+b = 0\) 将两类样本分隔开，这样可以得到：
\[y_{i} \operatorname{sign}\left(\boldsymbol{w}^{\top} \boldsymbol{x}_{i}+b\right)=1 \iff y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{x}_{i}+b\right)>0 \tag{1.1} \]