Principal Component Analysis; PCA (主成分分析)

  この投稿では，複数の画像データ間に対して，主成分分析を適用する場合における，数学的背景を示します．
MNISTのデータ (手書き数字の画像データ) の各画像間の変化に対して，PCAを適用した場合，下記のような式展開となります．
(画像1枚に対して，PCAを適用する場合は，また別の式展開となります．)

概要

• 変数間に相関のある観測値を，相関の無い主成分に変換する直交変換手法
• 特徴

• データの特徴抽出

• ばらつき (分散) が大きい部分，つまり，共通点の無い (変動する) 部分を抽出．

• データの (次元) 圧縮

• ばらつき (分散) が小さい部分，つまり，共通する部分を削除．
• 画像データの圧縮や，文字の識別など

• 多次元特徴量の可視化

• 人間が認識できないデータの関係性の調査

例: 次元圧縮 (MNIST) ≒ 特徴抽出

アルゴリズム

1. 全データの重心を求める (平均)
2. 重心を通り，分散が最大となる方向を見つける (固有値計算)
3. 2の方向に，新しい軸を引く
4. 3と直交する方向で，分散が最大となる方向を探す (固有値計算)
5. 4の方向に，新しい軸を引く
6. 次元数分だけ繰り返す

数学的背景の概略

1. $N$ 枚 $D$ pixel(次元)の画像データについて，$n$ 枚目の第 $d$ 主成分 $z_{n,d}$ を求める．
$z_{n,d}=l_{d,1}x_{n,1}+l_{d,2}x_{n,2}+\cdots+l_{d,D}x_{n,D}$


2. ラグランジュの未定計数法より，$z_{n,d}$ の分散を最大にする問題は，以下の固有値問題に帰着する．
$\bm{V}\bm{l}=\lambda_d\bm{l}$
($\bm{V}$: $\bm{X}$ の分散共分散行列, $\bm{X}$: $\bm{D}$ 行 $\bm{N}$ 列の画像データ)


3. 結局，PCA後の画像データ $\bm{Z}$ は以下のようにして求められる．

$\bm{Z}=\bm{L}^{\mathrm{T}}\bm{X}$

($\bm{L}$: $\bm{X}$ の固有ベクトル行列)

数学的背景: 証明

• 1枚のサンプルが $D$ 次元持つときの総合特性 $z$ (の分散 ($=$情報量) を最大化するように，変換係数 $l_{n}$ を求めたい．)
$$\begin{align*} z=l_{1}x_{1}+l_{2}x_{2}+\cdots+l_{D}x_{D} \end{align*}$$
ただし，$\bm{l}=(l_{1}x_{1}\ l_{2}x_{2} \cdots l_{D}x_{D})^{\mathrm{T}}$: 未知の重み係数
$\|\bm{l}\|^2=\bm{l}^{\mathrm{T}}\bm{l}=l_{1}^2+l_{1}^2+\cdots+l_{D}^2=1$: 制約条件
$\textcolor{red}{z}$ の分散を最大化するように，$\textcolor{red}{\bm{l}}$ を定めたい

• $n$ 枚目のサインプルにおける第 $d$ 主成分 ($d$ 番目に主要な (寄与率の大きな) 特性) (を定義しておく．)
$$\begin{align*} z_{1}(\bm{l}_{d})&=l_{1,d}x_{1,1}+l_{2,d}x_{2,1}+\cdots+l_{D,d}x_{D,1}\\ &\vdots \\ z_{N}(\bm{l}_{d})&=l_{1,d}x_{1,N}+l_{2,d}x_{2,N}+\cdots+l_{D,d}x_{D,N} \end{align*}$$ $\bm{x}_{n}\equiv(x_{1}\ x_{2} \cdots x_{D})^{\mathrm{T}}$: サンプル$1$枚
$\bm{X}\equiv(\bm{x}_{1}\ \bm{x}_{2} \cdots \bm{x}_{N})$: サンプル$N$枚

• $\bm{z}(\bm{l}_{d})=\bm{X}^{\mathrm{T}}\bm{l}_{d}$ の分散 $V_{\bm{z}}(\bm{l}_{d})$   ($V_{\bm{z}}(\bm{l}_{d})$ はスカラ)
  ($n$ 枚サンプル間の第 $d$ 主成分得点 $\bm{z}(\bm{l}_{d})=\bm{X}^{\mathrm{T}}\bm{l}_{d}$ の分散 $V_{\bm{z}}(\bm{l}_{d})$ を最大化するために，まずは $\bm{z}(\bm{l}_{d})$ を分散の定義に代入して，$V_{\bm{z}}(\bm{l}_{d})$ を求める．)
