サポートベクターマシン(完全に分離できない場合)の考え方

参考にしたもの：機械学習のエッセンスの第05章「機械学習アルゴリズム」
基本的な考え方は「サポートベクターマシン」について参照

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

直線・平面・超平面(完全に分離できる場合)(「サポートベクターマシン」について参照)
直線・平面・超平面(完全に分離できない場合)(=このページ)
曲線・曲面・超曲面

考え方

今回は、直線・平面・超平面ではキレイに分離できない場合の、境界として適した直線・平面・超平面の作り方を考える。
(↓こういう場合)

直線・平面・超平面(完全に分離できる場合)を参照すると、境界線を$w_0+\mathbf{w}\mathbf{x}=0$と置いたとき、

\begin{align}
Minimize \; &\frac{1}{2}|\mathbf{w}|^2 \\
Subject \; to \; &y_i(w_0+\mathbf{w}\mathbf{x_i}) \geq 1 \; (i=1, 2, \cdots, n) \\

\end{align}

という最適化問題を解いた。しかし$y_i(w_0+\mathbf{w}\mathbf{x_i})\geq1$は

「サポートベクタ(=境界に一番近い点)だと等号、サポートベクタ以外だと不等号となる」

という意味の拘束条件だが、今回は反対側になるものも出てくる。(↓で緑丸に囲まれたもの)

コレらも考えるため、スラック変数と呼ばれる間違いの度合いを表す変数$\xi_i \geq 0 ; (i = 1, \cdots, n)$を考え、

判別が誤っている点(緑丸で囲まれた点)で$\xi_i > 0$
判別が正しい点(↑以外)で$\xi_i = 0$

と設定し、最適化問題を

\begin{align}
Minimize \; &C \sum_{i=1}^{n}\xi_i + \frac{1}{2}|\mathbf{w}|^2 \\
Subject \; to \; &y_i(w_0+\mathbf{w}\mathbf{x_i}) \geq 1 - \xi_i \; (i=1, 2, \cdots, n) \\
&\xi_i \geq 0 \\
\end{align}

のように表す。

これは「境界に一番近い点との距離も小さくするけど、$\xi_i$(間違い度合い)の合計も小さくしよう」という意味。
Cは調整のための定数で、Cが大きくなるほど$\sum_{i=1}^{n}\xi_i$の影響が大きくなるので、$\xi_i$を小さくしようとする力が強く働く。

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

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

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

解き方

これにラグランジュの未定乗数法(Wikipedia)、カルーシュ・クーン・タッカー条件(Wikipedia)を適用すると、ラグランジュ関数は

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

となり、KKT条件は次のようになる。

\begin{align}
a_i &\geq 0 \\
y_i(w_0+\mathbf{w}\mathbf{x_i})-1 + \xi_i &\geq 0 \\
a_i \bigl(y_i(w_0+\mathbf{w}\mathbf{x_i})-1 + \xi_i \bigr) &= 0 \; \cdots (i)\\
\eta_i &\geq 0 \\
\xi_i &\geq 0 \\
\eta_i \xi_i &= 0 \\
\end{align}

直線・平面・超平面(完全に分離できる場合)と同様に

\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 \\
\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} \; \cdots (ii)\\
\end{align}

となるので、直線・平面・超平面(完全に分離できる場合)と同様に以下を最小にする$\mathbf{a}$を求め、$(i), (ii)$より$w_0, \mathbf{w}$を求めればよい

腑に落ちない点：

$C \sum_{i=1}^{n}\xi_i$と$- \sum_{i=1}^{n} a_i \xi_i$の項どこ行った・・・？
機械学習のエッセンス内のPythonでの実装時、$(i)$から$w_0$求めるとき、$\xi_i$を無視してる(微小だから無視して良いって事？)

L(w_0, \mathbf{w}, \mathbf{\xi}, \mathbf{a}) = 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}

ここで、

\begin{align}
\frac{\partial L}{\partial \xi_i} = C - a_i - \eta_i &= 0 \\
C - a_i &= \eta_i \geq 0 \\
a_i &\leq C \\
\end{align}

となるので、解くべき最適化問題は次のようになる。

\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} \\
Subject \; to \; &\sum_{i=1}^{n} a_i y_i = 0 \\
&0 \leq a_i \leq C\\
\end{align}

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だけ変更」について

基本の流れは直線・平面・超平面(完全に分離できる場合)参照
ただし、最後の拘束条件による修正は$0 \leq a_{i, j} \leq C$となるので、以下のようになる。

$a_i$を求める。ただし、$a_i \leq 0$となったら$a_i = 0$、$a_i \geq C$となったら$a_i = C$とする。
$a_j$を求める。ただし、$a_j \leq 0$となったら$a_j = 0$、$a_j \geq C$となったら$a_j = C$とする。
2で$a_j = 0 ; or ; C$となったら、$a_i$を計算しなおす。

↑の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} \\
Subject \; to \; &\sum_{i=1}^{n} a_i y_i = 0 \\
&0 \leq a_i \leq C\\
\end{align}

にもう一度ラグランジュの未定乗数法(Wikipedia)、カルーシュ・クーン・タッカー条件(Wikipedia)を適用すると、ラグランジュ関数とKKT条件は次のようになる。($\mathbf{e}=(1, \cdots, 1)$)

f(\mathbf{a}) + \lambda \sum_{i=1}^{n} a_i y_i - \mathbf{\mu} \mathbf{a} - \mathbf{\nu} (C \mathbf{e} - \mathbf{a}) \\
\mu_k a_k = 0, \; \mu_k \leq 0, \; \nu_k (C - a_k) = 0, \; \nu_k \leq 0 \\

分離できる場合と同様にラグランジュ関数の$\mathbf{a}$についての勾配のt番目の成分を考えると、

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

ここで、

\mu_t \left\{
\begin{array}{ll}
\leq 0 & (a_t = 0) \\
= 0 & (a_t > 0)
\end{array}
\right.

\nu_t \left\{
\begin{array}{ll}
\leq 0 & (a_t < C) \\
= 0 & (a_t = C)
\end{array}
\right.

より、

\nabla_a {f(\mathbf{a})}_t + \lambda y_t = \mu_t - \nu_t \left\{
\begin{array}{ll}
\geq 0 & (a_t > 0) \\
\leq 0 & (a_t < C)
\end{array}
\right.

\nabla_a {f(\mathbf{a})}_t \left\{
\begin{array}{ll}
\geq - \lambda y_t & (a_t > 0) \\
\leq - \lambda y_t & (a_t < C)
\end{array}
\right.

$y_t = 1 ; or ; -1$なので、両辺に$y_t$をかけると

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

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

ここからは分離できる場合と同様に考えると

$(a_t > 0 ; and ; y = 1) ; or ; (a_t < C \; and \; y = -1)$で、$y_t \nabla_a f(\mathbf{a})_t$が最小値をとる$t$を$i$
$(a_t > 0 ; and ; y = -1) ; or ; (a_t < C \; and \; y = 1)$で、$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を繰り返す」の収束条件となる。

参考リンク