TL;DR

最小二乗で求めた識別関数の重みベクトル$w$はよくなかったが、クラスの平均間の距離を大きく、かつ、各クラスの分散は小さくする、というフィッシャーの手法を使うといい感じの$w$が得られる。
フィッシャーの手法は多クラスでも使える。

4.1.4 フィッシャーの線形判別

前節「分類における最小二乗」では、識別関数の重みベクトル$w$を最小二乗法で求めるアプローチはよろしくないことが分かった。
そこで、別のアプローチで精度よくクラス識別ができるような重みベクトル$w$を求める方法をみる。
これは、次元の削減という観点から線形識別モデルを見るものである。

まずは2クラスの問題を考える。$D$次元入力ベクトル$x$を得て、以下の式で1次元に射影するとする。

$$
y = w^T x \tag{4.20}
$$

$ y \geq - w_0 $の場合クラス$C_1$、そうでなければクラス$C_2$であるとする。
$D$次元を1次元に射影しているので、情報量が損失する。なので、もとの$D$次元空間では線形分離できていたクラスが1次元空間では大きく重なり合うかもしれない。
そこで、クラスの分離が最大になるような射影ができる重みベクトル$w$を求めたい。

うまくいかない：クラスの平均の分離度を最大化

クラス$C_1$のデータ数が$N_1$個、$C_2$のデータ数が$N_2$個とする。2つのクラスの平均ベクトルは

$$
\mathbf{m_1} = \frac{1}{N_1} \sum_{n \in C_1} x_n, \quad \mathbf{m_2} = \frac{1}{N_2} \sum_{n \in C_2} x_n \tag{4.21}
$$

となる。クラスの分離が最大にすることをクラスの平均ベクトルが最も離れるようにする、と考える。
これは以下の式を最大化する$w$を選択することを意味している。

$$
m_2 - m_1 = w^T ( \mathbf{m_2} - \mathbf{m_1} ) \tag{4.22}
$$

ここで

$$
m_k = w^T \mathbf{m_k} \tag{4.23}
$$

はクラス$C_k$から射影されたデータの平均である。
式(4.22)を最大にするような$w$を求めたいが、この式は$w$を大きくすればするほどいくらでも大きな値になる。
この問題を避けるため、$w$は単位長であるという制約の下で式(4.22)を最大化したい。

制約つきの最大化問題なので、ラグランジュの未定乗数法を使うと解ける（演習4.4）。

演習4.4：射影後の平均が最大になるwは？

$w$は単位長、すなわち$ w^T w = 1 $という制約で$ w^T (m_2 - m_1) $を最大化する。
ラグランジュの未定乗数法を使い、$ L = w^T (m_2 - m_1) + \lambda (w^T w - 1) $を最大化する

\begin{align}

\frac{ \partial L }{ \partial w} &= m_2 - m_1 + 2 \lambda w = 0 \\
w &= - \frac{1}{2 \lambda} ( m_2 - m_1) \\
w & \propto m_2 - m_1

\end{align}

ただ、こうして求めた$w$は下図のようにもとの2次元空間ではうまく分離できているが、1次元への射影後は重なり合う部分が多くなってしまうという問題がある。

うまくいく：フィッシャーの提案法

フィッシャーの提案した方法では、射影されたクラス平均間の分離度を大きくすると同時に、各クラス内では小さな分散をあたる関数を最大化する。
その結果、クラス間の重なりを最小にできる。

これを図で考えると下図になる。
2クラスの入力ベクトルがそれぞれ赤、青のように分布していると考える。
上行と下行どちらも赤楕円の中心と青楕円の中心の距離は等しいので、射影されたクラス平均間の分離度だけをみると上行と下行どちらもクラスの分離度は同じ。
一方、各クラスの分散（＝楕円の大きさ）が小さい下行の方がクラスの分離度が大きいのは見ると明らか。
なので、各クラスの平均間の距離が大きくなりつつ、各クラスの分散が小さくなるような$w$を求めたい。

クラス$C_k$から射影されたデータのクラス内分散は

$$
s_k^2 = \sum_{n \in C_k} ( y_n - m_k)^2 \tag{4.24}
$$

ここで$y_n = w^T x_n$である。全データ集合に対する総クラス内分散は$s_1^2 + s_2^2$であると定義する。
各クラスの平均間の距離が大きくなればなるほど、また、各クラスの分散が小さくなればなるほど大きくなるような指標として、フィッシャーの判別規準はクラス内分散とクラス間分散の比で定義される。

