支持向量机
支持向量机是一个监督式学习对数据进行二进制分类的方法。他们受到……原则的激励最优的分离,一个好的分类器发现不同类的数据点之间可能存在的最大差距。
例如,学习在地图上区分美国和欧洲的算法可以正确地识别出美国东海岸100英里外的边界,但更好的边界应该是大西洋中部的边界。直观地说,这是因为后者的边界最大化了到美国和欧洲的距离。
背景
原始支持向量机(支持向量机)是由弗拉基米尔·瓦普尼克在1963年发明的。设计它们是为了解决一个长期存在的问题逻辑回归这是另一种用于分类数据的机器学习技术。
逻辑回归是一种概率二元线性分类器,意思是它计算一个数据点属于两个类之一的概率。逻辑回归试图根据模型最大化已知数据点的类别的概率,因此,可以将分类边界任意地靠近某个特定的数据点。这违反了一个常识,即一个好的分类器不应该在一个已知的数据点附近设置边界,因为彼此靠近的数据点应该属于同一类。
最大边缘分类器
支持向量机,另一方面,是non-probabilistic,所以它们100%确定地将一个数据点分配给一个类(尽管糟糕的SVM仍然可能将一个数据点分配给错误的类)。这意味着给一组数据点赋值相同的两个支持向量机具有相同的分类精度。那么,我们该如何确定两者中哪一个更好呢?
答案在于不同类的数据点之间的差距大小。如果两个svm对数据点进行相同的分类赋值,我们希望选择离其分类边界最近的数据点距离其分类边界最远的模型。理想情况下,分类边界将会是一条曲线,沿着类之间的间隙的中间向下,因为这将是与最近的数据点距离最大的分类边界。
在两个的情况下线性可分的类在平面中,这个边界将是一条穿过来自不同类的两个最近数据点的中间的线。通过连接两个数据点的线的中点可以使到每个数据点的距离最大化。在二维以上的情况下,这个边界被称为a超平面.这个推理认为,最好的线性分类器是从边界到每个类的数据点的距离最大的那个,给出了所谓的最大边缘分类器.最大边界分类器的分类边界称为最大利润超平面.支持向量机就是最大边界分类器的一个例子。
定义
SVM的分类边界到最近的数据点的距离称为保证金.最靠近分类边界的每个类的数据点称为支持向量.如果给SVM一个更接近分类边界的数据点,而不是支持向量,SVM宣称该数据点太接近分类准确。这定义了一个“无人地带”对于分类边界边缘内的所有点。因为支持向量是最接近这个“无人地带”的数据点,但并不在其中,所以从直觉上看,它们也是最容易被错误分类的点。
因此,支持向量机可以定义为以下两种假设下的线性分类器:
- 余量应该尽可能大。
- 支持向量是最有用的数据点,因为它们最有可能被错误分类。
第二个假设导致支持向量机的理想性质。SVM经过训练后,可以丢弃所有其他数据点,只使用支持向量进行分类。这意味着一旦分类完成,SVM可以非常有效地预测一个数据点的类别,因为它只需要使用少量的支持向量,而不是整个数据集。这意味着训练支持向量机的主要目标是在数据集中找到支持向量,既分离数据,又找到类之间的最大边界。
Hard-Margin支持向量机
当类是线性可分的时候,SVM的训练最容易在二维空间中可视化。假设我们得到一个数据集 在哪里 为输入 在0班和 为输入 在1班。回顾二维直线的向量方程,定义分类边界为 ,在那里 和 是二维的向量。进一步定义负支持向量为输入向量 和正支持向量作为输入向量 从类1。
再次回顾直线的向量方程,定义负分类边界为 正分类边界为 .则负分类边界与正分类边界的距离为 .因此,边际的大小 是 .
因为我们想要最大化 ,我们要最小化 .然而,我们也想确保没有分数落在“无人地带”,所以我们还需要引入约束 对所有 在0班和 对所有 在1班。这导致了以下优化问题:
最小化 受 为
这个优化问题可以使用线性规划技术。