サポートベクターマシンの考え方

参考にしたもの：機械学習のエッセンスの第05章「機械学習アルゴリズム」
回帰、ロジスティック回帰分析は別ページ

サポートベクターマシンとは

2つのデータ群を分ける境界を引く方法。境界の形は直線・平面・超平面や曲線・曲面・超曲面
略称SVM (Support Vector Machine)

分け方(=境界の作り方)

直線・平面・超平面(完全に分離できる場合)(=このページ)
直線・平面・超平面(完全に分離できない場合)
曲線・曲面・超曲面

特徴、考え方

基本の考え方:「境界から一番近くなる点」との距離が最大になるように、境界を作る

↓の例だと、点線でも境界にはなるが、ギリギリを攻めすぎているため「新しく点が増えたとき、どちらになるか？」という判別が不正確になる。
SVMでは、実線のように両方の点群のちょうど間を通るように境界を作る。
↓では「境界(実線)から一番近い点」に丸がついており、コレをサポートベクタと呼ぶ。サポートベクタによって境界が決まる。

**考え方はココまでで終わり。**コレ以降は数学・数値計算問題としての解き方。

図作ったときのコード置き場

https://github.com/kzy611/qiita/blob/master/LinearSVM_hard.ipynb

解き方

n個の点(↑の赤、青)に$i(=1, 2, \cdots, n)$と番号をつける。それぞれの点の位置は$\mathbf{x_i}=(x_1, x_2, \cdots, x_d)_i$と表す。
境界線を$w_0+\mathbf{w}\mathbf{x}=0$と置く。$\mathbf{w}=(w_1, w_2, \cdots, w_d)$
1. $w_0$と$\mathbf{w}$で境界の形が決まる。
2. ある点iがどちらのグループになるかは、$w_0+\mathbf{w}\mathbf{x_i}$の符号(±)によって判別される
全部の点に$y_i=1,-1$を設定する。「$w_0+\mathbf{w}\mathbf{x_i}>0$になる点は$y_i=1$」「$w_0+\mathbf{w}\mathbf{x_i}<0$になる点は$y_i=-1$」とする。(=↑で同じ色は$y_i$が同じになる)
点i ($\mathbf{x_i}$)の、直線$w_0+\mathbf{w}\mathbf{x}=0$からの距離を$l_i$とすると、↓のように表される
$$
l_i = \frac{|w_0+\mathbf{w}\mathbf{x_i}|}{|\mathbf{w}|} = \frac{y_i(w_0+\mathbf{w}\mathbf{x_i})}{|\mathbf{w}|}
$$

1つ目の式は、「点と直線の距離公式をベクトルを使って導く」を参照
2つ目の式は、↑3での$y_i$の設定の仕方より、こう書くと絶対値と同じ(必ず+)になる

全て(n個)の点で最小の$l_i$を以下のように表すと、↓が最大(=「境界から一番近くなる点」との距離が最大)となるような$w_0, \mathbf{w}$を設定したい
$$
min_i(l_i) = min_i(\frac{y_i(w_0+\mathbf{w}\mathbf{x_i})}{|\mathbf{w}|}) = \frac{1}{|\mathbf{w}|}min_i(y_i(w_0+\mathbf{w}\mathbf{x_i}))
$$
ココで、$min_i(y_i(w_0+\mathbf{w}\mathbf{x_i}))=m$とすると、$w_0, \mathbf{w}$を両方$1/m$倍すると$min_i(y_i(w_0+\mathbf{w}\mathbf{x_i}))=1$と変形できる。(この操作は、$w_0+\mathbf{w}\mathbf{x}=0$にも$min_i(l_i)$にも影響を与えない)
よって、5は「↓を最大にする$w_0, \mathbf{w}$を求める」という問題とできる
$$
\frac{1}{|\mathbf{w}|}
$$
また、計算しやすくするため変形(逆数をとり、二乗し、$1/2$をかける)すると、「↓を最小にする$w_0, \mathbf{w}$を求める」という最適化問題となる
$$
\frac{1}{2}|\mathbf{w}|^2
$$

6で$min_i(y_i(w_0+\mathbf{w}\mathbf{x_i}))=1$としたことにより、拘束条件は全てのiで↓となる
境界から一番近くなる点(=サポートベクタ)で等号が成り立つ

$$
y_i(w_0+\mathbf{w}\mathbf{x_i})\geq1
$$

w0, wの求め方

↑より、↓を満たす$w_0, \mathbf{w}$を求める。

