問題
この演習問題では、パーセプトロンの学習アルゴリズムの双対表現を導く。パーセプトロンでの更新則
\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})$ の形でのみ現れることを示せ。
解釈
パーセプトロンモデルは、
y(\mathbf{x})
= f \left( \mathbf{w} ^ {\rm T} \boldsymbol{\phi}(\mathbf{x}) \right) \tag{4.52}
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)$ の線形結合で表せる。
証明 数学的帰納法を用いれば、
\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}$ であっても学習は収束する。また、より早く収束させるための初期値の候補として、例えば
\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)$ を書き換えると以下のようになる。
\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$ を使って表すと次のように変形できる。
\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}
以上より示された。（証明終）