$$
J(w) = \frac{ (m_2 - m_1)^2 }{ s_1^2+s_2^2 } \tag{4.25}
$$

次に式(4.25)を行列で書き直そう。
まずは分子を式変形する。

\begin{align}

(m_2 - m_1)^2 &= ( w^T \mathbf{m_2} - w^T \mathbf{m_1} ) \\
&= \{ w^T ( \mathbf{m_2} - \mathbf{m_1} ) \}^2 \\
&= w^T ( \mathbf{m_2} - \mathbf{m_1} ) ( \mathbf{m_2} - \mathbf{m_1} )^T w \\
&= w^T S_B w \\
ここでS_B &= ( \mathbf{m_2} - \mathbf{m_1} ) ( \mathbf{m_2} - \mathbf{m_1} )^T \tag{4.27}

\end{align}

次に分母を式変形する。

\begin{align}

s_1^2+s_2^2 &= \sum_{n \in C_1} (w^T x_n - w^T \mathbf{m_1} )^2 + 
\sum_{n \in C_2} (w^T x_n - w^T \mathbf{m_2} )^2 \\
&= w^T ( \sum_{n \in C_1} (x_n - m_1) )^2 w + w^T ( \sum_{n \in C_2} (x_n - m_2) )^2 w \\
&= w^T S_W w \\
ここでS_W &= \sum_{n \in C_1} (x_n - m_1)(x_n - m_1)^T + \sum_{n \in C_2} (x_n - m_2)(x_n - m_2)^T \tag{4.28}

\end{align}

よって式(4.25)は以下の式に書き直せる。

$$
J(w) = \frac{w^T S_B w}{w^T S_W w} \tag{4.26}
$$

式(4.26)を最大化する$w$を求めたいので、いつも通り$w$に関する微分＝０、の方程式を解く。

ここで分数の微分公式を思い出そう。

\begin{align}

\left( 
\frac{f(x)}{g(x)}
\right)'

=

\frac{ f'g - fg'}{g^2}

\end{align}

この公式に当てはめると

\begin{align}

\frac{ \partial J(w) }{ \partial w} = 
\frac{ 2 w^T S_B (w^T S_W w) - 2 w^T S_B w (w^T S_W)}{ (w^T S_W w)^2 } = 0 \\
\\
分子を整理すると\\
(w^T S_B w) (w^T S_W) = (w^T S_B) (w^T S_W w) \tag{A}

\end{align}

(A)の$(w^T S_B w), (w^T S_W w)$はスカラーである。
また、$S_B$は対称行列なので$ w^T S_B = S_B^T w = S_B w$。
式(4.27)より$ S_B w = ( \mathbf{m_2} - \mathbf{m_1} ) ( \mathbf{m_2} - \mathbf{m_1} )^T w$。
$ ( \mathbf{m_2} - \mathbf{m_1} )^T w $はスカラーなことに注意すると、$ S_B w$は常に$ (\mathbf{m_2} - \mathbf{m_1} )$の向きであると分かる。なので、

\begin{align}

S_W w &\propto (\mathbf{m_2} - \mathbf{m_1} ) \\
\therefore w &\propto S_W^{-1} (\mathbf{m_2} - \mathbf{m_1} ) \tag{4.30}

\end{align}

これにより写像した結果は下図のようになる。クラス分離度が大きく改善していることが分かる。
実務でもよく使われる手法である。

4.1.5 最小二乗との関連

目的変数ベクトルに1-of-K符号化法でなく、特殊な表記法を使うと最小二乗とフィッシャーの線形判別で求める重みベクトル$w$が一致する。（だから何なのかよく分からないので深入りしない）

4.1.6 多クラスにおけるフィッシャーの判別

詳細は追わないが、2クラスのときに定義した$ S_B, S_W $を多クラスに拡張する。
2クラスのときの$ J(w) $と同様、クラスの平均間の距離が大きく、各クラス内の分散が小さいほど大きくなるような指標の1つの例として、以下の式が提案されている。

$$
J(W) = \mathrm{Tr} \{ S_W^{-1} S_B \} \tag{4.50}
$$

各クラス内の分散が小さいほど$ S_W^{-1} $は大きくなり、クラスの平均間の距離が大きくなるほど$ S_B $が大きくなるので、確かに指標となってそうだという雰囲気が分かるだろう。

