SVM（サポートベクターマシン）の理論

こんにちは，デイビッドです．今回は，
教師あり学習（Supervised Learning）＞SVM（Support Vector Maachines，サポートベクターマシン）についてです．

全体に戻る場合はこちら↓

SVMとは

SVM；サポートベクターマシンは，データを最適な境界線で分類するための強力な機械学習モデル．教師あり学習であり，分類にも回帰にも使われますが，２値分類に利用されることが多いです．

二値分類においては，データ点を以下の式が，正か負かで分類します．
$$ \begin{eqnarray}
g(\phi({\bf x}))={\bf w}^T\phi({\bf x})+w_0
\end{eqnarray} $$

すなわち，以下が，境界線になって，これによって各クラスのデータを分離するわけですね．

$$\begin{eqnarray}
g(\phi({\bf x}))={\bf w}^T\phi({\bf x})+w_0=0
\end{eqnarray} $$

また，各クラスのデータ点と境界との最短距離をマージンと呼び，SVMではマージンが最大になるような境界（におけるパラメータ$ {\bf w},\ w_0 $）を学習します．
そして，マージン上にあるデータ点をサポートベクターと呼びます．

メリット

1. 効果的な高次元空間でのパフォーマンス： SVMは高次元のデータに対しても効果的に機能し、多くの特徴を持つデータセットに適しています。
2. 過学習のリスクが低い： SVMはマージンの最大化に基づく学習を行うため、過学習に強いという特性を持っています。これは、特にデータが少ない場合に有効です。
3. 異なるカーネル関数の使用： 線形分離可能でないデータに対しても、カーネルトリックを使用して非線形の関係を捉えることができます。これにより、多様な問題に対応可能です。
4. 一般化能力が高い： 分類面がデータの少数の「サポートベクタ」にのみ依存するため、未知のデータに対しても良い一般化性能を示す。単純な問題に対して，ニューラルネットワークよりも高い汎化性能を持つ．

デメリット

1. スケーラビリティの問題： サンプル数が100,000以上など非常に多い場合には、上手く機能しなくなる．
2. データの前処理が必要： 正規化や標準化などが必要．

マージン最大化

マージン最大化とは，分類問題において，汎化性能を向上させる基本的な手法．

マージンを最大化することにより，データポイントが識別面（Decision Boundary）からできるだけ遠く離れるようにします．マージンが少ないような場合，入力値を誤って分類するリスクが下がるということと理解．図でDecision Boundary 2（点線），がマージン小さい線．Decision Boundary 1（実線）ならば，正しく分類できるものも，Decision Boundary 2（点線）だと分類できない．こういうことを防ぎたいのであろう．

簡単のため，教師あり学習の二値分類を仮定する．

識別面（Decision Boundary）は，

$$\begin{eqnarray*}
{\bf w}\cdot{\bf x}+w_0=0
\end{eqnarray*}$$

この${\bf w}$を求めるのが目的になる．

ここで，識別面と各点との距離${\rm Dist}(x_i)$は，以下のように書ける

$$\begin{eqnarray*}{\rm Dist}(x_i) = \frac{\left|{\bf w} \cdot {\bf x_i} + w_0\right|}{\|w\|}
\end{eqnarray*}$$

このとき，入力データ${\bf x_i}$と識別面との最小距離は，
$$\begin{eqnarray*} \min_i{\rm Dist}(x_i) = \min_i\frac{\left|{\bf w} \cdot {\bf x_i} + w_0\right|}{\|w\|} \end{eqnarray*} $$
識別面と最も距離が近いデータに対して，
$$\begin{eqnarray*} \min_i\left|{\bf w} \cdot {\bf x_i} + w_0\right|= 1 \end{eqnarray*}$$
となるよう重みベクトル${\bf w}$を設定したとすると，
$$\begin{eqnarray*} \min_i{\rm Dist}({\bf x_i}) = \min_i\frac{1}{\|w\|} \end{eqnarray*}$$
マージン最大化する識別面を求めるためには，$\|w\|$を最小化すればよい．
計算上は扱いやすい，$\|w\|^2/2$を最小化する．

$$\begin{eqnarray*}
\text{Objective: }&min\frac{\|w\|^2}{2}\\
\text{Constraint: }&y_i({\bf w} \cdot {\bf x_i} + w_0)\geq 1
\end{eqnarray*}$$
を解く．
ラグランジュの未定乗数法を用いると，
$$\begin{eqnarray*}
& g(\mathbf{w}, w_0) = y_i (\mathbf{w} \cdot \mathbf{x}_i + w_0) – 1 \geq 0 \\
& f(\mathbf{w}, w_0) = \frac{1}{2} \|\mathbf{w}\|^2 \\
\end{eqnarray*}$$
と、おけるので、

ラグランジュ乗数を $\alpha_i $とすると、ラグランジュ関数 $L$ は，
$$\begin{eqnarray*}
& L(\mathbf{w}, w_0, \alpha) = f(\mathbf{w}, w_0) + \alpha g(\mathbf{w}, w_0) \\
& = \frac{1}{2} \|\mathbf{w}\|^2 – \sum_{i=1}^{N} \alpha_i \left( y_i (\mathbf{w} \cdot \mathbf{x}_i + w_0) – 1 \right) \\
\end{eqnarray*}$$
と書ける．
$$\begin{eqnarray*}
\frac{\partial L}{\partial w_0} = 0,\  \frac{\partial L}{\partial \mathbf{w}} = 0
\end{eqnarray*}$$
を計算して，
$$\begin{eqnarray*}
\sum_{i=1}^{N} \alpha_i y_i = 0 \\
\mathbf{w} = \sum_{i=1}^{N} \alpha_i y_i \mathbf{x}_i
\end{eqnarray*}$$
$\bf w$を求めるために，$\alpha_i$を求める必要がある．
これらの式をラグランジュ関数に代入すると，
$$\begin{eqnarray*}L(\alpha)
&=&\frac{1}{2} \sum_{i,j=1}^{N} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j – \sum_{i=1}^{N} \alpha_i\\
&=&\frac{1}{2}\left|w\right|^2-\left|w\right|^2+\sum\alpha_i\\
&=&-\frac{1}{2}\left|w\right|^2+\sum\alpha_i\\
\end{eqnarray*}$$

