サポートベクターマシン入門

目次

• 目標
• SVMとは何か?
• 最適な超平面はどのように計算されるか?
• ソースコード
• 解説
• 結果

次のチュートリアル: 線形分離不可能なデータに対するサポートベクターマシン

原著者	Fernando Iglesias García
互換性	OpenCV >= 3.0

目標

このチュートリアルでは、以下の方法を学ぶ:

• OpenCVの関数 cv::ml::SVM::train を用いてSVMに基づく分類器を構築し、cv::ml::SVM::predict を用いてその性能を検証する。

SVMとは何か?

サポートベクターマシン (SVM) は、分離超平面によって形式的に定義される識別的な分類器である。言い換えると、ラベル付き学習データ (教師あり学習) が与えられると、アルゴリズムは新しい事例を分類する最適な超平面を出力する。

得られる超平面はどのような意味で最適なのか? 次の単純な問題を考えてみよう。

2つのクラスのいずれかに属する線形分離可能な2次元点の集合に対して、それらを分離する直線を求める。

覚え書き

この例では、高次元空間における超平面やベクトルの代わりに、デカルト平面における直線と点を扱う。これは問題を単純化したものである。これは、想像しやすい例の方が直感を働かせやすいという理由だけで行っていることを理解しておくことが重要である。しかし、分類対象の事例が2より高い次元の空間に存在するタスクにも、同じ概念が適用される。

上の図を見ると、この問題の解となる直線が複数存在することがわかる。そのうちのどれかが他より優れているだろうか? 直線の良し悪しを見積もる基準を直感的に定義できる。 ある直線が点に近すぎる位置を通る場合、その直線はノイズに敏感で正しく汎化できないため、悪い直線である。 したがって、我々の目標は、すべての点からできるだけ遠くを通る直線を見つけることであるべきだ。

そこで、SVMアルゴリズムの動作は、学習事例までの最小距離が最大となる超平面を見つけることに基づいている。この距離の2倍は、SVMの理論においてマージンという重要な名前で呼ばれる。したがって、最適な分離超平面は学習データのマージンを最大化する。

最適な超平面はどのように計算されるか?

超平面を形式的に定義するために用いる記法を導入しよう。

\[f(x) = \beta_{0} + \beta^{T} x,\]

ここで \(\beta\) は重みベクトル、\(\beta_{0}\) はバイアスとして知られる。

覚え書き

これと超平面についてのより詳しい説明は、書籍 Elements of Statistical Learning(T. Hastie、R. Tibshirani、J. H. Friedman 著、[282]）の4.5節（Separating Hyperplanes）で見つけられる。

最適な超平面は、\(\beta\) と \(\beta_{0}\) のスケーリングによって無限に多くの異なる方法で表現できる。慣例として、超平面のあらゆる表現の中から選ばれるのは次のものである。

\[|\beta_{0} + \beta^{T} x| = 1\]

ここで \(x\) は超平面に最も近い学習事例を表す。一般に、超平面に最も近い学習事例はサポートベクターと呼ばれる。この表現は正準超平面として知られる。

ここで、点 \(x\) と超平面 \((\beta, \beta_{0})\) の間の距離を与える幾何学の結果を用いる。

\[\mathrm{distance} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||}.\]

特に、正準超平面の場合、分子は1に等しく、サポートベクターまでの距離は次のようになる。

\[\mathrm{distance}_{\text{ support vectors}} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||} = \frac{1}{||\beta||}.\]

前節で導入したマージンは、ここでは \(M\) と表記し、最も近い事例までの距離の2倍であることを思い出そう。

\[M = \frac{2}{||\beta||}\]

最後に、\(M\) を最大化する問題は、いくつかの制約条件のもとで関数 \(L(\beta)\) を最小化する問題と等価である。制約条件は、超平面がすべての学習事例 \(x_{i}\) を正しく分類するという要件をモデル化する。形式的には次のようになる。

\[\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,\]

ここで \(y_{i}\) は各学習事例のラベルを表す。

これはラグランジュ最適化の問題であり、ラグランジュ乗数を用いて解くことで、最適な超平面の重みベクトル \(\beta\) とバイアス \(\beta_{0}\) を得ることができる。

ソースコード

C++

