はじめに
今回の記事は前回の記事の続きになっています。
よろしければ以下の記事もご覧ください。
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく①～理論と数式編～
前回の復習
前回の記事で、ハードマージンとソフトマージンにおける最適化問題の式を導出しました。以下にまとめます。
ハードマージンのとき
min_{W, b}\frac{1}{2}||W||^2, \quad t_i(W^TX_i + b)\geq 1 \quad (i = 1, 2, 3, ...N)
ソフトマージンのとき
min_{W, \xi}\Bigl\{\frac{1}{2}||W||^2 + C\sum_{i=1}^{N} \xi_i\Bigr\} \quad \quad
t_i(W^TX_i + b)\geq 1 - \xi_i\\
\xi_i = max\Bigl\{0, M - \frac{t_i(W^TX_i + b)}{||W||}\Bigr\}\\
i = 1, 2, 3, ... N
ソフトマージンは線形分離不可能な問題のときに用いるもので、ハードマージンは線形分離可能な問題のときに用いるものでしたね。
最適化問題を解く
それでは最適化問題を解いていくことを考えていきましょう。
この最適化問題を解くときに、上記の式を直接解くことはほとんどありません。
上記のような式を最適化問題の主問題といいますが、多くの場合この主問題を直接解くのではなく、この主問題を双対問題と呼ばれる別の形の数式に変換して、その数式を解くことで最適化問題を解いていきます。
今回、この最適化問題を解くためにラグランジュの未定乗数法を用いましょう。
ラグランジュの未定乗数法についてはこちらの記事を参考にしてください。
自分も完全に理解している訳ではないので、一部厳密性に欠ける部分があると思いますがご了承ください。簡単に解説します。
ラグランジュの未定乗数法について
ラグランジュの未定乗数法は制約付き最適化問題の代表的な手法です。
目的関数$f(X)$をn個の不等式制約$g(X)_i \leqq0, i = 1, 2, 3, ...n$の条件の下で最小にするときを考えます。
まず、以下のラグランジュ関数を定義します。
L(X, α) = f(X) + \sum_{i=1}^{n}α_ig_i(X)
この不等式制約付き最適化問題は、ラグランジュ関数について以下の四つの条件を満たす$(\tilde{X}, \tilde{α})$を求める問題に帰結します。
\frac{\partial L(X, α)}{\partial X}=0\\
\frac{\partial L(X, α)}{\partial α_i} = g_i(X)\leqq 0, \quad (i=1, 2,... n)\\
0 \leqq α, \quad (i = 1,2, ...n)\\
α_ig_i(X) = 0, \quad (i = 1, 2,...n)
このように、最適化問題を直接解くのではなく、ラグランジュの未定乗数法を用いることで別の式を用いて最適化問題を解くことができます。この別の式を双対問題と呼ぶのでしたね。
最適化問題に適用
それでは、サポートベクトルマシンのソフトマージンの式にラグランジュの未定乗数法を適用してみましょう。
目的関数は以下です。
min_{W, \xi}\Bigl\{\frac{1}{2}||W||^2 + C\sum_{i=1}^{N} \xi_i\Bigr\}
不等式制約は以下です。
t_i(W^TX_i + b)\geq 1 - \xi_i \quad \xi_i \geq 0 \quad i = 1, 2,...N
今回はn個のデータ全てに不等式制約が二個ずつあるため、ラグランジュ乗数をα、βとすると、ラグランジュ関数は以下のようになります。
L(W,b,\xi,α,β)=\frac{1}{2}||W||^2 + C\sum_{i=1}^{N} \xi_i-\sum_{i=1}^{N}α_i\bigl\{t_i(W^TX_i+b)-1+\xi_i\bigl\}-\sum_{i=1}^{N}β_i\xi_i
最適化問題を解くとき、次の条件を満たします。
\frac{\partial L(W,b,\xi,α,β)}{\partial W}= W - \sum_{i=1}^{N}α_it_iX_i=0\\
\frac{\partial L(W,b,\xi,α,β)}{\partial b}= -\sum_{i=1}^{N}α_it_i = 0\\
\frac{\partial L(W,b,\xi,α,β)}{\partial W} = C - α_i -β_i = 0
これら三つの式を整理すると以下のようになります。
W =\sum_{i=1}^{N}α_it_iX_i\\
\sum_{i=1}^{N}α_it_i = 0\\
C = α_i + β_i
この三つの式をラグランジュ関数に代入して頑張って計算すると以下のように変数αのみの式になります。
\tilde{L}(α) = \sum_{i=1}^{N}α_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{i=j}^{N}α_iα_jt_it_j{X_i}^TX_j
また、αは0以上であるため、双対問題は以下の条件を満たすαを求めることになります、
max\Bigl\{{\tilde{L}(α) = \sum_{i=1}^{N}α_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{i=j}^{N}α_iα_jt_it_j{X_i}^TX_j\Bigr\}}\\
\sum_{i=1}^{N}α_it_i = 0, \quad 0 \leqq α_i \leqq C, i = 1,2,...N
このように、ソフトマージンにおけるサポートベクトルマシンの双対問題の式を導出することができました。
終わりに
ここまでで今回の記事は終了です。
ここまでお付き合いいただきありがとうございました。
次回の記事は以下になります。
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく③～カーネル法について～
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく④～ソフトマージンとハードマージンの実装～
[機械学習]サポートベクトルマシン(SVM)について、できるだけ分かりやすくまとめていく⑤～カーネル法を用いた分類の実装～