\begin{align}
Minimize \; &\frac{1}{2}|\mathbf{w}|^2 \\
Subject \; to \; &y_i(w_0+\mathbf{w}\mathbf{x_i})\geq1 \; (i=1, 2, \cdots, n) \\
&\Leftrightarrow -\bigl(y_i(w_0+\mathbf{w}\mathbf{x_i})-1\bigr) \leq 0
\end{align}

コレをラグランジュの未定乗数法(Wikipedia)、カルーシュ・クーン・タッカー条件(Wikipedia)で解く。
制約式がn個なので、$\mathbf{a}=(a_1, a_2, \cdots, a_n)$を導入すると、ラグランジュ関数は

L(w_0, \mathbf{w}, \mathbf{a}) = \frac{1}{2}|\mathbf{w}|^2 - \sum_{i=1}^{n} a_i \bigl(y_i(w_0+\mathbf{w}\mathbf{x_i})-1 \bigr) \; ・・・(i)

と表され、↓を満たす$w_0, \mathbf{w}, \mathbf{a}$を求めれば良い。

\begin{align}
\frac{\partial L}{\partial w_0} &= 0 \; ・・・(ii)\\
\frac{\partial L}{\partial w_j} &= 0 \; ・・・(iii)\\
\end{align}

\begin{align}
a_i &\geq 0  \; ・・・(iv)\\
y_i(w_0+\mathbf{w}\mathbf{x_i})-1 &\geq 0  \; ・・・(v)\\
a_i \bigl(y_i(w_0+\mathbf{w}\mathbf{x_i})-1 \bigr) &= 0  \; ・・・(vi)\\
\end{align}

$(ii), (iii)$より

\begin{align}
\frac{\partial L}{\partial w_0} = - \sum_{i=1}^{n} a_i y_i &= 0 \\
\Leftrightarrow \sum_{i=1}^{n} a_i y_i &= 0 \; ・・・(ii)'\\
\end{align}

\begin{align}
\frac{\partial L}{\partial w_j} &= w_j - \sum_{i=1}^{n} a_i y_i x_{ij} = 0 \\
\Leftrightarrow w_j &= \sum_{i=1}^{n} a_i y_i x_{ij} \; ・・・(iii)'\\
\end{align}

ここで$x_{ij}$は、$\mathbf{x_i}=(x_1, x_2, \cdots, x_j, \cdots, x_n)_i$の$x_j$
$(ii)', (iii)'$を$(i)$に代入すると

L(w_0, \mathbf{w}, \mathbf{a}) = \sum_{k=1}^{n} a_k - \frac{1}{2} \sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l}\; ・・・(i)'

となり$w_0, \mathbf{w}$が消えるため、「$w_0, \mathbf{w}, \mathbf{a}$についての最適化」から「$\mathbf{a}$についての最適化(二次計画法(Wikipedia))」となる。
$\mathbf{a}$を求めたら、

w_j = \sum_{i=1}^{n} a_i y_i x_{ij} \; ・・・(iii)'\\

より$\mathbf{w}$を求め、$(vi)$より$a_i \neq 0$となる$i$で

\begin{align}
y_i(w_0+\mathbf{w}\mathbf{x_i})-1 &= 0 \; ・・・(vi)'\\
w_0 &= y_i - \mathbf{w}\mathbf{x_i}
\end{align}

を使って$w_0$を求めればよい。(式変形には${y_1}^2 = 1$を利用した)

aの求め方

↑より$L(w_0, \mathbf{w}, \mathbf{a}) = f(\mathbf{a})$とおくと、↓を満たす$\mathbf{a}$を求める。

\begin{align}
Minimize \; &f(\mathbf{a}) = \sum_{k=1}^{n} a_k - \frac{1}{2} \sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l}\; ・・・(i)' \\
Subject \; to \; &\sum_{i=1}^{n} a_i y_i = 0 \; ・・・(ii)'\\
&a_i \geq 0  \; ・・・(iv)\\
&a_i \bigl(y_i(w_0+\mathbf{w}\mathbf{x_i})-1 \bigr) = 0  \; ・・・(vi)\\
\end{align}

ほとんどの$a_i$は0となるので、プログラムで解く際は「汎用の2次計画問題ソルバ」で解くよりも、「Platによるアルゴリズム」で解くのが効率が良い。(機械学習のエッセンスより)
↓の例だと、丸がついている2点(サポートベクタ)以外は$y_i(w_0+\mathbf{w}\mathbf{x_i})-1 \neq 0$なので、$(vi)$より$a_i=0$となる