• ダウンロード可能なコード: こちらをクリック
• コード全体:

  #include <opencv2/core.hpp>
  #include <opencv2/imgproc.hpp>
  #include <opencv2/imgcodecs.hpp>
  #include <opencv2/highgui.hpp>
  #include <opencv2/ml.hpp>
   
  using namespace cv;
  using namespace cv::ml;
   
  int main(int, char**)
  {
   // Set up training data
   int labels[4] = {1, -1, -1, -1};
   float trainingData[4][2] = { {501, 10}, {255, 10}, {501, 255}, {10, 501} };
   Mat trainingDataMat(4, 2, CV_32F, trainingData);
   Mat labelsMat(4, 1, CV_32SC1, labels);
   
   // Train the SVM
   Ptr<SVM> svm = SVM::create();
   svm->setType(SVM::C_SVC);
   svm->setKernel(SVM::LINEAR);
   svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, 100, 1e-6));
   svm->train(trainingDataMat, ROW_SAMPLE, labelsMat);
   
   // Data for visual representation
   int width = 512, height = 512;
   Mat image = Mat::zeros(height, width, CV_8UC3);
   
   // Show the decision regions given by the SVM
   Vec3b green(0,255,0), blue(255,0,0);
   for (int i = 0; i < image.rows; i++)
   {
   for (int j = 0; j < image.cols; j++)
   {
   Mat sampleMat = (Mat_<float>(1,2) << j,i);
   float response = svm->predict(sampleMat);
   
   if (response == 1)
   image.at<Vec3b>(i,j) = green;
   else if (response == -1)
   image.at<Vec3b>(i,j) = blue;
   }
   }
   
   // Show the training data
   int thickness = -1;
   circle( image, Point(501, 10), 5, Scalar( 0, 0, 0), thickness );
   circle( image, Point(255, 10), 5, Scalar(255, 255, 255), thickness );
   circle( image, Point(501, 255), 5, Scalar(255, 255, 255), thickness );
   circle( image, Point( 10, 501), 5, Scalar(255, 255, 255), thickness );
   
   // Show support vectors
   thickness = 2;
   Mat sv = svm->getUncompressedSupportVectors();
   
   for (int i = 0; i < sv.rows; i++)
   {
   const float* v = sv.ptr<float>(i);
   circle(image, Point( (int) v[0], (int) v[1]), 6, Scalar(128, 128, 128), thickness);
   }
   
   imwrite("result.png", image); // save the image
   
   imshow("SVM Simple Example", image); // show it to the user
   waitKey();
   return 0;
  }

Java

