MNISTのデータ (手書き数字の画像データ) の各画像間の変化に対して，PCAを適用した場合，下記のような式展開となります．
(画像1枚に対して，PCAを適用する場合は，また別の式展開となります．)
概要
- 変数間に相関のある観測値を，相関の無い主成分に変換する直交変換手法
- 特徴
- データの特徴抽出
- ばらつき (分散) が大きい部分，つまり，共通点の無い (変動する) 部分を抽出．
- データの (次元) 圧縮
- ばらつき (分散) が小さい部分，つまり，共通する部分を削除．
- 画像データの圧縮や，文字の識別など
- 多次元特徴量の可視化
- 人間が認識できないデータの関係性の調査
アルゴリズム
- 全データの重心を求める (平均)
- 重心を通り，分散が最大となる方向を見つける (固有値計算)
- 2の方向に，新しい軸を引く
- 3と直交する方向で，分散が最大となる方向を探す (固有値計算)
- 4の方向に，新しい軸を引く
- 次元数分だけ繰り返す
数学的背景の概略
- $N$ 枚 $D$ pixel(次元)の画像データについて，$n$ 枚目の第 $d$ 主成分 $z_{n,d}$ を求める．
- ラグランジュの未定計数法より，$z_{n,d}$ の分散を最大にする問題は，以下の固有値問題に帰着する．
- 結局，PCA後の画像データ $\bm{Z}$ は以下のようにして求められる．
$z_{n,d}=l_{d,1}x_{n,1}+l_{d,2}x_{n,2}+\cdots+l_{d,D}x_{n,D}$
$\bm{V}\bm{l}=\lambda_d\bm{l}$
($\bm{V}$: $\bm{X}$ の分散共分散行列, $\bm{X}$: $\bm{D}$ 行 $\bm{N}$ 列の画像データ)
($\bm{V}$: $\bm{X}$ の分散共分散行列, $\bm{X}$: $\bm{D}$ 行 $\bm{N}$ 列の画像データ)
$\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$主成分のラグランジュ関数
- $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} \]
\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*}
- $\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}$: 固有値行列 |
-
補題．$\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 (非対角成分は共分散) したがって，
- "固有値の総和 $ = D$ "を用いれば，すべての固有値を求めずとも，寄与率を計算できる．
\begin{align*} 第 d 主成分の寄与率 (情報量) &= \lambda_{d}/\mathrm{Tr}(\bm{V})\\ &= \lambda_{d}/D． \end{align*} ただし，$\bm{V}$ は $D\times D$ 行列．
終わりに
下記のSlideShareにアップロードしたスライドを示す．(ただし，日本語が表示できなかったため，画像化済み．)参考資料
10分でわかる主成分分析(PCA)
datB_prin00.doc Ver.4 主成分分析 (PCA: Principal Component Analysis)
MNISTのPCA結果の画像を借用: 主成分分析PCAを用いて手書き数字を分析する。その１
下記書籍の page.59~71．(FORTRAN ではあるが，サンプルプログラムも収録されている)
datB_prin00.doc Ver.4 主成分分析 (PCA: Principal Component Analysis)
MNISTのPCA結果の画像を借用: 主成分分析PCAを用いて手書き数字を分析する。その１
下記書籍の page.59~71．(FORTRAN ではあるが，サンプルプログラムも収録されている)
UNIX/Windowsを使った実践気候データ解析 ―気候学・気象学・海洋学などの報告書・論文を書く人が知っておきたい3つのポイント 著者: 松山 洋, 谷本 陽一 出版社: 古今書院 発売日: 2005/01 メディア: 単行本 ページ数: 107 ページ
UNIX/Windowsを使った実践気候データ解析
―気候学・気象学・海洋学などの報告書・論文を書く人が知っておきたい3つのポイント
著者: 松山 洋, 谷本 陽一
出版社: 古今書院
発売日: 2005/01
メディア: 単行本
ページ数: 107 ページ使用ソフト
使用させていただいたBeamerのテンプレート
0 件のコメント:
コメントを投稿