Platによるアルゴリズム

最初に初期値$\mathbf{a^0}$を設定する。今回は$\mathbf{a^0}=(0, 0, \cdots, 0)$
n個の点から、適当な$i, j$を選ぶ。(選び方は後述)
$Minimize ; f(\mathbf{a})$となるよう$a_i, a_j$だけ変更する。
収束条件を満たすまで、2, 3を繰り返す。(収束条件は後述)

↑の3.「a_i, a_jだけ変更」について

f(\mathbf{a}) = \sum_{k=1}^{n} a_k - \frac{1}{2} \sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l}\; ・・・(i)' \\

で、$\sum$から$k, l=i, j$の部分だけ取り出す。まず、$(i)'$第二項の$\sum \sum$部分だけ考えると

\begin{align}
&\sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
= &(\sum_{k=1}^{n} a_k y_k \mathbf{x_k}) (\sum_{l=1}^{n} a_l y_l \mathbf{x_l}) \\
= &(a_i y_i \mathbf{x_i} + a_j y_j \mathbf{x_j} + \sum_{k \neq i,j} a_k y_k \mathbf{x_k}) (a_i y_i \mathbf{x_i} + a_j y_j \mathbf{x_j} + \sum_{l \neq i,j} a_l y_l \mathbf{x_l}) \\
= &a_i^2 y_i^2 \mathbf{x_i} \mathbf{x_i} + a_j^2 y_j^2 \mathbf{x_j} \mathbf{x_j} + 2 a_i a_j y_i y_j \mathbf{x_i} \mathbf{x_j} \\
&+ \sum_{k \neq i,j} a_i a_k y_i y_k \mathbf{x_i} \mathbf{x_k} + \sum_{l \neq i,j} a_i a_l y_i y_l \mathbf{x_i} \mathbf{x_l} \\
&+ \sum_{k \neq i,j} a_j a_k y_j y_k \mathbf{x_j} \mathbf{x_k} + \sum_{l \neq i,j} a_j a_l y_j y_l \mathbf{x_j} \mathbf{x_l} \\
&+ \sum_{k \neq i,j} \sum_{l \neq i,j} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
\end{align}

ここで、↓を適用すると

$y_{i, j} = 1, -1$より、$y_i^2 =1$、$y_j^2 =1$
2行目(第4, 5項)、3行目(第6, 7項)は$k, l$で$\sum$が独立しているため、$\sum_{l \neq i,j}$を$\sum_{k \neq i,j}$とすると、それぞれまとめられる

\begin{align}
&\sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
= &a_i^2 \mathbf{x_i} \mathbf{x_i} + a_j^2 \mathbf{x_j} \mathbf{x_j} + 2 a_i a_j y_i y_j \mathbf{x_i} \mathbf{x_j} \\
&+ 2 \sum_{k \neq i,j} a_i a_k y_i y_k \mathbf{x_i} \mathbf{x_k} \\
&+ 2 \sum_{k \neq i,j} a_j a_k y_j y_k \mathbf{x_j} \mathbf{x_k} \\
&+ \sum_{k \neq i,j} \sum_{l \neq i,j} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
\end{align}

となる。コレを$(i)'$に代入すると

\begin{align}
f(\mathbf{a}) = &\sum_{k=1}^{n} a_k - \frac{1}{2} \sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
= &(a_i + a_j + \sum_{k \neq i, j} a_k) - \frac{1}{2} \sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
= &- \frac{1}{2} a_i^2 \mathbf{x_i} \mathbf{x_i} - \frac{1}{2} a_j^2 \mathbf{x_j} \mathbf{x_j} - a_i a_j y_i y_j \mathbf{x_i} \mathbf{x_j} \\
&+ a_i (1 - y_i \mathbf{x_i} \sum_{k \neq i,j} a_k y_k \mathbf{x_k}) \\
&+ a_j (1 - y_j \mathbf{x_j} \sum_{k \neq i,j} a_k y_k \mathbf{x_k}) \\
&+ \sum_{k \neq i, j} a_k - \frac{1}{2} \sum_{k \neq i,j} \sum_{l \neq i,j} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
\end{align}

となる、ここで

