Long Short-Term Memory Over Tree Structures

論文: https://arxiv.org/abs/1503.04881
実装: https://github.com/pfnet/chainer/blob/master/chainer/functions/activation/slstm.py (in chainer)

概要

LSTMの木構造への一般化を考える．

背景

LSTMは線形な系列を入力に受け取る，非常に成果をあげているニューラルネットワークである．
しかし，いくつかのケースでは入力が線形ではなく，なんらかの構造を持っていた方が良さそうなケースというものもある．
代表的なものにstanford nlpの[sentiment treebank](https://nlp.stanford.edu/sentiment/)がある．
これは文を構文解析し，構文木が入力として与えて文の極性を予測するタスクである．
葉ノード（単語に相当する）と内部ノード（フレーズに相当する）に対して極性が人手（？）でアノテーションされている．
[Socher et al.](https://nlp.stanford.edu/~socherr/EMNLP2013_RNTN.pd://nlp.stanford.edu/~socherr/EMNLP2013_RNTN.pdf)はRecursive Neural Network(RvNN)・RNTNNを用いてこのタスクを解いた．

RvNNは内部に再帰構造を持っており，木を入力とすることができる一方で，木の深さが深くなると勾配消失が起きてうまく学習できない問題がある．
これは通常のRNNにも見られる問題であり，LSTMはメモリブロックという概念を導入することでこの問題に対処した．
この成果を活かし，RvNNにもLSTMのメモリブロック構造を導入し，より深い構文木が入力されても学習可能なS-LSTM(Structured-LSTM)を提案した．

手法

モデル全体は以下の図のようになっている．
f:id:himkt:20170509121434j:plain

また，各ノードに注目すると以下の図のようになっている．
f:id:himkt:20170509121438j:plain

LSTMと非常によく似た構造であり，差分としてはS-LSTMには忘却ゲートが2つ存在する．
ちなみに，忘却ゲートが2つと言っているが，これは入力される木が2分木であると仮定しているからそうなっているだけであり，n分木の場合は忘却ゲートがn個になる．
著者曰く

> Extension of teh model to handle more children is rather straightforward

である．
ちなみに，なぜ入力が2分木なのかというと，sentiment treebankのデータ構造が2分木であり，Socher et al.と同じ条件で実験しているからである．

入力・セル・重み・入力ゲート・忘却ゲート・出力ゲートについて詳しく見ていく．

$\begin{align} i_t &=& \sigma(W^L_{hi}h^L_{t-1} + W^R_{hi}h^R_{t-1} + W^L_{ci}h^L_{t-1} + W^R_{ci}h^R_{t-1} + b_i) \\\ f^L_t &=& \sigma(W^L_{hf_l}h^L_{t-1} + W^R_{hf_l}h^R_{t-1} + W^L_{cf_l}h^L_{t-1} + W^R_{cf_l}h^R_{t-1} + b_{f_l}) \\\ f^R_t &=& \sigma(W^L_{hf_r}h^L_{t-1} + W^R_{hf_r}h^R_{t-1} + W^L_{cf_r}h^L_{t-1} + W^R_{cf_r}h^R_{t-1} + b_{f_r}) \\\ o_t &=& \sigma(W^L_{ho}h^L_{t-1} + W^R_{ho}h^R_{t-1} + W^L_{co}h^L_{t-1} + W^R_{co}h^R_{t-1} + b_{o}) \\\ x_t &=& W^L_{hx}h^L_{t-1} + W^R_{hx}h^R_{t-1} + b_x \\\ c_t &=& f^L_t \otimes c^L_{t-1} + f^R_t \otimes c^R_{t-1} \\\ h_t &=& o_t \otimes tanh(c_t) \end{align}$

忘却ゲートとセル，および重みが2つあることがわかる．
学習はSocher et al.と同じように行う．ロス関数は2通り考えられている．

1. ノードごとの予測のクロスエントロピーの総和
1. ルートノードの予測のクロスエントロピー

実験

sentiment treebankを用いて評価実験を行なった．
比較対象はSocher et al.のRvNNとRNTN,，あとNaive BayesとSVM．
RvNNは通常のRecursive Neural NetworkでRNTNはRecursive Neural Tensor Network．
RNTNはテンソルを用いたRvNNの一般化(?)モデルであるらしい．Socher et al.を読んでください．

MODEL	ROOTS	PHRASES
NB	41.0	67.2
SVM	40.7	64.3
RvNN	43.2	79.0
RNTN	45.7	80.7
S-LSTM	48.0	81.9

S-LSTMが一番良い性能を発揮した．
S-LSTMはRNTNと比較すると学習にかかる時間が短い点もアピールされている（論文を読んでください）．

ここからが面白い点だが，著者らはsentiment treebankのアノテーションはあまり現実のデータに則していないことを指摘している．
というのも，sentiment treebankは木のすべてのノードに対してアノテーションを行なっているが，現実のデータにフレーズ単位のアノテーションが付与されているとは考えにくい．
そのため，フレーズ単位のアノテーションが得られていない以下の2つの設定で追加実験をを行なった．

(a)ルートノードにのみアノテーションが付与されている
(b) 葉ノードとルートノードにアノテーションが付与されている)

おそらく以下のようなデータが与えられている（赤色がアノテーションされていることを示す）．
f:id:himkt:20170509121430j:plain

MODEL	ROOTS
(a) RNTN	29.1
(a) S--LSTM	29.1
(b) RNTN	34.9
(b) S--LSTM	44.1

同じ条件下ではRNTNよりも良い予測性能を発揮していることがわかる．

議論の腰を折りかねない疑問として「本当に入力に構造があった方が良いのか？」というものがある．
通常のLSTMも暗黙的に構造のようなものを学習していて，入力データには明示的な構造は必要ないのではないかという意見も起きうる．
そこで，データに対して特殊な制約を加えて，それらのデータを学習に使った場合と木構造を入力とした場合の予測性能も比較している．

LSTM--LRとLSTM--RRという2つの特殊なデータは，本来木構造を持っていた入力データの枝を張り替えて，構造を壊したものである．
LRは文中の1番左の単語の左側にルートノードを張り，RRは1番右の単語の右側にルートノードを張っていることを示している．

MODEL	ROOTS
(a) S--LSTM--LR	40.2
(a) S--LSTM--RR	40.3
(a) S--LSTM	43.5
(b) S--LSTM--LR	43.1
(b) S--LSTM--RR	44.2
(b) S--LSTM	44.1

LRとLLはほぼ同じ性能，もともとの木構造を入力としたものがそれより良い性能を発揮していることがわかる．
この結果から，著者は少なくともいくつかのタスクにおいては入力データの木構造は予測性能に影響を与えると結論付けた．