PRML演習問題 7.3(標準) - 機械学習基礎理論独習

問題

データ空間の次元数によらず、各クラスに一つずつデータが存在すれば、
$2$ つのデータ点だけから成るデータ集合でマージン最大の超半面を決定できることを示せ。

参照

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

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} \argmax_{{\bf w},b}\frac{1}{2}||{\bf w}||^2\tag{7.6} \end{eqnarray}$

解答

データが次の $2$ つ ${\bf x}_1\in{\mathcal C}_+(t_1=+1),{\bf x}_2\in{\mathcal C}_-(t_2=-1)$ のみが与えられているとします。
このとき、 $(7.4)$ より、以下の式が成り立ちます。

$\begin{eqnarray} &&{\bf w}^\top{\boldsymbol\phi}({\bf x}_1)+b=1\tag{1}\\ &&{\bf w}^\top{\boldsymbol\phi}({\bf x}_2)+b=-1\tag{2} \end{eqnarray}$

最適化問題 $(7.6)$ を解くために、 $(1),(2)$ の制約式にラグランジュ乗数 $\lambda,\eta$ を導入すると、次のラグランジュ関数が得られます。

$\begin{eqnarray} L=\frac{1}{2}||{\bf w}||^2+\lambda({\bf w}^\top{\boldsymbol\phi}({\bf x}_1)+b-1)+\eta({\bf w}^\top{\boldsymbol\phi}({\bf x}_1)+b+1)\tag{3} \end{eqnarray}$

$(3)$ を ${\bf w}$ で微分して、 $={\bf 0}$ とおきます。

$\begin{eqnarray} &&\frac{\partial L}{\partial {\bf w}}={\bf 0}\\ &&\Leftrightarrow {\bf w}+\lambda{\boldsymbol\phi}({\bf x}_1)+\eta{\boldsymbol\phi}({\bf x}_2)={\bf 0}\tag{4} \end{eqnarray}$

$(3)$ を $b$ で微分して、 $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial L}{\partial b}=0\\ &&\Leftrightarrow \lambda+\eta=0\tag{5} \end{eqnarray}$

$(4),(5)$ より、 ${\bf w},b$ は以下のように定まります。

$\begin{eqnarray} &&{\bf w}=\lambda({\boldsymbol\phi}({\bf x}_1)-{\boldsymbol\phi}({\bf x}_2))\tag{6}\\ &&b=-\frac{\lambda}{2}\left(||{\boldsymbol\phi}({\bf x}_1)||^2-||{\boldsymbol\phi}({\bf x}_2)||^2\right)\tag{7} \end{eqnarray}$

${\bf w},b$ が定まれば、超平面が定まります。
よって、題意が示せました。

補足

${\bf w},b$ に $\lambda$ が含まれていますが、これは超平面を決定するのに問題ありません。
これが問題にならない理由については、PRML演習問題7.2(基本)をご覧ください。