Xcodeでboost/numeric/bindings/lapack/syevd.hppを使うには。

覚え書き
Xcode Version 5.1.1 においてboost/numeric/bindings/lapack/syevd.hpp をincludeしたときは、Other Linker Flagsに -framework accelerateを追加する必要がある。(macportでインストールしたlapackやblasをリンクしてみたがコンパイルできなかった。)

主成分分析と白色化

はじめに

画像認識でも使われている主成分分析と白色化についてまとめます。

主成分分析

　観測値を $n$ 次元ベクトル $\vec{x}^{\;\mu},\;\mu=1,\cdots,N$ で表し、観測値で表される量の期待値演算を $E\left[\cdot\right]$ で表すことにする。 たとえば、観測値の平均値 $E\left[\vec{x}\right]$ は最も単純な方法では \begin{equation} E\left[\vec{x}\right] = \frac{1}{N}\sum_{\mu=1}^{N}\;\vec{x}^{\;\mu} \end{equation} と書ける。
　一般に、$\vec{x}^{\;\mu}$ は $n$ 次元ベクトルの正規直交基底 $\{\vec{\gamma}_{i}\}$ の一次結合で表現することができる。 \begin{equation} \vec{x}^{\;\mu} = \sum_{i=1}^{n}\;s_{i}^{\mu}\;\vec{\gamma}_{i} \label{eq1} \end{equation} ここで、 \begin{eqnarray} \vec{\gamma}_{i}^{\;T} \cdot \vec{\gamma}_{j} &=& \delta_{i,j} \label{eq2} \\ s_{i}^{\mu} &=& \vec{\gamma}_{i}^{\;T} \cdot \vec{x}^{\;\mu} \label{eq3} \end{eqnarray} である。式(\ref{eq1})において $n$ より少ない個数 $m(<n)$ の基底ベクトルで $\vec{x}^{\;\mu}$ をできるだけ正確に近似する手法を主成分分析 (Principal Component Analysis : PCA) と呼ぶ。つまり、PCAとは観測値を表現する最適な空間を見つける作業である。
　近似式 \begin{equation} \vec{x}^{\;\mu} \sim \sum_{i=1}^{m(<n)}\;s_{i}^{\mu}\;\vec{\gamma}_{i} \end{equation} が精度よく成り立つための $n$ 次元ベクトル $\vec{\gamma}_{i}$ を求めることを考える。これを実現するには、次式で定義される残差の2乗平均 $F$ を最小にすれば良い。 \begin{eqnarray} F&=&E\left[\;\left\|\; \vec{x} - \sum_{i=1}^{m}\;(\vec{\gamma}_{i}^{\;T} \cdot \vec{x})\;\vec{\gamma}_{i}\;\right\|^{2}\;\right] \nonumber \\ &=&E\left[\;\left\|\; \vec{x} \right\|^{2}\;\right]- \sum_{i=1}^{m}\; E \left[\; \; (\vec{\gamma}_{i}^{\;T} \cdot \vec{x} )^{2} \; \right] \label{eq4} \end{eqnarray} ここで、式(\ref{eq3})を用いた。 $\vec{x}$ は定数であるから、$F$ を最小にするには式(\ref{eq4})の第2項 \begin{equation} G=\sum_{i=1}^{m}\;E \left[\; \; (\vec{\gamma}_{i}^{\;T} \cdot \vec{x} )^{2} \; \right] \end{equation} を最大にすれば良い。$G$ は以下のように変形できる。 \begin{eqnarray} G&=&\sum_{i=1}^{m}\;\vec{\gamma}_{i}^{\;T}\;E \left[\; \; \vec{x} \cdot \vec{x}^{\;T} \; \right]\;\vec{\gamma}_{i}\nonumber \\ &=& \sum_{i=1}^{m}\;\vec{\gamma}_{i}^{\;T} \;V \; \vec{\gamma}_{i} \label{eq5} \end{eqnarray} ここで、$n\times n$ の共分散行列 \begin{equation} V=E \left[\; \; \vec{x} \cdot \vec{x}^{T} \; \right] \end{equation} を導入した。結局、規格化条件 $\left\| \vec{\gamma}_{i}\right\|^{2}=1$ の下で式(\ref{eq5})を最大にする問題に帰着したことになる。 Langurangeの未定係数法により、次式で定義される $L$ の停留点を求める。 \begin{equation} L=\sum_{i=1}^{m}\;\vec{\gamma}_{i}^{\;T} \;V \; \vec{\gamma}_{i} -\sum_{i=1}^{m}\;\lambda_{i}\; \left( \left\| \vec{\gamma}_{i} \right\|^{2} -1 \right) \end{equation} $\vec{\gamma}_{i}$ で微分すると次式を得る。 \begin{equation} V\;\vec{\gamma}_{i}=\lambda_{i}\;\vec{\gamma}_{i} \end{equation} これは行列 $V$ の固有値問題である。$V$ は実対称行列であるから対角化可能であり、次式が成り立つ。 \begin{eqnarray} V&=&R\;\Lambda\;R^{T}\label{eq10} \\ R&=&\left[ \vec{\gamma}_{1},\cdots,\vec{\gamma}_{n} \right] \\ \Lambda&=&{\rm diag}\left[ \lambda_{1},\cdots,\lambda_{n} \right] \end{eqnarray} ここで、$\vec{\gamma}_{i}$ と $\lambda_{i}$ は $V$ の固有ベクトル、固有値である。また、相異なる固有値に対応する固有ベクトルは直交するから、 式(\ref{eq2})は保証される。このとき、$G$は \begin{equation} G=\sum_{i=1}^{m}\;\lambda_{i} \end{equation} と書き直せるので、$G$ を最大にするには $n$ 個の固有値の中から大きな順に $m$ 個取り出せば良いことが分る。 以上の議論から、観測値 $\vec{x}_{i}^{\;\mu}$ は、その共分散行列の固有ベクトル $\vec{\gamma}_{i}$ を用いて \begin{eqnarray} \vec{x}^{\;\mu} &\sim& s_{1}^{\mu}\;\vec{\gamma}_{1} + \cdots + s_{m}^{\mu}\;\vec{\gamma}_{m} \label{eq6}\\ s_{i}^{\mu} &\sim& \vec{\gamma}_{i}^{\;T} \cdot \vec{x}^{\mu} \end{eqnarray} のように近似される。式(\ref{eq6})の右辺第 $k$ 項目を第 $k$ 主成分からの寄与と呼ぶ。

