ハードマージン

2値分類について考えます。
訓練データが ${\bf x}_1,\ldots,{\bf x}_N$ の $N$ 個の入力ベクトルと
それぞれに対応する目標値 $t_1,\ldots,t_N(t_n\in\{-1,1\})$ からなり、
未知のデータ点 ${\bf x}$ は $y({\bf x})={\bf w}^\top{\bf x}+b$ の符号について分類されるとします。

訓練データは特徴空間で線形分離可能と仮定します。

分類境界と最も近いデータ点までの距離をマージンと言います。

イメージ図を以下に示します。

f:id:olj611:20210408232135p:plain:w300

SVM(サポートベクトルマシン)においては、分類境界はマージンを最大化するものが選ばれます。
分類関数が $t_n=+1$ である点については $y({\bf x}_n)>0$ 、
$t_n=-1$ である点については $y({\bf x}_n)<0$ が成立すると仮定します。
これらの条件はまとめて $t_ny({\bf x}_n)>0$ と書けます。

主問題

分離境界から点 ${\bf x}_n$ までの距離は以下のように書けます。

$\begin{eqnarray} \frac{|{\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b|}{||{\bf w}||}=\frac{t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)}{||{\bf w}||}\tag{1} \end{eqnarray}$

マージンは訓練データと分類境界の最短距離であるので

$\begin{eqnarray} \frac{1}{||{\bf w}||}\underset{n}{\rm min}(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)\tag{2} \end{eqnarray}$

と表せます。
イメージは以下の図です。

f:id:olj611:20210408235856p:plain:w300

求めたいのはマージンを最大化する ${\bf w},b$ です。
したがって、解は次の最適化問題を解くことで得られます。

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} \argmax_{{\bf w},b}\left(\frac{1}{||{\bf w}||}\underset{n}{\rm min}(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)\right)\tag{3} \end{eqnarray}$

${\bf w},b$ を定数倍しても、点 ${\bf x}$ から分類境界までのまでの距離は変わりません。
この事を以下で示します。

$\begin{eqnarray} \frac{t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)}{||{\bf w}||}において、{\bf w}\rightarrow\kappa{\bf w},b\rightarrow\kappa bと定数倍すると、\\ \end{eqnarray}$

$\begin{eqnarray} \frac{t_n(\kappa{\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+\kappa b)}{||\kappa{\bf w}||}&=&\frac{\kappa t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)}{\kappa||{\bf w}||}\\ &=&\frac{t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)}{||{\bf w}||}\tag{4} \end{eqnarray}$

よって、 ${\bf w},t$ を適当に定数倍することによって、分類境界に最も近い点について

$\begin{eqnarray} t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)=1\tag{5} \end{eqnarray}$

を成立させることができます。

また、すべてのデータについて以下の制約式が成り立ちます。

$\begin{eqnarray} t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)\geq1\tag{6} \end{eqnarray}$

最適化問題を書き直すと、

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} &&\argmax_{{\bf w},b}\frac{1}{||{\bf w}||},\\ &&{\rm s.t.}\ \ t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)\geq1\tag{7} \end{eqnarray}$

となり、さらに書き直すと

$\newcommand{\argmin}{\mathop{\rm arg~min}\limits}\begin{eqnarray} &&\argmin_{{\bf w},b}\frac{1}{2}||{\bf w}||^2,\\ &&{\rm s.t.}\ \ t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)\geq1\tag{8} \end{eqnarray}$

となります。
$(8)$ の ${\rm argmin}$ に $b$ も含まれていますが、
これは制約条件を満たすために $||{\bf w}||$ が変化すると、 $b$ も変化する必要があるためです。

双対問題

$(8)$ は主問題と言います。
この主問題は二次計画法の一例で凸計画法の一種です。
二次計画法とは線形不等式系で与えられる制約条件の下で二次関数を最小化する問題のことです。

不等式制約のラグランジュ未定乗数法を用いて双対問題に置き換えます。
双対問題に置き換えることにより、カーネルが利用できるようなり、最適化問題が解きやすくなります。

$\begin{eqnarray} L({\bf w},b, {\bf a})=\frac{1}{2}||{\bf w}||^2-\sum_{n=1}^Na_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b-1))\tag{9} \end{eqnarray}$

ここで、 ${\bf a}=(a_1,\ldots,a_N)^\top,a_n\geq0$ です。
${\bf w},b$ を主変数、 ${\bf a}$ を双対変数と言います。

$L({\bf w},b, {\bf a})$ を主変数について最小化し、双対変数について最大化することに双対問題を導出します。

ラグランジュ関数 $L({\bf w},b, {\bf a})$ について、次のような不等式を満たすような $({\bf w}^*,b^*{\bf a}^*)$ が存在するとき、
この点を鞍点といいます。

$\begin{eqnarray} L({\bf w}^*,b^*, {\bf a})\leq L({\bf w}^*,b^*, {\bf a}^*)\leq L({\bf w},b, {\bf a}^*)\tag{10} \end{eqnarray}$

f:id:olj611:20210409002804p:plain:w400

鞍点とは ${\bf w},b$ については最小値となり、 ${\bf a}$ については最大値となる点です。

