1月10日の記事の続きで, Recursive Autoencoder (RAE) と Unfolding RAE の訓練アルゴリズムについて書く (RAE そのものがわからない人は,1月10日の記事を参照のこと). 基本的には,RAE は Recursive Neural Network (RNN) のお仲間なので, Backpropagation Through Structure (BPTS) というアルゴリズムで学習できるのだけれど, エンコーダ(次元削減を行う部分)とデコーダ(再構築を行う部分)の2つのパーツで構成されているので, アルゴリズムの導出がいささかややこしい. 慣れている人にとっては簡単だと思うけど,どういう式になるか,メモしておく(導出過程は省略).

Unfolding RAE の計算

訓練アルゴリズムの前に,RAE の計算式をおさらいしておく. 子ノードを $c_1, c_2, \dots, c_M$,親ノードを $p$ とし, ノードの特徴ベクトルを $\mathbf{vec}(\cdot) \in \Real^D$ とすると, RAE は次の図のように, 子の特徴ベクトル $\mathbf{vec}(c_1), \dots, \mathbf{vec}(c_M)$ の情報を圧縮して, 親の特徴ベクトル $\mathbf{vec}(p)$ を計算する.

![Unfolding RAE Encoder](/img/UnfoldingRAE-encoder.png)

ただし,$M$ は子の個数(ノードによって異なる),$\bm{a}(p)$ はノード $p$ の活性(activation), $f : \Real^D \to \Real^D$ は活性化関数(activation function), $\bm{b} \in \Real^D$ はバイアス,$\bm{W}_m \in \Real^{D \times D}$ は重み行列であり, 次のように,($m$ に依らない)2つの重み行列 $\bm{W}_\mathrm{L}, \bm{W}_\mathrm{R}$ により計算される.

機械学習では,この情報圧縮のことを次元削減 (dimensionality reduction) と呼び, RAE の中で,次元圧縮を行う部分をエンコーダと呼ぶ. 機械学習では,次元削減の逆,つまり,圧縮された情報を解凍することを再構築 (reconstruction) と呼び, RAE の中ではデコーダと呼ばれる部分が再構築を担当する.

![Unfolding RAE Decoder](/img/UnfoldingRAE-decoder.png)

ここで,$\bm{b}’ \in \Real^D$ はバイアス, $\bm{W}_m’ = (1 - \alpha_m) \bm{W}_\mathrm{L}’ + \alpha_m \bm{W}_\mathrm{R}’ \in \Real^{D \times D}$ は重み行列です.

このエンコーダ,デコーダを次の図のように,多層に積み上げたものが Unfolding Recursive Autoencoder である.

![Unfolding RAE Decoder](/img/UnfoldingRAE-vecs.png)

Unfoling RAE のエンコーダは葉の特徴ベクトルを次元削減して,根の特徴ベクトルを計算する. デコーダはその逆で,根の特徴ベクトルから葉の特徴ベクトルを再構築する. RAE や Unfolding RAE は非可逆圧縮なので,一般に,葉の特徴ベクトルを完全に復元することはできない. しかし,だいたい同じようなベクトルを復元して欲しいので,上の図で言うと, $\mathbf{vec}(l_i) \approx \mathbf{vec}’(l_i)$ となって欲しい. そこで,次の再構築誤差 (reconstruction error) $E$ を最小化するようなパラメータ $\Theta = (\bm{b}, \bm{W}_\mathrm{L}, \bm{W}_\mathrm{R}, \bm{b}’, \bm{W}_\mathrm{L}’, \bm{W}_\mathrm{R}’)$ を求めることを目指す.

Unfolding RAE の訓練

訓練は確率的勾配降下法で行うことにする.

誤差逆伝搬法を導出する際に,ベクトルで関数を微分する必要があるけれど, 基本的には,1月2日の記事村上・泉田研究室 ニューラルネットワーク 第6章 誤差逆伝播法について のように,成分単位で計算した後に,行列表現に変換したほうが間違いが少ない. 冒頭でも話したように,RAE は RNN の親戚なので, Backpropagation Through Structure (BPTS) で勾配を計算できる.

