• [アーティクル]

2019 年 3 月

Volume 34 Number 3

[C#]

C# を使用したサポート ベクター マシン

James McCaffrey

サポート ベクター マシン (SVM) とは、データを使用して予測を行うことができるソフトウェア システムのことです。初期タイプの SVM は、二項分類を実行するために設計されました。たとえば、個人の身長、体重、年収に基づいて、その個人が男性か女性かを予測するなどといった用途です。また、マルチクラス分類 (3 つ以上のクラスから 1 つを予測する) や回帰 (数値を予測する) を実行できるタイプの SVM もあります。

この記事では、外部ライブラリを一切使用せず、未加工の C# のみを使用して実装される SVM の実例を詳しく紹介します。今回の主旨を理解するには、図 1 のデモ プログラムを調べるのが一番です。

SVM デモ プログラムの動作
図 1 SVM デモ プログラムの動作

このデモでは、最初に 8 つのダミー トレーニング データ項目を設定しています。各項目には 3 つの予測因子値があり、その後に、予測するクラスが -1 または +1 としてエンコードされています。ダミー データは実際の問題を表すものではないので、予測因子値に特定の意味はありません。実際の SVM 問題では、予測因子値を正規化することが重要です。これは通常、最小/最大正規化を適用することで実行されます。これにより、すべての値が 0.0 ～ 1.0 の間でスケーリングされます。

このデモでは、多項式カーネル関数を使用した SVM 分類器を作成します。(カーネル関数については後ほど説明します)。 この SVM モデルをトレーニングすると、次の 3 つのサポート ベクターが生成されました:(4, 5, 7)、(7, 4, 2)、(9, 7, 5)。これらは、トレーニング データ項目 [0]、[1]、[4] です。各サポート ベクターには、次の加重値が関連付けられています: (-0.000098、-0.000162、0.000260)。また、SVM モデルには、バイアスと呼ばれる単一の値があります。このデモ データの場合は -2.505727 です。

トレーニング済みの SVM モデルは、サポート ベクター、加重、およびバイアスによって定義されます。このデモ プログラムでは、このモデルを使用して、8 個の各トレーニング項目に対し、予測クラス値を生成します。負の決定値は予測クラス ラベル -1 に対応し、正の決定値は予測クラス +1 に対応します。したがって、このトレーニング済みモデルでは、8 個のトレーニング項目すべてが正しく予測されていることになります。問題が単純なので、これは特に驚くべきことはありません。

このデモでは最後に、前例のない新しい項目に対し、予測値 (3, 5, 7) を使用してクラスが予測されています。算出された決定値は -1.274 なので、予測クラス ラベルは -1 です。決定値の計算については、この記事の後半で説明します。

今回は、少なくとも中級レベルの C# プログラミング スキルがあることを前提としますが、SVM の知識は問いません。このデモ プログラムは C# を使用して記述されており、その内容は複雑ですが、必要であれば、コードを別の言語 (Java や Python など) にリファクタリングすることもできます。

デモ プログラムのコードは長すぎてここにすべて掲載することはできませんが、完全なソース コードはこの記事付属のファイル ダウンロードから入手できます。中心となる考え方を可能な限り明瞭にするために、通常のエラー チェックはすべて削除しています。

プログラムの全体構造

デモ プログラムの構造は、図 2 のようになります。制御ロジックはすべて単一の Main メソッドに含めています。プログラムで定義された SupportVectorMachine クラスでは、すべてのメンバー フィールドがパブリックとして宣言されているので、プログラムによる検査が行いやすくなっています。

このデモ プログラムは Visual Studio 2017 を使用して作成しましたが、.NET Framework との大きな依存関係はないので、どのバージョンの Visual Studio でも問題なく機能します。私は新しい C# コンソール アプリケーションを作成し、「SVM_CSharp」という名前を付けました。また、テンプレート コードがエディター ウィンドウに読み込まれた後、不要な using ステートメントをすべて削除し、その後、Collections.Generic アセンブリへの参照を追加しました。さらに、ソリューション エクスプローラー ウィンドウで Program.cs ファイルを右クリックし、名前を「SVM_Program.cs」に変更して、Program クラスの名前が Visual Studio によって自動的に変更されるようにしました。

図 2 デモ プログラムの構造

using System;
using System.Collections.Generic;
namespace SVM_CSharp
{
  class SVM_Program
  {
    static void Main(string[] args)
    {
      // Set up training data
      // Create SVM object, set parameters
      // Train the SVM
      // Display SVM properties
      // Use trained SVM to make a prediction
    }
  }
  public class SupportVectorMachine
  {
    // All member fields are declared public
    public SupportVectorMachine(string kernelType,
      int seed) . .
    public double PolyKernel(double[] v1, double[] v2) . .
    public double ComputeDecision(double[] input) . .
    public int Train(double[][] X_matrix,
      int[] y_vector, int maxIter) . .
    public double Accuracy(double[][] X_matrix,
      int[] y_vector) . .
    private bool TakeStep(int i1, int i2,
      double[][] X_matrix, int[] y_vector) . .
    private int ExamineExample(int i2, double[][] X_matrix,
      int[] y_vector) . .
    private double ComputeAll(double[] vector,
      double[][] X_matrix, int[] y_vector) . .
  }
}

SVM の使用

このデモ プログラムでは、ハードコードされた 8 つのトレーニング項目が設定されています。

double[][] train_X = new double[8][] {
  new double[] { 4,5,7 },
  ...
  new double[] { 8,9,10 }  };
int[] train_y = new int[8]{ -1, -1, -1, -1, 1, 1, 1, 1 };

実際のシナリオでは、予測値を正規化する必要があります。また通常は、データをテキスト ファイルに格納します。SVM 分類器は次のように作成されます。

var svm = new SupportVectorMachine("poly", 0);
svm.gamma = 1.0;
svm.coef = 0.0;
svm.degree = 2;

SVM は多項式カーネル関数を使用するようにハードコードされているので、poly 引数は実際にはダミー値です。0 引数は、トレーニング アルゴリズムのランダム コンポーネントのシード値です。gamma、coef (constant とも呼ばれます)、および degree 引数は、多項式カーネル関数のパラメーターです。次に、トレーニング アルゴリズムのパラメーターが次のように指定されています。

svm.complexity = 1.0;
svm.epsilon = 0.001;
svm.tolerance = 0.001;
int maxIter = 1000;

これらの値はすべて、試行錯誤を通じて決定する必要があるハイパーパラメーターです。SVM の実装を使用する際の主な課題は、使用するカーネルと、カーネル パラメーター、およびトレーニング パラメーターについて理解することです。トレーニングは単一のステートメント (下記) によって実行されます。

int iter = svm.Train(train_X, train_y, maxIter);

SVM 分類器のトレーニングは反復処理です。Train メソッドは、実行された実際のイテレーション数を返します。これは、問題が生じた際のデバッグに役立ちます。トレーニングの後、SVM オブジェクトにはサポート ベクターの List<double[]> コレクションが保持されます。これは、モデルの加重 (サポート ベクターごとに 1 つ) と、1 つのバイアス値を保持した配列です。これらは次のように表示されます。

foreach (double[] vec in svm.supportVectors) {
  for (int i = 0; i < vec.Length; ++i)
    Console.Write(vec[i].ToString("F1") + "  ");
  Console.WriteLine("");
}
for (int i = 0; i < svm.weights.Length; ++i)
  Console.Write(svm.weights[i].ToString("F6") + " ");
Console.WriteLine("");
Console.WriteLine("Bias = " + svm.bias.ToString("F6") + "\n");

デモの最後には、予測が実行されます。

double[] unknown = new double[] { 3, 5, 7 };
double predDecVal = svm.ComputeDecision(unknown);
Console.WriteLine("Predicted value for (3.0 5.0 7.0) = " +
  predDecVal.ToString("F3"));
int predLabel = Math.Sign(predDecVal);
Console.WriteLine("Predicted label for (3.0 5.0 7.0) = " +
  predLabel);

決定値は double 型です。決定値が負の場合、予測クラスは -1 となり、決定値が正の場合、予測クラスは +1 となります。

SVM について理解する

SVM について理解するのは非常に難しく、それらを実装することも非常に困難です。図 3 のグラフをご覧ください。この例の目標は、赤と青のデータを区別するルールを作成することです。このグラフでは、問題を視覚化するためにデータのディメンション (予測因子変数の数) を 2 つだけにしていますが、SVM では 3 つ以上のディメンションがあるデータを処理することもできます。

SVM の基本概念
図 3 SVM の基本概念

SVM は、2 つのクラスを分離する最も幅の広いレーンを特定し、各クラスから、分離レーンの端に最も近いポイントを 1 つ以上特定することによって機能します。

前例のない新しいデータ ポイントを分類するには、新しいポイントがレーンの中央から見てどちら側に位置しているかを見ればよいことになります。図 3 では、 (0.3, 0.65) にある丸付きの赤い点と、(0.5, 0.75) および (0.65, 0.6) にある青い点がサポート ベクターと呼ばれます。ただし、私はこれらを "サポート ポイント" と考えることにしています。なぜなら、私は通常、線をベクターとして考えるからです。

使用可能な SVM を実装するには、解決するべき主な課題が 3 つあります。1 つは、データを図 3 のように線形に分離できない場合にどうするかという課題です。2 つ目は、サポート ベクター、加重、およびバイアスの値をどのように特定するかということです。そして 3 つ目は、境界レーンの反対側にある異常なトレーニング データ ポイントをどのように処理するかという課題です。

この記事で説明しているように、線形分離できないデータは、カーネル関数というものを使用して処理できます。サポート ベクター、加重、およびバイアスは、逐次最小問題最適化法 (SMO) と呼ばれるアルゴリズムを使用して決定できます。一貫性のないトレーニング データは、複雑度と呼ばれる考え方を使用して処理することができます。これは、異常なデータにペナルティを課す手法です。

カーネル関数

カーネル関数にはさまざまな種類があります。簡単に言うと、カーネル関数は 2 つのベクターを受け取り、それらを何らかの方法で結合して、単一のスカラー値を生成します。わかりにくいかもしれませんが、カーネル関数を使用すれば、線形分離できないデータを SVM で処理することができます。これは "カーネル トリック" と呼ばれます。

たとえば、1 つ目のベクターが v1 = (3, 5, 2) で、2 つ目のベクターが v2 = (4, 1, 0) だとします。線形カーネルと呼ばれる非常にシンプルなカーネルでは、ベクター要素の積の合計が返されます。

K(v1, v2) = (3 * 4) + (5 * 1) + (2 * 0) = 17.0

多くのカーネル関数には、省略可能なスケール ファクターがあります。これは gamma とも呼ばれます。上記の例では、gamma を 0.5 に設定すると、次のように処理されます。

K(v1, v2) = 0.5 * [(3 * 4) + (5 * 1) + (2 * 0)] = 8.5

このデモ プログラムでは、多項式カーネルで degree = 2、gamma = 1.0、constant = 0 を使用しています。つまり、積の合計を計算し、gamma で乗算し、constant を追加した後、degree 乗を計算するということです。以下に例を示します。

K(v1, v2) = [1.0 * ((3*4) + (5*1) + (2*0)) + 0]^2 = (1 * 17 + 0)^2 = 289.0

このデモ プログラムでは、多項式カーネルが次のように実装されています。

public double PolyKernel(double[] v1, double[] v2)
{
  double sum = 0.0;
  for (int i = 0; i < v1.Length; ++i)
    sum += v1[i] * v2[i];
  double z = this.gamma * sum + this.coef;
  return Math.Pow(z, this.degree);
}

gamma、degree、constant (言語キーワードとの名前の競合を避けるために coef と命名されています) の値はクラス メンバーです。これらの値は別の場所で指定されます。このデモ プログラムでは、カーネル関数がハード コードされるため、別の関数で実験を行う場合には、その関数を自分で実装する必要があります。

多項式カーネルの一般的な代替手段としては、放射基底関数 (RBF) カーネルがあります。これは、要素間の差を 2 乗して合計し、負の gamma で乗算した後、e 乗を計算するものです (e はオイラー数 (約 2.718))。コード内では、RBF カーネルは次のようになります。

public double RbfKernel(double[] v1, double[] v2)
{
  double sum = 0.0;
  for (int i = 0; i < v1.Length; ++i)
    sum += (v1[i] - v2[i]) * (v1[i] - v2[i]);
    return Math.Exp(-this.gamma * sum);
}

カーネル関数が異なればパラメーターも異なるということに注意してください。線形カーネルと RBF カーネルでは gamma のみが必要ですが、多項式カーネルでは、gamma、degree、および constant が必要となります。使用するカーネル関数の選択 (および使用されるカーネル関数に適用されるパラメーターの値) はフリー パラメーターであり、試行錯誤を通じて決定する必要があります。機械学習では、すべての分類手法にハイパーパラメーターがありますが、SVM はハイパーパラメーターの値に特に影響を受けやすい傾向があります。

逐次最小問題最適化法アルゴリズム

SVM 問題のサポート ベクターを決定するために使用できるアルゴリズムは多数あります。その中で最も一般的なのが SMO アルゴリズムです。このデモ プログラムは、1998 年の研究論文「Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines」(逐次最小問題最適化法: サポート ベクター マシンのトレーニング用の高速アルゴリズム) に記述されている SMO の説明に基づいて作成されています (この論文はインターネット上のさまざまな場所で公開されています)。

SMO アルゴリズムは非常に複雑で、詳しく説明しようとすると 200 ページほど必要になります (SMO だけをテーマにした本を読んだ経験上、これは確かです)。SMO には 3 つの主要関数があります。最上位は Train 関数で、これによりヘルパー関数の ExamineExample が呼び出されます。さらに、その関数によってヘルパー関数 TakeStep が呼び出されます。

TakeStep のシグネチャは次のとおりです: private bool TakeStep(int i1, int i2, double[][] X_matrix, int[] y_vector)。X_matrix パラメーターは、トレーニング データの予測値を保持します。y_vector パラメーターは、トレーニング データのターゲット値 (-1 または +1 ) を保持します。i1 パラメーターと i2 パラメーターは、それぞれトレーニング データを指す 1 つ目と 2 つ目のインデックスです。このアルゴリズムでは、TakeStep が呼び出されるたびに、より合理的なソリューションの特定が試行されます。2 つのトレーニング データ項目を使用して改善案が見つかった場合には true が返されます。見つからなかった場合は、false が返されます。

ExamineExample のシグネチャは次のとおりです: private int Examine­Example(nt i2, double[][] X_matrix, int[] y_vector)。この関数は、加えられた変更の数を返します。この値は、改善が進められているかどうかを確認するために TakeStep で使用できます。

TakeStep と ExamineExample では、complexity というクラススコープ変数が使用されます。complexity の値が大きいほど、トレーニング データの外れ値に対するペナルティも大きくなります。その場合 SMO アルゴリズムは、モデルのオーバーフィットという犠牲を払って解決策を見つけようとします。complexity は SMO によって使用されるパラメーターなので、常に存在します。一方、使用されるカーネル関数に関連付けられるパラメーターは、存在する場合もあれば、存在しない場合もあります。

TakeStep 関数では epsilon というクラススコープ変数が使用され、ExamineExample 関数では tolerance というクラススコープ変数が使用されます。どちらも値は小さく設定されます。このデモでは、既定で 0.001 に設定されています。epsilon は、反復処理を停止するタイミングを決定するために内部で使用されます。これは、特定されるサポート ベクターの数に影響します。tolerance はエラーを計算するときに使用されます。epsilon と tolerance の値はフリー パラメーターです。これらを変更した場合の影響の度合いは、対象となる問題の内容によってかなり違ってきます (影響が非常に小さい場合もあれば、非常に大きい場合もあります)。

Train メソッドのコードを図 4 に示します。このメソッドは反復プロセスであり、実行されたイテレーションの数を返します。このメソッドは maxIter パラメーターを受け取り、実行されたイテレーションの数に対してハード リミットを設定します。理論上、SMO アルゴリズムは必ず値を収束して反復処理を停止しますが、SMO のように複雑なアルゴリズムの場合、理論が必ずしも実際の結果と一致するとは限りません。

図 4 トレーニング メソッド

public int Train(double[][] X_matrix, int[] y_vector, int maxIter)
{
  int N = X_matrix.Length;
  this.alpha = new double[N];
  this.errors = new double[N];
  int numChanged = 0;
  bool examineAll = true;
  int iter = 0;
  while (iter < maxIter && numChanged > 0 || examineAll == true) {
    ++iter;
    numChanged = 0;
    if (examineAll == true) {
      for (int i = 0; i < N; ++i)
        numChanged += ExamineExample(i, X_matrix, y_vector);
    }
    else {
      for (int i = 0; i < N; ++i)
        if (this.alpha[i] != 0 && this.alpha[i] !=
          this.complexity)
          numChanged += ExamineExample(i, X_matrix, y_vector);
    }
    if (examineAll == true)
      examineAll = false;
    else if (numChanged == 0)
      examineAll = true;
  } // While
  List<int> indices = new List<int>();  // support vectors
  for (int i = 0; i < N; ++i) {
    // Only store vectors with Lagrange multipliers > 0
    if (this.alpha[i] > 0) indices.Add(i);
  }
  int num_supp_vectors = indices.Count;
  this.weights = new double[num_supp_vectors];
  for (int i = 0; i < num_supp_vectors; ++i) {
    int j = indices[i];
    this.supportVectors.Add(X_matrix[j]);
    this.weights[i] = this.alpha[j] * y_vector[j];
  }
  this.bias = -1 * this.bias;
  return iter;
}

Train は、実行されたイテレーションの数を明示的に返すだけでなく、サポート ベクターであるトレーニング データ項目のインデックスを検索し、格納します。サポート ベクターの数がわかったら、加重の値を保持した配列を割り当てることができます。加重値は 0 以外のアルファ値です。

Train メソッドには、カスタマイズ可能なポイントが多く存在します。たとえば、このデモ コードでは、サポート ベクターが List<double[]> コレクションとして格納されていますが、別の方法として、サポート ベクターのインデックスだけを、List<int> コレクションまたは int[] 配列オブジェクトに格納することもできます。SVM と SMO アルゴリズムについて理解するには、Train メソッドの内容を注意深く調べるのが最善の方法です。

SVM のメカニズムを理解する

図 1 を見ると、トレーニング済みの SVM に 3 つのサポート ベクターがあるのがわかります。(4, 5, 7)、(7, 4, 2)、および (9, 7, 5) です。また、モデルには 3 つの加重値 (-0.000098、-0.000162、0.000260) とバイアス (-2.506) があります。入力 (3, 5, 7) の決定値は、3 つの各サポート ベクターでカーネル関数の値を計算し、各カーネル値を対応する加重で乗算して、値を合計した後、バイアスを追加することで算出されます。

x = (3, 5, 7)
sv1 = (4, 5, 7)
sv2 = (7, 4, 2)
sv3 = (9, 7, 5)
K(x, sv1) * wt1 = 7396.0 * -0.000098 = -0.725
K(x, sv2) * wt2 = 3025.0 * -0.000162 = -0.490
K(x, sv3) * wt3 = 9409.0 * 0.000260 = 2.446
decision = -0.725 + -0.490 + 2.446 + -2.506 = -1.274
prediction = Sign(decision) = -1

このデモのように、予測値が正規化されていない場合は、カーネルの値が非常に大きくなり、その結果、加重の値が非常に小さくなって、算術エラーにつながる可能性があるので注意してください。

SVM のメカニズムを見ていくと、この手法の長所と短所が見えてきます。SVM では、主要なサポート ベクターのみに主眼が置かれるため、異常なトレーニング データへの対処がしやすいという傾向があります。サポート ベクターの数が少ない場合でも、SVM は比較的優れた精度でデータを解釈できます。これは、他の多くの手法と比べて優れている点です。他の多くの分類手法 (特にニューラル ネットワーク) と比べて、SVM は限られたトレーニング データでも通常効果的に機能しますが、非常に大きなトレーニング データセットを処理する場合には、問題が生じることもあります。SVM の主な欠点は、処理が非常に複雑であるため、多数のハイパーパラメーターに値を指定する必要があるという点です。

まとめ

この記事で示したように、サポート ベクター マシンの実装は非常に複雑で困難です。そのため、入手できる SVM ライブラリ実装の数は非常に少ないのが現状です。SVM ライブラリの多くは、LibSVM と呼ばれる C++ 実装に基づいて作成されています。これは、ある研究者グループによって作成されたものです。C++ の呼び出しは難しいことが多いので、LibSVM のラッパーを提供するライブラリも複数提供されています。これらは、Python、Java、C# などの言語で記述されています。

この記事で紹介したコードを使って色々な機能を試していくと、SVM の細かいしくみや、ライブラリ実装の使い方について、より効果的に理解することができるでしょう。この記事のコードは自己完結型のシンプルな内容なので、別のカーネル関数とそれらのパラメーターについて調べたり、SMO のトレーニング アルゴリズム パラメーター (epsilon、tolerance、complexity) について調べることができます。

Dr.James McCaffreyは、ワシントン州レドモンドの Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing など、いくつかの主要なマイクロソフト製品にも携わってきました。Dr.McCaffrey の連絡先は jammc@microsoft.com (英語のみ) です。

この記事のレビューに協力してくれたマイクロソフト技術スタッフのYihe Dong、Chris Lee に心より感謝いたします。