また，$w_0=-{\bf w}\cdot{\bf x}$なので，
$$\begin{eqnarray*}
w_0=-\frac{1}{2}\left({\bf w}\cdot{\bf x_{+}}+{\bf w}\cdot{\bf x_{-}}\right)
\end{eqnarray*}$$
$\bf x_{+},\bf x_{-}$は，サポートベクトル（識別面に最も近い点を通る傾き${\bf w}$のベクトル）

カーネル関数（Kernel Function）

元の特徴空間では線形分離不可能なデータを，より高次元の空間に写像することにより，線形分離可能にする．

カーネルトリック（Kernel Trick）

カーネル関数は，データ点間の類似度を計算する関数．
元々の特徴空間上の2点$ {\bf x}, {\bf x^{\prime}} $の距離に基づいて定義されるある関数$ K({\bf x}, {\bf x^{\prime}}) $を考える．

元々の特徴空間を線形分離可能にするための，高次元空間に写像する非線形写像を$ \phi $として，以下のようなカーネル関数を定義する．
$$ \begin{eqnarray}
K({\bf x}, {\bf x^{\prime}})=\phi({\bf x}^T)\phi({\bf x^{\prime}})
\end{eqnarray} $$

元々の特徴空間の2点間の距離が，ある非線形写像後の特徴空間での内積になるので，2点間の「近さ」の情報が保存される．

このとき，写像後の特徴空間での識別関数$ g $は以下のように表せる．

$$ \begin{eqnarray}
g(\phi({\bf x}))={\bf w}^T\phi({\bf x})+w_0
\end{eqnarray} $$

SVMを適用すると，
$$ \begin{eqnarray}
{\bf w}=\sum{\alpha_iy_i\phi(x_i)}
\end{eqnarray} $$

となるので，識別関数は，
$$\begin{eqnarray}g(\phi({\bf x}))
&=&{\bf w}^T\phi({\bf x})+w_0\\
&=&\sum{\alpha_iy_i\phi({\bf x})^T\phi(x_i)+w_0}\\
&=&\sum{\alpha_iy_iK({\bf x}, {\bf x^{\prime}})+w_0}\\
\end{eqnarray}$$

また，ラグランジュ関数は，

$$ \begin{eqnarray}
L(\alpha)=\frac{1}{2}\sum^N_{i,j=1}{\alpha_i\alpha_jy_iy_jK({\bf x}, {\bf x^{\prime}})}-\sum^N_{i=1}\alpha_i
\end{eqnarray} $$

識別関数にも，ラグランジュ関数にも，非線形写像$ \phi $が現れないため，直接求めることなく，SVMの計算が実行できる！
これが，カーネルトリックです．

カーネル関数の例

適用例

ChatGPTに聞けばコードはすぐに出てきますね．
Prompt「SVMを用いる具体例とcolabで実装するコードを教えて」
私のところで出てきたのは以下でした．

# 必要なライブラリをインストール
!pip install scikit-learn
!pip install matplotlib

# ライブラリのインポート
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.metrics import classification_report, confusion_matrix

# MNISTデータセットを読み込む
digits = datasets.load_digits()

# 特徴量とラベルを設定
X = digits.data
y = digits.target

# トレーニングセットとテストセットに分割
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 特徴量を標準化
scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)

# SVMモデルの作成
svm = SVC(kernel='linear', random_state=42)

# モデルのトレーニング
svm.fit(X_train, y_train)

# テストセットで予測
y_pred = svm.predict(X_test)

# 結果の評価
print("Confusion Matrix:")
print(confusion_matrix(y_test, y_pred))
print("\nClassification Report:")
print(classification_report(y_test, y_pred))

皆さんもそれぞれの環境できいてみてください．以下に飛んでコピペで実行だ！

from sklearn.svm import SVC

# 線形カーネル
svm_linear = SVC(kernel='linear', C=1.0, random_state=42)

# RBFカーネル
svm_rbf = SVC(kernel='rbf', C=1.0, gamma='scale', random_state=42)

# 多項式カーネル
svm_poly = SVC(kernel='poly', C=1.0, degree=3, gamma='scale', random_state=42)

# モデルのトレーニング
svm_linear.fit(X_train, y_train)
svm_rbf.fit(X_train, y_train)
svm_poly.fit(X_train, y_train)

from sklearn.model_selection import GridSearchCV

# ハイパーパラメータの候補を設定
param_grid = {
    'C': [0.1, 1, 10, 100],
    'gamma': ['scale', 'auto', 0.001, 0.01, 0.1, 1],
    'kernel': ['rbf', 'poly', 'sigmoid']
}

# グリッドサーチの設定
grid_search = GridSearchCV(SVC(), param_grid, refit=True, verbose=3)

# グリッドサーチの実行
grid_search.fit(X_train, y_train)

# 最適なハイパーパラメータの表示
print("Best parameters found: ", grid_search.best_params_)

# 最適なモデルで予測
best_model = grid_search.best_estimator_
y_pred = best_model.predict(X_test)

# 結果の評価
print("Confusion Matrix:")
print(confusion_matrix(y_test, y_pred))
print("\nClassification Report:")
print(classification_report(y_test, y_pred))

まとめ

SVMについてでした．意外とカーネル関数でググっても手軽な記事ないですね．