# 7章発表メモ
https://www.slideshare.net/kazunorisakai2/prml-7711-appendix-e を参照しました。

## 7.1 最大分類マージン器
### $y(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + \omega_0$で線形分離可能の場合

#### p. 37
##### SVMとは
共通のパラメータ$\sigma^2$を持つガウスカーネルを用いて、Parzen推定法を適用して、各クラスごとの入力ベクトル$\mathbf{x}$の分布を推定する。(2.250より)
$$
\begin{align}
p(\mathbf{x}|t) = \frac{1}{N_t}\sum_n \frac{1}{Z_k}exp\{\frac{||\mathbf{x}-\mathbf{x}_n||^2}
{2\sigma^2}\} \delta(t, t_n)
\end{align}
$$
今、
$$
\begin{align}
\delta(t, t_n) = \begin{cases}
1 &\text{if $t = t_n$} \\
0 &\text{otherwise}
\end{cases}
\end{align}
$$
そして、
$$
\begin{align}
Z_k = (2\pi \sigma^2)^{D/2}
\end{align}
$$
である。

ベイズの定理より、
$$
\begin{align}
p(t|\mathbf{x}) \propto p(\mathbf{x}|t) p(t)
\end{align}
$$
よって、 $p(\mathbf{x}|t)$を求めれば、決定境界も定まる。本文に戻る

##### 復習 超平面$y(\mathbf{x}) = 0$から点$\mathbf{x}$までの距離
$y(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + b$で、かつ、超平面上では$y(\mathbf{x}) = 0$なので、点と平面の距離の公式を用いて
$$
\begin{align}
\frac{\mathbf{w}^T \phi(\mathbf{x})}{||\mathbf{w}||} &= \frac{y(\mathbf{x})-b}{||\mathbf{w}||}\\
&= - \frac{b}{||\mathbf{w}||}
\end{align}
$$
よって、点$\mathbf{x}$の決定面への直行射影を$\mathbf{x}'$とし、面と点との距離を$r$とおくと、
$$
\begin{align}
&\phi(\mathbf{x}) = \phi(\mathbf{x}')+ r \frac{\mathbf{w}}{||\mathbf{w}||} \\
&\Rightarrow \mathbf{w}^T\phi(\mathbf{x}) + b = \mathbf{w}^T\phi(\mathbf{x}') + b + r \frac{\mathbf{w}^T\mathbf{w}}{||\mathbf{w}||} \\
&\Rightarrow y(\mathbf{x}) = y(\mathbf{x}')+ r \frac{\mathbf{w}^T\mathbf{w}}{||\mathbf{w}||} \\
&\Rightarrow r = \frac{y(\mathbf{x})}{||\mathbf{w}||}
\end{align}
$$
今、線形分離可能と仮定しているので、$t_n y(\mathbf{x}_n) > 0$がすべての$n$について成り立つ。よって、上記式を用いて、分類境界から$\mathbf{x}_n$までの距離は、
$$
\begin{align}
\frac{t_n y(\mathbf{x})}{||\mathbf{w}||}
\end{align}
$$
これの最小値がマージンであり、それを最大にするパラメータ$\mathbf{w}$と$b$を探す。

##### 最適化問題をラグランジュ乗数法で解ける形に
以下は、https://axa.biopapyrus.jp/machine-learning/svm/hard-margin-svm.html を参照した。

以上から、以下の最適化問題を解くことになる。
\begin{align}
\text{arg max}_{\mathbf{w,b}} \{ \frac{1}{||\mathbf{w}||} \text{min}_n t_n( \mathbf{w}^T\mathbf{x}+b ) \}
\end{align}

今、境界に最も近い点について、$\mathbf{w}^T\phi(\mathbf{n})+b = -1$を満たす点$\mathbf{n}$が存在するとする。その点から平面までの距離は、点と平面の公式から、
\begin{align}
\frac{|\mathbf{w}^T\phi(\mathbf{n})+b|}{||\mathbf{w}||} = \frac{1}{||\mathbf{w}||}
\end{align}
同様に、$\mathbf{w}^T\phi(\mathbf{n})+b = 1$を満たす点$\mathbf{p}$が必ず存在するとする。その点から平面までの距離は、点と平面の公式から、
\begin{align}
\frac{|\mathbf{w}^T\phi(\mathbf{p})+b|}{||\mathbf{w}||} = \frac{1}{||\mathbf{w}||}
\end{align}

よって、点$\mathbf{n}$を含む領域とと点$\mathbf{p}$を含む領域の距離は、$\frac{2}{||\mathbf{w}||}$である。これを最大化すれば良いので、$||w||^2$を最小化すれば良い。そして、その際の制約条件は、$t_n( \mathbf{w}^T\mathbf{x}+b )-1 =0$であり、ラグランジュ乗数法を用いて条件を満たす$\mathbf{w}, b$を求める。

#### p. 38
##### 　ラグランジュ乗数法を用いた二次計画法
$$
\begin{align}
L(\mathbf{w}, b, \mathbf{a})= \frac{1}{2}||\mathbf{w}||^2 - \sum_n^N a_n\{t_n(\mathbf{w}^T\phi(\mathbf{x}_n)+b)-1 \}
\end{align}
$$
まず、$\mathbf{w}$で微分すると、
$$
\begin{align}
&\frac{\partial L}{\partial \mathbf{w}}
= \mathbf{w} - \sum_n^N a_n t_n \phi(\mathbf{x}_n) = 0 \\
&\Rightarrow \mathbf{w} = \sum_n^N a_n t_n \phi(\mathbf{x}_n)
\end{align}
$$
また、$b$で微分すると、
\begin{align}
\frac{\partial L}{\partial b}
= - \sum_n^N a_n t_n = 0 \\
\end{align}

そして、$L$を、$\widetilde{L}(a)$で書き直すと、
\begin{align}
\widetilde{L}(a) &= \left( \frac{1}{2}\sum_n a_n t_n \phi(\mathbf{x}_n)\right)^T\sum_m a_m t_m \phi(\mathbf{x}_m) - \sum_n a_n t_n \left( \sum_m a_m t_m \phi(\mathbf{x}_m) \right)^T \phi(\mathbf{x_n}) - b \sum_n a_n t_n + \sum_n a_n \\
&= \sum_n a_n - \frac{1}{2}\sum_n \sum_m a_n a_m t_n t_m k(\mathbf{x}_n, \mathbf{x}_m)
\end{align}
なお、$k(\mathbf{x}_n, \mathbf{x}_m) = \phi(\mathbf{x}_n)^T\phi(\mathbf{x}_m)$である。

また、関数$y$は以下のように書き直せる
\begin{align}
y(\mathbf{x}) &= \mathbf{w}^T\phi(x) + b \\
&= \left( \sum_n^N a_n t_n \phi(\mathbf{x}_n)\right)^T \phi(\mathbf{x}) + b \\
&= \sum_n^N a_n t_n k(\mathbf{x}, \mathbf{x}_n) + b
\end{align}
なお、$k(\mathbf{x}, \mathbf{x}_n) = \phi(\mathbf{x}_n)^T \phi(\mathbf{x})$である。本文へ戻る