SVM（サポートベクターマシーン）についてのメモ。

SVM（サポートベクターマシーン）とは

SVMは「マージン最大化」の考えに基づいて分類する手法である。
n次元空間に超平面（線形識別関数、二次元なら直線）で分類境界を作ることでベクトルを分離する。
（マージンが大きいほど、未知データでの識別誤りが起こりにくいだろうという理屈でマージン最大化する）。

手法としては、線形分離可能を仮定する「ハードマージン法」と任意の識別誤りを許容する「ソフトマージン法」がある。
さらに、非線形問題に対しても、高次元特徴空間を作り「カーネルトリック」を使って分類する方法がある。
前者を線形SVM、後者を非線形 SVMと呼ぶ。

線形SVM（ハードマージン法とソフトマージン法）

「ハードマージン法」は、訓練データ（学習するデータ）を超平面で完全に分離できると仮定した問題である。

f:id:cochineal19:20210520010026p:plain

ただし、現実的には線形分離可能な問題は珍しく、ある程度の識別誤りを許容する「ソフトマージン法」が用いられる。識別誤りのパラメータとしてスラック変数 ξ を導入し、ハイパーパラメータCでその許容を調整する。

f:id:cochineal19:20210520010101p:plain

主問題と双対問題

SVMでは「主問題」を直接解くのではなく、計算コストの良い「双対問題」に帰着して解く方法が実装されている。双対問題を解く際、後に記載する「カーネルトリック」も扱える。

双対問題を解くにあたっては、主問題を不等式制約のラグランジュ未定乗数法を用いて双対問題へ置き換える（計算の詳細は割愛）。
以下はハードマージン法とソフトマージン法の式を横に並べたもの。赤字部分が異なる箇所。
f:id:cochineal19:20210520021551p:plain

ここで双対問題とは、主変数 $w, b, \xi$ を最小化し、双対変数 $\alpha , \beta$ を最大化する問題である。
これは主変数にとっての最小値が、双対変数にとっての最大値になる「鞍点」（あんてん）を探している（鞍点が最適解ということ。鞍点はKKT条件を満たす）。鞍点は字のごとく、馬の鞍（くら）の形。

※双対問題・鞍点の概念は、以下リンクのスライド22枚目が分かりやすかった（他サイト様のもの）。
はじめてのパターン認識第8章サポートベクトルマシン

以上により最適解 $\alpha_{i}$ が求まれば、ラグランジュ関数にて求めた次の式で係数 $w$ が求まる。

$\quad w=\sum_{i\in sv}α_{i}t_{i}x_{i}, \ sv:サポートベクトル$

ここで、マージンの外側（本記事の概念図で背景色を付けた領域）にある正解ベクトルは $\alpha_{i}=0$ となり、マージンの内側（ $0 < \xi _{i} \leq 1$ , または $1 < \xi_{i}$ ）にあるベクトルは $\alpha _{i} = C$ となる。そして、ちょうどマージンの上（概念図の点線）にあるベクトルは $0 < \alpha_{i} < C$ となることから、 $\alpha ≠ 0$ であるマージンの内側とマージン上のベクトル（これらが「サポートベクトル」と言われる）のみを用いて係数 $w$ を求めれば良い。

＜再掲＞
f:id:cochineal19:20210520010101p:plain:w400

Pythonによる実行

sklearn の svm.LinearSVC で線形SVMが実行できる。
ソフトマージン法のハイパーパラメータCはデフォルトで C=1.0 である。

Pythonコード

from sklearn.svm import LinearSVC
 
mod1 = LinearSVC(C=C, random_state=1)
mod1.fit(X_train, y_train)
y_pred1 = mod1.predict(X_test)
print(confusion_matrix(y_test, y_pred1))
print(classification_report(y_test, y_pred1))
print()

なお、線形SVMでもL1正則化とL2正則化を指定できる。デフォルトは penalty="l2"（L2正則化）。
正則化については次の記事を参照。
【機械学習_Python】Ridge回帰、Lasso回帰、Elastic Net回帰 - こちにぃるの日記

非線形 SVM（カーネルトリック）