\begin{align}
A &= - \frac{1}{2} \mathbf{x_i} \mathbf{x_i} \\
B &= - \frac{1}{2} \mathbf{x_j} \mathbf{x_j} \\
C &= - y_i y_j \mathbf{x_i} \mathbf{x_j} \\
D &= 1 - y_i \mathbf{x_i} \sum_{k \neq i,j} a_k y_k \mathbf{x_k} \\
E &= 1 - y_j \mathbf{x_j} \sum_{k \neq i,j} a_k y_k \mathbf{x_k}\\
F &= \sum_{k \neq i, j} a_k - \frac{1}{2} \sum_{k \neq i,j} \sum_{l \neq i,j} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l} \\
\end{align}

とおくと、

f(\mathbf{a}) = A a_i^2 + B a_j^2  + C a_i a_j + D a_i + E a_j + F \; ・・・(i)'' \\

と表せる。
また、拘束条件$(ii)'$で$\sum$のiをkに変更し、i,jを取り出すと

\begin{align}
& a_i y_i + a_j y_j + \sum_{k \neq i, j}^{n} a_k y_k = 0 \\
\Leftrightarrow & a_j = \frac {1}{y_j} (- a_i y_i - \sum_{k \neq i, j}^{n} a_k y_k) \\
\end{align}

となり「$y_j^2 = 1$より$\frac {1}{y_j} = y_j$」と「$G = \sum_{k \neq i, j}^{n} a_k y_k$」とおくと

\begin{align}
a_j =& y_j (- a_i y_i - \sum_{k \neq i, j}^{n} a_k y_k) \; ・・・(ii)'' \\
=& y_j (- a_i y_i - G) \\
\end{align}

となる。コレを$(i)''$に代入すると

\begin{align}
f(\mathbf{a}) = &A a_i^2 + B (y_j (- a_i y_i - G))^2 \\
&+ C a_i y_j (- a_i y_i - G) + D a_i \\
&+ E y_j (- a_i y_i - G) + F \\
= & a_i^2 (A + B y_j^2 y_i^2 - C y_j y_i) \\
&+ a_i \bigl(B y_j^2 (2 y_i G) - C y_j G + D - E y_j y_i \bigr) \\
&+ Const \\
= & a_i^2 (A + B - y_i y_j C) \\
&+ a_i (2 y_i B G - y_j C G + D - y_i y_j E) \\
&+ Const
\end{align}

$a_i$の二次関数と考えると、頂点となる$a_i$は(このへん参照)

a_ i = - \frac {2 y_i B G - y_j C G + D - y_i y_j E}{2 (A + B - y_i y_j C)}

分子、分母をそれぞれ計算すると

\begin{align}
2 y_i B G - y_j C G + D - y_i y_j E = & 2 y_i (- \frac{1}{2} \mathbf{x_j} \mathbf{x_j}) G - y_j (- y_i y_j \mathbf{x_i} \mathbf{x_j}) G \\
& + (1 - y_i \mathbf{x_i} \sum_{k \neq i,j} a_k y_k \mathbf{x_k}) - y_i y_j (1 - y_j \mathbf{x_j} \sum_{k \neq i,j} a_k y_k \mathbf{x_k}) \\
= & 1 - y_i y_j + y_i (\mathbf{x_i} - \mathbf{x_j}) (\mathbf{x_j} G - \sum_{k \neq i,j} a_k y_k \mathbf{x_k}) \\
= & 1 - y_i y_j + y_i (\mathbf{x_i} - \mathbf{x_j}) (\mathbf{x_j} \sum_{k \neq i, j}^{n} a_k y_k - \sum_{k \neq i,j} a_k y_k \mathbf{x_k})
\end{align}

\begin{align}
2 (A + B - y_i y_j C) = & 2 \bigl(- \frac{1}{2} \mathbf{x_i} \mathbf{x_i} - \frac{1}{2} \mathbf{x_j} \mathbf{x_j} - y_i y_j (- y_i y_j \mathbf{x_i} \mathbf{x_j}) \bigr) \\
= & - \mathbf{x_i} \mathbf{x_i} - \mathbf{x_j} \mathbf{x_j} + 2 \mathbf{x_i} \mathbf{x_j} \\
= & -|\mathbf{x_i} - \mathbf{x_i}|^2
\end{align}

よって、$f(\mathbf{a})$が頂点をとる$a_i$は

a_ i = \frac {1}{|\mathbf{x_i} - \mathbf{x_i}|^2} \bigl(1 - y_i y_j + y_i (\mathbf{x_i} - \mathbf{x_j}) (\mathbf{x_j} \sum_{k \neq i, j}^{n} a_k y_k - \sum_{k \neq i,j} a_k y_k \mathbf{x_k}) \bigr) \; ・・・(vii)

