PRMLの多項分類器について

Pattern Recognition and Machine Learning (Information Science and Statistics)

作者: Christopher Bishop
出版社/メーカー: Springer
発売日: 2010/02/15
メディア: ハードカバー
購入: 5人クリック: 67回
この商品を含むブログ (29件) を見る

PRML（↑）の「Chapter4 Linear Models for Classification」では、次のような多項分類器が紹介されています。

・ベクトル値のサンプル群 $\{\mathbf{x}_n\}_{n=0}^{N-1}$ をK個のクラス $\{C_k\}_{k=1}^{K}$ に分類します。

・各クラスを特徴づける線形関数（分類関数） $y_k(\mathbf{x})\, := \mathbf{w}_k^T\mathbf{x} + w_{0k} \, (k=1...K)$ を用意します。

・分類関数の値が最も大きいクラスに分類します。 $\mathbf{x} \in C_k \, \Leftrightarrow \, k = \arg\max_m\{y_m(\mathbf{x})\}$

この分類器の性質をちょっと調べてみます。

基本性質

分類関数 $y_k(\mathbf{x})\, := \mathbf{w}_k^T\mathbf{x} + w_{0k}$ において、 $\mathbf{w}_k$ は、 $y_k(\mathbf{x}) = {\rm const}$ で定義される超平面の法線ベクトルである事に注意します。サンプルのベクトル空間が2次元でクラス数が3個（ $K=3$ ）の場合を考えると、次のように分かりやすく図示できます。（この場合、 $y_k(\mathbf{x}) = {\rm const}$ は直線を表します。）

まず、2個の変数 $(x_1,\, x_2)$ を調整することで、必ず、 $y_1 = y_2 = y_3$ となる点を見つけることができます。この点は、3つの領域が接触する点となり、上図のようにY次型に平面が分割されます。この場合、各領域は、明らかに単連結な凸集合となりますが、一般の場合もこの性質（各領域は単連結な凸集合）は成り立ちます。（証明は、PRMLの(4.11)式あたりを参照。）

また、各領域の幅（Y字型の広がり具合）は、法線ベクトルの大きさで変わります。法線ベクトル $\mathbf{w_k}$ が大きいと、その方向に少し進むだけで $y_k$ の値が大きくなるので、Y字型の広がりは大きくなります。下図も参考にしてください。 $y_k$ の値を Δ だけ増加させるのに進む距離が短い（つまり、法線ベクトルが大きい）方向は、Y字型の広がりが大きくなります。

ただし、分類関数のとり方によっては、K個の分類関数を用意しても、必ずしもK個のクラスに分割されるわけではありません。つまり、特定の k について、 $y_k(\mathbf{x})$ を最大にする $\mathbf{x}$ が存在しない場合があります。自明な例としては、次が考えられます。

　 $y_1 = x_1, \,\,y_2 = x_2, \,\,y_3 = \frac{1}{2}(x_1+x_2)$
（平均値は最高値を越えることはありませんよね。）

また、 $K>3$ の場合は、すべての領域が1点で接触するとは限らず、次のような例も得られます。

　 $y_1=x_1,\,\,y_2=x_2,\,\,y_3=-0.1(x_1+x_2),\,\,y_4=-3(x_1+x_2)-3$

より一般的な議論は、こちらも参照してください。

最小二乗誤差によるフィッティング

K個のクラス $\{C_k\}_{k=1}^{K}$ を「1-of-K binary coding scheme」で表現したトレーニングデータ $(\mathbf{x}_n,\, \mathbf{t}_n)$ があるものとします。

「1-of-K binary coding scheme」というのは、k番目のクラスを $\mathbf{t}_n = (0,...0,1,0,...,0)$ （k番目の値のみが1）というベクトルで表現するものです。

この時、PRMLの「4.1.3 Least squares for classification」では、次のような誤差を定義して、これを最小にするという条件でパラメーター $(\mathbf{w}_k, w_{0k})$ をフィッティングするという学習手法を紹介しています。

$E_D\, := \frac{1}{2}\sum_{n=0}^{N}\{\mathbf{y}(\mathbf{x}_n)-\mathbf{t}_n\}^2$

※ $\mathbf{y}(\mathbf{x}_n)$ は、 $y_k(\mathbf{x}_n) \, (k=1,...,K)$ を並べたベクトル。