$$\begin{align*} V_{\bm{z}}(\bm{l}_{d}) &=\frac{1}{N}(\bm{X}^{\mathrm{T}}\bm{l}_{d}-\bm{\overline{X}}^{\mathrm{T}}\bm{l}_{d})^{\mathrm{T}} (\bm{X}^{\mathrm{T}}\bm{l}_{d}-\bm{\overline{X}}^{\mathrm{T}}\bm{l}_{d})\\ &=\frac{1}{N}(\bm{l}_{d}^{\mathrm{T}}\bm{X}-\bm{l}_{d}^{\mathrm{T}}\bm{\overline{X}}) (\bm{X}^{\mathrm{T}}-\bm{\overline{X}}^{\mathrm{T}})\bm{l}_{d}\\ &=\bm{l}_{d}^{\mathrm{T}}\frac{1}{N}(\bm{X}-\bm{\overline{X}}) (\bm{X}-\bm{\overline{X}})^{\mathrm{T}}\bm{l}_{d}\\ &=\bm{l}_{d}^{\mathrm{T}}\bm{V}\bm{l}_{d} \end{align*}$$
ただし， $(\bm{A}\bm{B})^{\mathrm{T}}=(\bm{B}^{\mathrm{T}}\bm{A}^{\mathrm{T}})$,
$\bm{V}\equiv\frac{1}{N}(\bm{X}-\bm{\overline{X}})(\bm{X}-\bm{\overline{X}})^{\mathrm{T}}$: 元データの分散共分散行列．
このとき，$\bm{V}$は，下記のようになる．
$$\begin{align*} \hspace{-3.2mm} \bm{V}= \begin{pmatrix} \frac{1}{N}\sum_{n=1}^{N} (x_{1n}-{\overline x_{n}})^2 & \cdots & \frac{1}{N}\sum_{n=1}^{N} (x_{1n}-{\overline x_{n}})(x_{Dn}-{\overline x_{n}}) \\ \vdots & \ddots & \vdots \\ \frac{1}{N}\sum_{n=1}^{N} (x_{Dn}-{\overline x_{n}})(x_{1n}-{\overline x_{n}}) & \cdots & \frac{1}{N}\sum_{n=1}^{N} (x_{Dn}-{\overline x_{n}})^2 \\ \end{pmatrix} \end{align*}$$

• ラグランジュの未定係数法 (を用いて，$V_{\bm{z}}(\bm{l}_{d})$ を最大化する．)
$L$: ラグランジュ関数, $\lambda_{d}$: 第$d$主成分のラグランジュ関数
$$\begin{align*} L(\bm{l},\lambda_{d}) &=V_{\bm{z}}(\bm{l}_{d})-\lambda(\|\bm{l}_{d}\|^2-1)\\ &=\bm{l}_{d}^{\mathrm{T}}\bm{V}\bm{l}_{d}-\lambda(\bm{l}_{d}^{\mathrm{T}}\bm{l}_{d}-1) \end{align*}$$
• $L$ 関数の偏微分が0となる条件で $L$ 関数は極値をとる．
このとき，分散 $V_{\bm{Z}}(\bm{l}_{d})$ は最大となる． $$\begin{align*} \frac{\partial L}{\partial\bm{l}_{d}} =\frac{\partial}{\partial\bm{l}_{d}} \Bigl\{\bm{l}_{d}^{\mathrm{T}}\bm{V}\bm{l}_{d}-\lambda_{d}(\bm{l}_{d}^{\mathrm{T}}\bm{l}_{d}-1)\Bigl\} &=\bm{V}\bm{l}_{d}+\bm{l}_{d}^{\mathrm{T}}\bm{V}-\lambda_{d}(\bm{l}_{d}+\bm{l}_{d})\\ &=2\bm{V}\bm{l}_{d}-2\lambda_{d}\bm{l}_{d}\\ &=2(\bm{V}\bm{l}_{d}-\lambda_{d}\bm{l}_{d})=\bm{0} \end{align*}$$ ただし，$\bm{V}$は実対象行列より， $\bm{l}_{d}^{\mathrm{T}}\bm{V}=\bm{V}\bm{l}_{d}$． $$\begin{align*} \frac{\partial L}{\partial\lambda_{d}} =\frac{\partial}{\partial\lambda_{d}} \Bigl\{\bm{l}_{d}^{\mathrm{T}}\bm{V}\bm{l}_{d}-\lambda_{d}(\bm{l}_{d}^{\mathrm{T}}\bm{l}_{d}-1)\Bigl\} =-1(\bm{l}_{d}^{\mathrm{T}}\bm{l}_{d}-1)=\bm{0}\ \ \ \ \ \ \ \ \ \ \end{align*}$$ したがって，PCAは次の固有値問題に帰着する． $$\begin{cases} \bm{V}\bm{l}_{d}=\lambda_{d}\bm{l}_{d}\\ \bm{l}_{d}^{\mathrm{T}}\bm{l}_{d}=1 \end{cases}$$

• $\bm{Z}$，$\bm{L}$ を次のように定義する．
$$\begin{align*} \bm{Z}&\equiv(\bm{z}(\bm{l}_{1})\ \bm{z}(\bm{l}_{2}) \cdots \bm{z}(\bm{l}_{D}))\\ \bm{L}&\equiv(\bm{l}_{1}\ \bm{l}_{2} \cdots \bm{l}_{D})\\ \bm{X}&\equiv(\bm{x}_{1}\ \bm{x}_{2} \cdots \bm{x}_{N})\\ \bm{x}_{n}&\equiv(x_{1}\ x_{2} \cdots x_{D})^{\mathrm{T}} \end{align*}$$
• 結局，PCA後の画像データ $\bm{Z}$ は以下のようにして求められる．
$\bm{Z}=\bm{L}^{\mathrm{T}}\bm{X}$

