6.2 Tree LSTM

LSTMs are used in a similar way as GRU through the propagation process based on a tree or a graph.

• Two extensions to the basic LSTM architecture
  • The Child-Sum Tree-LSTM
  • N-ary Tree-LSTM
• Each Tree-LSTM unit contains input and output gates $i_v$ and $o_v$, a memory cell $c_v$, and hidden state $h_v$
• The Tree-LSTM unit abandons the single forget gate but uses a forget gate $f_{vk}$ for each child k, allowing node v to aggregate information from its child accordingly.
• The equations of Child-Sum Tree-LSTM $$\tilde{h}_v^{t-1} = \sum_{k\in N_v} h_k^{t-1}$$ $$i_v^t = \sigma (W^i x_v^t + U^i \tilde{h}_v^{t-1} + b^i)$$ $$f_{vk}^t = \sigma (W^f x_v^t + U^f \tilde h_k^{t-1} + b^f)$$ $$o_v^t = \sigma(X^ox_v^t + U^o \tilde{h}_v^{t-1} + b^u$$ $$u_v^t = \tanh (W^ux_v^t + U^u \tilde{h}_v^{t-1} + b^u)$$ $$c_v^t = i_v^t \odot u_v^t + \sum_{k\in N_v} f_{vk}^t \odot c_k^{t-1}$$ $$h_v^t = o_v^t \odot \tanh(c_v^t)$$
• Tree구조에서 각 노드의 자식 수가 최대 K개이고 자식을 1-K까지 정렬할 수 있을 경우에는 N-ary Tree-LSTM을 적용할 수 있음 
  • The Transition equation $$i_v^t = \sigma (W^i x_v^t +\sum_{l=1}^K U_l^i h_{vl}^{t-1} + b^i)$$ $$f_{vk}^t = \sigma (W^f x_v^t + \sum_{l=1}^K U_l^f h_{vl}^{t-1} + b^f)$$ $$o_v^t = \sigma(X^ox_v^t + \sum_{l=1}^K U_l^o h_{vl}^{t-1} + b^u$$ $$u_v^t = \tanh (W^ux_v^t + \sum_{l=1}^K U_l^u h_{vl}^{t-1} + b^u)$$ $$c_v^t = i_v^t \odot u_v^t + \sum_{l\in N_v} f_{vl}^t \odot c_k^{t-1}$$ $$h_v^t = o_v^t \odot \tanh(c_v^t)$$

Child-Sum Tree-LSTM와 비교해서 N-ary Tree-LSTM은 separate parameter matrices for each child k, which allows the model to learn more fine-grained representations for each node conditioned on the it's children.