・・・が、これは、かなり酷いフィッティング方法です。

たとえば、2次元ベクトルのデータを2つのクラスに分類する場合で考えると、下図のように、分類関数の値 $(y_1,\, y_2)$ で張った平面において、トレーニングデータ（サンプル）から計算した点 $(y_1(\mathbf{x}_n),\, y_2(\mathbf{x}_n))$ と正しい分類値（(1,0)、もしくは、(0,1)）の二乗距離を誤差としています。

正しく分類された場合の方が誤差は小さくなりますが、たとえ正しく分類されていても、誤差そのものは非常に大きい値をとりえます。このため、 $(y_1(\mathbf{x}_n),\, y_2(\mathbf{x}_n))$ が(1,0)、もしくは、(0,1)から極端に外れるようなトレーニングデータがあると、それに過大に影響されます。つまり、「はずれ値」に対する耐性がなくなります。（PRMLのFigure4.4を参照。）

これは、次のように見ることもできます。まず、今の場合、サンプル値 $(x_1,\, x_2)$ とその分類関数値 $(y_1,\, y_2)$ は、次の線形変換によって紐づけられています。（変換行列の要素の定義は、よきに解釈してください。）

$\begin{pmatrix}y_1 \\ y_2\end{pmatrix}=\begin{pmatrix}w_{11}&w_{12} \\ w_{21}&w_{22}\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}+\begin{pmatrix}w_{01} \\ w_{02}\end{pmatrix}$

したがって、 $(x_1,\, x_2)$ 平面を $(y_1,\, y_2)$ 平面に線形変換した際に、 $(y_1,\, y_2)$ 平面における各クラスに属するトレーニングデータの（二乗距離の重みでの）重心が (1,0) と (0,1) に一致するように変換パラメーターが決定されます。また、この時の $(y_1,\, y_2)$ 平面における直線 $y_1 = y_2$ が分類結果の「境界線」になります。

つまり、「はずれ値」によって重心が大きく移動することで線形変換のパラメーターが変化して、「境界線」を踏み越えるデータ（つまり、誤分類されるデータ）が増えることになります。

Pandas&NumPyのコードで実際に数値シュミレーションした結果は次のようになります。

$y_1 = 1$ および $y_2 = 1$ の直線がちょうどデータ群の中央付近を通っていることが分かります。また、境界線では、 $y_1 = y_2 = 0.5$ となっているため、これから逆算すると、 $y_1 = 1$ の直線上では $y_2 = 0$ 、あるいは、 $y_2 = 1$ の直線上では $y_1 = 0$ であることも分かります。つまり、データ群の中央付近がまさに、(1,0) と (0,1) に一致しています。

なお、 $(x_1,\, x_2)$ 平面上の直線が $(y_1,\, y_2)$ 平面上の点 (1,0), (0,1) に一致するというのは、前述の線形変換が縮退しているということです。実際の計算で得られた $\begin{pmatrix}w_{11}&w_{12} \\ w_{21}&w_{22}\end{pmatrix}$ の例を下記に示します。すべて、行列式が 0 になっていることが分かります。

[[ -0.25050301  0.23878218 ]
 [  0.25050301 -0.23878218 ]]
[[ -0.25216085  0.2360489 ]
 [  0.25216085 -0.2360489 ]]
[[ -0.2285789   0.23445006 ]
 [  0.2285789  -0.23445006 ]]

３クラスの分類問題

PRMLのFigure4.5では、上述のフィッティング手法で、3つのクラスからなる2次元のデータ群を分類する例に触れています。下図のように、3つのクラスのデータがほぼ並行にならんでいます。

ただし、この分類器では必ず「Y字型」の領域に分類されますので、うまく分類するには、上図のように、1つの領域が細長くのびて、3領域がまじわる点（以下「交点」）から遠くの方にデータ群が配置されるようにフィッティングされる必要があります（以下、「理想配置」と呼びます。）・・・が、残念ながら、上記の「最小二乗誤差によるフィッティング」では、このような「理想配置」は実現できません。この理由をちょっとがんばって、半直感的（？）に説明してみます。

まず、冒頭の議論から分かるように、1つの領域が細長くのびるということは、この方向の法線ベクトルの値が「非常に小さい」ということを意味します。

$|\mathbf{w_2}| \, \ll \, |\mathbf{w_1}|,\, |\mathbf{w_3}|$