ソフトマージン法によって線形分離不可能なデータセットも扱えるようになったが、現実的には非線形の分類境界を作りたい場面が多い。
このような場面に対して、入力空間を高次元特徴空間に変換（特徴量を非線形に写像）して分類可能とする方法がある。
f:id:cochineal19:20210520162542p:plain:w400

上の例では、関数 $\phi \left( x_{i}\right)^{T} \phi \left( x_{j}\right)$ を用いて新たな特徴量（例えば $x_{1} x_{2}$ ）を作り、３次元空間とすることで分離可能になった。このように、特徴量を高次元に写像するほど分離可能性が高まる。
この方法は、次元を高めるほど計算コストが爆発的に高まり実装しづらい欠点があったが、カーネル関数を導入した「カーネルトリック」と呼ばれる方法によって計算コスト面を解消することができる。

カーネル関数

$\quad K\left(x_{i},x_{j}\right)=\phi \left( x_{i}\right)^{T} \phi \left( x_{j}\right)$

※簡単な記載になってしまうが、カーネル関数を用いることで関数 $\phi \left( x_{i}\right)^{T} \phi \left( x_{j}\right)$ の中身を計算せずとも、等価な結果を計算することができる。

f:id:cochineal19:20210520163237p:plain

Pythonによる実行

sklearn の svm.SVC で非線形 SVMが実行できる。
ソフトマージン法と同じくハイパーパラメータ：Cを設定可能。デフォルトは C=1.0 。
カーネルの指定は、linear、poly、rbf、sigmoid、precomputed があり、デフォルトは kernel='rbf' 。poly が多項式カーネル、rbf がGaussカーネル、sigmoid がシグモイドカーネルで、linear は線形SVM（sklearn.svm.LinearSVC と少し異なるらしい）。
多クラス分類においては、decision_function_shapeにおいて、ovo（one vs one、１対１）とovr（one vs rest、１対残り）を指定できる。ovoはクラス同士のペアを総当たりするため計算量が多い。デフォルトは decision_function_shape='ovr'

Pythonコード

from sklearn.svm import SVC
 
mod1 = SVC(C=C, kernel='rbf', random_state=1)
mod1.fit(X_train, y_train)
y_pred1 = mod1.predict(X_test)
print(confusion_matrix(y_test, y_pred1))
print(classification_report(y_test, y_pred1))
print()

Wineデータで実行

Wineデータから線形分離が難しそうなデータの組を適当に見つけて、線形SVMと非線形 SVMの識別性能を比較してみる。

import seaborn as sns
import pandas as pd
import numpy as np
from sklearn import datasets, model_selection
from sklearn.svm import LinearSVC, SVC
from sklearn.metrics import classification_report, confusion_matrix
import matplotlib.pyplot as plt

ROW = datasets.load_wine()
ADS = pd.DataFrame(ROW.data, columns=ROW.feature_names).assign(target=np.array(ROW.target))
sns.pairplot(ADS[["ash","proline","target"]], hue="target")

f:id:cochineal19:20210520192333p:plain:w400

特徴量 "ash", "proline" の target 1 vs. 2 が良い感じに混ざっていたので、今回これらを用いる。

ADS12 = ADS[ADS["target"]!=0]
ADS12["target"] = ADS["target"] - 1
 
X_train, X_test, y_train, y_test = model_selection.train_test_split(
        ADS12[["ash","proline"]], ADS12["target"], test_size=0.3, random_state=999)
 
#-- 線形SVM
mod1 = LinearSVC(C=1, random_state=999)
mod1.fit(X_train, y_train)
y_pred1 = mod1.predict(X_test)
print('線形SVM')
print(confusion_matrix(y_test, y_pred1))
print(mod1.score(X_test, y_test))
#print(classification_report(y_test, y_pred1))
print()
 
#-- 非線形SVM
klist=['poly','rbf','sigmoid']
for k in klist:
    mod1 = SVC(C=1, kernel=k, random_state=999)
    mod1.fit(X_train, y_train)
    y_pred1 = mod1.predict(X_test)
    print('非線形SVM ', k)
    print(confusion_matrix(y_test, y_pred1))
    print(mod1.score(X_test, y_test))
    #print(classification_report(y_test, y_pred1))
    print()