支持向量机（问题描述）_设二维特征空间r2中有一个线性可分的二分类问题,其判断函数为g(x,y)=x+2y=4. (1)

支持向量机（问题描述）

如果一个数据集是线性可分的将存在无穷多个超平面将各个类别分开；

一、 支持向量机算法

1. 分为两个步骤

• 解决线性可分问题；
• 再将线性可分问题中获得的结论推广到线性不可分情况。

2. 如何解决线性可分问题

提出问题：
既然一个数据集是线性可分的，那么将存在无数多个超平面将各个类别分开，在这无数多个超平面中，到底哪一个最好呢？

（1）例如如下这个例子：二维特征空间中的二分类问题

① 问题一：这三条线中哪条线好？

• 大部分人会认为第二条线好，这是很奇怪的事情；
• 因为根据没有免费午餐定理，在没有假设训练数据的先验分布的情况下，三条线的表现应该是一样的，那为什么大多数人会觉得第二条线更好呢？
• 我们认为第二条线比较好，实际上是对训练样本的先验分布有一定的假设；
• 这里给出其中一种假设：假设训练样本的位置在特征空间上有测量误差；
• 因为若是有○或×在第二条线上，那么此时1,3号线都会给出错误的结果，而第二条线对样本所处的位置的误差的容错程度是最高的；
• 相比较于1,3，第二号线更能抵御训练样本位置的误差；

② 问题二：二号线是怎么画出来的？

Vladimir Vapnik 给出的答案是基于最优化理论，将寻找二号线的过程，变成了一个最优化 的问题。
VAPNIK的回答：假设对于任意一条分开○与×这两个类别的直线，我们将这条直线朝一侧平行的移动，直到它碰到一个或几个训练样本为止，然后将这条直线往另外一侧平行的移动，直到它碰到一个或几个训练样本为止；（平行线移动）

• 在上图中，定义这两条平行线插到的训练样本叫作这个数据集的支持向量（Support Vectors），将这两条平行线之间的距离叫作间隔；
• 要求的2号线，是使得间隔（Margin）最大的一条线
• 对比三条线的间隔，2号最大；
  
• 支持向量机要找的是使margin最大的那一条直线；
• 但是我们会发现，使用margin最大这个条件并不能唯一确定一条直线，因为任何一条与2号线平行的直线且能分开两类的直线，所产生的margin是一样大的，为了让找到的直线唯一，我们还需要定义一个条件：这条线应该在上下两个平行线的正中间，即这条线应该到左右两边所有的支持向量距离应该相等；
• 因此在线性可分的情况下，支持向量机寻找的最优分类直线应满足如下三个条件：
• （1）该直线分开了两个类别；
• （2）该直线最大化间隔（margin）；
• （3）该直线处于间隔的中间，到所有支持向量距离相等；
• 上述的讨论是基于二维特征空间的结果，在高维的特征空间中，直线将变成超平面，但是以上结论一致

思考：证明在线性可分条件下，有且只有唯一一条直线，满足上面三个条件？