この指標を最大化することで所望の$w$が求まるのだが、その具体的な方法はテキストでも参考文献を見よ、となっているぐらいにややこしそうなので、頑張れば出来るとぐらいに理解しておこう。

4.1.7 パーセプトロンアルゴリズム

このアルゴリズムは実務ではほぼ使われていないので、読み物として。

パーセプトロンは2クラス分類用のモデル（多クラスへの拡張は難しいらしい）。
入力ベクトル$x$をある決まった非線形変換をして特徴ベクトル（基底関数）$\phi(x)$を得て、以下の式で表される一般化線形モデルを構成する。

$$
y(x) = f( w^T \phi(x) ) \tag{4.52}
$$

ここで活性化関数$f$はステップ関数であり、

\begin{align}

f(a) = 

\begin{cases}
+1, & a \geq 0 \\
-1, & a < 0

\end{cases}
\tag{4.53}

\end{align}

また、パーセプトロンではクラス$C_1$に対する目的変数値$ t = +1$、$C_2$に対しては$t=-1$を使用する。

次に、パーセプトロン規準とよばれる誤差関数を定義する。この誤差関数が小さくなるような$w$を求めていく。
式(4.52, 4.53)と目的変数の設定から$C_1$のデータ$x_n$に対して$ w^T \phi(x_n) > 0 $, $C_2$のデータ$x_n$に対して$ w^T \phi(x_n) < 0 $となることを期待している。
よって、$ w^T \phi(x_n) t_n $は正しく識別されていれば正になり、誤識別されていれば負になる。

なので、パーセプトロン規準（誤差関数）を以下で定義する：

$$
E_P(w) = - \sum_{n \in M} w^T \phi(x_n) t_n, \quad Mは誤識別されたすべてのパターン \tag{4.54}
$$

誤識別パターンが多いほどパーセプトロン規準が正に大きくなり、誤差関数として機能していることが分かる。

誤識別パターンを1つ見つけるたびに$w$を更新する逐次学習を適用する。3.1.3節「逐次学習」の確率的勾配降下法を用いる（下式3.22）。

\begin{align}

＃思い出すため再掲 \\
w^{ ( \tau +1 ) } = w^{ (\tau) } - \eta \nabla E_n \tag{3.22} \\

\\
＃パーセプトロンの場合は \\
w^{ ( \tau +1 ) } = w^{ (\tau) } - \eta \nabla E_p(w) = w^{ (\tau) } + \eta \phi(x_n) t_n
\tag{4.55}

\end{align}

式(4.52)より$ w^T \phi(x) $の正負に興味があり、$w$に定数$\eta$をかけても$y(x)$は変化しない。

よって、

\begin{align}

式(4.55)のwを\eta wに置き換えると \\
\eta w^{ ( \tau +1 ) } = \eta w^{ (\tau) } + \eta \phi(x_n) t_n \\
w^{ ( \tau +1 ) } =  w^{ (\tau) } + \phi(x_n) t_n \tag{4.55'}

\end{align}

となり、学習率$\eta = 1$としても一般性を失わない。
結局、誤識別が起きた際は目標変数値の正負に応じて$w$に特徴ベクトル$ \phi(x_n) $を足す or 引くだけでいい、という面白い$w$の更新ルールが導出された。

式(4.55')の両辺に$ - \phi(x_n) t_n $をかけると

$$

w^{ ( \tau +1 ) } \phi(x_n) t_n = - w^{ (\tau) } \phi(x_n) t_n - ( \phi(x_n) t_n )^T ( \phi(x_n) t_n ) < - w^{ ( \tau +1 ) } \phi(x_n) t_n
\tag{4.56}
$$

となる。式変形において$ ( \phi(x_n) t_n )^T ( \phi(x_n) t_n ) $は2乗の計算に相当するので、必ず正となることを使った。
式(4.56)の左辺である$w$更新後の誤識別サンプルの誤差は$w$更新前の誤識別サンプルの誤差より必ず小さくなる、と解釈できる。
ただし、$w$更新に用いた誤識別サンプル以外のサンプルの誤差も減少することは意味していないことに注意。

しかし、パーセプトロンの収束定理により、学習データ集合が線形分離可能であれば、この学習法で最適解に必ず収束すると保証されている。