特徴量の次元を低下させるとか(3) - らんだむな記憶の続き。
「元データの情報を極力壊さずに次元を低下させたい」⇒「$\mathcal{V}_k$がそのような空間」を検証したい。
Amazon.co.jp： Pattern Recognition and Machine Learning (Information Science and Statistics): Christopher Bishop: 洋書の12.1.2がちゃんとした議論だが、これを改悪する形でなんとなく確認する。
$(x_1,\ \cdots,\ x_m),\ x_n \in \mathbb{R}^d,\ 1 \le n \le m $を特徴量のデータとし、$\frac{1}{m}\sum_{n = 1}^m x_n = 0$とする。
$k < d$とし、$k$次元部分空間の点で元データを近似した時にもっともよく近似できるようなものを探したい。ここで、そのような "部分空間" は原点を通るか非自明だが、ここでは通ることにしてしまう。(実際、$\frac{1}{m}\sum_{n = 1}^m x_n = 0$の場合には通る。)
$k$次元部分空間を張る正規直交系を$\{u_1,\ \cdots,\ u_k \}$とする。各$x_n$を
\begin{equation}
\widetilde{x_n} = \sum_{j=1}^k z_{n,j} u_j
\end{equation}
で近似したい。
\begin{equation}
J = J(z_{1,1},\ z_{1,2},\ \cdots,\ z_{1,k},\ \cdots,\ z_{n,j},\ \cdots,\ z_{m,k}) = \frac{1}{m} \sum_{n=1}^m |x_n - \widetilde{x_n}|^2
\end{equation}
が最小になるようにしたい。
$\{ u_j \}_{j=1}^k$を固定する時、係数$z_{n,j}$はどのように選ぶと$J$は最小値をとるか？このため、$\nabla_z J = 0$を考える。
$\frac{\partial J}{\partial z_{n,j}} = 0$を計算する。
\begin{align}
\frac{\partial J}{\partial z_{n,j}} &= \frac{\partial}{\partial z_{n,j}} \frac{1}{m} \sum_{\ell=1}^m \left\langle \sum_{i=1}^k z_{\ell,i} u_i - x_\ell,\ \sum_{i^\prime=1}^k z_{\ell,i^\prime} u_{i^\prime} - x_\ell \right\rangle \\
& = \frac{2}{m} \left\langle \sum_{i=1}^k z_{n,i} u_i - x_n,\ u_j \right\rangle = \frac{2}{m} (z_{n,j} - \langle x_n,\ u_j \rangle) = 0
\end{align}
なので、$z_{n,j} = \langle x_n,\ u_j \rangle$となることが分かった。つまり、
\begin{equation}
\widetilde{x_n} = \sum_{j=1}^k \langle x_n,\ u_j \rangle u_j \hspace{5em} (1)
\end{equation}
である。
次に、どういう$\{ u_j \}_{j=1}^k$をとると、$J$が小さくなるか？を調べたい。
$\{ u_j \}_{j=1}^k$をGram-Schmidtの直交化法で$\mathbb{R}^d$の正規直交基底$\{ u_j \}_{j=1}^d$にまで拡張する。
この時、$x_n = \sum_{j=1}^d \langle x_n,\ u_j \rangle u_j$と展開できるので、$\langle u,\ v \rangle = v^T u = u^T v$に注意して、
\begin{align}
J &= \frac{1}{m} \sum_{n=1}^m \sum_{j > k} |\langle x_n,\ u_j \rangle u_j|^2 \\
& = \frac{1}{m} \sum_{n=1}^m \sum_{j > k} |\langle x_n,\ u_j \rangle|^2 \\
& = \frac{1}{m} \sum_{n=1}^m \sum_{j > k} (x_n^T u_j)\cdot(x_n^T u_j) \\
& = \frac{1}{m} \sum_{n=1}^m \sum_{j > k} (u_j^T x_n)\cdot(x_n^T u_j) \\
& = \sum_{j > k} u_j^T \left(\frac{1}{m} \sum_{n=1}^m x_n x_n^T \right) u_j = \sum_{j > k} u_j^T S u_j \hspace{5em} (2)
\end{align}
を得る。ここで$S := \frac{1}{m} \sum_{n=1}^m x_n x_n^T$は以前、天下り的に登場した共分散行列である。前回と同様にこれは対称半正定値行列であり直交行列で対角化可能である。
$S$を対角化する直交行列を$V$として、
\begin{equation}
S = V^T
\begin{pmatrix}
\lambda_1 & & \\
& \ddots & \\
& & \lambda_d
\end{pmatrix}
V
\end{equation}
となるとする。ここで、$\lambda_1 \ge \cdots \ge \lambda_d \ge 0$と並ぶようにする。
$v_j := V u_j$とおくと、$\{ v_j \}_{j=1}^d$もまた、$\mathbb{R}^d$の正規直交基底になることに注意する。この時、
\begin{equation}
\sum_{j > k} u_j^T S u_j = \sum_{j > k} v_j^T
\begin{pmatrix}
\lambda_1 & & \\
& \ddots & \\
& & \lambda_d
\end{pmatrix}
v_j
\end{equation}
であるが、これはどのくらい小さくできるだろうか？
ここで、本来はLagrangeの未定乗数法を使うべきだが、適当にお茶を濁す。
$e_1 = (1,\ 0,\ 0, \cdots,\ 0)^T,\ e_2 = (0,\ 1,\ 0, \cdots,\ 0)^T,\ e_3 = (0,\ 0,\ 1, \cdots,\ 0)^T,\ \cdots$を$\mathbb{R}^d$の標準基底として、$v_j = e_j\ (j > k)$の時に
\begin{equation}
\sum_{j > k} e_j^T
\begin{pmatrix}
\lambda_1 & & \\
& \ddots & \\
& & \lambda_d
\end{pmatrix}
e_j = \sum_{j > k} \lambda_j
\end{equation}
となって最小になる。あまりに適当で後ろめたいので言い訳的な補足。$\alpha_1^2 + \cdots + \alpha_d^2 = 1$の時$\lambda_1 \alpha_1^2 + \cdots + \lambda_d \alpha_d^2 \ge \lambda_d$ということに注意すると、$v_d$をできるだけ小さい固有値の固有空間、つまり$\lambda_d$の固有空間に押し込められるほうが良いことが分かる。これで$\lambda_d$の固有空間が占有されたので、$v_{d - 1}$は次に小さい固有値$\lambda_{d - 1}$の固有空間に押し込めて... と順に小さい固有値の固有空間に押し込んでいくのである。
ということで(2)に戻ると、
\begin{equation}
\min_{\{ u_j \}} \sum_{j > k} u_j^T S u_j = \sum_{j > k} \lambda_j
\end{equation}
が分かった、ことにする。ではこれはいつ見たされるのか？というと、
\begin{equation}
S u_j = \lambda_j u_j\quad (j > k)
\end{equation}
の時に満たされる。
「どういう$\{ u_j \}_{j=1}^k$をとると、Jが小さくなるか？」という問いに戻ると、$\{ u_j \}_{j = 1}^d$のうち$\{ u_j \}_{j = k + 1}^d$として$S$の小さいほうの固有値に属する固有ベクトルを順にとった場合にそうなることが分かったので、$\{ u_j \}_{j=1}^k$は$S$の大きいほうの固有値に属する固有ベクトルということになる。そいつらが張る$k$次元部分空間、つまり以前の記号では$\mathcal{V}_k$の点で元データを近似した時にもっともよく近似できるということになる。また、$\mathcal{V}_k$の点で元データを近似するというのは、(1)より、$x_n$を$\mathcal{V}_k$に射影した点で近似することであることも分かった。
なんか、思ったより粗くなったが「元データの情報を極力壊さずに次元を低下させたい」⇒「$\mathcal{V}_k$がそのような空間」ということがぼんやりと見えたことにする。(素直にLagrangeの未定乗数法を使いなさいよってな話)
また、PCAの中で謎の共分散行列が突如現れるわけもなんとなく見えたという感じか。
