機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100%趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

KL展開 分散最大基準 解の導出

分散最大基準のKL展開の解を導出します。次元削減後の分散を最大にするような射影を求めることが目的です。手法の概要と実験結果はKL展開 分散最大基準です。

解の導出

D次元からD^{\prime}次元へKL展開することを考えます。D^{\prime}次元の正規直交基底をD次元ベクトルで表したものを\mathbf{u}_1,\mathbf{u}_2, \cdots , \mathbf{u}_{D^{\prime}}とすると、データ\mathbf xD次元→D^{\prime}次元への変換は、


\mathbf y = \mathbf A^{T} \mathbf x \tag{1}

で与えられます。ここで\mathbf A = (\mathbf{u}_1,\mathbf{u}_2, \cdots , \mathbf{u}_{D^{\prime}})です。また、正規直交性より


\mathbf A^{T} \mathbf A = \mathbf I \tag{2}

が成り立ちます。

D^{\prime}次元に変換されたデータ\mathbf yの分散は、データ数をnとすれば


\displaystyle \sigma^2 = \frac{1}{n} \sum_{\mathbf y \in C_{D^{\prime}}} (\mathbf y - \mathbf m^{\prime})^{T}(\mathbf y - \mathbf m^{\prime}) \tag{3}

です。ここで\mathbf m^{\prime}\mathbf yの平均ベクトルで、C_{D^{\prime}}\mathbf yの集合です。\mathbf xの平均ベクトルを\mathbf mとすれば、\mathbf m^{\prime} = \mathbf A^{T} \mathbf mが成り立ちます。この関係と式(1)を式(3)に代入すれば、以下のように計算できます。


\begin{eqnarray*}
\sigma^2&=& \frac{1}{n} \sum_{\mathbf x \in C_{D}}( \mathbf A^{T} \mathbf x - \mathbf A^{T} \mathbf m)^{T}( \mathbf A^{T} \mathbf x -\mathbf A^{T} \mathbf m) \tag{4} \\
&=&  \frac{1}{n} \sum_{\mathbf x \in C_{D}} \mathrm{Tr} \left\{  \mathbf A^{T} (\mathbf x -  \mathbf m) \right\} \left\{  \mathbf A^{T} (\mathbf x - \mathbf m) \right\}^{T} \tag{5} 
\end{eqnarray*}

式(4)から式(5)の変形には、行列の内積とトレースの式(11)を使っています。ここで転置行列の定理を使えば、さらに以下のように計算できます。


\begin{eqnarray*}
\sigma^2&=& \frac{1}{n}  \sum_{\mathbf x \in C_{D}} \mathrm{Tr} \left\{ \mathbf A^{T}  ( \mathbf x -  \mathbf m) (\mathbf x - \mathbf m) ^{T} ) \mathbf A \right\}  \tag{6} \\
&=& \mathrm{Tr} \left\{\mathbf A^{T}  \frac{1}{n} \left(  \sum_{\mathbf x \in C_{D}}    ( \mathbf x -  \mathbf m) (\mathbf x - \mathbf m) ^{T} \right) \mathbf A \right\}  \tag{7}
\end{eqnarray*}

ここで式(7)の和の演算部分は、分散共分散行列の定義そのものですから、これを\Sigmaとすれば、


\displaystyle \sigma^2 =  \mathrm{Tr} (\mathbf A^{T} \Sigma \mathbf A ) \tag{8}

となります。和の演算と分散共分散行列がどちらも\Sigmaでややこしいですが。

さて、次元削減後の分散を最大にする射影\mathbf A を求めることが目的でした。\mathbf A は式(2)の関係がありましたから、この条件下における式(8)の極値を求めるにはラグランジュの未定乗数法を用います。ここで


\mathbf{\Lambda} = 
\left(
    \begin{array}{cccc}
      \lambda_1 &  & & 0 \\
       & \lambda_2 &  & \\
       &  & \ddots &  \\
       0 &  &  & \lambda_{D^{\prime}}
    \end{array}
  \right) \tag{9}

を用いれば、複数制約条件のラグランジュの未定乗数法により


L(\mathbf A) = \mathrm{Tr}(\mathbf A^{T} \Sigma \mathbf A) - \mathrm{Tr} \left\{ (\mathbf A^{T} \mathbf A - \mathbf I ) \mathbf{\Lambda} \right\} \tag{10}

を解けばよいことになります。制約条件の項はひと目でわかりにくいですが、書き出してみれば確かに複数の制約条件式であることがわかります。式(10)を\mathbf Aで偏微分すれば、


\begin{eqnarray*}
\displaystyle \frac{\partial L}{\partial \mathbf A} &=& (\Sigma^{T} + \Sigma)\mathbf A - 2 \mathbf A \mathbf{\Lambda}  \tag{11} \\
&=& 2 \Sigma \mathbf A - 2 \mathbf A \mathbf{\Lambda}  \tag{12}
\end{eqnarray*}

となります。前半の項は行列の微分(2)で求めた関係を使いました。後半の項はトレースの計算を書き出せば確認できます。書き出さなくても行列の計算に慣れている人ならひと目なんでしょうね。

以上より、求める解は


\mathbf A^{T} \Sigma \mathbf A =\mathbf{\Lambda} \tag{13}

となります。*1 ここで\Sigmaは分散共分散行列ですから対称行列です。そして対称行列の対角化より、式(13)における\mathbf Aは、\Sigmaを対角化する行列であることがわかります。また、このときの固有値は\mathbf{\Lambda}の対角成分で、\mathbf Aは対応する固有ベクトルを並べた行列です。いま、求めたいものは \mathrm{Tr} (\mathbf A^{T} \Sigma \mathbf A ) を最大にする\mathbf Aでした。そしてこれが式(13)より、固有値の和であることがわかります。つまり極値をとる点では、式(13)を満たすのですから、この極値の中で最大となるものを選択すれば良いはずです。したがって、\SigmaD個の固有値の中から、大きいものからD^{\prime}個採用し、それに対応する固有ベクトルを並べたものが求める\mathbf Aです。

*1:このとき最小値ではなく最大値と捉えてよいのはなぜだっけコメント頂いて解決しました!