PRML復活の呪文 part13 (4.1 - 4.1.4)

# TL;DR

- $K$クラスの識別を行うには、2クラスの識別関数を$K$個使えばよい。
- 識別関数の重みベクトル$w$を最小二乗法で求める方法はいい方法ではない。

# 4章「線形識別モデル」の準備

3章では説明変数$x$から任意の**実数**値$t$を予測する回帰問題を考えた。例えば、昨日の気温と今日の気温を説明変数$x$として、実数値である明日の気温が目標変数$t$である。

4章では入力データ$x$から、その入力データが属するクラスを$K$個の**離散**クラス$C_k$の1つに割り当てる識別問題を考える。例えば、画像$x$を入力して、その画像に写る動物が犬クラス($C_1$)か猫クラス($C_2$)かを識別したい。


ここでは、線形な識別モデルを対象とするので、3章「線形回帰モデル」でも扱った簡単な下式モデルから始めよう。

$$
y(x) = w^T x + w_0 \tag{4.4}
$$

3章と同様に、入力$x$の代わりに非線形な基底関数$ \phi(x) $を使ってもよいが、ほとんどの性質は$ \Phi(x) = x$としても変わらない（らしい）ので4.3節「確率的識別モデル」までは$ \phi(x) = x$とする
。

式(4.4)右辺の$ w_0$という表記が面倒なので、$D$次元の$w, x$を$D+1$次元に拡張し、$x_0 = 1$とするダミー入力値を導入すると下式のようにすっきり書ける。

$$
y(x) = \tilde{w}^T \tilde{x} \tag{4.8}
$$

回帰問題と異なり、識別問題で予測したい値は0～1の範囲の値をとる、入力データ$x$があるクラス$C_k$に属する事後確率だったりする。なので、(4.8)式を非線形関数$ f(\cdot) $によって変換するように一般化する。

$$
y(x) = f( w^T x + w_0) \tag{4.3}
$$

$f$は**活性化関数** (activation function) と呼ばれる[^1]。

いま、2クラスの識別問題を考えよう。入力ベクトル$x$は2次元であり、線形識別モデルの出力値$y(x)$はクラス1である事後確率となるように学習しているとしよう。入力ベクトルで張られる入力空間上で、クラス1と識別される領域とクラス2と識別される領域の境界（この境界を**決定境界** (decision boundary)という）はクラス1, 2の事後確率がそれぞれ50%になることは直観的に分かる。
すなわち$ f( w^T x + w_0 ) = 0.5 $が決定境界であり、$ w^T x + w_0 $が左式を満たすようなある定数であることが決定境界である。
つまり、**$ w^T x + w_0 = \text{const}$が決定境界であり、決定境界は$x$の線形関数**であることが分かる。そのため、入力空間で決定境界を図示すると下図のように$x$に線形になる。
2次元入力空間の決定境界が1次元の直線で表現されている。より一般には$D$次元入力空間の決定境界は$D-1$次元の超平面[^2]に対応する。

![キャプチャ36.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/84589665-6e05-6883-27f7-3af39335ad35.png)

[^1]: deep learningの領域でもよくつかわれる単語
[^2]: いかめしい言葉だが、1次元の直線、2次元の平面に対して3次元以上のものを超平面と呼んでいるだけ。

# 4.1 識別関数（判別関数）
# 4.1.1 2クラス

まずは2クラスの識別問題を考えよう。下式の線形識別モデルが$ y(x) \geq 0 $ならクラス1、$ y(x) < 0 $ならクラス2と識別する。入力データ$x$から直接クラスを判定する関数なので識別関数と呼ばれる。

$$
y(x) = w^T x + w_0 \tag{4.4}
$$

対応する決定境界は$ y(x) = 0 $で定義される。
決定境界上の任意の2点を$x_A, x_B$としよう。$ y(x_A) = y(x_B) = 0$であるから

```math
\begin{align}

w^T x_A - w^T x_B &= 0 \\
w^T ( x_A - x_B) &= 0 \\

\end{align}

```

決定境界向きのベクトル$x_A - x_B$と重みベクトル$w$の内積が0であるから、ベクトル$w$は決定境界に直交する。（この性質は4.1.7節「パーセプトロン」で出てくる）

