SVMのNumpy実装が非常に難しいです。SMOというアルゴリズムが主流で他には単一法などがあるようですが難しすぎます。そこで僕は下界または上界を最適化、勾配法でやろうと思っているのですがうまくいかずずっと止まっている状態です。
SVMの実装自体非常に少ないと思うのですが理論面について述べている記事はさらにありません。ここでは理論面の「双対」に焦点を置いて解説したいと思います。解説にあたってこのレジュメを使用します。
双対の例題
必要な栄養を摂りながら食費を最小にするには どのような割合で二つの食品を購入すれば良いか?
![](https://research.miidas.jp/wp-content/uploads/2019/08/Screen-Shot-2019-08-19-at-20.45.52-1024x361.png)
(1)
一方で、必要な栄養を摂りながら食費を最小にするにはどのような割合で二つの食品を購入すれば良いか?この時、問題
![Rendered by QuickLaTeX.com (\mathcal{P})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-56396306d856f79a65977292c774e1f0_l3.png)
![Rendered by QuickLaTeX.com (x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-4fb6b9a7dd8b54e22b861b4aed94cee8_l3.png)
![Rendered by QuickLaTeX.com (y)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-661259f4ca9661aea4ccc8ea9e468efa_l3.png)
- 「栄養1が2単位」 + 「栄養2が5単位」 = 「価格 1」
- 「栄養1が1単位」 + 「栄養2が3単位」 = 「価格 4」
(2)
(3)
![Rendered by QuickLaTeX.com (\mathcal{P})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-56396306d856f79a65977292c774e1f0_l3.png)
![Rendered by QuickLaTeX.com \geq](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-76929380bd24b7579265d2c8705fcd82_l3.png)
![Rendered by QuickLaTeX.com (\mathcal{D})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9ff995afcaad5bee596d04957c3a0e19_l3.png)
![Rendered by QuickLaTeX.com \mathcal{P}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-5bed2094d6826d2cb5b8f63cef61b30e_l3.png)
![Rendered by QuickLaTeX.com \geq](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-76929380bd24b7579265d2c8705fcd82_l3.png)
![Rendered by QuickLaTeX.com \mathcal{D}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-604919a910da61f809c93c64c0740a83_l3.png)
![Rendered by QuickLaTeX.com (\mathcal{P})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-56396306d856f79a65977292c774e1f0_l3.png)
![Rendered by QuickLaTeX.com (\mathcal{D})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9ff995afcaad5bee596d04957c3a0e19_l3.png)
ちゃんと進めましたがこれでは僕は全く理解できなかったのでもう少し調べてみました。すると次のことがわかりました。
ラグランジュ緩和
とある問題を解くのが困難な場合、これをもう少し簡単な問題に緩和しようというアプローチしたいですよね。 例えば、問題の制約式をどれか取り除いてしまった問題は、制約が「緩和されている」ことから緩和問題と呼ばれます。しかしながら、制約を取り去ってしまうことは、緩和の度合が激し過ぎて、緩和問題の最適解が元の問題からかけ離れてしまうことがしばしばあります。では制約を取り去ってしまうより、もう少しましな緩和法はないだろうか? そこで良く使われるのがラグランジュ緩和です。軸として考える問題を「主問題」と呼びます。双対問題とはその補集合を解くイメージです。今回の例だとMinimize問題をMaximize問題へと変形します。
(4)
![Rendered by QuickLaTeX.com (\mathcal{D})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9ff995afcaad5bee596d04957c3a0e19_l3.png)
(5)
![Rendered by QuickLaTeX.com (\mathcal{P})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-56396306d856f79a65977292c774e1f0_l3.png)
(6)
(7)
(8)
(9)
(10)
(11)
![Rendered by QuickLaTeX.com \mathcal{D}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-604919a910da61f809c93c64c0740a83_l3.png)
- 「主問題・双対問題」は表裏一体。
- 双対問題とはラグランジュ緩和を使って下界/上界を最適化する問題
- 双対問題の制約は有界性を考慮することで生じる
- 主問題より双対問題の方が簡単に解くことができる時もある
SVMの双対問題
ここまで双対問題とその導出について解説しました。最後に一気に飛んだ議論になりますがせっかくなのでSVMの双対問題を紹介します。