支持向量机
用於監督統計學習的一套方法 / 維基百科,自由的 encyclopedia
親愛的 Wikiwand AI, 讓我們通過簡單地回答這些關鍵問題來保持簡短:
你能列出最重要的事實和統計數據嗎 支持向量机?
為 10 歲的孩子總結這篇文章
在机器学习中,支持向量机 (台湾称支援向量機,英語:support vector machine,常简称為SVM,又名支援向量网络[1])是在分类与迴歸分析中分析数据的監督式學習模型与相关的学习算法。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法建立一个将新的实例分配给两个类别之一的模型,使其成为非概率二元(英语:binary classifier)线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。
除了进行线性分类之外,SVM还可以使用所谓的核技巧(英语:kernel trick)有效地进行非线性分类,将其输入隐式映射到高维特征空间中。
当数据未被标记时,不能进行监督式学习,需要用非監督式學習,它会尝试找出数据到簇的自然聚类,并将新数据映射到这些已形成的簇。将支援向量机改进的聚类算法被称为支援向量聚类[2],当数据未被标记或者仅一些数据被标记时,支援向量聚类经常在工业应用中用作分类步骤的预处理。
将数据进行分类是机器学习中的一项常见任务。 假设某些给定的数据点各自属于两个类之一,而目标是确定新数据点将在哪个类中。对于支持向量机来说,数据点被视为 维向量,而我们想知道是否可以用 维超平面来分开这些点。这就是所谓的线性分类器。可能有许多超平面可以把数据分类。最佳超平面的一个合理选择是以最大间隔把两个类分开的超平面。因此,我们要选择能够让到每边最近的数据点的距离最大化的超平面。如果存在这样的超平面,则称为最大间隔超平面,而其定义的线性分类器被称为最大间隔分类器(英语:margin classifier),或者叫做最佳稳定性感知器。[來源請求]
更正式地来说,支持向量机在高维或无限维空间中构造超平面或超平面集合,其可以用于分类、回归或其他任务。直觀來說,分類邊界距離最近的訓練資料點越遠越好,因為這樣可以缩小分類器的泛化誤差。
尽管原始问题可能是在有限维空间中陈述的,但用于区分的集合在该空间中往往线性不可分(英语:Linear separability)。为此,有人提出将原有限维空间映射到维数高得多的空间中,在该空间中进行分离可能会更容易。为了保持计算负荷合理,人们选择适合该问题的核函数(英语:Positive-definite kernel) 来定义SVM方案使用的映射,以确保用原始空间中的变量可以很容易计算点积。[3] 高维空间中的超平面定义为与该空间中的某向量的点积是常数的点的集合。定义超平面的向量可以选择在数据集中出现的特征向量 的图像的参数 的线性组合。通过选择超平面,被映射到超平面上的特征空间中的点集 由以下关系定义: 注意,如果随着 逐渐远离 , 变小,则求和中的每一项都是在衡量测试点 与对应的数据基点 的接近程度。这样,上述内核的总和可以用于衡量每个测试点相对于待分离的集合中的数据点的相对接近度。
- 用于文本和超文本的分类,在归纳和直推方法中都可以显著减少所需要的有类标的样本数。
- 用于图像分类。实验结果显示:在经过三到四轮相关反馈之后,比起传统的查询优化方案,支持向量机能够取得明显更高的搜索准确度。这同样也适用于图像分割系统,比如使用Vapnik所建议的使用特权方法的修改版本SVM的那些图像分割系统。[4][5]
- 用于手写字体识别。
- 用于医学中分类蛋白质,超过90%的化合物能够被正确分类。基于支持向量机权重的置换测试已被建议作为一种机制,用于解释的支持向量机模型。[6][7] 支持向量机权重也被用来解释过去的SVM模型。[8] 为识别模型用于进行预测的特征而对支持向量机模型做出事后解释是在生物科学中具有特殊意义的相对较新的研究领域。
原始SVM算法是由蘇聯數學家弗拉基米尔·瓦普尼克和亞歷克塞·澤范蘭傑斯于1963年发明的。1992年,伯恩哈德·E·博瑟(Bernhard E. Boser)、伊莎贝尔·M·盖昂(Isabelle M. Guyon)和瓦普尼克提出了一种通过将核技巧应用于最大间隔超平面来创建非线性分类器的方法。[9] 当前标准的前身(软间隔)由科琳娜·科特斯和瓦普尼克于1993年提出,并于1995年发表。[1]
我们考虑以下形式的 点测试集:
其中 是 1 或者 −1,表明点 所属的类。 中每个都是一个 维实向量。我们要求将 的点集 与 的点集分开的 “最大间隔超平面”,使得超平面与最近的点 之间的距离最大化。
任何超平面都可以写作满足下面方程的点集
其中 (不必是归一化的)是该法向量。参数 决定从原点沿法向量 到超平面的偏移量。
如果这些训练数据是线性可分的,可以选择分离两类数据的两个平行超平面,使得它们之间的距离尽可能大。在这两个超平面范围内的区域称为“间隔”,最大间隔超平面是位于它们正中间的超平面。这些超平面可以由方程:
或是
来表示。通过几何不难得到这两个超平面之间的距离是 ,因此要使两平面间的距离最大,我们需要最小化 。同时为了使得样本数据点都在超平面的间隔区以外,我们需要保证对于所有的 满足其中的一个条件:
- 若
或是
- 若
这些约束表明每个数据点都必须位于间隔的正确一侧。
这两个式子可以写作:
可以用这个式子一起来得到优化问题:
“在 条件下,最小化 ,对于 "
这个问题的解 与 决定了我们的分类器 。
此几何描述的一个显而易见却重要的结果是,最大间隔超平面完全是由最靠近它的那些 确定的。这些 叫做支持向量。
为了将SVM扩展到数据线性不可分的情况,我们引入铰链损失函数,
当约束条件 (1) 满足时(也就是如果 位于边距的正确一侧)此函数为零。对于间隔的错误一侧的数据,该函数的值与距间隔的距离成正比。 然后我们希望最小化
其中参数 用来权衡增加间隔大小与确保 位于间隔的正确一侧之间的关系。因此,对于足够小的 值,如果输入数据是可以线性分类的,则软间隔SVM与硬间隔SVM将表现相同,但即使不可线性分类,仍能学习出可行的分类规则。
弗拉基米尔·瓦普尼克在1963年提出的原始最大间隔超平面算法构造了一个线性分类器。而1992年,伯恩哈德·E·博瑟(Bernhard E. Boser)、伊莎贝尔·M·盖昂(Isabelle M. Guyon)和瓦普尼克提出了一种通过将核技巧(英语:kernel trick)(最初由Aizerman et al.[10]提出)应用于最大边界超平面来创建非线性分类器的方法。[11] 所得到的算法形式上类似,除了把点积换成了非线性核函数。这就允许算法在变换后的特征空间中拟合最大间隔超平面。该变换可以是非线性的,而变换空间是高维的;虽然分类器是变换后的特征空间中的超平面,但它在原始输入空间中可以是非线性的。
值得注意的是,更高维的特征空间增加了支持向量机的泛化误差,但给定足够多的样本,算法仍能表现良好。[12]
常见的核函数包括:
- 齊次多項式:
- 非齐次多项式(英语:Polynomial kernel):
- 高斯径向基函数:,其中 。有时参数化表示
- 双曲正切:,其中一些(而非所有) 且
由等式 ,核函数与变换 有关。变换空间中也有 w 值,。与 w 的点积也要用核技巧来计算,即 。
计算(软间隔)SVM分类器等同于使下面表达式最小化
如上所述,由于我们关注的是软间隔分类器, 选择足够小的值就能得到线性可分类输入数据的硬间隔分类器。下面会详细介绍将(2)简化为二次规划问题的经典方法。之后会讨论一些最近才出现的方法,如次梯度下降法和坐标下降法。
最小化(2)可以用下面的方式改写为目标函数可微的约束优化问题。
对所有 我们引入变量 。注意到 是满足 的最小非负数。
因此,我们可以将优化问题叙述如下
这就叫做原型问题。
通过求解上述问题的拉格朗日对偶(英语:Duality (optimization)),得到简化的问题
这就叫做对偶问题。由于对偶最小化问题是受线性约束的 的二次函数,所以它可以通过二次规划算法高效地解出。 这里,变量 定义为满足
.
此外,当 恰好在间隔的正确一侧时 ,且当 位于间隔的边界时 。因此, 可以写为支持向量的线性组合。 可以通过在间隔的边界上找到一个 并求解
得到偏移量 。(注意由于 因而 。)