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