白色化

　観測値 $\vec{z}$ の共分散行列が単位行列に等しいとき、$\vec{z}$ は白色であるという。 任意の観測値 $\vec{x}$ を白色にすることを白色化と呼ぶ。白色化は $\vec{x}$ に対するPCAの結果を使えば、次式で実現できる。 \begin{equation} \vec{z}=U\;\Lambda^{-1/2}\;R^{T}\;\vec{x} \label{eq7} \end{equation} ただし、$U$ を任意の直交行列とした( $U\;U^T=U^T\;U=I$ )。 上式で白色化できることは以下のように証明できる。 \begin{eqnarray} E\left[ \vec{z} \cdot \vec{z}^{\;T} \right] &=& E\left[ U\;\Lambda^{-1/2}\;R^{T}\;\vec{x}\cdot \vec{x}^{\;T}\;R\;\Lambda^{-1/2}\;U^{T} \right]\\ &=& U\;\Lambda^{-1/2}\;R^{T} E\left[ \;\vec{x}\cdot \vec{x}^{\;T} \right] \;R\;\Lambda^{-1/2}\;U^T\\ &=& U\;\Lambda^{-1/2}\;R^{T} V\;R\;\Lambda^{-1/2}\;U^T\\ &=& U\;\Lambda^{-1/2}\;R^{T} R\;\Lambda\;R^{T} \;R\;\Lambda^{-1/2}\;U^T\\ &=& U\;\Lambda^{-1/2}\; \Lambda \;\Lambda^{-1/2}\;U^T\\ &=& I \end{eqnarray} ただし、式(\ref{eq10})と $R^{T}\;R=R\;R^{T}=I$ を用いた。 $U=R$ とした白色化行列 \begin{equation} W=R\;\Lambda^{-1/2}\;R^{T} \end{equation} が使われることが多い。$W$ はその形から $V$ の逆平方根と呼ばれるものである。