「サポートベクターマシン」-完全に分離できない場合の直線・平面・超平面の作り方-

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

* 参考にしたもの：[機械学習のエッセンス](https://www.sbcr.jp/product/4797393965/)の第05章「機械学習アルゴリズム」
* 基本的な考え方は[「サポートベクターマシン」について](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)参照

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

* 直線・平面・超平面(完全に分離できる場合)([「サポートベクターマシン」について](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)参照)
* **直線・平面・超平面(完全に分離できない場合)**(=このページ)
* [曲線・曲面・超曲面](https://qiita.com/kazuya_minakuchi/items/4f238120032224909cf4)

# 考え方

今回は、直線・平面・超平面ではキレイに分離できない場合の、境界として適した直線・平面・超平面の作り方を考える。
(↓こういう場合)
![svm_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/9ee176a3-7075-8317-3943-e522cf5265ad.png)


[直線・平面・超平面(完全に分離できる場合)](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)を参照すると、境界線を<font color="Red">$w_0+\mathbf{w}\mathbf{x}=0$</font>と置いたとき、

```math
\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$は

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

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

![svm_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/ba984db3-7df3-aefa-e1c3-97dc21dc3814.png) ![svm_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/96ccc73e-17f7-57fa-12c9-0e847695ec6a.png)

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

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

と設定し、最適化問題を

```math
\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)](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95)、[カルーシュ・クーン・タッカー条件(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AB%E3%83%BC%E3%82%B7%E3%83%A5%E3%83%BB%E3%82%AF%E3%83%BC%E3%83%B3%E3%83%BB%E3%82%BF%E3%83%83%E3%82%AB%E3%83%BC%E6%9D%A1%E4%BB%B6)を適用すると、ラグランジュ関数は

```math
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条件は次のようになる。

```math
\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}
```

[直線・平面・超平面(完全に分離できる場合)](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)と同様に

```math
\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}
```
```math
\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}
```

となるので、[直線・平面・超平面(完全に分離できる場合)](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)と同様に以下を最小にする$\mathbf{a}$を求め、$(i), (ii)$より$w_0, \mathbf{w}$を求めればよい
<font color="Red">
腑に落ちない点：
1. $C \sum_{i=1}^{n}\xi_i$と$- \sum_{i=1}^{n} a_i \xi_i$の項どこ行った・・・？
2. [機械学習のエッセンス](https://www.sbcr.jp/product/4797393965/)内のPythonでの実装時、$(i)$から$w_0$求めるとき、$\xi_i$を無視してる(微小だから無視して良いって事？)
</font>



```math
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}
```

ここで、

```math
\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}
```

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

```math
\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によるアルゴリズム

[直線・平面・超平面(完全に分離できる場合)](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)と同様に、以下の流れで解いていく

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

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

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

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

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

```math
\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)](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95)、[カルーシュ・クーン・タッカー条件(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AB%E3%83%BC%E3%82%B7%E3%83%A5%E3%83%BB%E3%82%AF%E3%83%BC%E3%83%B3%E3%83%BB%E3%82%BF%E3%83%83%E3%82%AB%E3%83%BC%E6%9D%A1%E4%BB%B6)を適用すると、ラグランジュ関数とKKT条件は次のようになる。($\mathbf{e}=(1, \cdots, 1)$)

```math
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 \\
```

[分離できる場合](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)と同様にラグランジュ関数の$\mathbf{a}$についての勾配のt番目の成分を考えると、

```math
\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}
```

ここで、

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

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

より、

```math
\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.
```

```math
\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$をかけると

```math
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.
```

```math
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.
```

ここからは[分離できる場合](https://qiita.com/kazuya_minakuchi/items/5102f2d1d865980f279a)と同様に考えると

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

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

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

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

# 参考リンク

- [サポートベクターマシン(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3%82%AF%E3%82%BF%E3%83%BC%E3%83%9E%E3%82%B7%E3%83%B3)
- [超平面](https://ja.wikipedia.org/wiki/%E8%B6%85%E5%B9%B3%E9%9D%A2)
- [超曲面](https://ja.wikipedia.org/wiki/%E8%B6%85%E6%9B%B2%E9%9D%A2)
- [点と直線の距離公式をベクトルを使って導く](https://okimath.com/tento)
- [ラグランジュの未定乗数法(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95)
- [カルーシュ・クーン・タッカー条件(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AB%E3%83%BC%E3%82%B7%E3%83%A5%E3%83%BB%E3%82%AF%E3%83%BC%E3%83%B3%E3%83%BB%E3%82%BF%E3%83%83%E3%82%AB%E3%83%BC%E6%9D%A1%E4%BB%B6)
- [二次計画法(Wikipedia)](https://ja.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A8%88%E7%94%BB%E6%B3%95)
- [二次関数の軸と頂点の求め方など](https://mathtrain.jp/jikutyoten)