PRMLの多項分類器の分類クラスが空にならない条件について

「PRMLの多項分類器について」で紹介した、下記の多項分類器があります。

ベクトル値のサンプル群 $\{\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})\}$

この分類器は、あるクラスに属する点の集合が空になることがあります。その条件について考えます。

D次元空間の点を(D+1)個のクラスに分類する場合

この場合、ある前提の下に、すべてのクラスが必ず空にならない事が示せます。

命題
法線ベクトルの集合 $\{\mathbf{w}_k\}_{k=1}^{D+1}$ が、すべての $1 \leq j \leq D$ について、「 $j$ を固定した場合に、D個のベクトル $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ は一次独立である」という条件を満たすものとする。この時、各クラスに属する点の集合は、空になることはない。（そのクラスに属する点は必ず存在する。）

（証明）

任意の $j$ を固定して考えた際に、 $\forall k \ne j;\,\,y_j(\mathbf{x}) - y_k(\mathbf{x}) > 0$ を満たす $\mathbf{x}$ が存在することを示す。

$y_j(\mathbf{x}) - y_k(\mathbf{x}) = (\mathbf{w}_j - \mathbf{w}_k)\cdot\mathbf{x} + (w_{0j} - w_{0k})$

これより、 $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ 内のすべての元に対して、 $(\mathbf{w}_j - \mathbf{w}_k)\cdot\mathbf{x}_0 > 0$ となる $\mathbf{x}_0$ が存在したとすると、十分大きな $\alpha$ を用いて、 $\mathbf{x} = \alpha\mathbf{x}_0$ が求める $\mathbf{x}$ となることが分かる。

今、 $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ は、D次元空間のD個の一次独立なベクトルであるので、これらが張る超平面を考えて、その（大きさ1の）法線ベクトル $\mathbf{n}$ を取れば、 $(\mathbf{w}_j - \mathbf{w}_k)\cdot\mathbf{n} = 1$ が成立する。これが求める $\mathbf{x}_0$ に他ならない。

超平面を用いた幾何学的な議論が腑に落ちない場合は、D次元空間の直行基底で成分表示して考えるとよい。

$\mathbf{w}_j - \mathbf{w}_k = (d_{k1},d_{k1},...,d_{kD}),\,\,\mathbf{n} = (n_1,...,n_D)$

この時、 $\forall k \ne j;\,\,(\mathbf{w}_j - \mathbf{w}_k)\cdot\mathbf{n} = 1$ は次の線形方程式となり、 $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ が一次独立であることから、単一解を持つことが保証される。

$\begin{pmatrix}d_{11}&\dots&d_{1D}\\\vdots&(j \ne k)&\vdots\\d_{j1}&\dots&d_{jD}\end{pmatrix}\begin{pmatrix}n_1 \\ \vdots \\ n_D\end{pmatrix}=\begin{pmatrix}1 \\ \vdots \\ 1\end{pmatrix}$

（証明終）

ちなみに、「PRMLの多項分類器について」では、2次元平面を3つのクラスに分割する例で、1つのクラスが空になる次の例をあげました。

　 $y_1 = x_1, \,\,y_2 = x_2, \,\,y_3 = \frac{1}{2}(x_1+x_2)$

実は、これは、上記の命題の前提が成り立たない特殊な例になります。

$\mathbf{w}_1 = (1,\,0),\,\,\mathbf{w}_2 = (0,\,1),\,\,\mathbf{w}_3 = (\frac{1}{2},\,\frac{1}{2})$ より、 $\mathbf{w}_1 - \mathbf{w}_3 = (\frac{1}{2},\,-\frac{1}{2}),\,\,\mathbf{w}_2 - \mathbf{w}_3 = (-\frac{1}{2},\,\frac{1}{2})$ で、 $\mathbf{w}_1 - \mathbf{w}_3$ と $\mathbf{w}_2 - \mathbf{w}_3$ が一次独立になりません。

$y_3 = \frac{1}{3}(x_1+x_2)$ 、あるいは、 $y_3 = \frac{2}{3}(x_1+x_2)$ のように少しだけ係数を変化させると、前提が成立して、平面は3つのクラスに分割されるようになります。次の比較図をみると様子がよく分かります。

D次元空間の点を(D+2)個のクラスに分類する場合

先ほどの命題からもうひとつクラスを増やすと、属する点の集合が空になるクラスが存在することがあります。D次元空間ですので、「任意の $j$ について(D+1)個のベクトル $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ は一次独立である」という前提を満たすことは当然できませんが、「任意の $j$ について(D+1)個のベクトル $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ は互いに独立である（並行なものは存在しない）」という少しゆるめた条件下でも、属する点の集合が空になるクラスを持つものが構成できます。以下に具体例を示します。