![キャプチャ37.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/f6fd0c6e-4553-164b-3c88-09a77cbf0691.png)

# 4.1.2 多クラス

$K=2$クラスの識別を$K>2$クラスへ拡張する。
3クラス以上に拡張する際に思いつく素朴な方法は、2クラス識別関数の組み合わせである。が、単純な組み合わせではうまくいかない。
まずはうまくいかない方法を見てから、うまくいく方法を見る。

### うまくいかない：1対他分類器

ある特定のクラス$C_k$に属するか否かという識別関数を$K-1$個利用する方法で1対他分類器[^3] (one-versus-the-rest classifier) と呼ばれる。この方法では下図の緑領域のように、どのクラスに識別すべきか曖昧な領域が存在するという問題がある。

![キャプチャ38.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/f5c1596b-9c17-410e-5d27-68e344a18d8a.png)

[^3]: ある特定の1クラスか、その他のクラスかの識別関数から成るので1対他分類器という名称

### うまくいかない：1対1分類器

クラス$i$かクラス$j$かを識別する関数を$ {}_K C_2 $個利用し、多数決によって識別する方法で1対1分類器と呼ばれる。この方法でも下図の緑領域のように、どのクラスに識別すべきか曖昧な領域が存在するという問題がある。

![キャプチャ39.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/11d70ad4-73ea-37b5-b645-fca041520ec6.png)

### うまくいく：K個の線形関数を用意

K個の関数を考える。

$$
y_k (x) = w_k^T x + w_{k0} \tag{4.9}
$$

すべての$ j \neq k$に対して$ y_k(x) > y_j(x) $であれば、入力$x$はクラス$C_k$に識別される。
つまり、$C_k$と$C_j$の決定境界は$ y_k(x) = y_j(x) $によって与えられる。

この方法により、どのクラスに識別すべきか曖昧な領域がなくなる。
下図のようにクラス$C_k$と識別される領域（決定領域）中の任意の2点$x_A, x_B$を考える。この2点を結ぶ直線上にある任意の点$ \hat{x} $は

$$
\hat{x} = \lambda x_A + (1 - \lambda), \quad 0 \leq \lambda \leq 1 \tag{4.11}
$$

である。両辺に$w_k^T$をかけて$w_{k0}$をかけると式(4.9)から

$$
y_k ( \hat{x} ) = \lambda y_k (x_A) + (1 - \lambda) y_K (x_B) \tag{4.12}
$$

2点$x_A, x_B$は決定領域$R_k$内にあるので、すべての$ j \neq k$に対して$ y_k(x_A) > y_j(x_A) , y_k(x_B) > y_j(x_B) $が成り立ち、$y_k( \hat{x_A} ) > y_j( \hat{x_B} ) $となる。
よって、任意の点$ \hat{x} $も$R_k$内にあり、すべてのクラスの決定境界の交点は上図にように1点となり、
どのクラスに識別すべきか曖昧な領域がなくなる。

![キャプチャ40.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/344c9911-8b13-8ce2-7d14-194bef5bf3c9.png)


# 4.1.3 分類における最小二乗

$K$クラス識別問題には$K$個の識別関数を用意すればうまくいくことが分かった。
では、識別関数の重みベクトル$w$を最小二乗法で求めてみよう。
（先に結論を言うと、最小二乗法によって求めた$w$は性能が全然よくない）

目標変数ベクトル$\mathbf{t}$は1-of-K符号化法を使って表記する。これは、ベクトルの長さはクラス数$K$で、クラスが$i$番目のクラス$C_i$の場合は$i$番目の要素が1、他はすべて0とするものである。
例えば、$K=5$で、クラス2の目標変数ベクトルは

$$
\mathbf{t} = (0,1,0,0,0)^T \tag{4.1}
$$

と表記される。
さて、上述のとおり各クラス$C_k$は各クラスごとの線形モデルで記述できる。

$$
y_k(x) = w_k^T x + w_{k0} \tag{4.13}
$$

ここで$k=1, \cdots, K$である。これらをひとまとめにすると

$$
y(x) = \tilde{W}^T \tilde{x} \tag{4.14}
$$

と書ける[^4]。この式の解釈は下図参照。

