Recursive neural network (RNN) は, 構文木の意味を表現する特徴ベクトルを計算するために使用されるモデルである. 歴史的には,主に自然言語処理において利用されてきたが, プログラミング言語の意味の解析とかにも使える [Li14](詳細は, 1月2日の記事を参照のこと). 今日は,RNN の訓練に用いられる backpropagation through structure (BPTS) [Go96] というアルゴリズムについて紹介する.

Recursive neural network (RNN)

RNN では,子を表現する特徴ベクトルを用いて,親を表現する特徴ベクトルを計算する, という処理を再帰的に繰り返すことで,根に対応する特徴ベクトル,すなわち,木全体を表現する特徴ベクトルを計算する. 例えば,42 + 123 * foo というプログラムを構文解析して,次の図の左のような構文木が得られたとしよう. この構文木を表現する特徴ベクトルは,右図のような RNN で計算される.

![RNN と構文木](/img/RNN-and-syntax-tree.png)

RNN の細かい計算はさておき,大雑把な動作を先に説明しておく. まず,葉に対応する特徴ベクトルが何らかの手段で予め得られているとしよう. すると,42*foo に対応する特徴ベクトルを基に,RNN が 42 * foo に対応する特徴ベクトルを作ってくれる. 次に,同じようにして,123+42 * foo に対応する特徴ベクトルを基に, 123 + 42 * foo に対応する特徴ベクトルを得ることができる. これが,構文木全体を表現するベクトルとなる. 親のベクトルは子のベクトルから計算されるので,子の情報を(ある程度)含んでいる. なので,直感的には,根のベクトルは構文木に含まれる全てのノードの情報を含んでいると考えられる. 最終的に求まった構文木の特徴ベクトルは,クラス分類とかクラスタリングとかに用いられる.

さて,RNN の具体的な計算について見てみよう. $p$ を親ノード,$c_1, c_2, \dots, c_M$($M$ は子の数)を $p$ の子ノードとし, $\mathbf{vec}(\cdot) \in \Real^D$($D$ は特徴ベクトルの次元)を特徴ベクトルとする. RNN は特徴ベクトル $\mathbf{vec}(c_1), \dots, \mathbf{vec}(c_M)$ を入力として受け取り, 次の式で出力 $\mathbf{vec}(p)$ を計算する.

ここで,$\bm{a}(p)$ は親 $p$ の活性 (activation), $\bm{W}_m \in \Real^{D \times D}$ は重み行列, $\bm{b} \in \Real^D$ はバイアス項,$f : \Real^D \to \Real^D$ は活性化関数である. この計算は,次のような模式図で表される.

![RNN のユニット](/img/RNN-unit-vecs.png)

基本的には,普通のニューラルネットと変わらないように思われるが, 子の数 $M$ がノードごとに異なるという,重大な違いがある. これは,パラメータ数(厳密には,重み行列の個数)がノードごと異なるということなので,学習アルゴリズムの設計が難しくなる. 自然言語処理では,強引に構文木を二分木に変換することで,$M = 2$ に固定して,この問題を回避している (正確には,文法をチョムスキー標準形に変換することで,構文木が必ず二分木になるようにしている). でも,このアイディアを,もうちょっと一般化して考えることもできる [Li14]. 単純に $\bm{W} _m$ を2つの重み行列 $\bm{W} _\mathrm{L}$,$\bm{W} _\mathrm{R}$ をブレンドして作れば良い.

混合比は次のように定義されている.左端に近い子ほど $\bm{W} _\mathrm{L}$ の割合が高くなり, 逆に右端に近い子ほど $\bm{W} _\mathrm{R}$ の割合が高くなるように,2つの重み行列を混ぜている.

これで,子の数 $M$ に依らず,重み行列は $\bm{W} _\mathrm{L}$,$\bm{W} _\mathrm{R}$ だけになる. $M=2$ では,本質的に,自然言語処理で用いられている方法に一致する.

ちなみに,無闇に一般化すれば良いというものでもない. 結局,最終的な用途(クラス分類やクラスタリングなど)について, 精度が上がらなければ意味がないので,一般化して得するかどうか,実験してみないとわからない.

Backpropagation through structure (BPTS)

冒頭でも述べたように,RNN の訓練には,backpropagation through structure (BPTS) [Go96] という方法を使う. まず,ここでは誤差関数として,以下のように定義される二乗誤差を考える(お好みで,交差エントロピー関数などに置き換えても良い).

ただし,$r$ は根であり,$\mathbf{vec}(r)$ は RNN の出力ベクトル,$\bm{t}$ は目標ベクトルである. そして,誤差逆伝搬法 (backpropagation) において,逆伝搬させる誤差を

とおく($x$ は任意のノード).RNN の順伝搬では,子の特徴ベクトルを基に親の特徴ベクトルを計算するので, 逆伝搬では親 $p$ の誤差を基に子 $c_m$ の誤差を計算する.

![RNN の逆伝搬](/img/RNN-feedback.png)

ただし,$\otimes$ はベクトルの要素単位の積である. 根 $r$ については,親が存在しないので,$\bm{\delta}(x)$ の定義にしたがって,誤差を計算する.

ちなみに,$f’(\bm{a}(c_m))$ は

  • $f$ がシグモイド関数の時は,$f’(\bm{a}(c_m)) = (\bm{1} - \mathbf{vec}(c_m)) \otimes \mathbf{vec}(c_m)$,
  • $f$ が tanh の時は,$f’(\bm{a}(c_m)) = \bm{1} - \mathbf{vec}(c_m) \otimes \mathbf{vec}(c_m)$

で計算できる.葉ではないノードの集合を $S$ とおくと,パラメータの勾配は

\begin{align} \frac{\partial E}{\partial \bm{W}_\mathrm{L}} & = \sum_{p \in S} \bm{\delta}(p) \left( \sum^M_{m=1} (1-\alpha_m) \mathbf{vec}(c_m) \right)^\top \
\frac{\partial E}{\partial \bm{W}_\mathrm{R}} & = \sum_{p \in S} \bm{\delta}(p) \left( \sum^M_{m=1} \alpha_m \mathbf{vec}(c_m) \right)^\top \
\frac{\partial E}{\partial \bm{b}} & = \sum_{p \in S} \bm{\delta}(p) \end{align
}

となる.

サンプルプログラム

せっかくなので,簡単なサンプルプログラムを作ってみた.

このプログラムは

$ ocamlfind ocamlopt -linkpkg -package slap recursiveNeuralNetwork.ml

でコンパイルできる.

例のごとく,Size Linear Algebra Library (SLAP) を使ってプログラミングしている. SLAP については,(私が書いた)以下の記事が詳しい.

参考文献