@[toc]
注：转载请标明原文出处链接：https://xiongyiming.blog.csdn.net/article/details/94553561

1 SVM 简介

支持向量机 (Support Vector Machine, SVM)是一类按监督学习 (supervised learning)方式对数据进行二元分类(binary classification)的广义线性分类器 (generalized linear classifier)，其决策边界是对学习样本求解的最大边距超平面(maximum-margin hyperplane)。
SVM被提出于1964年，在二十世纪90年代后得到快速发展并衍生出一系列改进和扩展算法，在人像识别（face recognition）、 文本分类（text categorization）等模式识别（pattern recognition）问题中有得到应用。
SVM是由模式识别中广义肖像算法（generalized portrait algorithm）发展而来的分类器，其早期工作来自前苏联学者Vladimir N. Vapnik和Alexander Y. Lerner在1963年发表的研究 [8] 。1964年，Vapnik和Alexey Y. Chervonenkis对广义肖像算法进行了进一步讨论并建立了硬边距的线性SVM [9] 。此后在二十世纪70-80年代，随着模式识别中最大边距决策边界的理论研究 [10] 、基于松弛变量（slack variable）的规划问题求解技术的出现 [11] ，和VC维（Vapnik-Chervonenkis dimension, VC dimension）的提出 [12] ，SVM被逐步理论化并成为统计学习理论的一部分。1992年，Bernhard E. Boser、Isabelle M. Guyon和Vapnik通过核方法首次得到了非线性SVM。1995年，Corinna Cortes和Vapnik提出了软边距的非线性SVM并将其应用于手写数字识别问题，这份研究在发表后得到了广泛的关注和引用，为其后SVM在各领域的应用奠定了基础。
(以上来源于百度百科)

2 引例

我们通过一个故事来理解SVM。这个故事也主要参考博客：https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html
很久以前一位大侠闭关修炼10年，想在江湖上留下自己的名号，不断地向各个武林门派挑战。其中一个门派的掌门布局迎接这位大侠的挑战。这位掌门对这位大侠说："你能用一根棍将下面不同颜色的球分开？要求：尽量在放更多球之后，仍然适用。"(布局如下图所示)

这位大侠很快地找到一个合适的位置放了棍，心想这是考我的智商吗？

这位掌门又随机放了很多球。

显然掌门有几个故意是放错了，大侠有赶紧对棍的位置做出调整。

如上图所示，大侠试图把棍放在最佳位置，好让在棍的两边有尽可能大的间隙。这个间隙就是球到棍的距离，这就是SVM。然而，这位掌门发现这位大侠智力还可以，再考一考内功如何，掌门又重新布局，如下图所示：

现在，这位大侠没有棍可以很好帮他分开两种球了，现在怎么办呢？大侠苦思冥想，一会儿想到了一个办法，大侠用自己闭关修炼10年练出来的内功将这球都打入空中，然后，大侠随手拿一张纸，插入两个球的中间，如下图所示：

现在，掌门这个布局被大侠用一条曲线给分开了，如下图所示：

掌门看了这位大侠内功深厚，对这位大侠赞不绝口。

多年以后，大牛们把这些球称为数据(data)，把棍子称为分类器 (classifier), 找到最大间隙的trick叫做优化(optimization)，用内功将这些球弄到空中称为核(kernel), 那张纸称为超平面 (hyperplane)。

SVM超平面视频链接如下
B站：https://www.bilibili.com/video/av33852263/
YouTube: https://www.youtube.com/watch?v=3liCbRZPrZA

当一个分类问题，数据是线性可分的，也就是用一根棍就可以将两种小球分开的时候，我们只要将棍的位置放在让小球距离棍的距离最大化的位置即可，寻找这个最大间隔的过程，就叫做最优化。但是，现实往往是很残酷的，一般的数据是线性不可分的，也就是找不到一个棍将两种小球很好的分类。这个时候，我们就需要像大侠一样，运用内功将小球拍起，用一张纸代替小棍将小球进行分类。想要让数据飞起，我们需要的东西就是核函数 (kernel)，用于切分小球的纸，就是超平面(hyperplane)。
下面就将具体说明SVM背后的最优化问题。

