本文是我学习周志华老师编写的机器学习书籍『西瓜书』的第六章：支持向量机的过程中做的笔记

间隔与支持向量

分类学习的基本思想: 基于训练集 D 在样本空间中找到一个划分超平面, 将不同类别的样本分开.

问题: 划分超平面不唯一, 选择标准?

直观: 应该去找位于两类训练样本“正中间”的划分超平面, 因为为该划分超平面对训练样本局部扰动的“容忍”性最好 ( 鲁棒性高, 泛化能力强 ).

在样本空间中, 使用如下方程定义划分超平面:

可以写出样本空间任意点 到朝平面 的距离可写为:

假设超平面 能将训练样本正确分类, 即对于 , 若 , 则有 ;
若 , 则有 .

由于我们希望划分超平面能够使得两类样本点尽可能可分, 故而为分类面设置余量 ( 间隔 ), 令:

在满足上述条件求解出的分类器在分类超平面与样本点之间保留出一块余量空间, 从而提高分类器的性能, 如图所示.

距离超平面最近的几个训练样本点使得不等式的等号成立, 它们被称为”支持向量” ( support vector ),
两个异类支持向量到超平面的距离之和称为”间隔” ( margin ), 大小为:

我们希望找到具有最大间隔的分类超平面, 从而使分类器有充足的容错率进行分类决策. 这需要我们求解以下优化问题:

显然, 求解的优化问题等价于最小化 , 我们重写优化问题, 使其更加易于求解:

由此, 我们便得到了支持向量机的基本型.

对偶问题

注意到, 支持向量机的基本型本身是一个凸二次规划问题, 可以直接求解, 但是可以更加高效.

我们使用拉格朗日乘数法构造拉格朗日函数:

其中, 针对第 i 条约束添加的拉格朗日乘子 .

不难发现我们添加的拉格朗日乘数项均小于等于零, 这相当于在原优化问题的基础上加入了衰减,
为了还原我们的优化目标, 我们希望所构造的拉格朗日函数尽可能大.

此时, 支持向量机的优化函数可以进一步写为:

由于 与 b 的优化问题更好求解, 我们将该优化问题转化为对偶问题.

令 对 和 b 的偏导为零可得:

将两个等式带入拉格朗日函数 , 即可消去 和 b.

再考虑原优化问题的约束, 我们可以得到以下只与 有关的优化问题:

解出 后, 求出 和 b 即可求解出分类超平面, 而 , b 的求解, 需要利用之前提到的支持向量.

思考这样一个问题, 我们如何确保原问题和对偶问题等价 ( 这里实际上是引入 KKT 条件 ), 从直觉上看, 我们肯定希望引入的拉格朗日乘数项尽可能为 0, 也就是满足:

事实上, 这就是 KKT 条件所需要满足的不等式约束之一. 我们在上文提到过支持向量的概念, 支持向量是位于分类间隔边界的样本点, 满足 ,
因此, 支持向量的存在, 实际上天然地满足以上提到的 KKT 条件约束. 而对于非支持向量的样本点, 只能通过置 使其满足 KKT 条件.

基于以上分析, 不难发现, 对于 的样本点, 即为主导分类超平面的支持向量.

其中, 可以由拉格朗日函数的偏导直接得出表达式, 对于 b, 我们将支持向量带入等式 即可求出.为了充分利用支持向量信息,
一般会通过代入全部支持向量求出 n 组解, 并求平均作为最终的 b.

之前提到, 为了保证对偶问题的等价性, 我们引入 KKT 条件.

我们可以发现, 当 时, 该样本将不会影响 和 b 的值,
分类朝平面只与支持向量有关, 这说明 SVM 的本质是一个小样本学习机.

关于 的求解, 不难发现是一个二次规划问题, 困难在于其问题规模 ( 变量个数 ) 正比于训练样本, 造成巨大开销. SMO 算法是求解 的常用算法,
其基本思路是每次选择两个变量 和 并固定其他参数. 循环往复直到收敛. 其优点是提高了求解效率.

核函数

线性支持向量机不能解决非线性问题 ( ex. XOR ), 因此, 引入核函数.

核函数隐式地定义了输入空间的低维样本在高维空间的相对关系, 其原理在于:

如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分.

令 表示 映射后的特征向量, 则分类超平面可以表示为:

则优化问题为: