【caret】R で SVM

| 0件のコメント

SVM (Support Vector Machine) はマージン最大化を特徴とした教師あり学習です。

  • 線形SVM
  • 非線形SVM
  • 正則化
  • OCSVM
  • RでSVM

線形SVM

SVMでは2つのクラスを分ける分離超平面を求めます。 ω を重みベクトル, γ を切片として各サンプルに対するマージンを正にする ω と γ が存在するとき線形分離可能であるといいます。

     \begin{eqnarray*}   f_\omega_\gamma(x) = \omega^Tx+\gamma \end{eqnarray*}

このマージンを最大限に余裕を持って分離する超平面を選択することをマージン最大化といいます。
この分離超平面を求めることは, マージンの逆数の二乗を最小化する最適化問題です。

制約が等式の場合, 最適解を探すのは難しいことからラグランジュの未定乗数法というテクニックを用います。
ラグランジェ関数 L を使うことでラグランジュ関数と制約関数の連立方程式にできるのでこれを解くことで最適解を見つける事ができます。

例えば、以下のようラグランジュ乗数 λを導入して x で偏微分すると連立方程式となりこれを解くと最適解が得られます。

     \begin{eqnarray*}   L(x,\lambda) = L(x)+ \lambda_g(x) \end{eqnarray*}

また制約が不等式の場合, ラグランジュ関数の最大化は双対問題になります。この場合, 双対問題の最適解を求めることで主問題の最適解を求めることができます。

最適解が見つかれば, ω と γ が定まるので分離超平面が得られます。

上記をハードマージンSVMといいますが, 線形分離不可能な場合には解自体を求めることができない事があります。
そこで, 制約式を緩め誤差項 (スラック変数) を導入することで誤差を許容することをソフトマージンSVMといいます。

この時の誤差の許容度の度合いを C と呼ばれるコストパラメータで調整します。Cを上げるとハードマージンSVMに近づきます。

非線形SVM

ソフトマージンSVM では線形分離不可能な場合でも柔軟に対応できますが, 必ずしも良い分離超平面が求めるとは限りません。
SVMを非線形モデルに拡張する場合, カーネルトリック (Müller et al 2001) と呼ばれる技法を用います。

以下の入力空間に対して,

     \begin{eqnarray*}   \{x_i\}_{i=1}^n \end{eqnarray*}

非線形関数 Φ で特徴空間に写像 (map) します。

     \begin{eqnarray*}   \{\phi\(x_i\)\}_{i=1}^n \end{eqnarray*}

しかし, 単に高次元空間への写像することは計算量やメモリの点で困難です。
まず, 入力空間でのある2点を x, x’ とした時 カーネル関数は以下で表され, 非線形関数によってD次元空間 (特徴空間 または 再生カーネルヒルベルト空間) に写像された2点 Φ(x), Φ(x’) の内積となります。

     \begin{eqnarray*}   K(x, x') = \sum_{k=1}^{D} \phi_{k} (x) \phi_{k} (x') \end{eqnarray*}

この内積計算と同じことが入力空間の(半正定値)カーネル関数によって行えます。例えば, RBFカーネル は以下で示されます。

     \begin{eqnarray*}   K(x, x') = \exp(-\frac{||x - x'||^{2}}{\sigma^{2}}) \end{eqnarray*}

高次元の特徴空間で線形モデルで学習を行うことは, 元の空間で非線形のモデルを用いていることと等価となります。
これはカーネルトリックと呼ばれ, 展開がエレガントなこともありカーネル法は広く普及しました。

正則化

過学習 (Overfitting) を避けるために正則化項 (λ, 罰則項) を追加することを正則化 (Regularization) といいます。SVMにも正則化を導入できます。L1やL2の正則化が有名です。
ソフトマージンSVMでは損失関数を何に設定するかで最終的に得られるアルゴリズムが変化します。損失関数とは、あるデータについて分類に失敗した場合にそれに対して与えるペナルティのことです。例えば ramp関数 と呼ばれる上界を持つ損失関数を用いる事でロバスト性が向上します。

     \[   min\{1,max & (0,1-m) \}= \begin{cases}     1 & (m < 0) \\     1-m & (0 \leq m \leq 1) \\     0 & (m > 1)   \end{cases} \]

