线性SVM

目标函数的转换

• 由于目标函数$\frac{1}{2}||w||^2$,是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数，

线性可分支持向量机学习算法

* 最大间隔算法

* 最大间隔分离超平面的存在唯一性

• 若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一
• 李航书中有证明

支持向量和间隔边界

* 支持向量

• 线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量

• 支持向量是使得$y_i(wx_i+b)-1=0$成立的点

• 在$u_i=+1$的正例点，支持向量在超平面$H_1:wx+b=1$上

• 在$u_i=-1$的负例点，支持向量在超平面$H_1:wx+b=-1$上

• $H_1和H_2$上的点就是支持向量

* 间隔

• $H_1和H_2$之间的距离是间隔；
• 间隔=$\frac{2}{||w||}$
• 间隔边界:$H_1和H_2$

* 结论

• 决定分离超平面时，只有支持向量起作用
• 超平面由很少的重要的支持向量确定；即由重要的训练样本确定

学习的对偶算法

• 线性可分优化问题的数学模型

* 求解方法

• 上述是原始最优化问题；应用拉格朗日对偶性；
• 求解对偶问题
• 从而得到原始问题的最优解
• 优点：(1)对偶问题方便求解(2)可以引入核函数，推广到非线性问题

对偶算法求解线性可分SVM

* 构建拉格朗日函数

* 　和最大熵模型一样的，我们的这个优化函数满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解

* 求解对偶问题

继续求解

* 结论

• 对于线性可分数据集合：
• 首先，求对偶问题(7.22-7.24)的解$\alpha^\ast$
• 再利用（7.25-7.26）求解 元素问题的$w^\ast,b^\ast$
• 得到决策平面和决策函数

例题

* 问题

• 线性可分SVM的学习方法对于非线性的数据集是没有办法使用的， 有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分， 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢？ 我们在下一节的线性SVM的软间隔最大化里继续讲。