文档结构  
翻译进度:已翻译     翻译赏金:0 元 (?)    ¥ 我要打赏

目标

本教程你将会学到:

  • 对线性不可分训练数据的SVM优化问题定义
  • 如何为你的SVM问题选择 CvSVMParams

动机

为什么使用SVM优化解决非线性不可分训练数据的问题是有趣的?SVM的大部分计算机视觉应用需要一个更加强大的工具而不仅仅是简单的线性分类。这主要是由于:这些问题的训练数据能够通过使用超平面分开。以其中一个任务为例:面部检测。这个任务的训练数据由包含人脸的图像和不含人脸(除了人脸以外的其他东西)的图像组成。对于这个训练数据找到一个能够使得含人脸图像和不含人脸图像线性可分的特征向量是很困难的。

第 1 段(可获 2 积分)

优化问题的扩展

我们能够通过SVM得到一个分割超平面。因此,由于训练数据是线性不可分的,我们需要允许超平面会产生一些误分割。误分割是在优化中的我们必须考虑在内的一个新变量。新的模型需要包含之前的要求:找到使划分数据产生最大间隔的超平面,以及新的要求:通过控制较少的误分类生成正确的训练数据。我们从找到最大间隔(以前的教程有它的解释)超平面优化问题的公式开始。

第 2 段(可获 2 积分)