• ダウンロード可能なコード: こちらをクリック
• コード全体:

  import org.opencv.core.Core;
  import org.opencv.core.CvType;
  import org.opencv.core.Mat;
  import org.opencv.core.Point;
  import org.opencv.core.Scalar;
  import org.opencv.core.TermCriteria;
  import org.opencv.highgui.HighGui;
  import org.opencv.imgcodecs.Imgcodecs;
  import org.opencv.imgproc.Imgproc;
  import org.opencv.ml.Ml;
  import org.opencv.ml.SVM;
   
  public class IntroductionToSVMDemo {
   public static void main(String[] args) {
   // Load the native OpenCV library
   System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
   
   // Set up training data
   int[] labels = { 1, -1, -1, -1 };
   float[] trainingData = { 501, 10, 255, 10, 501, 255, 10, 501 };
   Mat trainingDataMat = new Mat(4, 2, CvType.CV_32FC1);
   trainingDataMat.put(0, 0, trainingData);
   Mat labelsMat = new Mat(4, 1, CvType.CV_32SC1);
   labelsMat.put(0, 0, labels);
   
   // Train the SVM
   SVM svm = SVM.create();
   svm.setType(SVM.C_SVC);
   svm.setKernel(SVM.LINEAR);
   svm.setTermCriteria(new TermCriteria(TermCriteria.MAX_ITER, 100, 1e-6));
   svm.train(trainingDataMat, Ml.ROW_SAMPLE, labelsMat);
   
   // Data for visual representation
   int width = 512, height = 512;
   Mat image = Mat.zeros(height, width, CvType.CV_8UC3);
   
   // Show the decision regions given by the SVM
   byte[] imageData = new byte[(int) (image.total() * image.channels())];
   Mat sampleMat = new Mat(1, 2, CvType.CV_32F);
   float[] sampleMatData = new float[(int) (sampleMat.total() * sampleMat.channels())];
   for (int i = 0; i < image.rows(); i++) {
   for (int j = 0; j < image.cols(); j++) {
   sampleMatData[0] = j;
   sampleMatData[1] = i;
   sampleMat.put(0, 0, sampleMatData);
   float response = svm.predict(sampleMat);
   
   if (response == 1) {
   imageData[(i * image.cols() + j) * image.channels()] = 0;
   imageData[(i * image.cols() + j) * image.channels() + 1] = (byte) 255;
   imageData[(i * image.cols() + j) * image.channels() + 2] = 0;
   } else if (response == -1) {
   imageData[(i * image.cols() + j) * image.channels()] = (byte) 255;
   imageData[(i * image.cols() + j) * image.channels() + 1] = 0;
   imageData[(i * image.cols() + j) * image.channels() + 2] = 0;
   }
   }
   }
   image.put(0, 0, imageData);
   
   // Show the training data
   int thickness = -1;
   int lineType = Imgproc.LINE_8;
   Imgproc.circle(image, new Point(501, 10), 5, new Scalar(0, 0, 0), thickness, lineType, 0);
   Imgproc.circle(image, new Point(255, 10), 5, new Scalar(255, 255, 255), thickness, lineType, 0);
   Imgproc.circle(image, new Point(501, 255), 5, new Scalar(255, 255, 255), thickness, lineType, 0);
   Imgproc.circle(image, new Point(10, 501), 5, new Scalar(255, 255, 255), thickness, lineType, 0);
   
   // Show support vectors
   thickness = 2;
   Mat sv = svm.getUncompressedSupportVectors();
   float[] svData = new float[(int) (sv.total() * sv.channels())];
   sv.get(0, 0, svData);
   for (int i = 0; i < sv.rows(); ++i) {
   Imgproc.circle(image, new Point(svData[i * sv.cols()], svData[i * sv.cols() + 1]), 6,
   new Scalar(128, 128, 128), thickness, lineType, 0);
   }
   
   Imgcodecs.imwrite("result.png", image); // save the image
   
   HighGui.imshow("SVM Simple Example", image); // show it to the user
   HighGui.waitKey();
   System.exit(0);
   }
  }

Python

• ダウンロード可能なコード: こちらをクリック
• コード一覧:

  import cv2 as cv
  import numpy as np
   
  # Set up training data
   
  labels = np.array([1, -1, -1, -1])
  trainingData = np.matrix([[501, 10], [255, 10], [501, 255], [10, 501]], dtype=np.float32)
   
   
  # Train the SVM
   
  svm = cv.ml.SVM_create()
  svm.setType(cv.ml.SVM_C_SVC)
  svm.setKernel(cv.ml.SVM_LINEAR)
  svm.setTermCriteria((cv.TERM_CRITERIA_MAX_ITER, 100, 1e-6))
   
  svm.train(trainingData, cv.ml.ROW_SAMPLE, labels)
   
   
  # Data for visual representation
  width = 512
  height = 512
  image = np.zeros((height, width, 3), dtype=np.uint8)
   
  # Show the decision regions given by the SVM
   
  green = (0,255,0)
  blue = (255,0,0)
  for i in range(image.shape[0]):
   for j in range(image.shape[1]):
   sampleMat = np.matrix([[j,i]], dtype=np.float32)
   response = svm.predict(sampleMat)[1]
   
   if response == 1:
   image[i,j] = green
   elif response == -1:
   image[i,j] = blue
   
   
  # Show the training data
   
  thickness = -1
  cv.circle(image, (501, 10), 5, ( 0, 0, 0), thickness)
  cv.circle(image, (255, 10), 5, (255, 255, 255), thickness)
  cv.circle(image, (501, 255), 5, (255, 255, 255), thickness)
  cv.circle(image, ( 10, 501), 5, (255, 255, 255), thickness)
   
   
  # Show support vectors
   
  thickness = 2
  sv = svm.getUncompressedSupportVectors()
   
  for i in range(sv.shape[0]):
   cv.circle(image, (int(sv[i,0]), int(sv[i,1])), 6, (128, 128, 128), thickness)
   
   
  cv.imwrite('result.png', image) # save the image
   
  cv.imshow('SVM Simple Example', image) # show it to the user
  cv.waitKey()

