目标

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

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

动机

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

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

优化问题的扩展

请记住，使用SVM，我们获得一个分离超平面。因此，由于训练数据现在是非线性可分的，我们必须承认找到的超平面将错误分类一些样本。这种错误分类是优化中必须考虑的一个新变量。新模型必须同时包含找到提供最大裕度的超平面的旧要求，以及通过不允许太多分类错误来正确概括训练数据的新要求。

我们从寻找最大化裕度的超平面的优化问题的公式出发（这在之前的教程(支持向量机简介)中解释过）。

\[\min_{\beta, \beta_{0}} L(\beta) = \frac{1}{2}||\beta||^{2} \text{ 约束条件 } 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{ 约束条件 } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 - \xi_{i} \text{ 和 } \xi_{i} \geq 0 \text{ } \forall i\]

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

较大的C值给出错误分类错误较少但裕度较小的解决方案。考虑在这种情况下，产生错误分类错误的代价很高。由于优化的目标是最小化参数，因此允许的错误分类错误很少。
较小的C值给出裕度较大且分类错误较多的解决方案。在这种情况下，最小化并不那么考虑求和项，因此它更侧重于找到具有较大裕度的超平面。

源代码

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

解释

设置训练数据

本练习的训练数据由一组属于两个不同类别之一的标记二维点组成。为了使练习更具吸引力，训练数据是使用均匀概率密度函数 (PDF) 随机生成的。

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

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

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

设置 SVM 参数

注意: 在之前的教程支持向量机简介中，解释了我们在训练 SVM 之前在此处配置的cv::ml::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

目录

目标

动机

优化问题的扩展

源代码

解释

结果