メインコンテンツへスキップ
見出し画像

scikit-learn機械学習㉕SVM理論4:多クラス分類

    前回は、カーネルを使ってハイパープレーンを決定する仕組みであるカーネル・トリックを紹介しました。

    カーネル・トリックでは、入力データを高次元の特徴量へ明示的に変換することなく、非線形データの分類を効率良く行うことが可能です。

    今回は、カーネル・トリックの数学的な側面について、もう少し深掘りします。

    また、これまでクラスを2つに分類すること(二項分類)を想定して解説してきましたが、SVMはもちろんもっと多数のクラスを扱うことができます。

    よって、SVMによる3つ以上のクラスのサポートについても解説します。

    線形のサポート・ベクトル分離器

    前回、距離や内積を使うことでさまざまなカーネルを表現できることを紹介しました。今回はこれを数式として表現しなおします。

    まずは、線形のサポート・ベクトル分類器を内積で表現します。

    訓練データポイント間の内積の計算

    まず、線形分離によるサポート・ベクトル分類器がデータポイント間の内積を使って表現できることを示します。その後に、非線形分離の場合には、内積を利用したカーネルを使うことで対応できることを解説します。

    訓練データセットXXには、nn個のデータポイントがあるとします。

    X=x1,x2,…,xnX = {x_1, x_2, \ldots, x_n}

    各データポイントxix_iは、ベクトルでありpp個の特徴量を含んでいます。

    xi=(xi1,xi2,…,xip)x_i = (x_{i1}, x_{i2}, \ldots, x_{ip})

    例として、2つのデータポイントx1x_1とx2x_2の内積は次のようになります。

    x1⋅x2=x11x21+x12x22+…+x1px2p=∑j=1px1jx2jx_1 \cdot x_2 = x_{11}x_{21} + x_{12}x_{22} + \ldots + x_{1p}x_{2p} = \sum\limits_{j=1}^p x_{1j}x_{2j}

    同じことを内積をより明確に表示するために次のようにも書けます。

    ⟨x1, x2⟩=x11x21+x12x22+…+x1px2p=∑j=1px1jx2j\braket{x_1, x_2} = x_{11}x_{21} + x_{12}x_{22} + \ldots + x_{1p}x_{2p} = \sum\limits_{j=1}^p x_{1j}x_{2j}

    この内積の書き方⟨x1, x2⟩\braket{x_1, x_2}は、x1⋅x2x_1 \cdot x_2よりも内積であることが明白であり、またx1x_1とx2x_2がベクトルであることがハッキリします。

    なお、一般に二つのデータxix_iとxi′x_{i'}の内積は以下になります。

    ⟨xi,xi′⟩=∑j=1pxijxi′j\braket{x_i, x_{i'}} = \sum\limits_{j=1}^p x_{ij} x_{i'j}

    内積による線形分離の式

    内積を使うと線形のサポート・ベクトル分類器は次のように表現されます。

    f(x)=β0+∑i=1nαi⟨x,xi⟩f(x) = \beta_0 + \sum\limits_{i=1}^n \alpha_i \braket{x, x_i}

    このf(x)f(x) は、入力データxxの分類結果を表す関数です。つまり、入力データxxがどちらのクラスに属するかを決定するための判定式です。

    • f(x)>0f(x) > 0の場合、データxxは正のクラスに分類されます。

    • f(x)<0f(x) < 0の場合、データxxは負のクラスに分類されます。

    正負がどのクラスになるのかは、入力データxxがどのクラスの訓練データにより類似するかによって決まります。

    各訓練データポイントに対する係数αi\alpha_iは、そのデータポイントに類似したデータがどのクラスに属するかに寄与します。

    バイアスβ0\beta_0を無視して単純に考えると、正のクラスに対して係数αi\alpha_iは正の値となり、負のクラスに対して係数αi\alpha_iは負の値となります。

    よって、入力データxxがどのクラスの訓練データに類似するのかが総合的に判断されることになります。

    f(x)f(x)の式の中身から分かるように、nn個の訓練データポイントxix_iと入力データxxの内積を利用して、データがどちらのクラスに属するかを判断しています。

    また、nn個の訓練データに対して、nn個のパラメータα1,…,αn\alpha_1, \ldots, \alpha_nがあり、1個のバイアス値β0\beta_0があります。

    訓練と推論の違い

    これらのパラメータの値の計算には、全ての訓練データポイント間の組み合わせに対して内積を計算する必要があります。

    参考までに、この組み合わせの数を数式で表すと以下になります。

    nC2=(n2)=n!(n−2)!2!_nC_2 = \begin{pmatrix} n \\ 2 \end{pmatrix} = \dfrac{n!}{(n-2)!2!}

    こうして見ると、訓練データセットの大きさによっては、膨大な数の組み合わせに対して内積の計算が必要です。

    また、新しいデータポイントxxを分類する際にも、数式上はnn個の内積を計算する必要があります。

    しかし、実際には、サポート・ベクトル(境界上のデータポイント)以外では、αi=0\alpha_i = 0となるために、実質の計算量はずっと低くなります。

    SVMの訓練中にサポートベクトルが決まり、その過程でサポートベクトル以外のデータポイントはαi=0\alpha_i = 0 となり、分類に寄与しなくなります。したがって、訓練後はサポートベクトルだけが分類に関与します。

    サポート・ベクトルの集合をS\mathcal{S}とすると、線形のサポート・ベクトル分類器を次のように表現できます。

    f(x)=β0+∑i∈Snαi⟨x,xi⟩f(x) = \beta_0 + \sum\limits_{i \in \mathcal{S}}^n \alpha_i \braket{x, x_i}

    カーネルとサポート・ベクトル・マシン

    線形カーネル

    内積によって線形分離をするという手法をより一般化して、カーネルを使って線形分離するという手法として捉え直します。

    ここでカーネルとは2つのデータポイントからのベクトル値を使ってなんらかの値を返すものです。

    K(xi,xi′)K(x_i, x_{i'})

    このカーネルKKが内積であれば次のようになります。

    K(xi,xi′)=⟨xi,xi′⟩=∑j=1pxijxi′jK(x_i, x_{i'}) = \braket{x_i, x_{i'}} = \sum\limits_{j=1}^p x_{ij} x_{i'j}

    これが線形カーネルとなります。このカーネルを使うと線形のサポート・ベクトル分類器は次のように表現されます。

    f(x)=β0+∑i=1nαiK(x,xi)f(x) = \beta_0 + \sum\limits_{i=1}^n \alpha_i K(x, x_i)

    多項式カーネル

    多項式カーネルは次のように定義されます。

    K(xi,xi′)=(1+∑j=1pxijxi′j)dK(x_i, x_{i'}) = \left(1 + \sum\limits_{j=1}^p x_{ij} x_{i'j} \right)^d

    ここで、ddは正の整数で多項式の次数を与えます。

    簡単な例を挙げます。データポイントの要素数ppが2の場合を考えます。2次の多項式(d=2d=2)は以下になります。

    K(xi,xi′)=(1+∑j=1pxijxi′j)2=(1+xi1xi′1+xi2xi′2)2= (1+xi1xi′1+xi2xi′2)(1+xi1xi′1+xi2xi′2)=1+2xi1xi′1+2xi2xi′2+xi12xi′12+2xi1xi′1xi2xi′2+xi22xi′22\begin{aligned} K(x_i, x_{i'}) &= \left(1 + \sum\limits_{j=1}^p x_{ij} x_{i'j} \right)^2 \\[1ex] &= \biggl(1 + x_{i1} x_{i'1} + x_{i2} x_{i'2} \biggr)^2 \\[2ex] &= \biggl(1 + x_{i1} x_{i'1} + x_{i2} x_{i'2} \biggr)\biggl(1 + x_{i1} x_{i'1} + x_{i2} x_{i'2} \biggr) \\[3ex] &= 1 + 2x_{i1} x_{i'1} + 2x_{i2} x_{i'2} + x_{i1}^2 x_{i'1}^2 + 2x_{i1}x_{i'1}x_{i2}x_{i'2} + x_{i2}^2 x_{i'2}^2 \end{aligned}

    これによって、もともとのデータセットよりも高次元の特徴量の空間でデータを線形分離するのと同等ことが可能となります。

    なお、次数がd=1d=1の場合は線形カーネルと同等です(1が余分ですが、バイアスβ0\beta_0で吸収されれば同じことです)。

    このように非線形のカーネルを使うサポート・ベクトル分類器をサポート・ベクトル・マシン(SVM)と呼びます。しかし、線形カーネルも含めてSVMと呼ぶことも多いです。

    なお、一般的な式の形は変わりません。

    f(x)=β0+∑i=1nαiK(x,xi)f(x) = \beta_0 + \sum\limits_{i=1}^n \alpha_i K(x, x_i)

    なお、回帰にSVMの仕組みを使うことも可能です。

    scikit-learnでは、SVR(Support Vector Regression)が実装されています。

    SVR — scikit-learn 1.5.1 documentation

    RBFカーネル

    RBF(Radial Basis Function)カーネルは、次の変換を行います。

    K(xi,xi′)=exp⁡(−γ∑j=1p(xij−xi′j)2)K(x_i, x_{i'}) = \exp \left(-\gamma \sum\limits_{j=1}^p \left(x_{ij} - x_{i'j} \right)^2 \right)

    なお、γ\gammaはスケールのためのハイパーパラメータ(正の定数)です。

    RBFカーネルは内積ではなく、2つのベクトル間のユークリッド距離(の2乗)∑j=1p(xij−xi′j)2\sum\limits_{j=1}^p \left(x_{ij} - x_{i'j} \right)^2を使っています。距離もデータ間の類似度の指標ですが、方向などは関係なく近いかどうかだけが重要です。

    訓練データポイントからの距離が離れているほど、RBFカーネルの値は小さくなります。逆に、距離的に近くの訓練データに敏感です。また、γ\gammaがその敏感度を調節しています。

    RBFカーネルは、ガウス関数に形が似ているので、ガウス・カーネルとも呼ばれますが、その観点からするとγ\gammaは分散の逆数に相当します。つまり、γ\gammaが小さいことは、分散が大きいのと同等であり、その形状は平坦になります。

    画像
    ガウス分布における異なる分散の比較

    ここで、SVMの式をもう一度眺めてみます。

    f(x)=β0+∑i=1nαiK(x,xi)f(x) = \beta_0 + \sum\limits_{i=1}^n \alpha_i K(x, x_i)

    各訓練データポイントに対しての係数αi\alpha_iの値は、そのデータポイントに近いデータがどのクラスに属するかを左右します。

    バイアスβ0\beta_0を無視して単純に考えると、正のクラスに対して係数αi\alpha_iは正の値となり、負のクラスに対して係数αi\alpha_iは負の値となります。よって、入力データxxがどのクラスの訓練データにより近いのかが総合的に判断されることになります。

    なお、別の観点からRBFカーネルを理解することもできます。

    指数関数eze^zはテイラー展開を行うと、無限に多くの項を持つ多項式として表現されます。

    ez=1+z+z22!+z33!+z44!+⋯e^z = 1 + z + \frac{z^2}{2!} + \frac{z^3}{3!} + \frac{z^4}{4!} + \cdots

    つまり、RBFカーネルは、データを無限次元の特徴空間に暗黙的に写像していることになります。

    SVMによる多クラス分類

    これまでずっと、2クラス分類(2項分類、バイナリ分類)に関して解説してきました。ハイパープレーンによる分類という性質上、2つより多いクラスの分類は不可能に見えます。

    しかし、SVMを任意のクラス数を持つ多クラス分類に拡張することができます。また、複数の手法が存在します。

    • 1対1分類(one-versus-one classification)

    • 1対他分類(one-versus-all classification、あるいはone-versus-rest classification)

    1対1分類

    1体1分類とは、K>2K>2クラスの問題を、各クラス間で2クラスの分類として処理する手法です。

    例として、クラスA、B、Cの3つのクラスがあるとします。この場合、以下の3つのSVM分類器を構築します。

    1. A 対 B の SVM分類

    2. A 対 C の SVM分類

    3. B 対 C の SVM分類

    テストデータを分類する際、各SVMで予測を行います。例えば、テストデータが次のように分類されたとします。

    • A 対 B => A と予測

    • A 対 C => C と予測

    • B 対 C => C と予測

    この結果、クラスAが1回、クラスCが2回選ばれたため、テストデータは最終的にクラスCに分類されます。

    まとめると、Kクラスのうち、任意の2つのクラスを比較するSVMを構築し、すべてのクラスペアについて分類を行います。最終的に、各クラスが何回選ばれたかを集計し、最も多く選ばれたクラスに分類します。

    この手法では、すべてのクラスの組み合わせでSVMを適用するため2CK_2C_K個のSVM分類器が必要となります。

    1対他分類

    一対他分類とは、K>2K>2クラスの問題を、各クラスと残りの全クラス(K−1K-1)とを比較するSVMを構築する方法です。

    例として、クラスA、B、Cの3つのクラスに対して、それぞれ次の3つのSVM分類器を構築します。

    1. A 対 他(BとC)の SVM分類

    2. B 対 他(AとC)の SVM分類

    3. C 対 他(AとB)の SVM分類

    テストデータを分類する際、各分類器で次のような結果が得られたとします。

    • A 対 他(BとC)=> A と予測

    • B 対 他(AとC)=> B と予測

    • C 対 他(AとB)=> C と予測

    これらの予測結果の中で、各SVMに対してfA(x)f_A(x)、fB(x)f_B(x)、fC(x)f_C(x)が計算されます。そこで最も強く正として予測されたクラス(例えばC)にテストデータが分類されます。

    この手法では、各クラスに対して一つのSVMを適用するためKK個のSVM分類器が必要となります。

    1対1分類と1対他分類の比較

    1対1分類と1対他分類における計算量の違いについて比較してみます。

    まず、1対1分類は分類器の数が組み合わせの数必要であり、1対他分類と比較して分類器の数が多くなり訓練時間が長くなる可能性があります。ただし、各分類器が扱う訓練データセットは比較的小さくなります。

    その一方、1対他分類は分類器の数はクラスの数だけ必要であり、1対1分類と比較して少ないですが、各分類器は全データを使用して訓練されます。

    なので、どちらの計算量が多いかは一概に言えません。

    また、性能に関してもどちらが優れているかを理論的に証明できません。なぜなら、両方の手法の性能は問題に依存するからです。

    ただし、1対他分類においては、各分類器が扱うデータが多くなるので予測精度が高くなる可能性があります。逆に、1対1分類で各組み合わせに対してデータ量が少ない場合は性能が悪くなることが想定されます。

    ちなみに、scikit-learnのSVCでは1対1分類が採用されています。

    from sklearn.svm import SVC
    
    clf = SVC()  # 内部で1対1分類を使う
    clf.fit(X_train, y_train)

    ただし、1対他分類用のモジュール(OneVsRestClassifier)もあります。

    from sklearn.svm import SVC
    from sklearn.multiclass import OneVsRestClassifier
    
    clf = OneVsRestClassifier(SVC()) # SVCのオブジェクトを渡す
    clf.fit(X_train, y_train)

    次回予告

    次回は、scikit-learnによるSVMを使って実験を行います。

    お楽しみに!

     
     
    「わかりやすく、具体的に」AIとサイエンスの情報を発信中

    あなたへのおすすめ