目标

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

对 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 文件夹中找到源代码，或在此处下载。

说明

设置训练数据

本练习的训练数据由一组带标签的 2D 点组成，它们属于两个不同的类。为了让练习更吸引人，训练数据是使用均匀概率密度函数 (PDF) 随机生成的。

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

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

在第二部分，我们为两类创建不可线性分隔的数据，即重叠数据。

设置 SVM 的参数

注意: 在之前的教程SVM 导言中，对 cv::ml::SVM 类的属性进行了说明，我们在此在训练 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 已训练并用于对图片的所有像素进行分类。此操作将图片分成一个蓝色区域和一个绿色区域。两个区域之间的边界是分离超平面。由于训练数据不可线性地分开，因此可以看到两个类别中的一些示例已错误分类；一些绿点位于蓝色区域，而一些蓝点位于绿色区域。
最后，支撑向量使用训练示例周围的灰色环形进行显示。

您可以在此处看到该代码的运行实例。


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

目录

目标

动机

优化问题的扩展

源代码

说明

结果