はじめに
本記事は, 機械学習の教科書の決定版ともいえる, Christopher Bishop先生による『Pattern Recognition and Machine Learning （パターン認識と機械学習）』 , 通称PRMLの演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する生物測定学研究室 の輪読会でPRMLを取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, PRML 演習問題 解答集 まとめ をご覧ください.
問題
データ空間の次元数によらず, 各クラスに一つずつデータが存在すれば, 2つのデータ点だけから成るデータ集合でマージン最大の超平面を決定できることを示せ.
解答
まず, ２つのデータ点から成るデータ集合ということは, これらの２つのデータ点は両方ともサポートベクターと成ることに注意する。
このデータ集合のマージン最大の超平面を決定することは, 制約付き最適化問題を解く事に相当し, この時ラグランジュ乗数
\begin {align*}
L \left ( \textbf{w}, b, \textbf{a}\right ) =\frac{1}{2}\|\textbf{w}\|^2-\sum_{n=1}^{N} a_n \left \{ t_n \left ( \textbf{w}^\textrm{T}\boldsymbol{\phi} \left ( \textbf{x}_n\right ) +b\right ) -1\right \}
\tag{7.7}
\end {align*}
に, $N = 2$を代入した
\begin {align*}
L \left ( \textbf{w}, b, \textbf{a}\right ) =\frac{1}{2}\|\textbf{w}\|^2-\sum_{n=1}^{2} a_n \left \{ t_n \left ( \textbf{w}^\textrm{T}\boldsymbol{\phi} \left ( \textbf{x}_n\right ) +b\right ) -1\right \}
\tag{7.3.1}
\end {align*}
を利用して, $\textbf{w}$ と $b$ については最小化し, $\textbf{a}$ については最大化すれば良いことがわかる。
$ \left ( 7.3.1\right ) $ を $\textbf{w}$ と $b$ についてそれぞれ偏微分し, それらを $0$ とすると, 2つの条件
\begin {align*}
\textbf{w} = \sum_{n=1}^{2} a_n t_n \boldsymbol{\phi} \left ( \textbf{x}_n\right ) = a_1 \boldsymbol{\phi} \left ( \textbf{x}_1\right ) - a_2 \boldsymbol{\phi} \left ( \textbf{x}_2\right )
\tag{7.3.2}
\end {align*}
\begin {align*}
0 = \sum_{n=1}^{2} a_n t_n= a_1 - a_2
\tag{7.3.3}
\end {align*}
を得る。
ここで, 2つのデータ点が各クラスに1つずつ存在することから, $t_1 = 1$ 及び $t_2 = -1$ を仮定した。
これは $t_1 = -1$ 及び $t_2 = 1$ としても良いが, 同じことなのでここでは $t_1 = 1$ 及び $t_2 = -1$ として話を進める。
さて, $\left ( 7.3.3\right )$ より, $a_1 = a_2 = a$ と置き, $L \left ( \textbf{w}, b, \textbf{a}\right ) $ から $\textbf{w}$ と $b$ を消去して, $\left ( 7.6\right )$ の双対表現を考えると,
\begin {align*}
L \left ( \textbf{a}\right ) =2a+a^2 k \left ( \textbf{x}_1, \textbf{x}_2\right ) - \frac{1}{2}a^2 \left \{ k \left ( \textbf{x}_1, \textbf{x}_1\right ) + k \left ( \textbf{x}_2, \textbf{x}_2\right ) \right \}
\tag{7.3.4}
\end {align*}
が得られる。ただし, $k \left ( \textbf{x}, \textbf{x} ^ { \prime } \right ) = \boldsymbol{\phi} \left ( \textbf{x}\right ) ^\textrm{T}\boldsymbol{\phi} \left ( \textbf{x} ^ { \prime }\right ) $ で定義される。
この $\left ( 7.3.4\right )$ を $a$ に対しての最大化を考えると,
\begin {align*}
a = \frac{2}{k \left ( \textbf{x}_1, \textbf{x}_1\right ) + k \left ( \textbf{x}_2, \textbf{x}_2\right ) - 2k \left ( \textbf{x}_1,\textbf{x}_2\right ) }
\tag{7.3.5}
\end {align*}
を得る。ここから, $\textbf{w}$ と $b$ についてそれぞれ
\begin {align*}
\textbf{w} = \frac{2 \left \{ \boldsymbol{\phi} \left ( \textbf{x}_1\right ) - \boldsymbol{\phi} \left ( \textbf{x}_2\right ) \right \} }{k \left ( \textbf{x}_1, \textbf{x}_1\right ) + k \left ( \textbf{x}_2, \textbf{x}_2\right ) - 2k \left ( \textbf{x}_1,\textbf{x}_2\right ) }
\tag{7.3.6}
\end {align*}
\begin {align*}
b = \frac{k \left ( \textbf{x}_2, \textbf{x}_2\right ) - k \left ( \textbf{x}_1, \textbf{x}_1\right ) }{k \left ( \textbf{x}_1, \textbf{x}_1\right ) + k \left ( \textbf{x}_2, \textbf{x}_2\right ) - 2k \left ( \textbf{x}_1,\textbf{x}_2\right ) }
\tag{7.3.7}
\end {align*}
と求めることができる。
したがって, 各クラスに一つずつデータ点が存在すれば, 2つのデータ点から成るデータ集合でマージン最大の超平面を決定できることが証明できた。(証明終)
※ 本解答中の式番号はそれぞれPRMLの以下の番号と対応する。
$\left ( 7.3.1\right ) : \left ( 7.7\right ) , \quad \left ( 7.3.2\right ) : \left ( 7.8\right ) , \quad \left ( 7.3.3\right ) : \left ( 7.9\right ) , \quad \left ( 7.3.4\right ) : \left ( 7.10\right ) , \quad \left ( 7.3.6\right ) : \left ( 7.8\right ) , \quad \left ( 7.3.7\right ) : \left ( 7.18\right ) $