めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

PRMLの多項分類器について

Pattern Recognition and Machine Learning (Information Science and Statistics)

Pattern Recognition and Machine Learning (Information Science and Statistics)

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 ]]

3クラスの分類問題

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

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

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

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

一方、上図のような「理想配置」において、C_2 のデータ群付近(重心付近)では、y_2 \simeq 1 と期待されます。それでは、この状態で、C_1,\, C_3 のデータ群付近では、y_1,\, y_3 の値はどうなっているでしょうか?

下図から分かるにように・・・、

どうがんばっても、y_1 > 1,\, y_3 > 1 となり、これらのデータは大きな誤差を与えることになります。

先ほどのコードで数値シュミレーションすると、下図のように、交点付近にデータ群があつまることになります。2種類の結果を示します。

y = 0.5y = 1 の直線を示してあるので、これから脳内で線形補完すると、どちらも、だいたい次のような状態になっています。

・交点付近(つまりC_2データ群の重心付近)では、y_1=y_2=y_3 \simeq 0.3

C_1データ群の重心付近では、y_1 \simeq 0.7,\, \,y_2 \simeq 0,\, y_3 \simeq 0

C_3データ群の重心付近では、y_3 \simeq 0.7,\, \,y_1 \simeq 0,\, y_2 \simeq 0

つまり、C_1,\, C_3 のデータについては誤差が0に近くなるように最適化されて、一方、C_2 については、y_1=y_2=y_3 \simeq 0.3 で、誤差はあるものの、極端に大きな誤差とはならないように、最適化されているようです。