数学的背景: 性質

• 次の性質を利用して，PCAの性質を探る．
$$\begin{cases} \bm{V}\bm{l}_{d}=\lambda_{d}\bm{l}_{d}\\ \bm{l}_{d}^{\mathrm{T}}\bm{l}_{d}=1 \end{cases}$$
• $d$ 番目に大きな固有値 $\lambda_{d}$ $\Leftrightarrow$ 分散 $V_{\bm{Z}}(\bm{l}_{d})$
$$\begin{align*} V_{\bm{Z}} =\bm{l}_{d}^{\mathrm{T}}\bm{V}\bm{l}_{d} &=\bm{l}_{d}^{\mathrm{T}}(\bm{V}\bm{l}_{d})\\ &=\bm{l}_{d}^{\mathrm{T}}(\lambda_{d}\bm{l}_{d})\\ &=\lambda_{d}\bm{l}_{d}^{\mathrm{T}}\bm{l}_{d}\\ &=\lambda_{d} \end{align*}$$ 結局，分散 $V_{\bm{Z}}(\bm{l}_{d})$ は，固有値 $\lambda$ の大きな順に最大化される．
($\bm{Z}(\bm{l}_{d})=\bm{X}^{\mathrm{T}}\bm{l}_{d}$ を，第 $d$ 主成分と呼ぶ． また，$\bm{V}$ は実対象行列のため，$\bm{l}$ は互いに直交し，主成分同士は無相関．)

定理 1.

実対象行列は常に対角化可能．


定理 2.

行列が対角化可能なとき，固有値の和は元の行列の対角和に等しい．



証明．	$\bm{A}$: 実対象行列 (今回は $\bm{X}$ の分散共分散行列 $\bm{V}$ )
	$\bm{P}$: 固有ベクトル行列
	$\bm{\Lambda}$: 固有値行列

$$\begin{align*} \bm{A}\bm{P}&=\bm{P}\bm{\Lambda}\\ \Leftrightarrow\bm{P}^{-1}\bm{A}\bm{P}&=\bm{\Lambda}\\ \end{align*}$$ $$\begin{align*} \mathrm{Tr}(\bm{\Lambda}) &=\mathrm{Tr}(\bm{P}^{-1}\bm{A}\bm{P})\\ &=\mathrm{Tr}(\bm{A}\bm{P}^{-1}\bm{P})\\ &=\mathrm{Tr}(\bm{A}) \end{align*}$$
補題．$\mathrm{Tr}(\bm{A})\equiv\sum_{i=1}^{n} a_{i,i}$,  $\mathrm{Tr}(\bm{AB})=\mathrm{Tr}(\bm{BA})$

• このとき，第 $d$ 主成分の寄与率 (情報量) は，次のように与えられる．
$$\begin{align*} 第d主成分の寄与率 (情報量) &= 固有値の大きさ/固有値の総和\\ &= 固有値の大きさ/分散共分散行列\bm{V}の対角和\\ &= \lambda_{d}/\mathrm{Tr}(\bm{V}) \end{align*}$$
• 元の行列 $\bm{X}$ を平均0，分散1に標準化した場合，$\bm{V}$ の対角成分は分散なので，全て1 (非対角成分は共分散)
したがって，
$$\begin{align*} 第 d 主成分の寄与率 (情報量) &= \lambda_{d}/\mathrm{Tr}(\bm{V})\\ &= \lambda_{d}/D． \end{align*}$$ ただし，$\bm{V}$ は $D\times D$ 行列．
• "固有値の総和 $= D$ "を用いれば，すべての固有値を求めずとも，寄与率を計算できる．

終わりに

下記のSlideShareにアップロードしたスライドを示す．(ただし，日本語が表示できなかったため，画像化済み．)
手間を惜しんで作成したため，完成度は悪いです．手間を惜しまないと無限に時間が掛かる訳ではありますけれど．

Principal component analysis (主成分分析) の 概要 と 数学的背景 from ADMIS Walker

---

参考資料

10分でわかる主成分分析(PCA)
datB_prin00.doc Ver.4 主成分分析 (PCA: Principal Component Analysis)
MNISTのPCA結果の画像を借用: 主成分分析PCAを用いて手書き数字を分析する。その１

下記書籍の page.59~71．(FORTRAN ではあるが，サンプルプログラムも収録されている)

UNIX/Windowsを使った実践気候データ解析
―気候学・気象学・海洋学などの報告書・論文を書く人が知っておきたい3つのポイント
著者: 松山 洋, 谷本 陽一
出版社: 古今書院
発売日: 2005/01
メディア: 単行本
ページ数: 107 ページ

使用ソフト

PDFの.png化: PDF PNG 変換
画像のPDF化に使用したソフト: 画像梱包

使用させていただいたBeamerのテンプレート

LATEXチートシート (作成途中)>テンプレート>Beamerでスライドを作る

---