[^4]: 行列$W$の定義が各クラスの重みを列方向に置いたものとであるため、式(4.14)では行列$W$の転置をとるというややこしい表記になっている。これは後で出てくる$\tilde{W}$3.1.1節ででてきた$w$の最小二乗法による解（疑似逆行列）の表記とあわせるため

![キャプチャ41.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/8ea3a77f-05ec-7c97-c8b3-0ade48161488.png)

このとき、入力$x$は出力$y_k = \tilde{w_k}^T \tilde{x} $が最大となるクラスに割り当てられる。

3章の回帰の場合と同様に、二乗和誤差を最小化して重み行列$\tilde{W}$を求めよう。
学習データ集合$ \\{ \mathbf{x_n}, \mathbf{t_n} \\} (n=1, \cdots, N) $を考える。$n$番目の行がベクトル$\mathbf{t_n}^T$となる行列$T$、$n$番目の行が$\tilde{ \mathbf{x_n} }^T $となる行列$ \tilde{X} $を定義する。

![キャプチャ42.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/7281a6e1-893a-f15e-73f4-c52141113396.png)

線形モデルの出力$y_k$はデータ$x$がクラス$C_k$である事後確率$p(C_k | x)$となることを期待している。
行列$XW-T$の各要素はあるデータの教師値(0か1)と線形モデルの予測値の差となっていることが分かる。

![キャプチャ43.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/9fef68b3-8150-4fcd-c91c-cc3bb8106071.png)

さて、$p(C_i | x_j)$の予測値と教師値の差 [$j$番目のデータのクラス$i$に関する予測値と教師値の誤差] を$a_{ij}$とおこう。
クラス数が2、データ数が3のとき：

```math
\begin{align}

& (\tilde{X} \tilde{W} - T)^T (\tilde{X} \tilde{W} - T) \\
=& 

\begin{pmatrix}
a_{11} & a_{21} & a_{31}\\\
a_{12} & a_{22} & a_{32}
\end{pmatrix}

\begin{pmatrix}
a_{11} & a_{12} \\\
a_{21} & a_{22} \\\
a_{31} & a_{32}
\end{pmatrix}

\\
=&

\begin{pmatrix}
a_{11}^2 + a_{21}^2 + a_{31}^2 & \cdot \\\
\cdot         & a_{12}^2 + a_{22}^2 + a_{32}^2
\end{pmatrix}

\end{align}
```

となり、**行列の対角成分の和が、すべてのデータ/クラスに関する予測値と教師値の誤差の2乗になっている**ことが分かる。
よって二乗和誤差関数$E_D(\tilde{W})$は

$$
E_D(\tilde{W}) = \frac{1}{2} \mathrm{Tr} \left\\{ 
(\tilde{X} \tilde{W} - T)^T (\tilde{X} \tilde{W} - T)
\right\\}
\tag{4.15}
$$

やっと誤差関数が行列形式で書けたので、いつも通り(4.15)式の$\tilde{W}$に関する導関数＝０の方程式を解くと、以下の解が得られる（らしい）。

$$
\tilde{W} = (\tilde{X}^T \tilde{X} )^{-1} \tilde{X}^T T = \tilde{X}^{\dagger} T \tag{4.16} 
$$

ここで、$\tilde{X}^{\dagger}$は3.1.1節「最尤推定と最小二乗法」ででてきた擬似逆行列である。
結局、識別関数は以下の式で表現できる。

$$
y(x) = \tilde{W}^T \tilde{x} = T^T ( \tilde{X}^{\dagger} )^T \tilde{x} \tag{4.17}
$$

さて、この式により得られる決定境界を下図の緑線に示す。左図のように学習データが分布しているときは良好な決定境界が得られているが、右図のように決定境界から離れた位置に学習データがあると、決定境界が変わってしまうという問題がある。
1.2.5節「曲線フィッティング再訪」でみたように、最小二乗法は目標変数がガウス分布に従うという仮定のもとでの結果であった。
一方、本節で用いた目標変数ベクトルは0か1の二値であり、ガウス分布からかけ離れている。なので、うまく機能しない。


![キャプチャ44.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/140135/4db111c5-de30-56ee-8af4-4694b0b7d1e4.png)