PRML　演習問題  7.33（標準）　解答

## はじめに
本記事は, 機械学習の教科書の決定版ともいえる, **Christopher Bishop先生**による[**『Pattern Recognition and Machine Learning （パターン認識と機械学習）』**]  (https://www.microsoft.com/en-us/research/people/cmbishop/prml-book/) , 通称**PRML**の演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する[生物測定学研究室] (https://www.ut-biomet.org/) の輪読会で**PRML**を取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, [PRML　演習問題　解答集　まとめ]  (https://qiita.com/Lab_of_Biomet/items/15e38ca34fafa8176d89) をご覧ください.



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


## 解答
まず, ２つのデータ点から成るデータ集合ということは, これらの２つのデータ点は両方ともサポートベクターと成ることに注意する。
このデータ集合のマージン最大の超平面を決定することは, 制約付き最適化問題を解く事に相当し, この時ラグランジュ乗数

```math
\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$を代入した

```math
\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つの条件

```math
\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*}
```

```math
\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 )$ の双対表現を考えると, 

```math
\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$ に対しての最大化を考えると, 

```math
\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$ についてそれぞれ

```math
\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*}
```

```math
\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 ) $