めもめも

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

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本の法線ベクトルをきれいに円形にならべた場合の例になります。

調子にのって、100分割ぐらいするとこうなります(笑)。