3 SVM背后的最优化问题

3.1 自然语言描述

对于下图的数据进行分类，我们容易地将其进行分类，并且有很多种方法。

如下图所示，给出了三种办法将数据进行分类，直观看上去，应该去找位于两类训练样本的“正中间”画出分界线。因为中间的那条线中规中矩，对训练样本的局部扰动的容忍性最好。

因此，在进行分类时，我们需要找出最佳的分界线(超平面)，这样的分类结果的鲁棒性更强。

SVM需要尝试寻找最优的决策边界，距离两个类型的最近的样本最远。上图外边的两条直线上的点(最近的样本点) 称之为支持向量。而外边的两条直线的距离称之为间隔(margin)。SVM的任务就是使得间隔最大化。
对于上述问题可以很容易的进行分类，我们称之为硬间隔 (Hard Margin)。而在实际情况中，大部分数据并不是这么容易进行分类。为了解决上述问题，我们允许SVM出现一些错误并且这些错误在一定范围是可接受的，这被称之为软间隔 (soft margin)。

3.2 数学语言描述

前面说到，SVM的任务就是使得间隔最大化，如下图所示，间隔为2，那么如何使用做数学去描述这个间隔呢？

首先回顾一下高中学习过的<stron>：
给出点，直线为，则点到直线的距离为：
$\left( {{x_0},{y_0},{z_0}} \right){\rm{A}}x + {\rm{B}}y{\rm{ + C}}z{\rm{ + D}} = 0rn{\bf{w}} = ({w_1};{w_2}; \ldots ;{w_d})bn\left( {{\bf{w}},b} \right)n\left( {{\bf{w}},b} \right)\left| {\bf{w}} \right| = \sqrt {w_1^2 + w_2^2 + \ldots + w_d^2}D = \left{ {({{\bf{x}}_1},{y_1}),({{\bf{x}}_2},{y_2}), \ldots ,({{\bf{x}}_m},{y_m})} \right},{y_i} \in \left{ { + 1, - 1} \right}({{\bf{x}}_m},{y_m}) \in D\forall {y_i} = + 1{{\left| {{{\bf{w}}^{\rm{T}}}{\bf{x}} + b} \right|} \over {\left| {\bf{w}} \right|}} \ge d\forall {y_i} = - 1d{{\left| {{{\bf{w}}^{\rm{T}}}{\bf{x}} + b} \right|} \over {\left| {\bf{w}} \right|}} \ge d{{{{\bf{w}}^{\rm{T}}}{\bf{x}} + b} \over {\left| {\bf{w}} \right|}} \le - d\left| {\bf{w}} \right|d{\bf{w}}_d^{\rm{T}} = {{{{\bf{w}}^{\rm{T}}}} \over {\left| {\bf{w}} \right|d}}{b_d} = {b \over {\left| {\bf{w}} \right|d}}$。这样化简的目的是方便后面的计算。</stron>

因此，化简后的分类直线如下图所示：

其中，最中间的直线方程同样也可以化简，如下图所示：

这样三条直线方程都统一起来，为了后面表达方便，我们再次化简，将公式(7)重新定义为：
${y_i}$因此，要有正确分类，必须满足公式(9)的表达式。即公式(9)作为约束条件。

我们的任务就是最大化间隔，而间隔的大小为2：
$$注：这个最优化问题是有约束条件的，我们称之为有条件的最优化问题。

显然，为了最大化间隔，仅需要最大化 ，这个等价于最小化 。则公示最优化问题可转化为：
$$这就是支持向量机 (Support Vector Machine, SVM) 背后的最优化问题。

注：本博客只说明支持向量机的原理(背后的最优化的问题)。关于最优化问题如何求解比较复杂，后面有时间会更新。

参考资料

[1] https://coding.imooc.com/class/169.html#Anchor
[2] https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html
[3] 机器学习, 北京: 清华大学出版社, 2016年1月
[4] 机器学习(西瓜书). 公式推导解析