誤差逆伝搬法で逆伝搬させる誤差は,普通,誤差関数を活性で偏微分したものだけど, エンコーダとデコーダがそれぞれ別々の活性 $\bm{a}(s), \bm{a}’(s)$ を持っているので, ちょっと話がややこしい. ノード $s$ に対して,エンコーダ側,デコーダ側の誤差はそれぞれ次のように定義される.

ただし,$s$ が根もしくは葉である場合は気をつけなければいけない. $s$ が葉である場合,$\mathbf{vec}(s)$ は訓練事例として与えられているもので, エンコーダが計算して求めたものではない.したがって,活性 $\bm{a}(s)$ は存在せず, 故に $\bm{\delta(s)}$ も存在しない($\bm{\delta}’(s)$ は存在する). 一方で,$s$ が根である場合,$s$ はエンコーダとデコーダを接続する部分のノードに当たる. このとき,$\mathbf{vec}’(s) = \mathbf{vec}(s) = f(\bm{a}(s))$ となり, $\bm{a}’(s)$ が存在しないことが理解できる. なので,本当は $\bm{\delta}’(s)$ は存在しないのだが,便宜上, 根については $\bm{\delta}’(s) = \bm{\delta}(s)$ とおく.

計算自体は基本的に簡単であるが,ノードが根・葉・それ以外の場合を意識して計算しないと間違えるので, 結構面倒くさい.デコーダ側の誤差を頑張って計算すると,

となる.ただし,$\dot f, \dot g$ はそれぞれ活性化関数 $f, g$ の導関数を表している. 一方,エンコーダ側の誤差は

となる.ただし,前述した通り,根 $r$ について $\bm{\delta}(r) = \bm{\delta}’(r)$ である. 構文木に含まれる,根ではないノードの集合を $\mathcal{N}$, 葉ではないノードの集合を $\mathcal{M}$ とおくと, パラメータの勾配は

\begin{gather} \frac{\partial E}{\partial \bm{W}_\mathrm{L}} = \sum_{p \in \mathcal{M}} \sum^M_{m=1} (1-\alpha_m) \bm{\delta}(p) \mathbf{vec}(c_m)^\top, \quad \frac{\partial E}{\partial \bm{W}_\mathrm{R}} = \sum_{p \in \mathcal{M}} \sum^M_{m=1} \alpha_m \bm{\delta}(p) \mathbf{vec}(c_m)^\top, \quad \frac{\partial E}{\partial \bm{b}} = \sum_{p \in \mathcal{M}} \bm{\delta}(p), \
\frac{\partial E}{\partial \bm{W}_\mathrm{L}’} = \sum_{p \in \mathcal{M}} \sum^M_{m=1} (1-\alpha_m) \bm{\delta}’(c_m) {\mathbf{vec}’(p)}^\top, \quad \frac{\partial E}{\partial \bm{W}_\mathrm{R}’} = \sum_{p \in \mathcal{M}} \sum^M_{m=1} \alpha_m \bm{\delta}’(c_m) {\mathbf{vec}’(p)}^\top, \quad \frac{\partial E}{\partial \bm{b}’} = \sum_{p \in \mathcal{N}} \bm{\delta}’(p). \end{gather
}

で計算できる.

サンプルプログラム

上記のややこしい式を頑張って実装してみた.

コンパイル:

$ ocamlfind ocamlopt -linkpkg -package slap unfoldingRAE.ml

このプログラムは,私が作っている線形代数ライブラリ Size Linear Algebra Library (SLAP) を使ってプログラミングしている. SLAP については,私が書いた以下の記事が詳しい.

上のプログラムでは,エンコーダ側の活性化関数は tanh,デコーダ側は線形にしている.