m < 0 の場合を1で打ち切っているのが hinge関数と異なります。rampとは高速道路と一般道などの傾斜の段差を繋ぐ傾斜道のことで, ランプ損失の表す 0 と 1 と繋ぐ直線がこれに似ていることから命名されたようです。

OCSVM

One Class SVM (Schölkopf et al 2001) は外れ値検出 (Outlier Detection) などで用いられる手法で, カーネルを用いて特徴空間への写像を行うと入力空間での外れ値が特徴空間では原点近くに写像されるという性質を利用し原点とサンプル群を分ける超平面を求めます。
超平面の位置は予め決められた割合 v のサンプル群が原点側に残るように設定されます。通常, 学習時には正常データのみを使用します。

RでSVM

Rでは有名な libsvm の wrapper である {kernlab} や {e1071}, {KlaR} でSVMを使えます。
今回は {kernlab} を使って Iris libsvm
の versicolor と virginica の2クラス分類を行ってみます。

kernlab::ksvm の type には分類問題の場合は SVC (Support Vector Classification) , 回帰問題の場合は SVR (Support Vector Regression) を指定します。

library(kernlab)

set.seed(1500)

d <- data.frame(iris[51:150,3:4], y = as.character.factor(iris[51:150,5])) # versicolor and virginica
d$y <- setattr(d$y,"levels", c("versicolor", "virginica"))

iris.ksvm <- ksvm(
  y ~ ., # y is Species
  data = d,
  kernel = "rbfdot",
  kpar = list(sigma=0.2), # kernel param sigma
  C = 5, # margin param C
  cross = 3
)

print(iris.ksvm)

plot(iris.ksvm, data = d[,1:2])

table(d$y, predict(iris.ksvm, d[,1:2]))
#             versicolor virginica
# versicolor         47         3
# virginica           3        47

kernlab_plot

パラメータチューニング

交差検定 (cross-validation) の目的は訓練データに適合しすぎる過学習を避けるためです。過学習は未知のデータに対する汎化能力が低いことも意味します。
交差検定は kernlab::ksvm の引数 cross で設定できます。

SVMの コストパラメータ C とRBFカーネルのパラメータ sigma のより良い値をグリッドサーチ (Grid Search) で探します。

{caret} は 100以上の機械学習手法や予測モデルに対して評価が行えるRのパッケージです。
caret::train の methodでモデルを指定します。trControl で trainingデータ, tuneGridで Grid Searchのカスタマイズも行えます。

library(caret)
library(kernlab)
library(ggplot2)
library(e1071)

grid <- expand.grid(
  C = ((2:10)*0.5),
  sigma = ((1:10)*0.01)
)

ctrl <- trainControl(
  method = "cv",
  savePred = T,
  classProb = T,
  number = 3
)

svmFit <- train(
  Species ~ .,
  data = iris,
  method = "svmRadial", # gaussian kernel
  trace = T,
  trControl = ctrl,
  tuneGrid = grid
)

p <- ggplot(svmFit$results, aes(x = C, y = sigma))
p + geom_point(aes(colour = Accuracy), size = 10) + scale_colour_gradient(low = "#0068b7", high = "#f39800")

grid_search

RでOCSVM

OCSVM は ksvm の type に "one-svc" を指定します。 RBFカーネルでは外れ値は特徴空間上の原点側に写像されます。 nu には特徴空間上での原点からのサンプル群の割合を指定します。

set.seed(1500)

df <- data.frame(miles = airmiles[1:24], class = 1)

svm <- ksvm(
  x = class ~ .,
  data = df,
  type = "one-svc",
  kernel = "rbfdot",
  kpar = list(sigma = 0.1),
  nu = 0.1 # 10% from the origin
)

preds <- predict(svm)
pred <- ifelse(preds == TRUE, 1, 0)
res <- data.frame(df, pred)
res$idx <- seq.int(nrow(res))

g <- ggplot(res, aes(x = idx, y = miles, colour = pred)) + geom_point() +
  labs(title = "OCSVM", x = "index", y = "miles")
plot(g)

結果は以下です。

参考書籍は パターン認識と学習の統計学-新しい概念と手法 です。


[1] SVMの双対問題について
[2] SVM回帰
[3] 過学習を防ぐ正則化
[4] caret package
[5] SMO徹底入門 - SVMをちゃんと実装する