この記事は古川研究室 Workout_calendar 11日目の記事です。
本記事は古川研究室の学生が学習の一環として書いたものです。内容が曖昧であったり表現が多少異なったりする場合があります。
記事を書くのは初めてですので至らない点が多々あると思います．
有識者の皆様，どうか暖かい目で見守っていただければ幸いです．
分類の基本的な手法として有名なサポートベクターマシン（以下SVM）ですが，私はその説明が腑に落ちるまでかなり苦戦しました．具体的には，以下のような疑問が長いことついてきてました．
- 分離直線の式における切片とは直線の公式$y=ax+b$における$b$と同じ役割なのか？
- マージン最大化って具体的にはどうやってるの？
- マージンの式で分子が$1$になってる説明が多いけどなんで？
せっかく自分なりに理解できたので，備忘録も兼ねて理解の過程を残しておこうと思い，今回記事にしました．回りくどい説明も多いかと存じますが，読んでいただければ幸いです．
SVMとは
SVMとは主にクラス分類に用いられる手法であり，大きく分けて３つの種類があります．以下ではその3つについて簡単に説明します．
ハードマージンSVM
ハードマージンSVMは訓練サンプルが線形分離可能である場合に，考えられる分離直線のうち訓練サンプルを最も余裕をもって分離する直線を求める手法です．
以下のようなイメージです．
赤と青のクラスが直線によって分離されています．ハードマージンSVMではこの直線のパラメータを更新し，２つのクラスを最も余裕をもって分離するように最適化します．これにより，未学習データに対しても高い分類性能が期待できるのです．
ソフトマージンSVM
ソフトマージンSVMは分布に重なりがある訓練サンプル，つまりは線形分離不可能なサンプルに対して，分類の誤りを許容しつつもある程度の分類性能が得られるような分離直線を求める手法です．
以下のようなイメージです．
先ほどのハードマージンSVMとは訓練サンプルについての前提条件が違うため，線形分離することは不可能です．しかし，誤分類の数に対して，正しく分類できているサンプルが多いという点で，ある程度の分類性能が確保されていると捉えることができます．ハードマージンSVMよりも柔軟な対応をしてくれるSVMです．
カーネルトリックSVM
カーネルトリックSVMは，線形分離不可能（非線形）なデータを高次元空間へと写像し，写像先の空間で高い分類性能を発揮することを目指す手法です．高次元空間への写像とは，既存の特徴量を新たな特徴量へと変換することで空間の軸を増やすイメージです．
以下の図のような感じです．
2次元空間では線形分離不可能なデータが，3次元空間へと写像することで平面によって線形分離できています．
上図における特徴量$x_3$が既知の特徴量を新たな特徴量に変換したものです．
しかし，高次元空間へ写像したとしても，訓練サンプルが線形分離可能になるとは限りません．そのような場合は高次元空間でソフトマージンSVMを適用します．
カーネルトリックSVMはハードマージンSVMとソフトマージンSVMを包含しており，高い分類性能を獲得するためにデータ空間の次元を変えるパワフルなSVMだといえます．
本記事で取り上げる手法
一般的にSVMを使うときはカーネルトリックSVMが用いられます．これはカーネルトリックSVMがハードマージンSVMとソフトマージンSVMを包含しているからです．そのため，SVMをちゃんと理解しようと思ったら、まずはハードマージンSVMの導出を追い理解する必要があります．この記事ではハードマージンSVMについて取り上げ，私の勉強の過程を記します．
ハードマージンSVMの問題設定
SVMは，上図のように単純な線形しきい素子を用いて，2クラスの分類器を構成します．
線形しきい素子は，入力特徴ベクトル$\boldsymbol{x}^T_i = (x_1,...,x_m)$に対し，識別関数
y = \mbox{sign}(\boldsymbol{w}^T\boldsymbol{x}-h) =\begin{cases}
+1 \quad \mbox{when} \quad \boldsymbol{w}^T\boldsymbol{x}_i > h , \quad(i=1,...,N)\\
-1 \quad \mbox{when} \quad \boldsymbol{w}^T\boldsymbol{x}_i \leq h, \quad(i=1,...,N)
\end{cases}\tag{1}
によって2値の出力値を計算します．
ハードマージンSVMは訓練サンプルから，マージンを最大化するように線形しきい素子のパラメータを学習します．
※線形しきい素子：出力として0,1の2値をとるようなモデルを，入力の線形和$( \sum_{i}^{N}w_ix_i)$がしきい値$(h)$を越えた時のみ1を出力することから，「線形しきい素子」という．
ハードマージンSVMによる分離直線の決定
この章では，ハードマージンSVMを用いた2クラス分類のための分離直線の決定の過程について記します．
与えられているもの
今，2つのクラスを$C_1, C_2$とし，各クラスのラベルを $1$ と $-1$ に数値化しておきます．また，訓練サンプル集合として， $N$ 個の特徴量ベクトル$\boldsymbol{x}_1,...,\boldsymbol{x}_N$と，それぞれのサンプルに対する正解のクラスラベルが与えられているとします．
D = \{(\boldsymbol{x}_1,t_1),...,(\boldsymbol{x}_N,t_N)\}
\boldsymbol{x}_i = (x_1,..., x_M),\quad(i=1,...,N)
\mbox{ラベル} : t_i =
\begin{cases}
+1 \quad \boldsymbol{w}^T\boldsymbol{x}_i > h , \quad(i=1,...,N)\\
-1 \quad \boldsymbol{w}^T\boldsymbol{x}_i \leq h, \quad(i=1,...,N)
\end{cases}
更に，与えられた訓練サンプル集合は，線形分離可能であると仮定します．つまり，識別関数を表す$(1)$式のパラメータ$(\boldsymbol{w},h)$を上手く調整することで，訓練サンプル集合のラベルを誤りなく出力することができます．二次元空間において幾何的に考えると以下のようなイメージです．
赤（クラスラベル：$1$）と青（クラスラベル：$-1$）の点群が与えられた訓練サンプルであり，真ん中あたりにある直線が，2つのクラスを分離する分離直線（分離超平面）です．
また，二次元空間で考えるならば，特徴量は2つなので，各特徴量ベクトルは2つの要素を持ちます．$x_1$は横軸，$x_2$は縦軸の値を表すと考えることができます．
\boldsymbol{x}_i = (x_1,x_2)
マージン最大化
訓練サンプル集合が線形分離可能であるとしても，一般にパラメータ$(\boldsymbol{w},h)$は一意に決まるとは限りません．これは，訓練サンプルを線形分離する直線がいくつも存在するからです．以下のようなイメージ．
上図のように黒色，緑色，黄色すべての直線で訓練サンプルは線形分離できてしまいます．
SVMは，そういったたくさんの分離直線のうち，訓練サンプルを余裕を持って分ける直線を求めます．「余裕を持って分ける」とはすなわち，識別平面に最も近い訓練サンプルとの距離（マージン）が最大になるような識別平面を求めることです．
以下のようなイメージ．
SVMが求める分離直線は，分離直線の最も近くに位置する各クラスのサンプルとのマージンが同じ大きさになるようになっています．上の図でいうと，マージン1とマージン2が同じ大きさになるようにするのです．
マージン1とマージン2の大きさが同じかつ，その条件のなかで各クラスの最近傍サンプルとのマージンが最大である分離直線を目指す．これがマージン最大化と呼ばれる所以です．
マージンの正規化
マージンの大きさは，直線と点の距離の公式より以下のように定義することができます．
\begin{align}
m_i &= \frac{t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h)}{\|\boldsymbol{w}\|} \tag{2}
\end{align}
そして今，分離直線と分離直線に最も近い位置に存在するサンプルとのマージンを正規化します．これは必ず必要な処理ではなく，計算をし易くするためです．
前節において，マージン1とマージン2は同じ大きさになると述べました．この大きさを$K$とします．
|\mbox{margin1}| = |\mbox{margin2}| = K \tag{3}
$(2)$式と$(3)$式より，全ての訓練サンプルについてマージンの大きさは以下のようになります．
\frac{t_i(\boldsymbol{w}^T\boldsymbol{x}_i -h)}{\|\boldsymbol{w}\|} \geq K, \quad (i=1,...,N) \tag{4}
$(4)$式の両辺を$K$で割り，$\frac{\boldsymbol{w}^T}{K}$と$\frac{h}{K}$を再度$\boldsymbol{w}^T$と$h$に置き換えることで以下の不等式が得られます．
\frac{t_i(\boldsymbol{w}^T\boldsymbol{x}_i -h)}{\|\boldsymbol{w}\|} \geq 1, \quad (i=1,...,N) \tag{5}
等号が成立する（最近傍サンプルについて考える）場合，分子の値は$1$としてよいです．これは分母にあるベクトル $\boldsymbol{w}$ について，その方向が重要なのであり，向きさえ同じであれば大きさが$1$の単位法線ベクトルとみなせることに起因します．
したがって，分離直線の最近傍サンプル$\boldsymbol{x}_s$について以下のようになります．
\frac{t_s(\boldsymbol{w}^T\boldsymbol{x}_s -h)}{\|\boldsymbol{w}\|} = \frac{1}{\|\boldsymbol{w}\|} =1 \tag{6}
制約条件
訓練サンプル集合は線形分離可能であると仮定しました．これは，以下の式が成り立つパラメータ$(\boldsymbol{w},h)$が存在することを意味します．
t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h)\geq 1, \quad (i=1,...,N) \tag{7}
$t_i$は各サンプルのクラスラベル($1$か$-1$)であり，${\boldsymbol w}^T {\boldsymbol x}_i-h$は各サンプルのクラスラベルと同符号の数値を返す関数でした．
識別に誤りがなければ符号が一致するため，$t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h) \geq 1$とするパラメータ$(\boldsymbol{w},h)$が必ず存在するのです．
２クラス分類におけるSVMでは，$(6)$式が満たさなければいけない制約条件として立ちはだかります．
目的関数
SVMにおける主問題は，マージン最大化の原理を使って分離直線と各クラスの最近傍サンプルとのマージを最大にするパラメータ$(\boldsymbol{w},h)$を探すことです．訓練サンプル $\boldsymbol{x}_i$ に対するマージンの大きさは，直線と点の距離の公式より以下のように求めることができました．
\begin{align}
m_i &= \frac{t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h)}{\|\boldsymbol{w}\|} \geq 1, \quad (i=1,...,N) \tag{8}
\end{align}
そして，マージン最大化を目指すのは各クラスの最近傍サンプルとのマージンでした．最近傍サンプル $\boldsymbol{x}_s$とのマージンは以下のようになります．
m_s = \frac{1}{\|\boldsymbol{w}\|} \tag{9}
このマージン $m_s$を最大化するということは，その逆数である以下の関数を最小化するという問題に置き換えることができます．
L = \|\boldsymbol{w}\| \tag{10}
$(8)$式は計算の都合上扱いづらいので，以下のように二次関数に置き換えます．
なぜ二次関数に置き換えることができるのか．それは$|\boldsymbol{w}|$がユークリッドノルムであり常に正の値をとることに起因します．係数$\frac{1}{2}$は，後々微分をすることになるので，その際に係数が1になるように調整しているだけです．
L = \frac{1}{2}\|\boldsymbol{w}\|^2 \tag{11}
SVMにおいては$(11)$式が目的関数となり，これを最小化するパラメータを求めることが主問題になります．
解法
ここまでで述べてきたSVMにおける制約条件と目的関数を主問題としてまとめると以下のようになります．
- 目的関数（最小化）: $L(\boldsymbol{w})=\frac{1}{2}|\boldsymbol{w}|^2$
- 不等式制約条件 : $t_i(\boldsymbol w^T\boldsymbol x_i -h) \geq \Rightarrow -\{t_i(\boldsymbol w^T\boldsymbol x_i-h)-1\}\leq0$
制約条件を考慮した関数の極値を求める問題はラグランジュの未定乗数法を使って解くことができます．（ラグランジュの未定乗数法について，簡単ではありますが記事の終わりの方に乗せているので参考にしてください．）
以下のような未知数 $\boldsymbol{\lambda}$ を導入します.
$$\boldsymbol{\lambda}=(\lambda_1,...,\lambda_N),\quad \lambda_i\geq0\quad(i=1,...,N)$$そして，$\boldsymbol{\lambda}$ を用いてSVMにおける主問題をラグランジュの未定乗数法に落とし込むと以下のようになります．
\tilde{L}(\boldsymbol{w},h,\lambda) = \frac{1}{2}\|\boldsymbol{w}\|^2-\sum_{i=1}^{n}\lambda_i(t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h)-1)
上式を$\boldsymbol{w}$と$h$について偏微分して$0$とおくと，
\frac{\partial{}}{\partial{\boldsymbol{w}}}L(\boldsymbol{w},h,\lambda)=\boldsymbol{w}-\sum_{i=1}^{n}\lambda_it_i\boldsymbol{x}_i=0 \Leftrightarrow \boldsymbol{w}=\sum_{i=1}^{n}\lambda_it_i\boldsymbol{x}_i
\\
\frac{\partial{}}{\partial{h}}L(\boldsymbol{w},h,\lambda)=-\sum_{i=1}^{n}\lambda_it_i=0 \Leftrightarrow \sum_{i=1}^{n}\lambda_it_i = 0
となります．
上の二つの式が，SVMにおける主問題をラグランジュの未定乗数法に落とし込んだときの新たな条件となります．
ここまでに登場した条件をすべてまとめてみましょう．
- $\frac{\partial{}}{\partial{\boldsymbol w}}L(\boldsymbol w,h,\lambda)=\boldsymbol w-\sum_{i=1}^{n}\lambda_it_i\boldsymbol x_i=0 \Leftrightarrow \boldsymbol{w}=\sum_{i=1}^{n}\lambda_it_i\boldsymbol x_i$
- $\frac{\partial{}}{\partial{h}}L(\boldsymbol{w},h,\lambda)=-\sum_{i=1}^{n}\lambda_it_i=0 \Leftrightarrow \sum_{i=1}^{n}\lambda_it_i = 0$
- $t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h)-1\geq0$
- $\lambda_i \geq 0$
- $\lambda_i{(t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h)-1)} = 0$
実は上記の5つの条件には名前があるらしく，KKT条件（Karush-Kuhn-Tucker）というそうです．このKKT条件が，SVMの主問題をラグランジュの未定乗数法に落とし込んだ時に満たさなければいけない条件です．
改めて，偏微分した値を$L(\boldsymbol{w},h,\lambda)$に代入して計算すると以下のようになります．
\begin{align}
L(\boldsymbol{w},h,\lambda) &= \frac{1}{2}\|\boldsymbol{w}\|^2-\sum_{i=1}^n\lambda_i\{t_i(\boldsymbol{w}^T\boldsymbol{x}_i-h)-1\}\\
&=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_i\lambda_jt_it_j\boldsymbol{x}_i^T\boldsymbol{x}_j-\sum_{i=1}^{n}\{\lambda_it_i(\boldsymbol{w}^T\boldsymbol{x}-h)-\lambda_i\}\\
&=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^{n}\lambda_i\lambda_jt_it_j\boldsymbol{x}_i^T\boldsymbol{x}_j-\sum_{i=1}^n\lambda_it_i\boldsymbol{w}^T\boldsymbol{x}_i+h\sum_{i=1}^n\lambda_it_i+\sum_{i=1}^n\lambda_i\\
&=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^{n}\lambda_i\lambda_jt_it_j\boldsymbol{x}_i^T\boldsymbol{x}_j-\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jt_it_j\boldsymbol{x}^T_i\boldsymbol{x}_j+h\sum_{i=1}^n\lambda_it_i+\sum_{i=1}^n\lambda_i\\
&=\sum_{i=1}^n\lambda_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jt_it_j\boldsymbol{x}_i^T\boldsymbol{x}_j
\end{align}
L(\lambda) = \sum_{i=1}^n\lambda_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jt_it_j\boldsymbol{x}_i^T\boldsymbol{x}_j
関数から$\boldsymbol{w}$と$h$が消え，$\lambda$の関数となりました．この関数に効いてくる条件はKKT条件における以下の二つです．
- $\frac{\partial{}}{\partial{h}}L(\boldsymbol{w},h,\lambda)=-\sum_{i=1}^{n}\lambda_it_i=0 \Leftrightarrow \sum_{i=1}^{n}\lambda_it_i = 0$
- $\lambda_i \geq 0$
SVMの主問題を，上記の二つの条件を考慮したうえで$L(\lambda)$を最大化する問題へと置き換えることができました．$(\boldsymbol{w},h)$の二つのパラメータを最適化する問題が，$\lambda$のみを最適化する問題へと置き換えることができたのです．
この$\lambda$に関する最適化問題は勾配法を使って解くことができます．勾配法を使って最適解$\lambda=\tilde{\lambda}$が得られたとします．すると，SVMにおける識別関数の最適なパラメータ$(\boldsymbol{w}=\tilde{\boldsymbol{w}},h=\tilde{h})$はKKT条件より以下のように求めることができます．
\tilde{\boldsymbol{w}} = \sum_{i=1}^n\tilde{\lambda_i}t_i\boldsymbol{x}_i \\
\tilde{h} = \sum^s\tilde{\boldsymbol{w}}\boldsymbol{x}_s-t_s
ここで，$x_s$はサポートベクトルと呼ばれるもので，私が何度か書いてきた「分離直線の最も近くに位置する各クラスのサンプル」にあたります．$t_s$はそのサンプルに対応するクラスラベルです．最適なパラメータの導出において，このサポートベクトルを用いることが，サポートベクターマシンと呼ばれる所以です．
ラグランジュの未定乗数法
ある関数 $f(x_1,x_2)$ を制約条件 $g(x_1,x_2)=0$ のもとで最大化もしくは最小化する$(x_1,x_2)$を求める際に使われるのがラグランジュの未定乗数法です．
関数が2変数関数の場合，新たな変数$\lambda$を導入して以下のような式を作ります．
L(x_1,x_2,\lambda) = f(x_1,x_2)-\lambda g(x_1,x_2)
このとき，$(x_1=\alpha,x_2=\beta)$が極値を与えるならば，$(\alpha,\beta)$は，以下の等式の解となります．
\frac{\partial{L}}{\partial{x_1}} = \frac{\partial{L}}{\partial{x_2}} = \frac{\partial{L}}{\partial{\lambda}} = 0
以上がラグランジュの未定乗数法による等式制約条件を考慮した極値の求め方です．
次に，制約条件が不等式 $g(x_1,x_2)\leq0$ の場合に $f(x_1,x_2)$ を最大化するケースについて（SVM等）．
もし $g(x_1,x_2)<0$ の範囲に $f(x_1,x_2)$ の最大値があれば，この制約条件は解に影響を与えない．これは，$(10)$式において$\lambda=0$となることを意味している．
もし $g(x_1,x_2)<0$ の範囲に解がないのなら，関数の凸条件により領域の境界 $g(x_1,x_2)=0$ 上に解が存在する．$g(x_1,x_2)=0$ 上に $f(x_1,x_2)$ が最大となる解があるということは，$(10)$式より，この点において$\nabla{g}$と$\nabla{f}$が平行であり，$\nabla{f}=\lambda\nabla{g}$ となる$\lambda$が存在することを意味します．
以上より，解が境界内にあれば $\lambda = 0$ ，境界上にあれば $g(x_1,x_2) = 0$ なので，いずれの場合にしても以下の等式が成り立つ．
\lambda g(x_1,x_2) = 0
これが，不等式制約条件を考慮したラグランジュの未定乗数法における条件となる．
おわりに
今回は分類手法として有名なSVMについて，ハードマージンSVMにおける分離直線の決定をメインに取り上げ，私の理解の過程を記事にさせていただきました．主問題を導いたあとも最適解を求めるためにラグランジュの未定乗数法を使ったり，新たな制約条件を考慮したりと忙しく，理解するまでにかなりエネルギーを使いました．
一般的にSVMといえばカーネルトリックSVMを思い浮かべる人が多いと思います．私は理論を順を追って理解するためにもハードマージンSVMから勉強しました．この記事がSVMについて知りたい人々にとって，少しでも役に立てば嬉しいなと思います．
呼んでいただいた皆様，ありがとうございます！
参考資料
サポートベクターマシン入門. 栗田 多喜夫.
https://home.hiroshima-u.ac.jp/tkurita/lecture/svm.pdf
パターン認識と機械学習 下. C.M.ビショップ
第4回 線形SVM · levelfour/machine-learning-2014 Wiki.
https://github.com/levelfour/machine-learning-2014/wiki/%E7%AC%AC4%E5%9B%9E---%E7%B7%9A%E5%BD%A2SVM
SVMについて.
https://www.slideshare.net/mknh1122/svm-13623887
初心者向け】KKT条件を使ってSVMの計画問題を解く - バナナでもわかる話. https://www.bananarian.net/entry/2018/09/03/003013
線形SVMの理論と実装.
https://satopirka.com/2018/12/theory-and-implementation-of-linear-support-vector-machine/