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$ の逆平方根と呼ばれるものである。

std::forward_as_tuple

覚え書き このとき出力は以下の通り。 http://faithandbrave.hateblo.jp/entry/20100428/1272422821
http://faithandbrave.hateblo.jp/entry/2014/04/15/151845

std::unique_ptr<T>はTのfull definitionを必要とするか？

以下のコードなら foo.h に #include "hoge.h" は必要ない。 以下の場合、foo.h に #include "hoge.h" は必要である。 後者の場合、foo の destructor は inline で定義される。これは、hoge の full definition を要求してしまう。

Neural Networkにおける誤差逆伝播法

はじめに

Neural Network(NN)で使われる誤差逆伝播法の計算をまとめます。

NNの基本構造

いま、NNの中間層 $k-1,k,k+1$ を考える。$k-1$ 層内の $j$ 番目のユニットと $k$ 層内の $i$ 番目のユニット間の重みを $\omega_{i,j}^{k}$ とする。

$k-1$ 層内の全てのユニットから $k$ 層内の $i$ 番目のユニットへの入力値 $x_{i}^{k}$ は以下のように書ける(本解説ではバイアス項を無視する)。 \begin{equation} x_{i}^{k} = \sum_{j}\;\omega_{i,j}^{k}\;h_{j}^{k-1} \label{first} \end{equation} ここで、$h_{j}^{k-1}$ は $k-1$ 層内の $j$ 番目のユニットからの出力値である。$k$ 層内の $i$ 番目のユニットからの出力値 $h_{i}^{k}$ は、活性化関数 $f$ を用いて \begin{equation} h_{i}^{k} = f(x_{i}^{k}) \end{equation} と書くことができる。
NNに解かせたい問題が多クラス問題の場合、最上層($a$ 層とする)のユニットの数をクラスと同数とする。そして、各ユニットからの出力値を次式で定義する。 \begin{equation} h_{i}^{a} = \frac{ \exp{ \left(x_{i}^{a}\right) } }{ \sum_{j}\exp{ \left(x_{j}^{a}\right) } } \equiv p_{i} \end{equation} $p_{i}$ は正規化された量である。 \begin{equation} \sum_{i}\;p_{i}=1 \end{equation} 最下層に与えられるデータ $X$ のクラスのラベルが $i$ であるなら、最上層からの出力値は $p_{i}=1,p_{j\neq i}=0$ となるのが理想である。

目的関数

NNにおける学習の目的は、パラメータ $w_{i,j}^{k}$ を全て求めることである。その際、次の目的関数を用いる。 \begin{equation} C = -\sum_{i}\;d_{i}\;\log{p_{i}} \label{obj} \end{equation} 最下層に与えられるデータ $X$ のクラスのラベルが $i$ なら、$\{d_{i}\}$ は $d_{i}=1,d_{j\neq i}=0$ である。ここで、$0\le p_{i}\le 1$ であるから $\log{p_{i}}\le 0$ が成り立つ。もし、$p_{i}=1,p_{j\neq i}=0$ が成り立つなら、このとき $C$ は最小値 $0$ となる。 従って、理想に近い $p_{i}$ を実現するには、$C$ を最小化すればよい。

勾配降下法(Gradient Descent Method)

$C$ は重み $w_{i,j}^{k}$ の関数である。 \begin{equation} C = C(w_{1,1}^{1},w_{1,2}^{1},\cdots,w_{i,j}^{k},\cdots) \end{equation} この全ての重みを求めることが目的である。 勾配降下法の手順は以下の通りである。

1. 適当な初期値 $\{\omega_{i,j}^{k}\}$ を設定する。
2. $C$ を計算する。$C$ の変化量がしきい値以下なら終了。
3. 次式を計算する。 \begin{equation} \delta w_{i,j}^{k} = -\epsilon \frac{\partial C}{\partial w_{i,j}^{k}} \end{equation} ここで、$\epsilon$ は正のパラメータである。
4. $w_{i,j}^{k}$ を更新する($w_{i,j}^{k}\leftarrow w_{i,j}^{k}+\delta w_{i,j}^{k}$)。
5. 2へ

