目标

在本教程中，你将学习如何：

定义当训练数据无法线性分离时 SVM 的优化问题。
如何配置参数以使您的 SVM 适应此类问题。

动机

为什么扩展 SVM 优化问题以处理非线性可分训练数据很有意义？在计算机视觉中使用 SVM 的大多数应用都需要比简单线性分类器更强大的工具。这是因为在这些任务中，训练数据很少能使用超平面完全分离。

考虑其中一项任务，例如人脸检测。在这种情况下，训练数据由一组人脸图像和另一组非人脸图像（世界上除人脸之外的所有其他事物）组成。这些训练数据过于复杂，以至于很难找到一种样本表示（特征向量）能使整组人脸与整组非人脸线性可分。

优化问题的扩展

请记住，使用 SVM 我们会获得一个分离超平面。因此，由于训练数据现在是非线性可分的，我们必须承认找到的超平面会错误分类某些样本。这种误分类是优化中必须考虑的一个新变量。新模型必须同时包含旧的要求（找到具有最大间隔的超平面）和新的要求（通过不允许过多的分类错误来正确泛化训练数据）。

我们从寻找最大化间隔的超平面优化问题公式开始（这在前一篇教程支持向量机简介中有所解释）：

\[\min_{\beta, \beta_{0}} L(\beta) = \frac{1}{2}||\beta||^{2} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 \text{ } \forall i\]

有多种方法可以修改此模型，使其考虑到误分类错误。例如，可以考虑最小化相同的量加上一个常数乘以训练数据中误分类错误的数量，即：

\[\min ||\beta||^{2} + C \text{(误分类错误数)}\]

然而，这并不是一个很好的解决方案，因为除其他原因外，我们无法区分误分类样本与其所属决策区域的距离大小。因此，更好的解决方案将考虑到误分类样本到其正确决策区域的距离，即：

\[\min ||\beta||^{2} + C \text{(误分类样本到其正确区域的距离)}\]

对于训练数据的每个样本，定义了一个新参数 \(\xi_{i}\)。这些参数中的每一个都包含其对应训练样本到其正确决策区域的距离。下图显示了来自两个类别的非线性可分训练数据、一个分离超平面以及误分类样本到其正确区域的距离。

注意: 图中仅显示了误分类样本的距离。其余样本的距离为零，因为它们已经位于正确的决策区域内。

图中出现的红色和蓝色线条是到各个决策区域的间隔。重要的一点是，每个 \(\xi_{i}\) 都是从误分类的训练样本到其所属区域的间隔边界的距离。

最后，优化问题的新公式为：

\[\min_{\beta, \beta_{0}} L(\beta) = ||\beta||^{2} + C \sum_{i} {\xi_{i}} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 - \xi_{i} \text{ and } \xi_{i} \geq 0 \text{ } \forall i\]

应该如何选择参数 C？显而易见，这个问题的答案取决于训练数据的分布方式。虽然没有通用答案，但考虑以下规则会很有帮助：

较大的 C 值会导致误分类错误较少但间隔较小的解决方案。考虑到在这种情况下，发生误分类错误的代价很高。由于优化的目标是最小化该参数，因此只允许很少的误分类错误。
较小的 C 值会导致间隔较大且分类错误较多的解决方案。在这种情况下，最小化过程不太考虑求和项，因此更多地关注寻找具有大间隔的超平面。

源代码

您也可以在 OpenCV 源码库的 samples/cpp/tutorial_code/ml/non_linear_svms 文件夹中找到源代码，或者从这里下载。

说明

设置训练数据

本练习的训练数据由一组带标签的二维点组成，这些点属于两个不同的类别。为了使练习更有趣，训练数据是使用均匀概率密度函数 (PDF) 随机生成的。

我们将训练数据的生成分为两个主要部分。

在第一部分中，我们为两个类别生成线性可分的数据。

在第二部分中，我们为两个类别创建非线性可分的数据，即存在重叠的数据。

设置 SVM 参数

注意: 在前一篇教程支持向量机简介中，解释了类 cv::ml::SVM 的属性，我们在训练 SVM 之前会对其进行配置。

此处我们进行的配置与参考的前一篇教程 (支持向量机简介) 仅有两点不同：

C。我们在这里为该参数选择了一个较小的值，以便在优化过程中不至于过度惩罚误分类错误。这样做的目的是为了获得一个接近直观预期的解决方案。但是，我们建议通过调整此参数来更深入地了解该问题。

注意
在这种情况下，两个类别之间的重叠区域中只有极少数点。通过减小 FRAC_LINEAR_SEP 的值，可以增加点的密度，并深入探索参数 C 的影响。
算法的终止标准。必须大幅增加最大迭代次数，才能正确解决非线性可分训练数据的问题。特别地，我们将此值增加了五个数量级。
训练 SVM

我们调用 cv::ml::SVM::train 方法来构建 SVM 模型。请注意，训练过程可能需要较长时间。运行程序时请耐心等待。

显示决策区域

cv::ml::SVM::predict 方法用于使用训练好的 SVM 对输入样本进行分类。在此示例中，我们使用此方法根据 SVM 的预测结果对空间进行着色。换句话说，遍历一幅图像，将其像素解释为笛卡尔平面上的点。每个点根据 SVM 预测的类别进行着色；如果是标签为 1 的类别则着为深绿色，如果是标签为 2 的类别则着为深蓝色。

显示训练数据

cv::circle 方法用于显示组成训练数据的样本。标签为 1 的类别样本以浅绿色显示，标签为 2 的类别样本以浅蓝色显示。

支持向量

我们在这里使用几个方法来获取有关支持向量的信息。cv::ml::SVM::getSupportVectors 方法获取所有支持向量。我们在这里使用该方法找出作为支持向量的训练样本并突出显示它们。

结果

代码打开一个图像并显示两个类别的训练样本。一类的点用浅绿色表示，另一类用浅蓝色表示。
训练 SVM 并将其用于对图像的所有像素进行分类。这导致图像被划分为蓝色区域和绿色区域。两个区域之间的边界就是分离超平面。由于训练数据是非线性可分的，可以看到两个类别的某些样本被错误分类了；一些绿点落在蓝色区域，一些蓝点落在绿色区域。
最后，在训练样本周围使用灰色圆环显示支持向量。

您可以在此处 YouTube 上观看此过程的运行时演示。


原作者	Fernando Iglesias García
兼容性	OpenCV >= 3.0

目录

目标

动机

优化问题的扩展

源代码

说明

结果