はじめに
深層学習が強すぎる現在においても，まだまだ使用されている「SVM」の理論についてまとめました．わかりやすい記事は多くあると思いますが，勉強した理解度を確かめるための忘備録として書いています．「理解してる人からすると当たり前だけど，はじめは躓きやすい」みたいな部分をある程度まで掘り下げる記事を目標にしています．
嘘があればご教授お願い致します．
目次
- ハードマージン
- ソフトマージン
- ラグランジュの未定乗数法とKKT条件による双対表現
- カーネルトリック
- 最適化方法
- 他クラス分類に向けて
ハードマージン
まず，はじめは一番簡単な問題として．完全に線形分離可能な状況を考えてみます．二次元空間においては直線，三次元空間においては平面，それ以上の次元においては超平面といわれるやつで分離できるということです．
大前提として，SVMでは２クラスを分ける境界を決定するとき，その境界から最も近いデータ（サポートベクトル）ができるだけ遠くなるように決定します．
そこで，境界からの距離を測る指標として，高校で習う「点と直線の距離」の考え方を活用します．（実際は，これを拡張した「点と超平面の距離」です）
境界面は，\boldsymbol{w} と b を用いて，\boldsymbol{w}^T \boldsymbol{x} + b = 0 と書くことができます．
具体的には，2次元であれば w_1 x + w_2 y + b = (w_1, w_2) (x, y)^T + bなので，\boldsymbol{w} = (w_1, w_2)^Tにあたります．
n 次元の点と超平面の距離は，以下の式で表されます．
d =\frac{|\boldsymbol{w}^T \boldsymbol{x} + b|}{||\boldsymbol{w}||} = \frac{ |w_1 x_1 + w_2 x_2 + \cdots + w_n x_n + b| }{\sqrt{w_1^2 + w_2^2 + \cdots + w_n^2}}
いよいよ定式化です．式の書き方は記事によって様々ですが，言いたいことは一緒です．
\max_{\boldsymbol{w}, b} d \;\; \mathrm{subject\;to\;} \frac{|\boldsymbol{w}^T \boldsymbol{x_i} + b|}{||\boldsymbol{w}||} \geq d \;\; (i=1, 2, ..., n) \tag{1}
この式が言っているのは，「すべてのデータ点における境界面からの距離 d を変数 \boldsymbol{w}, b のもとで最大化する」ということです．
つづいて，この式を書き換えます．
以下の手順で，条件式を扱いやすい形にしていきます．
- 絶対値の処理
- 距離の基準を変更
- 最大化問題から最小化問題へ変更
まず１です．式(1)のままでは非常に扱いにくいので，ラベル情報を使用して絶対値を外します．具体的には，||内が正となる領域は1，負になる領域は-1のラベルを定義する（これを t_i で表す）ことで以下のように書き換えられます．
\frac{t_i (\boldsymbol{w}^T \boldsymbol{x_i} + b)}{||\boldsymbol{w}||} \geq d \;\; (i=1, 2, ..., n)
づづいて，距離をスケーリングします．
\begin{align*}
\frac{t_i (\boldsymbol{w}^T \boldsymbol{x_i} + b)}{||\boldsymbol{w}||} &= \frac{t_i (\boldsymbol{w}^T \boldsymbol{x_i} + b)}{ d||\boldsymbol{w}||} \\
&= t_i (\frac{\boldsymbol{w}^T}{d||\boldsymbol{w}||} \boldsymbol{x_i} + \frac{b}{d||\boldsymbol{w}||}) \\
&= t_i (\boldsymbol{\tilde{w}}^T \boldsymbol{x_i} + \tilde{b}) \geq 1
\end{align*}
なぜ，こんな変形をするのか疑問に思われる方が多いと思いますが，目的関数をより簡単に書き換えるためです．境界面からの距離をｄ以上から１以上とし直した部分を意識しておいて下さい．新たにスケーリングした変数 \boldsymbol{\tilde{w}}, \tilde{b} を用いて，目的関数を以下のように書き換えられます．
\max \frac{1}{||\boldsymbol{\tilde{w}}||} \;\;
\mathrm{subject \; to \;}
t_i (\boldsymbol{\tilde{w}}^T \boldsymbol{x_i} + \tilde{b}) \geq 1
\; (i=1, 2, ..., n) \tag{2}
もともとの式(1)にてすべての点について考えている部分を，境界面からもっとも近いデータ点について考え直している部分がミソです．この点（サポートベクトル）を正・負それぞれの領域ごとに \boldsymbol{x^+}, \boldsymbol{x^-} とすると
\max_{w. b} d = \frac{\boldsymbol{w}^T \boldsymbol{x^+} + b}{||\boldsymbol{w}||}
= \frac{- \boldsymbol{w}^T \boldsymbol{x^-} + b}{||\boldsymbol{w}||}
と表されますが，これを以下のようにできるということです．
\max_{\tilde{w}. \tilde{b}} d = \frac{\boldsymbol{\tilde{w}}^T \boldsymbol{x^+} + \tilde{b}}{||\boldsymbol{\tilde{w}}||}
= \frac{- \boldsymbol{\tilde{w}}^T \boldsymbol{x^-} + \tilde{b}}{||\boldsymbol{\tilde{w}}||}
= \frac{1}{||\boldsymbol{\tilde{w}}||}
サポートベクトルの境界面からの距離を１にしたことがいきてますね．
最後に，最大化問題を最小化問題に書き換えます．これものちの計算の都合をよくするためです．
\min_{\boldsymbol{\tilde{w}}, \tilde{b}} \frac{1}{2} ||\boldsymbol{\tilde{w}}||^2 \;\; \mathrm{subject\; to\;} t_i(\boldsymbol{\tilde{w}}^T \boldsymbol{x_i} + \tilde{b}) \geq 1 \;\; (i=1,2, ..., n) \tag{3}
以降では，正規化した変数である \boldsymbol{\tilde{w}}, \tilde{b} をそれぞれ \boldsymbol{w}, b で表記しますのでご注意ください．
ソフトマージンの導入
今までは，完全に２クラス分類可能な問題を考えてきましたが，これは制約が強すぎるので一般には使用されません．そこで，0以上の値を取るスラッグ変数 \xi_i というものを導入することで制約を緩和します．
具体的には，制約条件を以下のように書き換えます．
t_i(\boldsymbol{w}^T \boldsymbol{x_i} + b) \geq 1 - \xi_i \\
\xi_i = \max{(0, d_{sv} - \frac{t_i(\boldsymbol{w}^T \boldsymbol{x_i} + b)}{||\boldsymbol{w}||})}
先ほどのハードマージンの議論を思い起こすと，サポートベクトルの距離が１になるように \boldsymbol{w} と b を正規化したので境界面からサポートベクトルまでの距離は，d_{sv} = 1 です．つまり，d > 1 （サポートベクトルより境界面から遠い）ならばmax関数は第一引数を採用し，逆に d < 1（サポートベクトルより境界面に近い，もしくは反対側にある）ならば，max関数は第二引数を採用します．
まとめると，サポートベクトルよりも境界面に近かったり，反対の領域側にデータがある場合，\xi_i の値が大きくなり，制約が弱まるというわけです．
ここで気になるのが，\xi_i をどの程度まで許容するか（制約条件をどこまで弱めていいか）です．これは目的関数の方でバランスを取る必要があります．
そこで，目的関数を以下のように書き換えます．
\min {\frac{1}{2} ||\boldsymbol{w}||^2 + C\sum_{i=1}^{n} \xi_i} \tag{4}
C は制約をどの程度弱めてよいかのハイパーパラメータで，うまく設定する必要があります．
ラグランジュの未定乗数法とKKT条件による双対表現
ラグランジュの未定乗数法は「（等式）制約付き極値問題」を解くための手段で，例えば次のような問題を解くときに使用できます．
f(x,y) = 5x + y の最大値を x^2 + y^2 -1 = 0 のもとで求めよ．
ラグランジュの未定乗数法を用いることで，極値の解候補が求まります（解だけがでてくるわけではない点に注意）．ラグランジュ関数は図形的にイメージすることで条件を導き出せるので覚える必要はありませんが，詳細については触れません．やまたくさんの動画やヨビノリさんの動画を参照するとわかりやすいと思います．
お気づきの方もいらっしゃると思いますが，不等式制約のもとで解けなければ今回の問題には使えないので，不等式制約まで拡張します．この条件を導き出した数学者たちにちなんでKKT条件なんて呼ばれたりします．
ちなみに，KKT条件の導出も理解することで導き出せます．ヨビノリさんのまとめ動画がわかりやすいです．
さっそく定式化します．
まず，不等式制約をもつラグランジュ関数 Lを以下のように定めます．
L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) + \sum_{i=1}^{n} \lambda_i g_i(\boldsymbol{x}) \\
ただし，
\boldsymbol{\lambda} = (\lambda_1, \lambda_2, ..., \lambda_n)^T,
\;\; g_i(\boldsymbol{x}) \geq 0
です．すると，KKT条件は以下のようになります．
- \nabla f(\boldsymbol{x}) = - \lambda_i \nabla g_i(\boldsymbol{x})
- \lambda_i \geq 0
- g(\boldsymbol{x_i}) \geq 0
- \lambda_i g(\boldsymbol{x_i}) = 0
これを今回のSVMに当てはめると，最適化式は，
L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\beta}) = \frac{1}{2} ||\boldsymbol{w}||^2 + C\sum_{i=1}^{n} \xi_i - \sum_{i=1}^{n} \alpha_i \{t_i(\boldsymbol{w}^T \boldsymbol{x_i} + b) - 1 + \xi_i \} - \sum_{i=1}^{n} \beta_i \xi_i
となり，KKT条件として以下を得ます．
- 変数に関する偏微分
- \boldsymbol{w} = \sum_{i=1}^{n} \alpha_i t_i \boldsymbol{x_i}
- \sum_{i=1}^{n} \alpha_i t_i = 0
- C - \alpha_i -\beta_i = 0
- ラグランジュ乗数に対する制約
- \alpha_i \geq 0, \beta_i \geq 0
- 不等式制約
- t_i(\boldsymbol{w}^T \boldsymbol{x_i} + b) - 1 + \xi_i \geq 0
- \xi_i \geq 0
- 解の存在領域に関する条件
- \alpha_i \{t_i(\boldsymbol{w}^T \boldsymbol{x_i} + b) - 1 + \xi_i \} = 0
- \beta_i \xi_i = 0
さて，ここからが正念場です．このKKT条件をラグランジュ関数に代入することで，\alpha だけで表される双対関数を得ることができます．
特に今回の問題は，「強双対性」が成り立つため，最初に定義した最小化問題（主問題）の代わりに，これから定義する最大化問題（双対問題）を解くことで主問題の最適解が得られます．
KKT条件の「変数に関する偏微分」から得られた３式をラグランジュ関数に代入し，以下のラグランジュ双対関数を得ます．
\begin{align*}
L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\beta}) &= - \frac{1}{2} ||\sum_{i=1}^{n} \alpha_i t_i \boldsymbol{x_i}||^2 + (\alpha_i + \beta_i) \sum_{i=1}^{n} \xi_i - \sum_{i=1}^{n} \alpha_i \{- 1 + \xi_i \} - \sum_{i=1}^{n} \beta_i \xi_i \\
&= -\frac{1}{2} ||\sum_{i=1}^{n} \alpha_i t_i \boldsymbol{x_i}||^2 + \sum_{i=1}^{n} \alpha_i \\
&= -\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j t_i t_j \boldsymbol{x_i}^T \boldsymbol{x_j} + \sum_{i=1}^{n} \alpha_i \\
\end{align*}
制約条件は，0 \leq \alpha_i と \beta_i = C - \alpha_i \geq 0 より，0 \leq \alpha_i \leq C となり，まとめると，次のようになります．（双対問題なので，最大化になっている点に注意）
\max \tilde{L}(\boldsymbol{\alpha}) = - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j t_i t_j \boldsymbol{x_i}^T \boldsymbol{x_j} + \sum_{i=1}^{n} \alpha_i
\\
\mathrm{subject\; to\;} \; 0 \leq \alpha_i \leq C, \;\sum_{i=1}^{n} \alpha_i t_i = 0
カーネルトリック
これまでは，多少の不純物やノイズが混ざることはあっても基本的に線形分離可能な状況しか考えていません．しかし，円の内側と外側に別々のラベルのデータが存在しているような場合はどのようにすればよいでしょうか．
答えはシンプルで，
「できるだけ線形分離できそうな高次元空間にとばしてそこで分離した結果を元に戻す」
です．
一般に，高次元空間にとばすほど線形分離可能な状態に近づいていくことがしられています．例えば，線形分離可能な空間に写像する関数\boldsymbol{\phi} を以下のように定めてみます．
\boldsymbol{\phi (\boldsymbol{x})} = (\phi_1(\boldsymbol{x}), \phi_2(\boldsymbol{x}), ..., \phi_n (\boldsymbol{x}))
\boldsymbol{x} はベクトルで，入力する特徴量です（三次元なら\boldsymbol{x}^T = (x_1, x_2, x_3)）
\phi_i (i=1, 2,..., n) はそれぞれ別の関数です．
もし，関数 \boldsymbol{\phi} を使って，線形分離可能な空間にうつったと仮定すると今までの理論が使えます．
したがって，この仮定のもとでの最適化式は以下のようになります．
\max \tilde{L}(\boldsymbol{\alpha}) = - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j t_i t_j \boldsymbol{\phi}(\boldsymbol{x_i})^T \boldsymbol{\phi}(\boldsymbol{x_j}) + \sum_{i=1}^{n} \alpha_i \tag{5}
\\
\mathrm{subject\; to\;} \; 0 \leq \alpha_i \leq C, \;\sum_{i=1}^{n} \alpha_i t_i = 0
\phiが加わっただけですね．しかし，この部分が牙をむいてきます．結論からいうと計算量が増加してしまい，計算が困難となります．
具体的に見ていきます．まず計算量は，式(5)を見ると（データ数）^2 \times（特徴量）が律速です．ここで（特徴量）の数が重要です．高次元空間に写像するときに，２次元から１０次元に拡張するだけで5倍時間がかかり，100次元だと50倍算出に時間がかかるということです．結構やばそうですね．
そこでこの部分の計算を早くする工夫として，「カーネルトリック」があります．
具体的には，式(5)では高次元空間データの内積しか用いていないことを利用します．ある特定の条件を満たす関数（カーネル関数）はこの内積を高速に計算できます．
よく使用されるカーネル関数は以下の通りです：
- 多項式カーネル K(\boldsymbol{x_i}, \boldsymbol{x_j}) = (\boldsymbol{x_i}^T\boldsymbol{x_j} + c)^d
- ガウスカーネル(RBFカーネル) K(\boldsymbol{x_i}, \boldsymbol{x_j}) = \exp{(- \frac{||\boldsymbol{x_i}-\boldsymbol{x_j}||^2}{2\sigma^2})}
- シグモイドカーネル K(\boldsymbol{x_i}, \boldsymbol{x_j}) = \tanh (b\boldsymbol{x_i}^T \boldsymbol{x_j} + c)
なぜ早くなるのかを具体例で見てみましょう．
例えば，多項式カーネルにて c = 1, d = 2，元の特徴量は2次元だとすると，
\begin{align*}
K(\boldsymbol{x_i}, \boldsymbol{x_j}) &= (\boldsymbol{x_i}^T\boldsymbol{x_j} + 1)^2 \\
&= (\boldsymbol{x_i}^T\boldsymbol{x_j})^2 + 2(\boldsymbol{x_i}^T\boldsymbol{x_j}) + 1 \\
&= (x_{i1}x_{j1})^2 + 2x_{i1}x_{i2}x_{j1}x_{j2} + (x_{i2}x_{j2})^2 + 2x_{i1}x_{j1} + 2x_{i2}x_{j2} + 1 \\
&= (x_{i1}^2, \sqrt{2}x_{i1}x_{i2}, x_{i2}^2, \sqrt{2}x_{i1}, \sqrt{2}x_{i2}, 1)^T (x_{j1}^2, \sqrt{2}x_{j1}x_{j2}, x_{j2}^2, \sqrt{2}x_{j1}, \sqrt{2}x_{j2}, 1) \\
\end{align*}
となります．気づきましたか？
一番下の式を直接計算することが本来の内積計算（５回ループ）に当たります．一方で，一番上の式は括弧の中身をそのまま計算し，d 乗するだけなので元の空間の次元分の内積計算（２回ループ）で済みます．革命ですね．（高校数学における約数の総和を求める問題にも似ていますね．）
しかし，デメリットとして，写像する空間は任意に定められるわけではなく，ある特徴のある空間へ飛ばされています．ここまで便利なので好きな空間に飛びたいというのは，二兎追うものはなんとやらってことです．（たぶん）
最適化方法
概要だけパッと紹介します．
手順としては，以下の通りです：
- 双対問題を解く（\boldsymbol{\alpha}を求める）
- 決定境界を求める
- サポートベクトル（と超平面の内側にある点）を求める
-
\boldsymbol{w}, b を算出する
1. 双対問題を解く
有名なLIBSVMなどでは，SMO(Sequentially minimal optimization)が採用されている．アルゴリズムはシンプルで，
2つの \alpha_i, \alpha_j を選択 \rightarrow 他の変数を固定して2変数問題を解く \rightarrow 最適解 or 既定回数以上でstop
(２変数である理由は，双対問題の制約条件である t_i^T\alpha_i = 0を守れる最低限の数だから)
です．変数選択や最適解の判定に関してはこちらの方の記事を参照してください．
また，より単純な考え方として勾配降下法を使用できます．ここでは最大化問題なので，勾配ベクトルの方向に \boldsymbol{\alpha} を以下のように更新すればいいです．
\alpha_i \leftarrow \alpha_i + \eta \frac{\partial L(\boldsymbol{\alpha})}{\partial \alpha_i}
2. 決定境界を求める
全てのデータ点を使用する必要がないので，先にサポートベクトルとサポートベクトルより内側のデータ点を求めておきます．（ここは少々場合分け等が伴うので詳しい説明は省略しますが，この記事を参照するとわかりやすいです．）
続いて，\boldsymbol{w} と b を求めて終わりです．
\boldsymbol{w} はKKT条件の制約から，b は全サポートベクトルで求めた値を平均することで算出できます．
多クラス分類に向けて
詳しくは触れませんが，一般に以下の二つが主流っぽいです．
- one vs one（n クラスから2つ選択し，n(n-1)/2 個の2クラス分類器を使用）
- one vs rest（1 vs (n-1) クラスのどれかの n 個の2クラス分類器を使用）
いずれも簡単で精度のよい手法のようですが，以下の図のように未決定の領域が発生する可能性があります．
Utku's Blogより引用
他にもアルゴリズム自体にsoftmax等をかますことで，そのまま多次元へ拡張する方法もあるようです．興味がある方は調べてみてください．
おわりに
思った以上に長くなってしまいましたが，一旦忘れない程度に理解できた気がします．実際は，各言語の主要ライブラリに必要な機能が入っていると思うので，自分で実装する必要性はありませんが，それぞれのハイパーパラメータの役割や挙動を理解しているとそうでないのとでは，得られた結果に対する考察が雲泥の差だと思ったりしてます．色々と数学的な工夫が詰まっているのでまた，忘れたころに見直す予定です．
参考
Discussion