これを実行するには、 \begin{equation} \frac{\partial C}{\partial w_{i,j}^{k}} \end{equation} を計算しなければならない。 $C$ は $\{x_{i}^{k}\}$ の関数である。 \begin{equation} C = C(x_{1}^{k},x_{2}^{k},\cdots) \end{equation} また、$x_{i}^{k}$ は $\{\omega_{i,j}^{k}\}$ の関数である。 \begin{equation} x_{i}^{k} = x_{i}^{k}(w_{i,1}^{k},w_{i,2}^{k},\cdots) \end{equation} 従って、 \begin{eqnarray} \frac{\partial C}{\partial \omega_{i,j}^{k}}&=&\frac{\partial C}{\partial x_{i}^{k}}\frac{\partial x_{i}^{k}}{\partial \omega_{i,j}^{k}}\nonumber \\ &=&\frac{\partial C}{\partial x_{i}^{k}}h_{j}^{k-1} \label{point} \end{eqnarray} を得る。ただし、最後の式で式(\ref{first})を用いた。結局、$\frac{\partial C}{\partial \omega_{i,j}^{k}}$ を得るには、$\frac{\partial C}{\partial x_{i}^{k}}$ を求めなければならないことが分かる。 これを計算する手法が誤差逆伝播法である。

誤差逆伝播法

$C$ を $k+1$ 層への入力値 $\{x_{i}^{k+1}\}$ の関数とみなす。 \begin{equation} C = C(x_{1}^{k+1},x_{2}^{k+1},\cdots) \end{equation} また、$k+1$ 層への入力値 $x_{i}^{k+1}$ は、$k$ 層への入力値 $\{x_{i}^{k}\}$ の関数である。 \begin{equation} x_{i}^{k+1} = x_{i}^{k+1}(x_{1}^{k},x_{2}^{k},\cdots) \end{equation} 従って、次式が成り立つ。 \begin{equation} \frac{\partial C}{\partial x_{i}^{k}}=\sum_{j}\;\delta _{j}^{k+1}\frac{\partial x_{j}^{k+1}}{\partial x_{i}^{k}} \label{aa} \end{equation} ここで、 \begin{equation} \delta_{j}^{k+1} \equiv \frac{\partial C}{\partial x_{j}^{k+1}} \end{equation} とした。ところで、 \begin{equation} x_{j}^{k+1} = \sum_{l}\;\omega_{j,l}^{k+1}\;f(x_{l}^{k}) \end{equation} であるから、 \begin{equation} \frac{\partial x_{j}^{k+1}}{\partial x_{i}^{k}}=\omega_{j,i}^{k+1}\;f^{\;\prime}(x_{i}^{k}) \end{equation} が成り立つ。従って、式(\ref{aa})は \begin{equation} \delta_{i}^{k}=f^{\;\prime}(x_{i}^{k})\;\sum_{j}\;\delta_{j}^{k+1}\;\omega_{j,i}^{k+1} \label{ite} \end{equation} と変形される。ただし、 \begin{equation} \delta_{i}^{k} \equiv \frac{\partial C}{\partial x_{i}^{k}} \end{equation} とした。式(\ref{ite})から、$\{\delta_{i}^{k+1}\}$ が決まれば、$\{\delta_{i}^{k}\}$ が求まることが分る。すなわち、最上層の値 \begin{equation} \delta_{i}^{a} \equiv \frac{\partial C}{\partial x_{i}^{a}} \end{equation} が決まれば、式(\ref{ite})を順に適用することにより、全ての $\{\delta_{i}^{k}\}$ を求めることができる。
ここで、最上層の $\delta_{i}^{a}$ を計算するため、$C$ を変形する。 \begin{eqnarray} C &=& -\sum_{l}\;d_{l}\;\log{p_{l}}\nonumber\\ &=& -\sum_{l}\;d_{l}\;\log{h_{l}^{a}} \nonumber\\ &=& -\sum_{l}\;d_{l}\;\log{\frac{ \exp{ \left(x_{l}^{a}\right) } }{ \sum_{j}\exp{ \left(x_{j}^{a}\right) } } } \nonumber\\ &=& -\sum_{l}\;d_{l}\;x_{l}^{a} + \left( \sum_{l}\;d_{l} \right)\;\log{ \left(\sum_{j}\exp{ \left( x_{j}^{a} \right) }\right) } \nonumber\\ &=& -\sum_{l}\;d_{l}\;x_{l}^{a} + \log{ \left(\sum_{j}\exp{ \left( x_{j}^{a} \right) }\right) } \end{eqnarray} 最後の式で \begin{equation} \sum_{l}\;d_{l}=1 \end{equation} を用いた。従って \begin{equation} \frac{\partial C}{\partial x_{i}^{a}}=p_{i}-d_{i}=\delta_{i}^{a} \end{equation} を得る。 $p_{i}$ は $\{\omega_{i,j}^{k}\}$ が決まれば計算できる量であり、$\{d_{i}\}$ は最初に当たられる量である。この量は、実際の出力($p_{i}$)と理想の出力($d_{i}$)とのずれ(誤差)を表している。ここまでの議論で、最上層から最下層まで全ての $\{\delta_{i}^{k}\}$ を計算できることが分かる。そして、式(\ref{point})を用いれば次式のように $\frac{\partial C}{\partial \omega_{i,j}^{k}}$ を全て求めることができる。 \begin{equation} \frac{\partial C}{\partial \omega_{i,j}^{k}}=\delta_{i}^{k}\;h_{j}^{k-1} \end{equation} 最上層の誤差を最下層へ向かって伝播していく手法なので、誤差逆伝播法と呼ぶ。

