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