線形判別法におけるクラス間変動行列の階数と定値性

「わかりやすいパターン認識」p.118で、クラス内変動行列の逆行列とクラス間変動行列の積 ${\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B\boldsymbol{A}={\lambda}\boldsymbol{A}$ の固有値を求めていますが、$\boldsymbol{S}_B$の非負定値性と階数がどのように固有値問題に関連するかは明記されていません。そこで、本記事はその消息を明らかにします。 記号の定義は「わかりやすいパターン認識」から流用しています。また、簡単のためクラス数$c=2$としていますが、一般の次元についても同じ議論ができます。


まず、$\boldsymbol{S}_B$が非負定値であることを証明する。定義から $${\boldsymbol{S}_B}\overset{\textrm{def}}{=}\sum_{i=1,2}^{}{n_i}({\boldsymbol{m}_i}-\boldsymbol{m})({\boldsymbol{m}}_i-\boldsymbol{m})^t$$ であり、$\boldsymbol{S}_B$が $$\boldsymbol{S}_B= \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}}) & ({\boldsymbol{m}_2}-{\boldsymbol{m}})\\ \end{bmatrix} \begin{bmatrix} n_1 & 0\\ 0 & n_2\\ \end{bmatrix} \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}})^t\\ ({\boldsymbol{m}_2}-{\boldsymbol{m}})^t\\ \end{bmatrix} \tag{1}$$ と書けることに注意する。 $$\boldsymbol{D}^{\frac{1}{2}}\overset{\textrm{def}}{=} \begin{bmatrix} \sqrt{n_1} & 0\\ 0 & \sqrt{n_2}\\ \end{bmatrix},$$ $$\boldsymbol{A}\overset{\textrm{def}}{=} \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}})^t\\ ({\boldsymbol{m}_2}-{\boldsymbol{m}})^t\\ \end{bmatrix}$$ とおくと、 $$\begin{eqnarray*} \boldsymbol{S}_B&=&\boldsymbol{A}^{t}\boldsymbol{D}^{\frac{1}{2}}\boldsymbol{D}^{\frac{1}{2}}\boldsymbol{A}\\ &=&\boldsymbol{A}^{t}{(\boldsymbol{D}^{\frac{1}{2}})}^{t}\boldsymbol{D}^{\frac{1}{2}}\boldsymbol{A}\\ &=&{(\boldsymbol{D}^{\frac{1}{2}}\boldsymbol{A})}^{t}\boldsymbol{D}^{\frac{1}{2}}\boldsymbol{A}\\ \end{eqnarray*}$$ と分解できるので、$\boldsymbol{S}_B$は非負定値である。


$(2 \times 2)$行列$\boldsymbol{S}_B$の階数はたかだか$1$である。実際、式(1)より $$\rm{rank}(\boldsymbol{S}_B)\leq\min\{ \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}}) & ({\boldsymbol{m}_2}-{\boldsymbol{m}})\\ \end{bmatrix}, \begin{bmatrix} n_1 & 0\\ 0 & n_2\\ \end{bmatrix}, \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}})^t\\ ({\boldsymbol{m}_2}-{\boldsymbol{m}})^t\\ \end{bmatrix} \}$$ である。 $$\rm{rank}( \begin{bmatrix} n_1 & 0\\ 0 & n_2\\ \end{bmatrix}) =2$$ であり、 $$\rm{rank}( \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}}) & ({\boldsymbol{m}_2}-{\boldsymbol{m}})\\ \end{bmatrix} )=\rm{rank}( \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}})^t\\ ({\boldsymbol{m}_2}-{\boldsymbol{m}})^t\\ \end{bmatrix} )$$ であることを利用すると、$\boldsymbol{S}_B$の階数は $\rm{rank}( \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}}) & ({\boldsymbol{m}_2}-{\boldsymbol{m}})\\ \end{bmatrix} )$以下になるはずである。$\{\boldsymbol{m}_1-\boldsymbol{m}, \boldsymbol{m}_2-\boldsymbol{m}\}$には、自明でない線型関係 $$\begin{eqnarray*} n_1(\boldsymbol{m}_1-\boldsymbol{m})+n_2(\boldsymbol{m}_2-\boldsymbol{m})&=&n_1\boldsymbol{m}_1+n_2\boldsymbol{m}_2-(n_1+n_2)\boldsymbol{m}\\ &=&n_1\boldsymbol{m}_1+n_2\boldsymbol{m}_2-(n_1+n_2)\frac{n_1\boldsymbol{m_1}+n_2\boldsymbol{m_2}}{n_1+n_2}\\ &=&0 \end{eqnarray*}$$ が成り立つので、$\{\boldsymbol{m}_1-\boldsymbol{m}, \boldsymbol{m}_2-\boldsymbol{m}\}$は線型従属であり $\rm{rank}( \begin{bmatrix} ({\boldsymbol{m}_1}-{\boldsymbol{m}}) & ({\boldsymbol{m}_2}-{\boldsymbol{m}})\\ \end{bmatrix} )$ は1以下となる。一般に、$\rm{rank}(\boldsymbol{S}_B){\leq}c-1$が成り立つ。


