「サポートベクターマシン」について

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

* 参考にしたもの：[機械学習のエッセンス](https://www.sbcr.jp/product/4797393965/)の第05章「機械学習アルゴリズム」
* [回帰](https://qiita.com/kazuya_minakuchi/items/186b20efd0eefdeb026b)、[ロジスティック回帰分析](https://qiita.com/kazuya_minakuchi/items/c6f3ec731e9eca74c282)は別ページ

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

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

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

* **直線・平面・超平面(完全に分離できる場合)**(=このページ)
* [直線・平面・超平面(完全に分離できない場合)](https://qiita.com/kazuya_minakuchi/items/42d276cb1a6e68ffa0e4)
* [曲線・曲面・超曲面](https://qiita.com/kazuya_minakuchi/items/4f238120032224909cf4)

# 特徴、考え方

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

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

![svm_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/00730145-3f6d-c88f-1af1-d5eef4e474c3.png)

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

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

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

# 解き方
![svm_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/316f4dd4-9d6a-ebd5-5119-7bb899bd35e0.png)

1. n個の点(↑の赤、青)に$i(=1, 2, \cdots, n)$と番号をつける。それぞれの<font color="Red">点の位置は$\mathbf{x_i}=(x_1, x_2, \cdots, x_d)_i$</font>と表す。
2. 境界線を<font color="Red">$w_0+\mathbf{w}\mathbf{x}=0$</font>と置く。$\mathbf{w}=(w_1, w_2, \cdots, w_d)$
    1. $w_0$と$\mathbf{w}$で境界の形が決まる。
    2. ある点iがどちらのグループになるかは、$w_0+\mathbf{w}\mathbf{x_i}$の符号(±)によって判別される
3. <font color="Red">全部の点に$y_i=1,-1$を設定</font>する。「$w_0+\mathbf{w}\mathbf{x_i}>0$になる点は$y_i=1$」「$w_0+\mathbf{w}\mathbf{x_i}<0$になる点は$y_i=-1$」とする。(=↑で同じ色は$y_i$が同じになる)
4. 点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つ目の式は、「[点と直線の距離公式をベクトルを使って導く](https://okimath.com/tento)」を参照
  * 2つ目の式は、↑3での$y_i$の設定の仕方より、こう書くと絶対値と同じ(必ず+)になる
5. 全て(n個)の点で最小の$l_i$を以下のように表すと、<font color="Red">↓が最大(=「境界から一番近くなる点」との距離が最大)となるような$w_0, \mathbf{w}$</font>を設定したい
$$
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}))
$$
6. ココで、$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)$にも影響を与えない)
7. よって、5は「<font color="Red">↓を最大にする$w_0, \mathbf{w}$を求める</font>」という問題とできる
$$
\frac{1}{|\mathbf{w}|}
$$
8. また、計算しやすくするため変形(逆数をとり、二乗し、$1/2$をかける)すると、<font color="Red">「↓を最小にする$w_0, \mathbf{w}$を求める」という最適化問題</font>となる
$$
\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の求め方
↑より、<font color="Red">↓を満たす$w_0, \mathbf{w}$を求める。</font>

```math
\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)](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)で解く。
制約式がn個なので、$\mathbf{a}=(a_1, a_2, \cdots, a_n)$を導入すると、ラグランジュ関数は

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

と表され、<font color="Red">↓を満たす$w_0, \mathbf{w}, \mathbf{a}$を求めれば良い。</font>

```math
\begin{align}
\frac{\partial L}{\partial w_0} &= 0 \; ・・・(ii)\\
\frac{\partial L}{\partial w_j} &= 0 \; ・・・(iii)\\
\end{align}
```
```math
\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)$より

```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 \; ・・・(ii)'\\
\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} \; ・・・(iii)'\\
\end{align}
```

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

```math
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}$についての最適化」から「<font color="Red">$\mathbf{a}$についての最適化([二次計画法(Wikipedia)](https://ja.wikipedia.org/wiki/%E4%BA%8C%E6%AC%A1%E8%A8%88%E7%94%BB%E6%B3%95))</font>」となる。
$\mathbf{a}$を求めたら、

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

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

```math
\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})$とおくと、<font color="Red">↓を満たす$\mathbf{a}$を求める。</font>

```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}\; ・・・(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によるアルゴリズム」で解くのが効率が良い。([機械学習のエッセンス](https://www.sbcr.jp/product/4797393965/)より)
- ↓の例だと、丸がついている2点(サポートベクタ)以外は$y_i(w_0+\mathbf{w}\mathbf{x_i})-1 \neq 0$なので、$(vi)$より$a_i=0$となる

![svm_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/00730145-3f6d-c88f-1af1-d5eef4e474c3.png)

### Platによるアルゴリズム

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

```math
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$部分だけ考えると

```math
\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}$とすると、それぞれまとめられる

```math
\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)'$に代入すると

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

となる、ここで

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

とおくと、

```math
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を取り出すと

```math
\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$」とおくと

```math
\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)''$に代入すると

```math
\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$は([このへん](https://mathtrain.jp/jikutyoten)参照)

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

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

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

```math
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$を求めたら、

```math
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$という拘束条件があるので、
1. $(vii)$より$a_i$を求める。ただし、$a_i \leq 0$となったら$a_i = 0$とする。
2. $(ii)''$より$a_j$を求める。ただし、$a_j \leq 0$となったら$a_j = 0$とする。
3. 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.「収束条件」について

```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}\; ・・・(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)](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)を適用すると、ラグランジュ関数$L'$は

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

となり、拘束条件は

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

ここで

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

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

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

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

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

以上をまとめると

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

```math
{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$について考えているが、

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