目标

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

定义当训练数据无法线性分离时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{ 对于所有 } 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{ 对于所有 } 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经过训练并用于分类图像的所有像素。这导致图像被划分为蓝色区域和绿色区域。两个区域之间的边界是分离超平面。由于训练数据是非线性可分的，可以看到两个类别中的一些示例被错误分类；一些绿点落在蓝色区域，一些蓝点落在绿色区域。
最后，使用训练示例周围的灰色环显示支持向量。

你可以在此处观看其运行时实例。


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

目录

目标

动机

优化问题的扩展

源代码

解释

结果