以上で$\boldsymbol{S}_B$が非負定値かつ階数$c-1$以下であることが示せた。$\rm{rank}({\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B){\leq}\rm{rank}(\boldsymbol{S}_B){\leq}c-1$であることからは、${\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B\boldsymbol{A}={\lambda}\boldsymbol{A}$の解として最大$c-1$個のnonzero固有値が得られることが分かる: ${\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B$を$\mathbb{C}^d\rightarrow\mathbb{C}^d$の線形写像としてみると、階数・退化次数の定理より $$\rm{rank}({\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B)=d-\rm{dim\,ker}\,{\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B \tag{2}$$ が成り立つ。$\rm{ker}\,{\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B=\{\boldsymbol{A}\in\mathbb{C}^d:{\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B\boldsymbol{A}=0=0\boldsymbol{A}\}$であるので、この$\boldsymbol{A}$はゼロ固有値の固有ベクトルとなっている。よって$\rm{dim\,ker}\,{\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B\leq$(重複度込みの)ゼロ固有値の数 となる。これと(2)を組み合わせると、 $$\rm{rank}({\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B)=d-\rm{dim\,ker}\,{\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B\geq{d}-\rm{ゼロ固有値の数}=\rm{nonzero固有値の数}$$ となり、所望の結果が得られた。


最後に、$\boldsymbol{S}_B$の非負定値性が「固有値問題${\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B\boldsymbol{A}={\lambda}\boldsymbol{A}$の解が、すべて非負となる(したがって特に実数となる)」ことを担保していることを示す。対称行列$\boldsymbol{S}_B$を次のように対角化する。 $$\boldsymbol{S}_B=\boldsymbol{U}\Lambda\boldsymbol{U}^t.$$ ここで、$\boldsymbol{U}$は$\boldsymbol{S}_B$の正規化した固有ベクトルを並べた直行行列、$\Lambda$は$\boldsymbol{S}_B$を固有値を対角成分に持つ対角行列である。$\boldsymbol{S}_B$の非負定値性により$\Lambda$の対角成分はすべて非負であるので、$\boldsymbol{S}_B$を以下のように分解できる。 $${\boldsymbol{S}_B}^{\frac{1}{2}}\overset{\rm{def}}{=}\boldsymbol{U}{\Lambda}^{\frac{1}{2}}\boldsymbol{U}^t.$$ (定義の仕方により${\boldsymbol{S}_B}^{\frac{1}{2}}{\boldsymbol{S}_B}^{\frac{1}{2}}=\boldsymbol{S}_B$が成り立つ)。 $${\boldsymbol{S}_W}^{-1}\boldsymbol{S}_B\boldsymbol{A}={\boldsymbol{S}_W}^{-1}{\boldsymbol{S}_B}^{\frac{1}{2}}{\boldsymbol{S}_B}^{\frac{1}{2}}\boldsymbol{A}={\lambda}\boldsymbol{A}$$ の左から${\boldsymbol{S}_B}^{\frac{1}{2}}$をかけて、${\boldsymbol{S}_B}^{\frac{1}{2}}\boldsymbol{A}=\boldsymbol{A}’$と定義すると $${\boldsymbol{S}_B}^{\frac{1}{2}}{\boldsymbol{S}_W}^{-1}{\boldsymbol{S}_B}^{\frac{1}{2}}\boldsymbol{A}’={\lambda}\boldsymbol{A}’ \tag{3}$$ が得られる。${\boldsymbol{S}_B}^{\frac{1}{2}}$と${\boldsymbol{S}_W}^{-1}$は対称行列なので${\boldsymbol{S}_B}^{\frac{1}{2}}{\boldsymbol{S}_W}^{-1}{\boldsymbol{S}_B}^{\frac{1}{2}}$も対称行列であり、固有値がすべて実数になることが分かった。また、${\boldsymbol{S}_W}$は${\boldsymbol{S}_B}$と同じ手続きで半正定値であることが示せるので、${\boldsymbol{S}_W}=\boldsymbol{V}^t\boldsymbol{V}$と分解できる。よって${\boldsymbol{S}_W}$が正則だと仮定すると、${\boldsymbol{S}_W}^{-1}=\boldsymbol{V}^{-1}{(\boldsymbol{V}^{-1})}^t$であり、 $$\rm{(3)の左辺}={\boldsymbol{S}_B}^{\frac{1}{2}}\boldsymbol{V}^{-1}{(\boldsymbol{V}^{-1})}^t{\boldsymbol{S}_B}^{\frac{1}{2}}={({(\boldsymbol{V}^{-1})}^t{\boldsymbol{S}_B}^{\frac{1}{2}})}^t{(\boldsymbol{V}^{-1})}^t{\boldsymbol{S}_B}^{\frac{1}{2}}$$ と書ける。以上より${\boldsymbol{S}_B}^{\frac{1}{2}}{\boldsymbol{S}_W}^{-1}{\boldsymbol{S}_B}^{\frac{1}{2}}$は半正定値であるので、固有値問題の解はすべて非負となる。

まとめ。クラス数$c$の線形判別法を考えたとき、①$\boldsymbol{S}_B$の階数がたかだか$c-1$であることは得られるnonzero固有値の数が$c-1$以下であることを、②$\boldsymbol{S}_B$の非負定値性は固有値がすべて非負になることをそれぞれ示唆しています。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です