サポートベクターマシンの詳しい理論的な解説について【線形分離可能な場合】
この記事はこんな人におすすめです.
  • サポートベクターマシンの理屈を詳しく理解したい人
  • 機械学習の勉強をしている人
  • 人工知能の勉強をしている人

こんにちは.けんゆー(@kenyu0501_)です.
ここでは,サポートベクターマシンの理論的な解説をしていきます.
色々と長くなってしまそうなので,とりあえず線形分離可能な場合のみでまとめます.

サポートベクターマシンSVM

マージン最大化する線を引くこと

2つのクラスK1とK2をもつ,線形分離可能なデータに対して,マージン最大化する線を引くための理論的な解説を行います.

サポートベクターマシンは,上の図のような線を引くことです.
直線よりも上にあるデータは,クラス1(K1)に属し,直線よりも下にあるデータ群はクラス2(K2)に属します.
SVMでは,傾きwと切片bをマージン最大化するような最適化問題を解くことによって決定します.

2つのクラスの条件を扱うために

ここで,2つのクラスの条件を扱いやすくするために,ラベル変数tを用意します.

ラベル変数t
  • i番目のデータがK1に属する → t=1
  • i番目のデータがK2に属する → t=-1

ラベル変数を用いて,全てのデータに対して式が0より大きいという条件を満たすような形にします.
この条件を満たしながらマージン最大化をします.

点と超平面(直線)の距離について考える

ここで,単純な点と超平面の距離について考えます.
マージン最大化をするものは,この点と超平面の距離だからです.
まずは高校数学の復習として,「2次元平面上の点と直線」について考えた後で,n次元空間の点と超平面の距離」に拡張した方が考えやすいかもしれないです.

ここで,||W||はノルムと言われるもので,簡単にいうと単純な長さのことです.

マージン最大化をするための最適化問題

以上の要素を踏まえて,マージン最大化を以下の最適化問題に置き換えます.
ここで,マージンをMという記号で置き換えています.

一般的にこの最適化問題を解くためには,以下2つの条件を満たす必要があります.

  • 2つのクラスを分ける超平面に最も近いデータ(サポートベクトル)への距離(マージン)を最大化すること
  • そのマージンに対して,他の全てのベクトルと超平面の距離が離れていること

最適化問題の式変形

マージン最大化を最適化問題へと定式化し,置き換えることができましたが,より計算をしやすいような変形をしておきます.

手順
  1. 導出した最適化問題をマージンMで割る
  2. w~とb~を導入して式をシンプルにする.
  3. サポートベクトルのおいては,M~が成り立つ(2より).
  4. M~が超簡単になる

最大化問題を最小化問題に置き換える

ここでは,さらに計算の都合を良くするために,最大化問題を最小化問題にしましょう.
最適化問題を解くときには,最大化するよりも最小化にするようが解を探しやすいのです.
そのために,よく逆数の最小化を求める,という作業をして,最大化問題を最小化問題に置き換えることがあります.

最小化問題の,2分の1や,2乗というのは,のちの最適化計算をやりやすいようにしているだけなので,あまり気にしないでください.

このような最適化計算を行って,マージン最大化というものを行います.
しかし,実際にSVMで平面を引くときにも,まだ直接これを解くわけではありません.
この後にもう少し特殊な変形がありますが,大体SVMの数学的な理屈が理解できたと思います.

線形分離が不可能な場合のSVMはこちらです.

実際にSVMを実装してみたい人向け

Pythonのサイキットラーン(Scikit-learn)のライブラリで実際にプログラムを実装してみたい人向けの記事はこちらです.