解説

• 訓練データを設定する

この演習の学習データは、2つの異なるクラスのいずれかに属する、ラベル付き2次元点の集合で構成されている。一方のクラスは1点から成り、もう一方は3点から成る。

C++

 int labels[4] = {1, -1, -1, -1};
 float trainingData[4][2] = { {501, 10}, {255, 10}, {501, 255}, {10, 501} };

Java

 int[] labels = { 1, -1, -1, -1 };
 float[] trainingData = { 501, 10, 255, 10, 501, 255, 10, 501 };

Python

labels = np.array([1, -1, -1, -1])
trainingData = np.matrix([[501, 10], [255, 10], [501, 255], [10, 501]], dtype=np.float32)

この後で用いる関数 cv::ml::SVM::train は、学習データが浮動小数点数の cv::Mat オブジェクトとして格納されていることを要求する。そこで、上で定義した配列からこれらのオブジェクトを作成する。

C++

 Mat trainingDataMat(4, 2, CV_32F, trainingData);
 Mat labelsMat(4, 1, CV_32SC1, labels);

Java

        Mat trainingDataMat = new Mat(4, 2, CvType.CV_32FC1);
        trainingDataMat.put(0, 0, trainingData);
        Mat labelsMat = new Mat(4, 1, CvType.CV_32SC1);
        labelsMat.put(0, 0, labels);

Python

labels = np.array([1, -1, -1, -1])
trainingData = np.matrix([[501, 10], [255, 10], [501, 255], [10, 501]], dtype=np.float32)

• SVMの引数を設定する

  このチュートリアルでは、学習事例が線形分離可能な2つのクラスに分かれているという最も単純なケースで、SVMの理論を紹介した。しかし、SVMはさまざまな問題に利用できる (例えば、線形分離不可能なデータの問題や、カーネル関数を用いて事例の次元を引き上げるSVMなど)。その結果、SVMを学習させる前にいくつかの引数を定義しなければならない。これらの引数は cv::ml::SVM クラスのオブジェクトに格納される。

C++

 Ptr<SVM> svm = SVM::create();
    svm->setType(SVM::C_SVC);
    svm->setKernel(SVM::LINEAR);
    svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, 100, 1e-6));

Java

        SVM svm = SVM.create();
        svm.setType(SVM.C_SVC);
        svm.setKernel(SVM.LINEAR);
        svm.setTermCriteria(new TermCriteria(TermCriteria.MAX_ITER, 100, 1e-6));

Python

svm = cv.ml.SVM_create()
svm.setType(cv.ml.SVM_C_SVC)
svm.setKernel(cv.ml.SVM_LINEAR)
svm.setTermCriteria((cv.TERM_CRITERIA_MAX_ITER, 100, 1e-6))

各引数の説明:

• SVMの種類。ここでは、n クラス分類 (n \(\geq\) 2) に使用できる C_SVC 型を選択する。この型の重要な特徴は、クラスの不完全な分離 (すなわち学習データが線形分離不可能な場合) を扱える点である。ここではデータが線形分離可能であるためこの特徴は重要ではなく、最も一般的に使われているという理由だけでこのSVMの種類を選んだ。
• SVMカーネルの種類。ここで扱う学習データにとってカーネル関数は重要でないため、これまで触れてこなかった。とはいえ、ここでカーネル関数の背後にある主な考え方を簡単に説明しておこう。これは、データを線形分離可能なデータ集合により近づけるために学習データに対して行う写像である。この写像はデータの次元を高めるもので、カーネル関数を用いて効率的に行われる。ここでは、写像を行わないことを意味する LINEAR 型を選択する。この引数は cv::ml::SVM::setKernel を用いて定義する。
• アルゴリズムの終了条件。SVMの学習手続きは、制約付き二次最適化問題を反復的に解くことで実装されている。ここでは最大反復回数と許容誤差を指定し、最適な超平面がまだ計算されていなくても、より少ないステップ数でアルゴリズムを終了できるようにする。この引数は構造体 cv::TermCriteria で定義する。
• SVMの学習 SVMモデルを構築するために、メソッド cv::ml::SVM::train を呼び出す。

C++

    svm->train(trainingDataMat, ROW_SAMPLE, labelsMat);

Java

        svm.train(trainingDataMat, Ml.ROW_SAMPLE, labelsMat);