はじめに、D次元空間の直行単位基底を $\{\mathbf{e}_i\}_{i=1}^D$ として、次の法線ベクトルを用意します。

$\mathbf{w}_{D+1}\, := 2\mathbf{e}_1$

これを元にして、残りの法線ベクトルを次のように定義します。

$\mathbf{w}_i\, := \mathbf{w}_{D+1}-\mathbf{e}_i$ 　 $(i=1...D)$

$\mathbf{w}_{D+2} := \frac{1}{D}\sum_{j=1}^{D}(\mathbf{w}_j+2\mathbf{e}_j)$

ここで、 $y_{D+1}$ で定義されるクラスに属する点の条件に注目します。まず、 $y_1,\,...,\,y_D$ との比較を考えると、

$y_{D+1}(\mathbf{x}) - y_i(\mathbf{x}) = (\mathbf{w}_{D+1}-\mathbf{w}_i) \cdot \mathbf{x}= \mathbf{e}_i \cdot \mathbf{x} = x_i$

したがって、 $y_{D+1}(\mathbf{x}) - y_i(\mathbf{x}) > 0\,\,\Leftrightarrow\,\,x_i > 0$ ---- (1)

一方、 $\mathbf{w}_i$ の定義より、 $\mathbf{w}_{D+1} = \frac{1}{D}\sum_{j=1}^D(\mathbf{w}_j+\mathbf{e}_j)$ と書けることに注意して、 $y_{D+2}$ と比較すると、

$y_{D+1}(\mathbf{x}) - y_{D+2}(\mathbf{x}) = -\frac{1}{D}\sum_{j=1}^D\mathbf{e}_j\cdot\mathbf{x} = -\frac{1}{D}\sum_{j=1}^Dx_j$ ---- (2)

ここで、(1)(2)を比較すると、 $y_{D+1}(\mathbf{x}) - y_i(\mathbf{x}) > 0$ かつ $y_{D+1}(\mathbf{x}) - y_{D+2}(\mathbf{x}) > 0$ を満たす $\mathbf{x}$ は存在しないことが分かります。

ここまでの議論は、 $\mathbf{w}_{D+1}$ の具体的なとり方に依存しません。最後に、(D+1)個のベクトル $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ が互いに独立になることを確認するために、 $\mathbf{w}_{D+1}\, := 2\mathbf{e}_1$ という具体的な定義にもとづいて、各法線ベクトルを次のように書き下します。

$\mathbf{w}_{D+1}\, = 2\mathbf{e}_1$

$\mathbf{w}_i\, = 2\mathbf{e}_1-\mathbf{e}_i$

$\mathbf{w}_{D+2} = 2\mathbf{e}_1+\frac{2}{D}\sum_{j=1}^D\mathbf{e}_j$

これより、前述の「互いに独立である」という条件が成り立つことも確認できます。

ちなみに $D=3$ の場合を図示すると、次のようになります。

$\left\{\mathbf{w}_{D+1}-\mathbf{w}_i\right\}_{i=1}^D = \left\{\mathbf{e}_i\right\}_{i=1}^D$ との内積をすべて正にするベクトル（たとえば、超平面に対する法線ベクトル）は、これらが張る「D角錐」の内部方向を向いていますが、このようなベクトルは、 $\mathbf{w}_{D+1}-\mathbf{w}_{D+2}$ との内積は必ず負になることを示しています。ここで用意した法線ベクトル群 $\{\mathbf{w}\}$ は、この図を作るように逆算して構成したものにすぎません。

任意の数のクラス数への分類

前述の説明は、「法線ベクトルのとり方によっては、空になるクラスが存在する」ということを主張するものでしたが、一方で、法線ベクトルのとり方によっては、任意の数の空にならないクラスに分類することも可能です。一般のD次元空間で、原点と半径1の超球面の表面を結ぶ、任意の数の（互いに独立な）法線ベクトル群 $\{\mathbf{w}_k\}$ を用意すると、すべての $1 \leq j \leq D$ について、

「 $j$ を固定した場合に、 $\{\mathbf{w}_j - \mathbf{w}_k\}_{k \ne j}$ 内のすべての元に対して、 $(\mathbf{w}_j - \mathbf{w}_k)\cdot\mathbf{x}_0 > 0$ となる $\mathbf{x}_0$ が存在する」

という条件が満たされます。（2次元か3次元の例で想像してみてください。）この時、冒頭の命題の証明（前半部分）を思い出すと、これらが分類するクラスはすべて空にならないことが分かります。

下記は、2次元の場合に、10本の法線ベクトルをきれいに円形にならべた場合の例になります。