CS229 课程笔记之五：支持向量机

「支持向量机」（support vector machines）被认为是最好的监督学习算法之一。本章将较完整地阐述支持向量机的内部原理，总体思路如下（本段引用自张雨石的博客）：首先介绍函数间隔和几何间隔，由它们引出最优间隔分类器；为了多快好地解决最优间隔分类器问题，使用了拉格朗日对偶性性质，先要理解原始优化问题与对偶问题，以及它们在什么条件下最优解等价，然后写出最优间隔分类器的对偶形式；通过对最优间隔分类器对偶问题的求解，发现求解时目标函数存在内积形式的计算，据此引入了核技法，引入核技法后就得到了完完全全的 SVM 求解问题，使用序列最小化算法（SMO）进行求解。

1 间隔：直观描述

可以看到，点 A 距离决策边界很远，因此如果要进行预测，我们非常“确信”其标签为 1。而对于点 C ，由于其离决策边界太近，所以我们不能非常确定其标签为 1 ，只要决策边界发生一点点变化，就可能导致对 C 的预测结果发生改变。而 B 的预测置信度介于 A 和 C 之间。

因此，给定一个训练集，我们希望能找到一条决策边界，使我们对所有训练样本的预测是正确且置信度高的，即要求所有样本都远离决策边界。之后我们将用「几何间隔」来对这一描述进行定义。

2 符号变换

3 函数间隔与几何间隔

4 最优间隔分类器

给定一个训练集，我们希望能找到一个超平面，使正样本与负样本之间的“间距”（几何距离）尽量大，这样预测的可信度会更高。

这样我们的问题就转化成了在线性约束下的二次规划问题，可以使用专业软件来求解这个优化问题，从而得到「最优间隔分类器」。

下面，我们要讨论一下拉格朗日对偶，其可以帮助我们推导出上述优化问题的对偶形式，从而更快地进行求解，同时还能够引出核函数，实现在超高维度空间中的求解。

5 拉格朗日对偶性

通过上式我们发现，现在新来一个数据，我们只需要计算它与训练样本的内积即可。并且通过前面的 KKT 对偶互补条件我们知道，只有除了支持向量的那些样本，都有 ，所以，我们只需要将新样本与支持向量进行内积即可进行预测。

通过求解优化问题的对偶形式，我们对要解决的问题的结构有了更为深入的理解，并且还根据输入特征向量之间的内积来表示整个算法。在下一节中，我们将充分利用这些内容，对我们的分类问题使用「核方法」。最终得到的算法，就是「支持向量机」，其将能够在非常高的维度空间中进行有效地学习。

7 核

「以上就是 CS229 中关于支持向量机的全部阐述。」

思维导图