\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{(\# misclassication errors)}

但是,这并不是一个非常好的解决方法,因为我们不能够区分出哪些是在决策区域附近相距较小的误分割,哪些不是。因此更好的解决方法需要把误分割数据距离正确决策区域的距离考虑在内,例如:

第 3 段(可获 2 积分)

\min ||\beta||^{2} + C \text{(distance of misclassified samples to their correct regions)}

对每一个训练数据定义一个新的参数\xi_{i} 。此参数报刊了相应训练数据距离正确决策区域的距离。下面的图像显示了包含两类数据的线性不可分数据,超分割平面,以及误分类数据距离正确分割区域的距离。

注:

只有误分类数据的距离显示显示在图像中。由于其他数据已经在正确决策区域内,因此他们的距离为0。图中的红线和蓝线是每一类距离决策区域的间隔。意识到每一个误分类训练数据到适当区域的间隔相关参数\xi_{i}是很重要的。最终,优化问题新的公式为:

第 4 段(可获 2 积分)

\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较小时,结果的间隔较大且误分类误差较大。这种情况最小化不需要考虑到总和,因此它更侧重于找到产生最大间隔的超平面。
第 5 段(可获 2 积分)

源代码

你可以在OpenCV的如下文件夹中找到源代码以及视频文件

samples/cpp/tutorial_code/gpu/non_linear_svms/non_linear_svms 或者 从这里下载.

#include <iostream>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/ml/ml.hpp>

#define NTRAINING_SAMPLES   100         // Number of training samples per class
#define FRAC_LINEAR_SEP     0.9f        // Fraction of samples which compose the linear separable part

using namespace cv;
using namespace std;

int main()
{
    // Data for visual representation
    const int WIDTH = 512, HEIGHT = 512;
    Mat I = Mat::zeros(HEIGHT, WIDTH, CV_8UC3);

    //--------------------- 1. Set up training data randomly ---------------------------------------
    Mat trainData(2*NTRAINING_SAMPLES, 2, CV_32FC1);
    Mat labels   (2*NTRAINING_SAMPLES, 1, CV_32FC1);

    RNG rng(100); // Random value generation class

    // Set up the linearly separable part of the training data
    int nLinearSamples = (int) (FRAC_LINEAR_SEP * NTRAINING_SAMPLES);

    // Generate random points for the class 1
    Mat trainClass = trainData.rowRange(0, nLinearSamples);
    // The x coordinate of the points is in [0, 0.4)
    Mat c = trainClass.colRange(0, 1);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(0.4 * WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));

    // Generate random points for the class 2
    trainClass = trainData.rowRange(2*NTRAINING_SAMPLES-nLinearSamples, 2*NTRAINING_SAMPLES);
    // The x coordinate of the points is in [0.6, 1]
    c = trainClass.colRange(0 , 1);
    rng.fill(c, RNG::UNIFORM, Scalar(0.6*WIDTH), Scalar(WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));

    //------------------ Set up the non-linearly separable part of the training data ---------------

    // Generate random points for the classes 1 and 2
    trainClass = trainData.rowRange(  nLinearSamples, 2*NTRAINING_SAMPLES-nLinearSamples);
    // The x coordinate of the points is in [0.4, 0.6)
    c = trainClass.colRange(0,1);
    rng.fill(c, RNG::UNIFORM, Scalar(0.4*WIDTH), Scalar(0.6*WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));

    //------------------------- Set up the labels for the classes ---------------------------------
    labels.rowRange(                0,   NTRAINING_SAMPLES).setTo(1);  // Class 1
    labels.rowRange(NTRAINING_SAMPLES, 2*NTRAINING_SAMPLES).setTo(2);  // Class 2

    //------------------------ 2. Set up the support vector machines parameters --------------------
    CvSVMParams params;
    params.svm_type    = SVM::C_SVC;
    params.C           = 0.1;
    params.kernel_type = SVM::LINEAR;
    params.term_crit   = TermCriteria(CV_TERMCRIT_ITER, (int)1e7, 1e-6);

    //------------------------ 3. Train the svm ----------------------------------------------------
    cout << "Starting training process" << endl;
    CvSVM svm;
    svm.train(trainData, labels, Mat(), Mat(), params);
    cout << "Finished training process" << endl;

    //------------------------ 4. Show the decision regions ----------------------------------------
    Vec3b green(0,100,0), blue (100,0,0);
    for (int i = 0; i < I.rows; ++i)
        for (int j = 0; j < I.cols; ++j)
        {
            Mat sampleMat = (Mat_<float>(1,2) << i, j);
            float response = svm.predict(sampleMat);

            if      (response == 1)    I.at<Vec3b>(j, i)  = green;
            else if (response == 2)    I.at<Vec3b>(j, i)  = blue;
        }

    //----------------------- 5. Show the training data --------------------------------------------
    int thick = -1;
    int lineType = 8;
    float px, py;
    // Class 1
    for (int i = 0; i < NTRAINING_SAMPLES; ++i)
    {
        px = trainData.at<float>(i,0);
        py = trainData.at<float>(i,1);
        circle(I, Point( (int) px,  (int) py ), 3, Scalar(0, 255, 0), thick, lineType);
    }
    // Class 2
    for (int i = NTRAINING_SAMPLES; i <2*NTRAINING_SAMPLES; ++i)
    {
        px = trainData.at<float>(i,0);
        py = trainData.at<float>(i,1);
        circle(I, Point( (int) px, (int) py ), 3, Scalar(255, 0, 0), thick, lineType);
    }

    //------------------------- 6. Show support vectors --------------------------------------------
    thick = 2;
    lineType  = 8;
    int x     = svm.get_support_vector_count();

    for (int i = 0; i < x; ++i)
    {
        const float* v = svm.get_support_vector(i);
        circle( I,  Point( (int) v[0], (int) v[1]), 6, Scalar(128, 128, 128), thick, lineType);
    }

    imwrite("result.png", I);                      // save the Image
    imshow("SVM for Non-Linear Training Data", I); // show it to the user
    waitKey(0);
}
第 6 段(可获 2 积分)

解释

  1. 设置训练数据

此练习的训练数据是由两组两类不同的二维点构成。为了使这个练习更具吸引力,训练数据由一个统一的概率密度函数(PDF)随机生成。我们把训练数据的生成分为两个主要部分。 在第一部分中,我们生成两类线性可分的数据。

// Generate random points for the class 1
Mat trainClass = trainData.rowRange(0, nLinearSamples);
// The x coordinate of the points is in [0, 0.4)
Mat c = trainClass.colRange(0, 1);
rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(0.4 * WIDTH));
// The y coordinate of the points is in [0, 1)
c = trainClass.colRange(1,2);
rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));
// Generate random points for the class 2
trainClass = trainData.rowRange(2*NTRAINING_SAMPLES-nLinearSamples, 2*NTRAINING_SAMPLES);
// The x coordinate of the points is in [0.6, 1]
c = trainClass.colRange(0 , 1);
rng.fill(c, RNG::UNIFORM, Scalar(0.6*WIDTH), Scalar(WIDTH));
// The y coordinate of the points is in [0, 1)
c = trainClass.colRange(1,2);
rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));
第 7 段(可获 2 积分)

在第二部分中,这两个类都生成是非线性可分离的,重叠的数据。

// Generate random points for the classes 1 and 2
trainClass = trainData.rowRange(  nLinearSamples, 2*NTRAINING_SAMPLES-nLinearSamples);
// The x coordinate of the points is in [0.4, 0.6)
c = trainClass.colRange(0,1);
rng.fill(c, RNG::UNIFORM, Scalar(0.4*WIDTH), Scalar(0.6*WIDTH));
// The y coordinate of the points is in [0, 1)
c = trainClass.colRange(1,2);
rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));
  1. 设置支持向量机的参数

