支持向量机

初见

从知乎上看到一个故事

在很久以前的情人节，大侠要去救他的爱人，但魔鬼和他玩了一个游戏。
魔鬼在桌子上似乎有规律放了两种颜色的球，说：“你用一根棍分开它们？要求：尽量在放更多球之后，仍然适用。

于是大侠这样放，干的不错？

然后魔鬼，又在桌上放了更多的球，似乎有一个球站错了阵营。

**SVM就是试图把棍放在最佳位置，好让在棍的两边有尽可能大的间隙。

现在即使魔鬼放了更多的球，棍仍然是一个好的分界线。

然后，在SVM 工具箱中有另一个更加重要的 trick。 魔鬼看到大侠已经学会了一个trick，于是魔鬼给了大侠一个新的挑战。

现在，大侠没有棍可以很好帮他分开两种球了，现在怎么办呢？当然像所有武侠片中一样大侠桌子一拍，球飞到空中。然后，凭借大侠的轻功，大侠抓起一张纸，插到了两种球的中间。

现在，从魔鬼的角度看这些球，这些球看起来像是被一条曲线分开了。

再之后，无聊的大人们，把这些球叫做 「data」，把棍子 叫做 「classifier」, 最大间隙trick 叫做「optimization」， 拍桌子叫做「kernelling」, 那张纸叫做「hyperplane」。

推导

通过上面的故事我们对SVM有了一个大概的认识
但是我们仍然不知道怎么找出最大的间隔以及实现样本映射
这就需要一些数学理论的支撑

硬间隔最大化

读者需了解拉格朗日乘子法、KTT条件和拉格朗日对偶性
可参考附录中的相关资料

线性可分支持向量机定义
给定线性可分训练数据，通过间隔最大化方法得到的分类超平面为

以及相应的分类决策函数

f(x) 的值样本表示所在分类，即 +1，-1

函数间隔
对于给定的训练数据集T和超平面(w, b)，定义超平面关点`(Xi, Yi)的函数间隔为

其中最小的间隔为

这里我们规范化|w|=1，使得函数间隔的值是唯一的（否则w，b按比例扩大，超平面又没改变，却增大了函数间隔）
称之为几何间隔

间隔最大化
所谓的最大间隔可以表示如下问题

所有点的距离大于最小几何间隔 r

把几何间隔替换为函数间隔，问题可以转述为

几何间隔 = 函数间隔/|W|

把最小函数间隔 r^ 缩放为 1（即按比例改变w，b，缩放所有样本的函数间隔，这并不影响约束关系的成立），这样我们就只需要考虑|W|了
又有最大化 1/|W| 等于最小化 |W|，所以

这是一个凸二次优化问题，我们可以应用拉格朗日对偶性得到原始问题的最优解，一来使得问题更容易求解，二来可以引入核函数。

定义拉格朗日函数

广义拉格朗日函数

根据拉格朗日对偶性，该凸二次优化问题等价于下面的极大极小问题

然后我们就可以开始求解了

根据拉格朗日对偶性，如果 a* 是对偶问题的解，KTT条件成立

然后我们便可以通过求解 a* 得到 w* 和 b*

软间隔最大化

对于有些训练数据集，不能满足应间隔最大化的分隔条件，所以可以对某些样本点的约束条件放宽

软间隔最大化约束条件

其中对每个松弛变量都要支持一个代价ε
这就是软间隔最大化

拉格朗日函数定义

广义拉格朗日函数

利用拉格朗日对偶性得到对偶问题

对偶问题

原始问题是凸二次问题，解满足KTT条件，可得

损失函数
软间隔最大化问题

下标+表示取非负值（小于0的数输出0）

当训练样本分类正确则
[图片上传失败...(image-6b3eec-1524099724972)]]_+=0)
否则代价大于0
并且要求 |w| 越小越好
证明略

非线性支持向量机和核函数

对于线性不可分的训练数据，核技巧把样本映射到不同的空间，从而实现数据可分割。
值得一说的是核技巧不止应用于SVM

核函数定义

其中X为输入空间(欧式空间R^n的子集或者离散集合)

我们注意到线性支持向量机中只应用了实例之间的内积，所以我们不显示定义 φ(x) 而是只定义K(x,z)。实例的内积都可用核函数来表示。这便是核技巧的思想

满足一定条件的函数才能作为核函数（通常所说的核函数即正定核）

结合软最大间隔和核函数我们得到
非线性支持向量机学习算法

附录

拉格朗日乘子法、KKT条件和拉格朗日对偶性
核函数的选择
支持向量机快速学习算法-SMO

参考

《统计学习方法》
Google
维基百科