3層の場合

　いま、3層の場合を具体的に考えてみる。各層において次式が成り立つ。 \begin{eqnarray} x_{i}^{1}&=&\sum_{j=1}^{D}\;\omega_{i,j}^{1}\;h_{j}^{0},\;\;\;i=1,\cdots,M \\ h_{i}^{1}&=&f(x_{i}^{1}),\;\;\; i=1,\cdots,M \\ x_{i}^{2}&=&\sum_{j=1}^{M}\;\omega_{i,j}^{2}\;h_{j}^{1},\;\;\; i=1,\cdots,K \\ h_{i}^{2}&=&\frac{\exp{x_i^2}}{\sum_{j=1}^{K}\;\exp{x_j^2}}=p_i,\;\;\; i=1,\cdots,K \end{eqnarray} 入力層( $k=0$ )のユニット数を $D$、隠れ層( $k=1$ )のユニット数を $M$、出力層( $k=2$ )のユニット数を $K$ とした。 活性化関数 $f$ として \begin{equation} f(x) = \tanh{x} \end{equation} を考える。このとき、次式が成り立つ。 \begin{equation} f^{\prime}(x) = 1-\left(f(x)\right)^2 \end{equation} 最初に $\delta_{i}^{2}$ を求める。 \begin{equation} \delta_{i}^{2}=p_{i}-d_{i},\;\;\; i=1,\cdots,K \end{equation} この結果を用いて、隠れ層の $\delta_{i}^{1}$ を計算する。 \begin{equation} \delta_{i}^{1}=\left(1-f(x_{i}^{1})^2\right)\;\sum_{j=1}^K\;\delta_{j}^{2}\;\omega_{j,i}^{2},\;\;\; i=1,\cdots,M \end{equation} ここまでで $\{\delta_{i}^{1}\}$と$\{\delta_{i}^{2}\}$ を求めることができた。これらを用いて \begin{eqnarray} \frac{\partial C}{\partial \omega_{i,j}^{1}}=\delta_{i}^{1}\;h_{j}^{0},\;\;\;i=1,\cdots,M,\;\;\;j=1,\cdots,D\\ \frac{\partial C}{\partial \omega_{i,j}^{2}}=\delta_{i}^{2}\;h_{j}^{1},\;\;\;i=1,\cdots,K,\;\;\; j=1,\cdots,M \end{eqnarray} を計算することができる。また、入力値 $h_j^0$ の微小変化に対する出力値 $p_k$ の変化分を表す量 $J_{k i}$ \begin{equation} J_{k i} = \frac{\partial p_k}{\partial h_i^0} \end{equation} は以下のように計算される。 \begin{eqnarray} J_{k i} &=& \frac{\partial p_k}{\partial h_i^0} \nonumber \\ &=& \sum\; \frac{\partial p_k}{\partial x_\eta^2} \frac{\partial x_\eta^2}{\partial h_\alpha^1} \frac{\partial h_\alpha^1}{\partial x_\beta^1} \frac{\partial x_\beta^1}{\partial h_i^0} \nonumber \\ &=& \sum_{\eta,\alpha,\beta}\; \frac{\partial p_k}{\partial x_\eta^2} \omega^2_{\eta,\alpha} \frac{\partial h_\alpha^1}{\partial x_\beta^1} \omega^1_{\beta,i} \nonumber \\ &=& \sum_{\eta,\alpha}\; \left(\delta_{\eta,k}\;p_k - p_k\;p_\eta\right) \omega^2_{\eta,\alpha}\; f^{\prime}(x_\alpha^1)\; \omega^1_{\alpha,i} \end{eqnarray}

moveの実験コード

私的な覚え書き。

2014年3月13日追記：std::forwardはテンプレート引数に対して使うものなので、ここで示した使い方は流儀に反するのかもしれません。

クラスfooのコンストラクタにクラスbarのオブジェクトを渡す。 このとき、std::moveで渡す場合(check_move_0)と、値で渡す場合(check_move_1)を比較する。 出力： 19行目のstd::forwardのおかげで、必要最低限のコピーで済むことがわかる。 std::forwardを使わず、bar_(b)と書くと以下のように不必要なコピーが行われる。 参照サイト

boost::logでlink error

BOOST_LOG_DYN_LINKあるいはBOOST_ALL_DYN_LINKを定義しておけば良い。