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

# 問題
この演習問題では、パーセプトロンの学習アルゴリズムの双対表現を導く。パーセプトロンでの更新則

```math
\mathbf{w} ^ {(\tau + 1)} = 
\mathbf{w} ^ {(\tau)} - 
\eta \nabla E_{\rm P} (\mathbf{w}) = 
\mathbf{w} ^ {(\tau)} + 
\eta \boldsymbol{\phi}_n t_n
\tag{4.55}
```

を用いて、訓練後の重みベクトル $\mathbf{w}$ が、ベクトル $t_n \boldsymbol{\phi}(\mathbf{x}_n)$（ただし $t_n \in (-1 , +1)$）の線形結合で表せることを示せ。この線形結合の係数を $\alpha_n$ として、パーセプトロンの学習アルゴリズムを導き、また、$\alpha_n$ を用いてパーセプトロンの予測関数を示せ。また、特徴ベクトル $\boldsymbol{\phi}(\mathbf{x})$ は、カーネル関数 $k(\mathbf{x}, \mathbf{x} ^ \prime) = \boldsymbol{\phi}(\mathbf{x}) ^ {\rm T} \boldsymbol{\phi}(\mathbf{x ^ \prime})$ の形でのみ現れることを示せ。

# 解釈

パーセプトロンモデルは、

```math
y(\mathbf{x})
= f \left( \mathbf{w} ^ {\rm T} \boldsymbol{\phi}(\mathbf{x}) \right) \tag{4.52}
```
```math
f(a) = \left\{
    \begin{array}{2}
      +1 & (a \geq 0)\\
      -1 & (a < 0)
    \end{array}
  \right.
 \tag{4.53}
```

で表される分類モデルである。この問題ではこれを双対表現を使って書き下す。なぜパーセプトロンが選ばれたのかは分からないが、ハードな閾値関数を採用している点などが「カーネルっぽくない」と思われたからだろうか。

# 解答

### 命題１

***命題***　訓練後の重みベクトル $\mathbf{w}$ は、ベクトル $t_n \boldsymbol{\phi}(\mathbf{x}_n)$ の線形結合で表せる。

***証明***　数学的帰納法を用いれば、

```math
\mathbf{w} ^ {(\tau + 1)} = 
\mathbf{w} ^ {(\tau)} + 
\eta \ t_n \boldsymbol{\phi}(\mathbf{x}_n)
\tag{4.55}
```

より、訓練におけるパラメータの初期値 $\mathbf{w} ^ {(0)}$ が $t_n \boldsymbol{\phi}(\mathbf{x}_n)$ の線形結合で表せることを示せばよい。

　パーセプトロンに厳密解が存在する場合（学習データ集合が線形に分離可能な場合）、学習アルゴリズムは必ず収束することが**パーセプロトロンの収束定理**から示されている。そのため、$\mathbf{w} ^ {(0)} = \mathbf{0}$ であっても学習は収束する。また、より早く収束させるための初期値の候補として、例えば

```math
\begin{align}
\mathbf{w} ^ {(0)} &=
\frac{1}{N_{+1}}
\sum_{n \notin \mathcal{M}} \boldsymbol{\phi}(\mathbf{x}_n) - 
\frac{1}{N_{-1}}
\sum_{n \in \mathcal{M}} \boldsymbol{\phi}(\mathbf{x}_n)
\\
&=
\frac{1}{N}
\sum_{n=1}^N t_n \boldsymbol{\phi}(\mathbf{x}_n)
\tag{ex6.2.1}
\end{align}
```

のように、$+1$ のラベルを持つ $ \boldsymbol{\phi}(\mathbf{x}) $ の平均と $-1$ のラベルを持つ $\boldsymbol{\phi}(\mathbf{x})$ の平均の差、なども考えられる。いずれの場合も、$\mathbf{w} ^ {(0)}$ は $t_n \boldsymbol{\phi}(\mathbf{x}_n)$ の線形結合で表される（証明終）。

### 命題２

***命題***　パーセプトロンの学習アルゴリズムは $\alpha_n$ を使って表せる。

***証明***　$\alpha_n$ を用いて $(4.55)$ を書き換えると以下のようになる。

```math
\begin{eqnarray}

&
& \mathbf{w} ^ {(\tau + 1)}
= 
\mathbf{w} ^ {(\tau)} + 
\eta \ t_n \boldsymbol{\phi}(\mathbf{x}_m)
\\

\iff
&
\sum_m \alpha_m^{(\tau+1)} t_m & \boldsymbol{\phi}(\mathbf{x}_m)
= 
\sum_m \alpha_m^{(\tau)} t_m \boldsymbol{\phi}(\mathbf{x}_m)
+ \eta \ t_n \boldsymbol{\phi}(\mathbf{x}_n)

\\

\iff
&&
\alpha_m^{(\tau + 1)} = 
\left\{
    \begin{array}{2}
      \alpha_m^{(\tau)} & (m \neq n)\\
      \alpha_m^{(\tau)} + \eta \ t_m & (m = n)
    \end{array}
  \right.
\tag{ex6.2.2}
\end{eqnarray}
```

以上より示された。（証明終）


### 命題３

***命題***　パーセプトロンの予測関数において、特徴ベクトル $\boldsymbol{\phi}(\mathbf{x})$ は、カーネル関数 $k(\mathbf{x}, \mathbf{x} ^ \prime) = \boldsymbol{\phi}(\mathbf{x}) ^ {\rm T} \boldsymbol{\phi}(\mathbf{x ^ \prime})$ の形でのみ現れる。

***証明***　$(4.52)$ を、$\alpha_n$ を使って表すと次のように変形できる。

```math
\begin{align}
y(\mathbf{x})
&= f \left( \mathbf{w} ^ {\rm T} \boldsymbol{\phi}(\mathbf{x}) \right)

\\

&= f \left( \sum_n \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n) ^ {\rm T} \boldsymbol{\phi}(\mathbf{x}) \right)

\\

&= f \left( \sum_n \alpha_n t_n k(\mathbf{x}_n, \mathbf{x}) \right)
\tag{ex6.2.3}
\end{align}
```

以上より示された。（証明終）