KL展開分散最大基準　解の導出 - 機械学習に詳しくなりたいブログ

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

解の導出

$D$ 次元から $D^{\prime}$ 次元へKL展開することを考えます。 $D^{\prime}$ 次元の正規直交基底を $D$ 次元ベクトルで表したものを $\mathbf{u}_1,\mathbf{u}_2, \cdots , \mathbf{u}_{D^{\prime}}$ とすると、データ $\mathbf x$ の $D$ 次元→ $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*}$

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

以上より、求める解は

$\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)を満たすのですから、この極値の中で最大となるものを選択すれば良いはずです。したがって、 $\Sigma$ の $D$ 個の固有値の中から、大きいものから $D^{\prime}$ 個採用し、それに対応する固有ベクトルを並べたものが求める $\mathbf A$ です。

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