另请参阅

前面的教程 Introduction to Support Vector Machines 这里对类 CvSVMParams 的属性作了解释,这些属性需要在训练 SVM 时配置的。

第 8 段(可获 2 积分)
CvSVMParams params;
params.svm_type    = SVM::C_SVC;
params.C              = 0.1;
params.kernel_type = SVM::LINEAR;
params.term_crit   = TermCriteria(CV_TERMCRIT_ITER, (int)1e7, 1e-6);

这里的配置与 前面教程介绍的配置只有两个地方不同。

  • CvSVM::C_SVC. 我们选择了一个较小的值,这是为了在优化中避免太多的错误分类。这样做的想法源于将获得接近一个直观预期的解决方案。但我们建议为了更好地分析问题就需要调整该参数.

    注:本例中在重叠区域中只有很少的点,对FRAC_LINEAR_SEP 设置较小的值可能会增加点的密度并且会影响参数CvSVM::C_SVC 

  • 算法的终止条件. 为了正确的解决问题与非线性可分离的训练数据量需要加大迭代次数。 特别是,我们已经对该值增加了五个数量级。

第 9 段(可获 2 积分)

3. 支持向量机训练

我们调用CvSVM::train方法创建支持向量机模型。注意这里的训练过程可能相当长,当你运行程序时要有耐心。

CvSVM svm;
svm.train(trainData, labels, Mat(), Mat(), params);

4. 决策区域展现

CvSVM::predict采用训练过的支持向量机来将输入样本分类。下面的案例中,我们基于支持向量机预测数据调用这个方法来空间着色。换句话说,一张图片上的像素点被遍历解释为笛卡尔平面上的点。每一点的着色取决于支持向量机的预测分类;分类标记为1的着深绿色,分类标记为2的着深蓝色。

第 10 段(可获 2 积分)
Vec3b green(0,100,0), blue (100,0,0);
for (int i = 0; i < I.rows; ++i)
     for (int j = 0; j < I.cols; ++j)
     {
          Mat sampleMat = (Mat_<float>(1,2) << i, j);
          float response = svm.predict(sampleMat);
          if      (response == 1)    I.at<Vec3b>(j, i)  = green;
          else if (response == 2)    I.at<Vec3b>(j, i)  = blue;
     }
  1. 显示训练数据

用画圆的方法显示组成训练数据的样本。 浅绿色标记 1 类的样本、淡蓝色标记 2 类的样本。

第 11 段(可获 2 积分)
int thick = -1;
int lineType = 8;
float px, py;
// Class 1
for (int i = 0; i < NTRAINING_SAMPLES; ++i)
{
     px = trainData.at<float>(i,0);
     py = trainData.at<float>(i,1);
     circle(I, Point( (int) px,  (int) py ), 3, Scalar(0, 255, 0), thick, lineType);
}
// Class 2
for (int i = NTRAINING_SAMPLES; i <2*NTRAINING_SAMPLES; ++i)
{
     px = trainData.at<float>(i,0);
     py = trainData.at<float>(i,1);
     circle(I, Point( (int) px, (int) py ), 3, Scalar(255, 0, 0), thick, lineType);
}

6. 支持向量

我们这里使用一些方法获取支持向量的信息.  CvSVM::get_support_vector_count 方法输出问题中使用的支持向量总数,CvSVM::get_support_vector 方法允许我们使用索引获取指定的支持向量。我们使用这个方法来找到支持向量的训练样例和并作出强调。

第 12 段(可获 2 积分)
thick = 2;
lineType  = 8;
int x     = svm.get_support_vector_count();
for (int i = 0; i < x; ++i)
{
     const float* v = svm.get_support_vector(i);
     circle(     I,  Point( (int) v[0], (int) v[1]), 6, Scalar(128, 128, 128), thick, lineType);
}

结果

  • 代码实现了:打开图像,并显示所有类的训练数据。一类数据使用亮绿色表示,另一种使用亮蓝色表示。
  • SVM已训练,并用于对图像中的像素进行分类。图像分割的结果是图像分为绿色和蓝色区域。所有区域的边界是超平面。由于训练数据是线性不可分的,能够看到一些数据是误分类的:一些绿色的点出现在蓝色区域,而一些蓝色点出现在绿色区域。
  • 最终支持向量由训练数据周围灰色的圆环表示。

Training data and decision regions given by the SVM

运行示例可以在YouTube 上观看。

第 13 段(可获 2 积分)

文章评论