Python

svm.train(trainingData, cv.ml.ROW_SAMPLE, labels)

• SVMによって分類された領域

  メソッド cv::ml::SVM::predict は、学習済みSVMを用いて入力サンプルを分類するために使用する。この例では、SVMが行った予測に応じて空間を色分けするためにこのメソッドを使った。言い換えると、画像を走査し、そのピクセルをデカルト平面上の点として解釈する。各点は、SVMが予測したクラスに応じて色付けされる。ラベル1のクラスなら緑、ラベル-1のクラスなら青である。

C++

 Vec3b green(0,255,0), blue(255,0,0);
 for (int i = 0; i < image.rows; i++)
    {
 for (int j = 0; j < image.cols; j++)
        {
 Mat sampleMat = (Mat_<float>(1,2) << j,i);
 float response = svm->predict(sampleMat);
 
 if (response == 1)
                image.at<Vec3b>(i,j)  = green;
 else if (response == -1)
                image.at<Vec3b>(i,j)  = blue;
        }
    }

Java

 byte[] imageData = new byte[(int) (image.total() * image.channels())];
        Mat sampleMat = new Mat(1, 2, CvType.CV_32F);
 float[] sampleMatData = new float[(int) (sampleMat.total() * sampleMat.channels())];
 for (int i = 0; i < image.rows(); i++) {
 for (int j = 0; j < image.cols(); j++) {
                sampleMatData[0] = j;
                sampleMatData[1] = i;
                sampleMat.put(0, 0, sampleMatData);
 float response = svm.predict(sampleMat);
 
 if (response == 1) {
                    imageData[(i * image.cols() + j) * image.channels()] = 0;
                    imageData[(i * image.cols() + j) * image.channels() + 1] = (byte) 255;
                    imageData[(i * image.cols() + j) * image.channels() + 2] = 0;
                } else if (response == -1) {
                    imageData[(i * image.cols() + j) * image.channels()] = (byte) 255;
                    imageData[(i * image.cols() + j) * image.channels() + 1] = 0;
                    imageData[(i * image.cols() + j) * image.channels() + 2] = 0;
                }
            }
        }
        image.put(0, 0, imageData);

Python

green = (0,255,0)
blue = (255,0,0)
for i in range(image.shape[0]):
 for j in range(image.shape[1]):
        sampleMat = np.matrix([[j,i]], dtype=np.float32)
        response = svm.predict(sampleMat)[1]
 
 if response == 1:
            image[i,j] = green
 elif response == -1:
            image[i,j] = blue

• サポートベクトル

  ここでは、サポートベクターに関する情報を得るためにいくつかのメソッドを使用する。メソッド cv::ml::SVM::getSupportVectors はすべてのサポートベクターを取得する。ここではこのメソッドを使って、サポートベクターとなっている学習事例を見つけ、それらを強調表示している。

C++

    thickness = 2;
 Mat sv = svm->getUncompressedSupportVectors();
 
 for (int i = 0; i < sv.rows; i++)
    {
 const float* v = sv.ptr<float>(i);
 circle(image,  Point( (int) v[0], (int) v[1]), 6, Scalar(128, 128, 128), thickness);
    }

Java

        thickness = 2;
        Mat sv = svm.getUncompressedSupportVectors();
 float[] svData = new float[(int) (sv.total() * sv.channels())];
        sv.get(0, 0, svData);
 for (int i = 0; i < sv.rows(); ++i) {
            Imgproc.circle(image, new Point(svData[i * sv.cols()], svData[i * sv.cols() + 1]), 6,
 new Scalar(128, 128, 128), thickness, lineType, 0);
        }

Python

thickness = 2
sv = svm.getUncompressedSupportVectors()
 
for i in range(sv.shape[0]):
 cv.circle(image, (int(sv[i,0]), int(sv[i,1])), 6, (128, 128, 128), thickness)

結果

• このコードは画像を開き、両クラスの学習事例を表示する。一方のクラスの点は白い円で表され、もう一方のクラスには黒い円が使われる。
• SVMが学習され、画像のすべてのピクセルの分類に使われる。その結果、画像は青い領域と緑の領域に分割される。両領域の境界が最適な分離超平面である。
• 最後に、サポートベクトルが訓練サンプルの周囲のグレーのリングを用いて表示される。