となる。$a_i$を求めたら、

a_j = y_j (- a_i y_i - \sum_{k \neq i, j}^{n} a_k y_k) \; ・・・(ii)'' \\

で$a_j$を求める。
最後に、$(iv)$より$a_{i, j} \geq 0$という拘束条件があるので、

$(vii)$より$a_i$を求める。ただし、$a_i \leq 0$となったら$a_i = 0$とする。
$(ii)''$より$a_j$を求める。ただし、$a_j \leq 0$となったら$a_j = 0$とする。
2で$a_j = 0$となったら、$a_i$を計算しなおす。(計算式は$a_i = y_i (- a_j y_j - \sum_{k \neq i, j}^{n} a_k y_k)$)

↑の2.「i, jを選ぶ」, 4.「収束条件」について

\begin{align}
Minimize \; &f(\mathbf{a}) = \sum_{k=1}^{n} a_k - \frac{1}{2} \sum_{k=1}^{n} \sum_{l=1}^{n} a_k a_l y_k y_l \mathbf{x_k} \mathbf{x_l}\; ・・・(i)' \\
Subject \; to \; &\sum_{i=1}^{n} a_i y_i = 0 \; ・・・(ii)'\\
&a_i \geq 0  \; ・・・(iv)\\
&a_i \bigl(y_i(w_0+\mathbf{w}\mathbf{x_i})-1 \bigr) = 0  \; ・・・(vi)\\
\end{align}

にもう一度ラグランジュの未定乗数法(Wikipedia)、カルーシュ・クーン・タッカー条件(Wikipedia)を適用すると、ラグランジュ関数$L'$は

L'(\mathbf{a}, \lambda, \mathbf{\mu}) = f(\mathbf{a}) - \lambda \sum_{i=1}^{n} a_i y_i - \mathbf{\mu} \mathbf{a}

となり、拘束条件は

\begin{align}
Subject \; to \; &\mu_j a_j = 0 \\
&\mu_j \leq 0 \\
\end{align}

ここで

\nabla_a L' = \nabla_a f(\mathbf{a}) + \lambda \mathbf{y} - \mathbf{\mu} = 0

の、ある成分$t$だけに注目すると

\begin{align}
&\nabla_a f(\mathbf{a})_t + \lambda y_t - \mu_t = 0 \\
&\nabla_a f(\mathbf{a})_t + \lambda y_t = \mu_t \leq 0 \\
\end{align}

となる。
拘束条件$\mu_j a_j = 0$より、$a_t = 0$(サポートベクタ以外の点)のとき$\mu_t \leq 0$より

\nabla_a f(\mathbf{a})_t \leq - \lambda y_t \\
y_t \nabla_a f(\mathbf{a})_t \left\{
\begin{array}{ll}
\geq - \lambda & (y = -1) \\
\leq - \lambda & (y = 1) \\
\end{array}
\right.

(両辺に$y_t$をかけて、$y_t^2 = 1$を適用した)

また、$a_t > 0$(サポートベクタ)のとき$\mu_t = 0$より

y_t \nabla_a f(\mathbf{a})_t = - \lambda \\

以上をまとめると

y_t \nabla_a f(\mathbf{a})_t \left\{
\begin{array}{ll}
\geq - \lambda & (y = -1 \; or \; a_t > 0) \\
\leq - \lambda & (y = 1 \; or \; a_t > 0) \\
\end{array}
\right.

{y_t \nabla_a f(\mathbf{a})_t}_{(y = 1 \; or \; a_t > 0)} \leq - \lambda \leq {y_t \nabla_a f(\mathbf{a})_t}_{(y = -1 \; or \; a_t > 0)}

コレは全部の点$t$について考えているが、

$y = -1 ; or ; a_t > 0$で、$y_t \nabla_a f(\mathbf{a})_t$が最小値をとる$t$を$i$
$y = 1 ; or ; a_t > 0$で、$y_t \nabla_a f(\mathbf{a})_t$が最大値をとる$t$を$j$

のように$i, j$を選ぶと

y_j \nabla_a f(\mathbf{a})_j \leq y_i \nabla_a f(\mathbf{a})_i

と表せる。
これらが「2. n個の点から、適当な$i, j$を選ぶ」の選び方、「4. 収束条件を満たすまで、2, 3を繰り返す」の収束条件となる。

参考リンク