凸計画問題において鞍点が最適解を与えることが知られています。(強双対性から導けます。)
(詳細については「機械学習プロフェッショナルシリーズサポートベクトルマシン」を参照してください。)

以下のように鞍点を求めます。
1: $L({\bf w},b, {\bf a})$ を主変数 ${\bf w},b$ について最小化します。
この時の ${\bf w},b$ を ${\bf w}^*({\bf a}),b^*(a)$ とおきます。
2: 次に $L({\bf w}^*({\bf a}),b^*(a), {\bf a})$ を双対変数 ${\bf a}$ について最大化します。

以下はイメージ図です。
f:id:olj611:20210409003045p:plain:w400

$L({\bf w},b, {\bf a})$ を ${\bf w}$ で微分して $={\bf 0}$ とおきます。

$\begin{eqnarray} &&\frac{\partial L}{\partial {\bf w}}={\bf 0}\\ &&\Leftrightarrow \frac{1}{2}\frac{\partial}{\partial{\bf w}}||{\bf w}||^2-\sum_{n=1}^N\frac{\partial}{\partial{\bf w}}a_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b-1))={\bf 0}\\ &&\Leftrightarrow{\bf w}=\sum_{n=1}^Na_n t_n{\boldsymbol\phi}({\bf x}_n)\tag{11} \end{eqnarray}$

$L({\bf w},b, {\bf a})$ を $b$ で微分して $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial L}{\partial b}=0\\ &&\Leftrightarrow \frac{1}{2}\frac{\partial}{\partial b}||{\bf w}||^2-\sum_{n=1}^N\frac{\partial}{\partial b}a_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b-1))=0\\ &&\Leftrightarrow\sum_{n=1}^Na_n t_n=0\tag{12} \end{eqnarray}$

$L({\bf w},b, {\bf a})$ に $(11)$ を代入します。

$\begin{eqnarray} L({\bf w},b, {\bf a})&=&\frac{1}{2}\left(\sum_{n=1}^Na_n t_n{\boldsymbol\phi}({\bf x})\right)^\top\left(\sum_{n=1}^Na_n t_n{\boldsymbol\phi}({\bf x})\right)-\sum_{n=1}^Na_n\left(t_n\left(\left(\sum_{n=1}^Na_n t_n{\boldsymbol\phi}({\bf x})\right)^\top{\boldsymbol\phi}({\bf x}_n)+b-1\right)\right)\\ &=&\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)-\sum_{n=1}^N\sum_{m=1}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)-b\sum_{n=1}^Na_nt_n+\sum_{n=1}^Na_n\\ &=&\sum_{n=1}^Na_n-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)\tag{13} \end{eqnarray}$

よって、 $(12),(13)$ より双対問題は以下のようになります。

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} &&\argmax_{{\bf a}}\left(\sum_{n=1}^Na_n-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)\right)\\ &&{\rm s.t.}\ \ \sum_{n=1}^Na_n t_n=0,\ a_n\geq0\tag{14} \end{eqnarray}$

サポートベクトル

$(11)$ より、決定関数は以下のようになります。

$\begin{eqnarray} y({\bf x})=\sum_{n=1}^Na_n t_n{\boldsymbol\phi}({\bf x})^\top{\boldsymbol\phi}({\bf x})+b\tag{15} \end{eqnarray}$

KKT条件 $a_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1)=0$ より、
$t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)>1$ となる点は $a_n=0$ となるため、予測と関係ないことが分かります。
それ以外の $a_n\not=0$ の点はサポートベクトルと呼ばれます。

$(15)$ は $N$ 回足していますが、実はサポートベクトル以外は足す必要がないことが分かります。

f:id:olj611:20210409011510p:plain:h400

バイアスパラメータ $b$ の導出

${\bf a}$ が求まると、次に $b$ を求めることができます。
任意のサポートベクトル ${\bf x}_n$ は $t_ny({\bf x}_n)=1$ であるので、

$\begin{eqnarray} t_n\left(\sum_{m\in\mathcal{S}}a_mt_m{\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)+b\right)=1\tag{16} \end{eqnarray}$

です。
$\mathcal{S}$ はサポートベクトルの添え字からなる集合です。
$(16)$ から $b$ が求まりますが、
数値誤差の影響を減らすために全てのサポートベクトルに対して、
平均を求めることによって $b$ を求めることが多いようです。

$\begin{eqnarray} b=\frac{1}{N_{\mathcal S}}\sum_{n\in{\mathcal S}}\left(t_n-\sum_{m\in\mathcal{S}}a_mt_m{\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)\right)\tag{17} \end{eqnarray}$

$N_{\mathcal S}$ はサポートベクトルの総数です。

次の記事で ${\bf a}$ を求めようと思います。お待ちください。

偉人の名言

f:id:olj611:20210409013236p:plain:w300
君がどんなに遠い夢を見ても、君自身が可能性を信じる限り、それは手の届くところにある。
ヘルマン・ヘッセ

参考文献

機械学習プロフェッショナルシリーズサポートベクトルマシン
パターン認識と機械学習下巻

動画

記事作成前に作成した動画なので、記事とは内容が異なる可能性があります。