Introduction
今日はSVMの定理について書いていきます。
この記事はpart 2になります。Part 1 では目的関数の導出までを書きました。Part 2では双対問題とゆわれるものを導出します。Part 1で導いた目的関数は主問題と呼ばれます。一般的に、SVMでは主問題ではなく、双対問題を解くことで最適解を得ます。
もし、まだPart 1を見ておられない場合は、Theorem of SVM part 1を見てくださるとよいのではないかと思います。
SVMの実装編は
Implement linear SVM
Implement kernel SVM
を御覧ください。
概要
主問題
Part 1で導いた主問題の復習をしておきます。
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
$$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$
これはソフトマージンの時の目的関数ですが、以後ソフトマージンの場合のみを扱っていきます。
さて、双対問題と呼ばれるものですが、これは主問題から自然に導かれます。
双対問題
SVMの最適化問題は凸二次最適化問題と呼ばれる種類の問題です。凸二次最低化問題は、必ず大域最適解に近づくことが知れれており、数値上の安全性が高いとされています。
双対問題を導出します。まず、主問題を以下のように書き換えます。
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
$$~~s.t~~ \forall i \in N, -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \}\leq 0,~~~, \forall i \in N~ -\epsilon \leq 0$$
Lagurange function
次に、新たに$\alpha,\mu$という要素に非負のパラメータを持つベクトルを導入します。これは以下のラグランジュ関数を定義するためです。
ラグランジュ関数は以下のようになります。
$$L(w,b,\epsilon,\alpha,\mu) := \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i -\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i$$
ここで、$\alpha = (\alpha_1,\alpha_2,...,\alpha_n)$、$\mu = (\mu_1,\mu_2,..,\mu_n)$です。
$w,b,\epsilon$は主変数といい、一方$\alpha,\mu$は双対変数と呼ばれています。
主変数についての最小化、双対変数についての最大化
新たに$P(w,b,\epsilon)$を$\alpha,\mu$についてLを最大化することで定義します。
$$P(w,b,\epsilon):= \max_{\alpha \geq 0, \mu \geq 0} L(w,b,\epsilon,\alpha,\mu)$$
次にPを主変数について最小化します。
$$\min_{w,b,\epsilon} P(w,b,\epsilon) = \min_{w,b,\epsilon}\max_{\alpha \geq 0, \mu \geq 0} L(w,b,\epsilon,\alpha,\mu)$$
この最適化問題は元の主問題と同等であることを示します。（ここでの同等とは、どちらの最適化問題を解いても同じ解が得られることとします。）
$\min_{w,b,\epsilon} P(w,b,\epsilon)$を次のように書き替えます。
$$\min_{w,b,\epsilon} P(w,b,\epsilon) = \min_{w,b,\epsilon}\max_{\alpha \geq 0, \mu \geq 0} L(w,b,\epsilon,\alpha,\mu)$$
$$= \min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i + \max_{\alpha \geq 0,\mu \geq 0} \{-\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i \}$$
最初の項と二つ目の項は$\alpha,\mu$とは関係のない項なのでこのように書き換えられました。
一方、主問題は
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
$$~~s.t~~ \forall i \in N, -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \}\leq 0,~~~, \forall i \in N~ -\epsilon \leq 0$$
でした。
さて、
もし、$\exists ~i \in N ~~s.t.~~ -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} > 0$, or $-\epsilon > 0$であれば、私たちは$\min_{w,b,\epsilon} P(w,b,\epsilon)$を解くことができません。なぜなら$\alpha,\mu$をどこまでも大きくすることができてしまい、$P(w,b,\epsilon)$の値が$\infty$をとってしまいます。
しかし、$\forall ~i \in N, -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \}\leq 0$ と$~ -\epsilon \leq 0$を二つとも満たしているとき、
$$\max_{\alpha \geq 0,\mu \geq 0} \{-\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i \} = 0$$
となります。
この時、
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i + \max_{\alpha \geq 0,\mu \geq 0} \{-\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i \}$$
$$= \min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
となり、元の最適化問題が現れました。
つまり、制約を満たしているときは、$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$に解が与えられ、満たしていないときはこの最適化問題は解けないということになり、同等であることがわかります。
双対変数について最大化し、主変数について最小化する
次に、$D(\alpha,\mu)$を主変数について最適化することで定義します。
$$D(\alpha,\mu) := \min_{w,b,\epsilon,\alpha,\mu} L(w,b,\epsilon,\alpha,\mu)$$
次に、
$D(\alpha,\mu)$を$\alpha,\mu$について最大化することを考えます。
$$\max_{\alpha,\mu} D(\alpha,\mu) = \max_{\alpha,\mu} \min_{w,b,\epsilon,\alpha,\mu} L(w,b,\epsilon,\alpha,\mu)$$
この問題は双対問題と呼ばれます。先ほどと違う点に注意が必要です。
先ほどの主問題では、初めに双対変数について最大化し、そのあと主変数について最小化しました。今回はまず初めに、主変数について最小化し、そのあとで双対変数について、最大化します。
$\min_{w,b,\epsilon,\alpha,\mu} L(w,b,\epsilon,\alpha,\mu)$について、それぞれの変数による偏微分は
$$\frac{\partial L}{\partial w} = w - \sum_{i \in {1,2,..,n}} \alpha_i y_i x_i = 0$$
$$\frac{\partial L}{\partial b} = - \sum_{i \in {1,2,..,n}} \alpha_i y_i = 0$$
$$\frac{\partial L}{\partial \epsilon} = C - \alpha_i - \mu_i = 0$$
となります。
Lを各項について分配法則を使い、書き換えます。
\begin{eqnarray*}
L &=& \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i -\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i\\
&=& \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i -\sum_{i \in {1,2,..,n}} \alpha_i y_i w^T \phi(x) + \alpha_i y_i b - \alpha_i + \alpha_i \epsilon_i - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i\\
&=& \frac{1}{2}||W||^2 - \sum_{i \in {1,2,..,n}} \alpha_i y_i w^T x_i - b \sum_{i \in {1,2,..,n}} \alpha_i y_i + \sum_{i \in {1,2,..,n}} \alpha_i + \sum_{i \in {1,2,..,n}} (C - \alpha_i - \mu_i) \epsilon_i
\end{eqnarray*}
この式に先ほどの偏微分によって得られた方程式を代入します。
$$-\frac{1}{2} \sum_{i,j \in {1,2,..,n}} \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j) + \sum_{i \in {1,2,..,n}} \alpha_i$$
そして、
\begin{eqnarray*}
C - \alpha_i - \mu_i &=& 0 \\
C - \alpha_i &=& \mu \geq 0\\
C - \alpha_i & \geq & 0
\end{eqnarray*}
であるので、
$$\max_{\alpha} -\frac{1}{2}\sum_{i,j \in {1,2,..,n}} \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j)+\sum_{i \in {1,2,..,n}} \alpha_i$$
$$s.t. \sum_{i \in {1,2,..,n}} \alpha_i y_i = 0 ~~~ , 0 \leq \alpha_i \leq C$$
と、書き換えられます。
よって最終的に双対問題は以下のように表されます。
$$\min_{\alpha} \frac{1}{2}\sum_{i,j \in {1,2,..,n}} \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j)-\sum_{i \in {1,2,..,n}} \alpha_i$$
$$s.t. \sum_{i \in {1,2,..,n}} \alpha_i y_i = 0 ~~~ , 0 \leq \alpha_i \leq C$$
Reference
https://www.amazon.co.jp/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E3%83%9E%E3%82%B7%E3%83%B3-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%AB%B9%E5%86%85-%E4%B8%80%E9%83%8E/dp/4061529064
この記事はpart 2になります。Part 1 では目的関数の導出までを書きました。Part 2では双対問題とゆわれるものを導出します。Part 1で導いた目的関数は主問題と呼ばれます。一般的に、SVMでは主問題ではなく、双対問題を解くことで最適解を得ます。
もし、まだPart 1を見ておられない場合は、Theorem of SVM part 1を見てくださるとよいのではないかと思います。
SVMの実装編は
Implement linear SVM
Implement kernel SVM
を御覧ください。
概要
- 主問題
- 双対問題
- ラグランジュ関数
- 主変数について、最小化、双対変数について最大化
- 双対変数について最大化、主変数について最小化
主問題
Part 1で導いた主問題の復習をしておきます。
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
$$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$
これはソフトマージンの時の目的関数ですが、以後ソフトマージンの場合のみを扱っていきます。
さて、双対問題と呼ばれるものですが、これは主問題から自然に導かれます。
双対問題
SVMの最適化問題は凸二次最適化問題と呼ばれる種類の問題です。凸二次最低化問題は、必ず大域最適解に近づくことが知れれており、数値上の安全性が高いとされています。
双対問題を導出します。まず、主問題を以下のように書き換えます。
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
$$~~s.t~~ \forall i \in N, -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \}\leq 0,~~~, \forall i \in N~ -\epsilon \leq 0$$
Lagurange function
次に、新たに$\alpha,\mu$という要素に非負のパラメータを持つベクトルを導入します。これは以下のラグランジュ関数を定義するためです。
ラグランジュ関数は以下のようになります。
$$L(w,b,\epsilon,\alpha,\mu) := \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i -\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i$$
ここで、$\alpha = (\alpha_1,\alpha_2,...,\alpha_n)$、$\mu = (\mu_1,\mu_2,..,\mu_n)$です。
$w,b,\epsilon$は主変数といい、一方$\alpha,\mu$は双対変数と呼ばれています。
主変数についての最小化、双対変数についての最大化
新たに$P(w,b,\epsilon)$を$\alpha,\mu$についてLを最大化することで定義します。
$$P(w,b,\epsilon):= \max_{\alpha \geq 0, \mu \geq 0} L(w,b,\epsilon,\alpha,\mu)$$
次にPを主変数について最小化します。
$$\min_{w,b,\epsilon} P(w,b,\epsilon) = \min_{w,b,\epsilon}\max_{\alpha \geq 0, \mu \geq 0} L(w,b,\epsilon,\alpha,\mu)$$
この最適化問題は元の主問題と同等であることを示します。（ここでの同等とは、どちらの最適化問題を解いても同じ解が得られることとします。）
$\min_{w,b,\epsilon} P(w,b,\epsilon)$を次のように書き替えます。
$$\min_{w,b,\epsilon} P(w,b,\epsilon) = \min_{w,b,\epsilon}\max_{\alpha \geq 0, \mu \geq 0} L(w,b,\epsilon,\alpha,\mu)$$
$$= \min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i + \max_{\alpha \geq 0,\mu \geq 0} \{-\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i \}$$
最初の項と二つ目の項は$\alpha,\mu$とは関係のない項なのでこのように書き換えられました。
一方、主問題は
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
$$~~s.t~~ \forall i \in N, -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \}\leq 0,~~~, \forall i \in N~ -\epsilon \leq 0$$
でした。
さて、
もし、$\exists ~i \in N ~~s.t.~~ -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} > 0$, or $-\epsilon > 0$であれば、私たちは$\min_{w,b,\epsilon} P(w,b,\epsilon)$を解くことができません。なぜなら$\alpha,\mu$をどこまでも大きくすることができてしまい、$P(w,b,\epsilon)$の値が$\infty$をとってしまいます。
しかし、$\forall ~i \in N, -\{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \}\leq 0$ と$~ -\epsilon \leq 0$を二つとも満たしているとき、
$$\max_{\alpha \geq 0,\mu \geq 0} \{-\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i \} = 0$$
となります。
この時、
$$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i + \max_{\alpha \geq 0,\mu \geq 0} \{-\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i \}$$
$$= \min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$
となり、元の最適化問題が現れました。
つまり、制約を満たしているときは、$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$に解が与えられ、満たしていないときはこの最適化問題は解けないということになり、同等であることがわかります。
双対変数について最大化し、主変数について最小化する
次に、$D(\alpha,\mu)$を主変数について最適化することで定義します。
$$D(\alpha,\mu) := \min_{w,b,\epsilon,\alpha,\mu} L(w,b,\epsilon,\alpha,\mu)$$
次に、
$D(\alpha,\mu)$を$\alpha,\mu$について最大化することを考えます。
$$\max_{\alpha,\mu} D(\alpha,\mu) = \max_{\alpha,\mu} \min_{w,b,\epsilon,\alpha,\mu} L(w,b,\epsilon,\alpha,\mu)$$
この問題は双対問題と呼ばれます。先ほどと違う点に注意が必要です。
先ほどの主問題では、初めに双対変数について最大化し、そのあと主変数について最小化しました。今回はまず初めに、主変数について最小化し、そのあとで双対変数について、最大化します。
$\min_{w,b,\epsilon,\alpha,\mu} L(w,b,\epsilon,\alpha,\mu)$について、それぞれの変数による偏微分は
$$\frac{\partial L}{\partial w} = w - \sum_{i \in {1,2,..,n}} \alpha_i y_i x_i = 0$$
$$\frac{\partial L}{\partial b} = - \sum_{i \in {1,2,..,n}} \alpha_i y_i = 0$$
$$\frac{\partial L}{\partial \epsilon} = C - \alpha_i - \mu_i = 0$$
となります。
Lを各項について分配法則を使い、書き換えます。
\begin{eqnarray*}
L &=& \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i -\sum_{i \in {1,2..n}} \alpha_i \{y_i (w^T \phi(x_i) + b) -1 + \epsilon_i \} - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i\\
&=& \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i -\sum_{i \in {1,2,..,n}} \alpha_i y_i w^T \phi(x) + \alpha_i y_i b - \alpha_i + \alpha_i \epsilon_i - \sum_{i \in {1,2,..,n}} \mu_i \epsilon_i\\
&=& \frac{1}{2}||W||^2 - \sum_{i \in {1,2,..,n}} \alpha_i y_i w^T x_i - b \sum_{i \in {1,2,..,n}} \alpha_i y_i + \sum_{i \in {1,2,..,n}} \alpha_i + \sum_{i \in {1,2,..,n}} (C - \alpha_i - \mu_i) \epsilon_i
\end{eqnarray*}
この式に先ほどの偏微分によって得られた方程式を代入します。
$$-\frac{1}{2} \sum_{i,j \in {1,2,..,n}} \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j) + \sum_{i \in {1,2,..,n}} \alpha_i$$
そして、
\begin{eqnarray*}
C - \alpha_i - \mu_i &=& 0 \\
C - \alpha_i &=& \mu \geq 0\\
C - \alpha_i & \geq & 0
\end{eqnarray*}
であるので、
$$\max_{\alpha} -\frac{1}{2}\sum_{i,j \in {1,2,..,n}} \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j)+\sum_{i \in {1,2,..,n}} \alpha_i$$
$$s.t. \sum_{i \in {1,2,..,n}} \alpha_i y_i = 0 ~~~ , 0 \leq \alpha_i \leq C$$
と、書き換えられます。
よって最終的に双対問題は以下のように表されます。
$$\min_{\alpha} \frac{1}{2}\sum_{i,j \in {1,2,..,n}} \alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j)-\sum_{i \in {1,2,..,n}} \alpha_i$$
$$s.t. \sum_{i \in {1,2,..,n}} \alpha_i y_i = 0 ~~~ , 0 \leq \alpha_i \leq C$$
Reference
https://www.amazon.co.jp/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E3%83%9E%E3%82%B7%E3%83%B3-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%AB%B9%E5%86%85-%E4%B8%80%E9%83%8E/dp/4061529064
コメント
コメントを投稿