今回は機械学習手法の一つ、特に分類問題で使用されるサポートベクターマシーンについて数式を用いて仕組みを解説していこうと思います。
Contents
1. SVMの概要
サポートベクターマシーン(SVM)は2値分類問題を解くために考えられた学習アルゴリズムであり、基本的には線形の識別器です。しかし、カーネル関数と最適化手法の組み合わせにより非線形な分類問題も解けるように拡張することができます。 SVMはハードマージンSVMとソフトマージンSVMの2種類に分けられます。ハードマージンは最も基本的なSVMで、データを完全に分類することを想定しています。実際には完全にデータを分類することができないことがあるため、分類できない部分を許す大きさの変数を導入したSVMをソフトマージンSVMと言います。どちらのSVMも線型分類を想定して作られたSVMで、これらとは別に非線形に拡張が可能です。
SVMの特徴として局所解にはまることがないという利点があります。学習に利用する目的関数が凸関数であるので局所解の問題がなくなります。しかし、非線形問題を解く場合のカーネル関数によっては局所解を持つ可能性があります。
今回はまずもっとも基本的なハードマージンSVMについて数式を用いて説明したいと思います。
2. ハードマージンSVMついて
では最も単純なSVMであるハードマージンSVMについて数学を用いず簡単に説明していきたいと思います。
簡単に説明する上の図でわかるように分布しているデータを識別器で境界線を引きます。この境界によってデータ分類することができます。境界線を引くだけであれば点線で表されるような境界線でも分類することができます。しかし、目的は未知のデータに対して正しい分類結果を与えることであるので点線のようにデータとぎりぎり被ってしまうような分類機は精度の良い分類機とは言えないでしょう。緑の線が求めたい境界だとするとできるだけこの点線と点線の真ん中に境界線を引ければ良い分類機になりそうです。緑の線はある程度良い境界線ですが最適な境界線ではまだありません。緑の境界線のパラメータを更新していくことで最適な境界を見つけます。
緑の境界線を更新していくアルゴリズムについて説明します。それぞれのクラスの緑の線から最も近い点(上の点線がかかる点)をサポートベクトル(サポートベクター)と呼びます。これがサポートベクターマシーン(SVM)の名前の由来です。このサポートベクトルと境界線の距離をマージンと呼びます。このマージンを目的関数として最大となるようにパラータを更新していくことで、最適な境界線を見つけることができます。このマージンに対して分類できない部分に対して許容する量を表すスラック変数を導入した目的関数を用いるとソフトマージンSVMとなります。
3. ハードマージンを数学的にみてみる
SVMの仕組みを数式を使って理解してみましょう。大学の数学が必要なので少し難しいかもしれませんが全体的な意味を理解できればいいと思います。詳しく理解したい場合は数式を一つずつ追ってみてください。
3.1 マージンの式と識別器の条件
SVMの基本的な仕組みのイメージはできましたでしょうか。では数学的に見ていこうと思います。
m個のn次元ベクトル
が二つのクラスにそれぞれ属することを想定します。 今回求めたい識別器(境界線)は
の超平面であり、パラメータである
を学習して求めます。
データのラベルをそれぞれ
として与える(1, -1など)あげると境界の上のデータも下のデータも
と書くことができます。
次にマージンについて考えていきます。まず識別器
と最も近いデータ点(サポートベクトル)との距離を求めます。
この際、超平面のパラメータである
を定数倍しても距離が変わらないことから
という制約をおきます。サポートベクトルとの距離は
となります。
この設定において識別器が存在する条件を考えます。
と識別できる識別器が存在すれば全ての点は
となります。
3.2 マージンの最大化とラグランジュ関数
識別器を最適化するにはマージンを最大化することでしたがマージンを表す数式が
であり、識別器の条件として
が必要であることがわかりました。
ここでマージンの最大化は以下の式の最小化として書き換えることができます。
この式が最小になればマージンは最大になることは理解できると思います。よって識別器が存在する条件での
の最小化が最適な識別器の最適化問題となります。
上のような制約のついている式の極値(今回は凸関数のため最小値)を求める手法としてラグランジュの未定乗数法という方法があります。簡単に説明するとベクトルの勾配の概念を利用した方法で、条件式と極値を求める関数が接する(極値となる)解をそれぞれの関数の勾配の一致と考えるというものです。それを求めるために導入されるのがラグランジュ関数です。
では、まずラグランジュ関数を定義します。ラグランジュ関数は以下の式としてかけます。
はラグランジュ乗数と言います。
この式を最小化する最適解は
の勾配が0となる点は
の勾配が0となる点でありこれらを求めます。
それぞれ計算してみます。
これらより
が得られます。
これらをラグランジュ関数に代入し
となります。
これまでの流れをまとめます。まず最適な識別器を求めるためにマージンの最大化を考えます。マージンの最大化は
の関数の最小化で表され、さらにこれを識別器の存在する条件で求めるとラグランジュ関数の最適解を求めることになります。さらにラグランジュ関数の最小化は先ほどもてめた数式の最小化と置き換えられます。つまり、目的関数は
の
についての最小化となります。
制約条件は
と
です。
3.3 目的関数の最適化結果と識別器への適用
目的関数は先ほど
と求めることができました。この目的関数を学習し最適な
を求めます。最適化アルゴリズムについては省略します。この
が求まったとして識別器のパラメータ
を求めます。
まず、偏微分の際に得られた式
に代入し
を得ます。また、
は
に代入することで得ることができます。
ここで
はそれぞれクラス1、-1に属するサポートベクトルです。
最適なパラメータを求めることができたので最適な識別器
を求めることができました。数学的にみると少し難しい部分もありますが、ある程度どのように計算を行っているのかはわかったと思います。
4. SVMを実装してみる
最後にライブラリを用いてSVMを実装してみたいと思います。PythonとRの両方で実装を行ってみようと思います。
4.1 Pythonで実装(scikit-learn)
Pythonを使って実装してみます。Pythonではscikit-learnに簡単に実装できるモデルがあるのでこれを使います。まずは、2つの変数を用いて分類機がどうなっているか確認してみようと思います。
####### 必要なライブラリのインポート #########
# データ加工用
import numpy as np
import pandas as pd
from pandas import Series, DataFrame
# データと学習用
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.svm import LinearSVC
# 可視化
import matplotlib.pyplot as plt
######### データの加工 ############
# irisデータを読み込む
iris = load_iris()
# データの加工
df = DataFrame(iris["data"], columns=iris.feature_names)
df_target = DataFrame(iris.target, columns=["target"])
df = pd.concat([df, df_target], axis=1)
# 今回は2値分類を行う
use_data = df[df.target != 2]
use_data = use_data[['petal length (cm)', 'petal width (cm)', 'target']]
# 訓練データとテストデータを分けるライブラリ
from sklearn.model_selection import train_test_split
# 訓練データとテストデータに分ける
X_train, X_test, y_train, y_test = train_test_split(use_data.iloc[:, :2].values,
use_data.iloc[:, 2].values,
test_size=0.4,
random_state=42)
####### こっからがSVM #########
# クラスの初期化と学習
model = LinearSVC()
model.fit(X_train, y_train)
####### 結果の表示 #############
# モデルの係数と切片を表示
print('係数:', model.coef_)
print('切片:', model.intercept_)
# 訓練データとテストデータのスコア
print('正解率(train):{:.3f}'.format(model.score(X_train, y_train)))
print('正解率(test):{:.3f}'.format(model.score(X_test, y_test)))
######################################
####### 分類平面の描画 #############
# 分類平面
x_min, x_max = X_test[:, 0].min() - 1, X_test[:, 0].max() + 1 #petal length (cm)
x = np.linspace(x_min, x_max, 1000)
y = (-model.coef_[0, 0] * x - model.intercept_[0]) / model.coef_[0, 1]
plt.plot(x, y)
# データ点
plt.scatter(X_test[y_test == 0, 0], X_test[y_test == 0, 1], c='red', edgecolors='k', label='target = 0 :setosa')
plt.scatter(X_test[y_test == 1, 0], X_test[y_test == 1, 1], c='blue', edgecolors='k', label='target = 1 :versicolor')
# 描画
plt.xlabel('Petal Length (cm)')
plt.ylabel('Petal Width (cm)')
plt.title('Decision Boundary')
plt.legend()
plt.show()scikit-learnのsklearn.svmの中にあるLinearSVCを読み込みました。modelにいれ初期化を行い、fitで学習します。scikit-learnのモデルは基本的にこの書き方なので同じように他のモデルも簡単に実装できます。では実装してみましょう。
簡単すぎて100%の精度がでたと思います。簡単に実装できますね。分類平面もはっきりわかり、この2つの変数だけでしっかりと2種類の花の種類を分類することができることがわかります。また、分類平面を見てみるとマージンが最大化され、ちょうど2種類のデータの中央にラインが引かれているのがわかるかと思います。
4.2 Rで実装
Rでも実装してみます。今度は他の変数も使って4変数での実装を行います。RでSVMを行うにはe1071のパッケージが必要です。記述の方法は他の学習機とほとんど同じです。
# irisデータの読み込む
df <- iris
# データの加工用ライブラリ
library(dplyr)
# データの加工
df <- df %>%
filter(Species == "setosa" | Species == "versicolor") %>%
mutate(Species = case_when(
Species == "setosa" ~ "0",
Species == "versicolor" ~ "1"),
Species = as.numeric(Species)
)
# 訓練データとテストデータを分ける
set.seed(42)
train_index <- sample(1:nrow(df), 60)
train_data <- df[train_index,]
test_data <- df[-train_index,]
######## こっからSVM #########
# SVMのライブラリ
library(e1071)
# クラスの初期化と学習
svm_model <- svm(Species ~ ., data = train_data, kernel = "linear")
##################################################
# 訓練データとテストデータのスコア
predictions <- ifelse(predict(svm_model, test_data) >= 0.5, 1, 0)
accuracy <- mean(predictions == test_data$Species)
paste("正解率(test):", sprintf("%.3f",accuracy))pythonのときと同様に2値分類に変更しsvm() 関数でモデルの学習を行い test データに反映し正解率を出します。
pythonの時と同様に100%の精度が出ました。この程度の分類ならSVMでも100%予測できますね。人が学習するより早いです。
5.まとめ
今回は分類問題の代表的な学習手法であるSVMの仕組み、特にハードマージンSVMについて数学を用いて詳しく説明し、PythonとRでそれぞれ実装してみました。ある程度理解できるといろんなことに応用できるかもしれないので知っとくといいかと思います。
