Tree-Structured Attention with Hierarchical Accumulation
Authors: Xuan-Phi Nguyen
Shafiq Joty
Steven Hoi
Richard Socher
Venue:  (2020)
Keywords: Tree
Constituency Tree
Hierarchical Accumulation
Machine Translation
NMT
WMT
IWSLT
Text Classification
Sentiment Analysis

Abstract: Incorporating hierarchical structures like constituency trees has been shown to be effective for various natural language processing (NLP) tasks. However, it is evident that state-of-the-art (SOTA) sequence-based models like the Transformer struggle to encode such structures inherently. On the other hand, dedicated models like the Tree-LSTM, while explicitly modeling hierarchical structures, do not perform as efficiently as the Transformer. In this paper, we attempt to bridge this gap with Hierarchical Accumulation to encode parse tree structures into self-attention at constant time complexity. Our approach outperforms SOTA methods in four IWSLT translation tasks and the WMT'14 English-German task. It also yields improvements over Transformer and Tree-LSTM on three text classification tasks. We further demonstrate that using hierarchical priors can compensate for data shortage, and that our model prefers phrase-level attentions over token-level attentions.

Published as a conference paper at ICLR 2020
TREE-STRUCTURED
ATTENTION
WITH
HIERARCHICAL ACCUMULATION
Xuan-Phi N "haafi Jotyf1, I Steven C.H. Hoi', Richard Sucher
Salesforre Research
i *Nanyang Technological University
nguyenxu0028e. ntu. ntu.edu. sg, shooo
ABSTRACT
Incorporating hierarchical structures like constituency trees has been shown be effective for various natural language processing (NLP) tasks. However, it is evident that state-of-the-ard (SOTA) sequence-based models like the Transformer struggle to encode such structures inherently. On the other hand, dedicated models like the Tree-LSTM, while explicitly modeling hierarchical structures, do not perform efficiently as the Transformer. In this paper, attempt to bridge this gap with "Hierarchical Accumulation" to encode parse tree structures into self- attention at constant time complexity. Our approach outperforms SOTA methods in four IWSLT translation tasks and the WMT' 14 English-German task. It also yields improvements over Transformer and Tree-LSTM three text classification tasks. We further demonstrate that using hierarchical priors can compensate for data shortage, and that model prefers phrase-level attentions over token-level attentions.
German translation
INTRODUCTION
Although natural language has linear surface form, the underlying construction process is known to be hierarchical (Frege 1892). As such, different tree-like structures have been proposed to represent the compositional grammar and meaning of text, such as constituency and dependency trees. Leveraging the hierarchical structures of language gives models more structural information about the data and improves performance on the downstream tasks (Tai et al. 2015) Eriguchi al. 2016).
Despite that, state-of-the- art neural models like the Transformer still prefer the linear (sequential)
form of natural language (Vaswani et al. 2017 7 Ott al. 2018 Devlin et al. 2018). This is because the linear form allows us to develop simple but efficient and scalable techniques (like self-attention which operates at constant parallel time complexiry to train models a large scale. Yet, there still no concrete evidence that these models learn grammatical and constituency structures implicitly. However, ad hoc tree-structured models (Socher et al. 2013) Tai et al.) 20155: [hhi et al., 2018) often operate recursive recurrent mechanisms, which are not parallelizable. thus hindering their application in larger-scale training. Besides, such models are designed to only operate at the sentence-level (i.e., single tree), limiting their application to document-level processing.
We propose a novel attention- based method that encodes trees in a bottom-up manner and executes competitively with the Transformer at constant parallel time complexity. In particular, our attention layers receive as input the constituency tree of a piece of text and then model the hidden states of all nodes in the tree (leaves and nonterminals) from their lower-layer representations according to the tree structure. As attentions typically have query, key and value components, our model uses hierarchical accumulation encode the value component of each nonterminal node by aggregating the hidden states of all of its descendants. The accumulation process is three-staged. First, we induce the value states of nonterminals with hierarchical embeddings, which help the model become aware of the hierarchical and sibling relationships between the nodes. Second, we perform an upward cumulative-average operation on each target node, which accumulates all elements in the branches originating from the target node to its descendant leaves. Third, these branch-level representations
Work done during an internship at Salesforce Research Asia, Singapore.
Given GPUs, "constant parallel time" process can perform all its computations once algorithmically.

---

Published as a conference paper at ICLR 2020
combined into new value representation of the target node by using weighted aggregation. Finally, the model proceeds to perform attention with subtree masking where the attention score between nonterminal query and a key is activated only if the key is a descendant of the query.
Our contributions are threefold. First, we present our attention- based hicrarchical encoding method. Our method overcomes linear parallel time complexity of Tree-LSTM TTai et al. 2015) and offers attractive scalability. Second, we adopt our methods within the Transformer architecture and show improvements across various NLP tasks over strong baselines. In particular, our model leverages tree-based prior to improve translation quality over the Transformer baselines in the IWSLT" 14 Baglish-German and German German-English, the IWSLT'13 English-Frenn French and French- French-English, and the WMT 14 English-German translation tasks. Furthermore, our model also exhibits advantages over Tre--ISTM classification tasks including Stanford Sentiment Analysis (SST) (Socher et al.) 2013). IMDB Sentiment Analysis and Subject-Verh Agreement (Linzen et al.) 2016). Finally, our analysis of the results suggests that incorporating hierarchical prior using our method can compensate for the lack of data in the context of machine translation. We also demonstrate that the model has natural and consistent preference for phrase-level attention over token-level attention. transformer
Our souree code is available at
2 RELATED WORK
The Transformer framework has become the driving force in recent NLP research. For example, it has achieved state-of-the--e art performance in machine translation tasks (Vaswani et al. 2017] Shaw
et al. 2018 Out et al. 2018 Wu et al. 2019) and self-supervised representational learning (Devlin al. 2018 Radford al.J 2018) Lample Conneau 2019) Yang et al., 2019). The self-attention layers in the Transformer encode sequence constant parallel time complexity. which makes it parallclizeable and scalable. On the other hand, there have been many proposals to use parse frees as architectural prior to facilitate different downstream tasks. [Socher et al. (2013) adopt recursive compositional method over constituency trees to solve sentiment analysis a bottom-up manner. Tree-LSTM (Tai al. 2015) improves the task performance by using an LSTM structure to encode trees recurrently. Both of the proposed methods, while effective, operate sequentially in parallel time complexity. Tree structures have also been used as an architectural bias improve machine translation (Eriguchi et al. 2016 Shi et al. 2018 Yang et al. (017). Constituency trees can also be decoded in top-down manner, as proposed (Alvarez-Melis & Jaakkola, 2017; Gü
et al. 2018 Besides, they can also be learned in an unsupervised way (Kim et al.) 2019]] Shen
al. 2018 2019| Yaushian Wang Chen 2019). Meanwhile, [Strubell et al. (2018): |Hao et al. Harer et al. (2019) attempted to incorporate trees into self-attention. |Hwwttt & Manning
(2019);
2019
showed that dependency semantics are already intrinsically embedded BERT (Devlin et al,,
2018).
Concurrently, Yaushian Wang & Chen (019) suggested that BERT may not naturally embed
constituency semantics.
Our approach encodes trees in bottom-up manner Tai al. 2015) and Socher al. 2013)) But it differs from them in that it leverages the attention mechanism to achieve high efficiency and performance. Plus, it is applicable self- and eross aross-attention layers in the Transformer sequence- to-sequence (Seq2Seq) skeleton. Unlike previous methods, our model works with multi-sentence documents (multi-tree) seamlessly. Our model also differs from Strubell al. (2018); Hao et al.) 2019); Harer et al.] (2019) in that their methods only use tree structures to guide and mask token- level attentions, while ours processes all the nodes of the tree hierarchically. In this paper, while applicable to dependency trees, our approach focused primarily on constituency trees because (1) constituency trees contain richer grammatical information in terms of phrase structure, and (2) there is yet no evidence, to the best of our knowledge, that constituency structures are learned implicitly in the standard self- supervised models.
BACKGROUND - TRANSFORMER FRAMEWORK
The Transformer Vaswani al.) 2017 Seq2Seq network that models sequential information using stacked self- and cross-altention layers. The output O of each attention sub-layer is computed via scaled multiplicative formulations defined as:
A (KW /T/V;;
An(Q, K, V) softmax (s))ma)(A((VW))
2

---

Published as a conference paper at ICLR 2020
Interpolation
Upward-CA
Weighted-
F
u
h
S
$
N
Figure 1:
The hierarchical accumulation process of tree structures (best seen in colors). Given a parse tree, it is interpolated into tensor S, which is then accumulated vertically from bottom to top to produce S. Next, the (branch-level) component representations of the nonterminal nodes are combined into one representation as V by weighted aggregation. Multi-colored blocks indicate accumulation of nodes of respective colors. The rows of S in Eq. S are counted from the bottom.
O At
where softmax is the softmax function, Q = (Q)...,, Q.,) E Rloxd, K = (ki...., kv,) E Riexd V (u1,-.,, Ui, Rlexd matrices of query, key and value vectors respectively, and E Rddd are the associated trainable weight matrices. A denotes the affinity
Wº, W scores (attention scores) between queries and keys, while Att(Q, K, V) are the attention vectors. Then, the final output of a Transformer layer is computed as:
(A, = LN(FFN(LN(O + Q)) +N + QQ)
(3)
where @ represents the typical serial computations of Transformer layer with layer normalization (LN) and feed-forward (FFN) layers. For simplicity, we omit the multi-head structure and other details and refer the reader to Vaswani et al. (2017) for complete description.
4 TREE-BASED ATTENTION
4.1 ENCODING TREES WITH HIERARCHICAL ACCUMULATIONS
To encode hierarchical structures in parallel, we need to represent the tree in a data structure that be parallellized. Given sentence X of length n, let G(X) be the directed spanning tree which represents the parse tree of X produced by a parser. We define a transformation H such that H(G(X)) = T(X) (C,N,
this formulation, L denotes the ordered sequence of terminal nodes (or leaves) of the tree (i.e., L X), and A denotes the set of m nonterminal nodes (or simply nodes), each of which has phrase label (e.g., NP, VP) and spans over a sequence of terminal nodes 2 R contains set of rules indexed by the nonterminal nodes in N such that for each node x E N, R(x) denotes the set of all nodes that belong to the subtree rooted at æ. For example, for the nonterminals y and h in Figure R(g) {g, c, h d, e) and (A) (h, e).
There might be various ways to transform the tree g(X). For a tree-encoding process, particular transformation is legitimate only if the resulting data structure represents only G(X) and not any other structures. Otherwise, the encoding process may confuse G(X) with another structure. In other words, the transformation should be one-to-one mapping. Our transformation H satisfies this requirement as shown in the following proposition (see Appendix 7.1 for proof).
Proposition 1 Suppose g(X) is a parse tree and there exists a inverse-tranfformation I that converts T(X) to a graph I(T(X)) then I can only transform T(X) back G or:
I(H(G(X))) ((X)
I = =
(4)
We now describe the tree accumulation method using T(X). Figure shows the overall process. Let L (4,,..,th)) E ga and N (ni,... Rmm) E gg be the hidden representations of the
We omit the part-of-speech tags of the words which constitute the preterminal nodes in constituency tree.
3

---

Published as a conference paper at ICLR 2020
leaves C (af ..., 2,,) and nodes N (xf ..... TM), respectively. We define an interpolation
function F (RRad Ix + R (mmx))x which takes L, N and R as inputs and returns
tensor S E R (mm+1)xxxdd The row i and column j vector of S, or Si.i E Rd. is defined as:
if else if af R(a
S.j. F R):
n;-1
(5)
otherwise.
where 0 denotes zero vector of length d. Note that the row and column arrangements in S reflect the tree structure (see Figure []. Next, we perform the upward cumulative-average (upward-CA) operation on to compose the node representations
bottom-up fashion over the induced tree structure. The result of this operation is a tensor $ E [mxxxxd in which each nonterminal node representation is averaged along with all of its descendants in particular branch. More formally,
uS)), = SS.j = Es, S
{
if Sit1j otherwise.
where Cj (S1,) (Su R(xx")} is the set of vectors in S representing the leaves and nodes in the branch that starts with nzY and ends with zzf. Note that we discard the leaves in S. As demonstrated in Figure I each row i of represents nonterminal node x and each entry Sijj represents its vector representation reflecting the tree branch from .r to leaf wff. This gives [R(x;)) ) n C different constituents of N.N that represent the branches rooted at a.".
The next task is combine the branch-level accumulated representations of nonterminal a: into single vector n., that encapsulates all the elements in the subtree rooted by xr Our method does so with weighted aggregation operation. The aggregation function takes as input and a weighting vector w IK" and computes the final node representations N (n1,... Rmm)) E IR mxx where each row-vector n. in N is computed as:
V w); = n2 CNR( jufER((M))
W/ @ S
where @ denotes the element-wiss multiplication. Specifically, the aggregation function V computes a weighted average of the branch-level representations. summary, the hierarchical accumulation process can be expressed as the following equation:
N V(u(S)) w) VUU(FLL R)),
(8)
4.2 HIERARCHICAL EMBEDDINGS
While the above technique is able to model the states of nonterminal nodes as an encapsulation of their respective descendants, those descendants are equally treated since no biases are imposed on them. In other words, although each branch from node comprises a distinctive descendants, the hierarchy of elements within a branch and the sibling relationship among branches are not explicitly represented. Thus, it may be beneficial to introduce biases that reflect such underlying subtree- level hierarchical structures. We propose Hierarchical Embeddings to induce distinguishable tree structures into the tensor S before being accumulated by Z/ and V. We also demonstrate the effectiveness of these embeddings with experiments in Section 5 Figure 2 illustrates the hierarchical embeddings for the nodes in Figure [ Given construct
2:1
2:2
2:3
3:4
4;5
1:1
1:2
of
1:1
2:2
2:3
1:1
1:2
0
0
Hierarchical Embeddings. Each block E.,j is an embedding vector (et; et] with indices y following the syntax "z;y", where = IV and y [H)) "O" indicates no embedding.
Figure 2:
L, N and R. as defined in Section 4.1
4

---

Published as a conference paper at ICLR 2020
tensor of hierarchical embeddings E R (mm+1)xxxd with entries defined as follows:
E. - -{
[ ( 1199
if and uf E R(()))
otherwise.
where Vj {a loy R(xN) and of Rxx))) the set of af's ancestors up to x and H = ( j and of E L Ln } is the set of leaves from the leftmost leaf up to af of the 2. -rooted subtree; ex and eº are embedding row-vectors of the respective trainable vertical and horizontal embedding matrices E", E. glA|x and (o: e] denotes the concatenation operation in the hidden dimension. The vertical embeddings represent the path length of node to leaf which expresses the hierarchical order within branch, whereas the horizontal embeddings exhibit the relationship among branch siblings in subtree. The resulting node representations after hierarchical encoding are defined as:
N V(U(S + E), E)
(10)
Note that we share such embeddings across attention heads, making them account for only 0.1 1 of the total parameters (see Appendix 7.3 for more information).
4.3 SUBTREE MASKING
Masking attentions is common practice to filter out irrelevant signals. For example, in the decoder self-attention layers of the Transformer, the affinity values between query qi and key k, are turned off for j > to avoid future keys being attended since they are not available during inference. This can done by adding to the affinity 9, k infinitely negative value (-oo) that the resulting attention weight (after softmax) becomes zero.
g
In the context of tree-based attentions (to be described next), we promote the bottom-up structure by introducing subtree masking for encoder self-attention Fl That is, if node-query g. N is attending to set of node-keys k."" W and leaf-keys be E L. attentions are turned on only for affinity pairs whose key belongs to the subtree rooted at q." In other words, each node-query has access only to its own subtree descendants, but not to its ancestors and siblings. On the other hand, if leaf-query of is attending. only leaf-keys are turned on, like in the Transformer. Figure 3 illustrates the subtree masking with example. More formally,
Figure 3: Subtree masking- Given the query at position 9. attentions are only included within the g-rooted subtree, while the remaining elements are masked out (shaded).
given Oij as the affinity value between a node/leaf-query E NUL and a node/teaf-key k; E NUC, the masking function j is defined as:
p(ar))
= aij aij
iq: N and ky E R(q:)) or (g., ky E ()) otherwise.
(11)
4.4 INTEGRATING INTO TRANSFORMER FRAMEWORK
In this section, we describe how the above proposed methods fit into self- and cross-attentions of the Transformer framework, which enable them to efficiently encode parse trees.
Encoder Self-attention. Figure 4a visualizes the encoder self-attention process. Without loss of generality, let L E x and N E m respectively denote the leaf and node representations that a Transformer encoder laver receives from its previous layer along with the parse tree represented T(X) (C, .. R) The tree-based self-attention layer then computes the respective output representations L and N. Specifically, first, we compare the node and leaf representations against
'I can only he done in the encoder self-attention. *For the first layer, L and N token embeddings; L also has positional encodings.
5

---

Published as a conference paper at ICLR 2020
ALL
ALL,
A
NIN
NL
LN
LL
QN
QU
Linear
Linear
Linear
Linear
Lineer
Lineer Q
Target
(a) Encoder Sell-attention
(b) Decoder Cross-attention
Figure 4: Illustration of the proposed Tree-based Attentions: (a) Encoder self-attention, (b) Decoder cross-attention. Cirele-ended arrows indicate where hierarchical accumulations take place. The overall Transformer architecture is provided in Figure (Appendix 7.3
each other to produce query-key affinity matrices ANL R ANN Rmxm ALL R and AN E Raxm for node-leaf (i.e., node representation as the query and leaf representation as the key), node-node, leaf-leaf, and leaf-node pairs, respectively, follows:
ANz. = (NWK) /Va
(12)
ALL. - (LW9)/WWW
(13)
ANN (NWK))NW
(14) ALN (LW9) (15)
Then, the value representation L of the leaves is computed by a linear layer, while the value representation N' of the nodes N is encoded with tree structure using the hierarchical accumulation
process (Section 4.1 4.2) as:
N = V(U(F(LWV NWW. R) + E), L LWV
(16)
where w Lu, with u, Rd being a trainable vector, while the weight matrices W WK WV. and W are similarly defined as in Section 3 After this, the resulting affinity scores for leaves and nodes are concatenated and then masked by subtree masking (Section 4.3 to promote bottom-up encoding. The final attention for the nodes and leaves are then computed by taking the weighted averages of the value vectors in N and L:
Atty = (iNimmax((((AAN:AAAAi
L) (17) Att, softmax(M((A ALL)) (18)
Both Att and Att,, are then passed through the Transformer's serial computations by function (Eq. in Section which results the final output representations Ñ and É as follows:
= O(ttN O N)
(19)
i
L)
(20)
Decoder Cross-attention. For tasks involving generation (e.g., NMT), we also use tree-based encoder-decoder attention (or cross-attention) in the decoder that the target-side queries can leverage the hierarchical structures in the source side (tree2seq). Figure/4bJshow the cross-attention process. Specifically, given the target-side query matrix Q Rxxd and the source-side leaf and node matrices and N, the affinity scores AQN E x and Aqr. E R are computed as:

---

Published as a conference paper at ICLR 2020
IWSLT
WMT En-De
Model
En-De
En-Fr
De-En
Fr-En
Base
Big
Tree2Seq (Shi et al. 2018
24.01
40.22
29.95
39.41
2Sn (Gehring et al..
2017)
24.76
39.51
30.32
39.56
25.16
Transformer (aaswam et al. 2017)
28.35
43.75
34.42
42.84
27.30
29.30
Dynamic Conv Wu et al. 2019
28.43
43.72
34.72
43.08
27.48
29.70
Ours
29.47
45.53
35.96
44.34
28.40
29.95
Table I: BLEU scores for the base models on IWSLT English++Grmma, IWSLT" 13
English++French, and the base and big models on WMT English->Germanl ~German task. Refer Table in the Appendix for parameter comparisons.
AqN = (QWW))NNKK)) (21)
Aor = (Q.=
(22)
Similar to encoder self-attention, the node representations N are encoded with the tree structure and the attention output Alto of decoder cross-attention computed as:
N VVU(FLWWV .WW. R) + E), w) L LWV:
(23)
Atto softmax (AQN; Aqu)) [N: L
(24)
where Lu, with u RRd Note that cross- gross-attention does not adopt subtree masking because the queries are from another domain and are not elements of the source tree.
Remark on Speed. Our model runs competitively with the Transformer, thanks to its constant parallel time complexity. In terms of sequential (single-CPU) computations, the hierarchical accumulation process takes O log( (N) time and our entire model maintains time complexity identical to the Transformer, which is O(N3); see Appendix 7.2 for proof.
5
EXPERIMENTS
We conduct experiments two types of tasks: Machine Translation and Text Classification.
5.1
NEURAL MACHINE TRANSLATION
Setup. We experiment with five translation tasks: IWSLT' 14 English-German (En-De), German- English (De-En). IWSLT' 13 English-French (En-Fr), French-English (Fr-En), and WMT' 14 English-German. We replicate most of the training settings from Out et al. (2018) for our models, enable a fair comparison with the Transformer-basee 2019). For IWSLT experiments, we trained the base models with d = 512 for 60K updates with a batch size of 4K tokens. For WMT, we used 200K updates and 32K tokens for base models (d = 512), and 20K updates and 512K tokens for the big models with d = 1024. We parsed the texts with the Stanford CoreNLP parser (Manning et al.) 2014). We used Byte Pair Encoding (Sennrich et al. 2016), where subwords of word form subtree. More details are provided in Appendix 7.4
methods (Vaswani et al. 2017, Wu et al.,
Results. Table shows the BLEU scores for the translation tasks. Our models outperform the baselines consistently in all the tested tasks. The results demonstrate the impact of using parse trees as prior and the effectiveness of our methods in incorporating such a structural prior. Specifically, our model surpasses the Transformer by more than BLEU for all IWSLT tasks. Our big model also outdoes dynamic convolution (Wu et al. 2019) by 0.25 BLEU.
5.2 TEXT CLASSIFCCATION
Setup. We also compare our attention attention-based tree encoding method with Tree-LSTM (Tai et al. 2015) and other sequence-based baselines the Stanford Sentiment Analysis (SST) (Socher al.
7

---

Published as a conference paper at ICLR 2020
Training Corpus Size Analysis
Training/Ifferecee Time Analysis
BLEU 30
TreeLSTM
1,500
TreTTransormmr
Transformee
20
1,000
Treel STM-Infer
Inffe
Tree Transfornerr Transformer DynamicConv
500
10
90K
225K
450K
1.1M
2.2M
3.4M 4.5M
16
32
6A
128
256
(a)
14
English-German
BLEU
on
(b) Elapse training and inference time in seconds (y- axis) w.r. sequence length (x- (x-axis).
newstes12014 with varying size of training data.
Figure 5: Training data size and training/inference time analysis.
Model
En-De
En-Fr
De-En
Fr-En
Leaves/Nodes
59.2/40.8
59.3/40.7
66.4/33.6
64.7/35.3
Target- Noodes 66.4=2e-4
61.9:6e-4
44
59.3+22-2
Table 4: Attention distributions (%) between phrases (nodes) and tokens (leaves) across different translation tasks. Statistics are derived from IWSLT' 14 En-De and IWSLT' 13 En-Fr test sets.
2013), IMDB Sentiment Analysis and Subject- Verb Agreement (SVA) (Lizzen et al. 2016) tasks. We adopt tiny-sized version of tree-based models and the Transformer baseline. The models have 2 Transformer layers, 4 heads in each layer, and dimensions d = 64. We trained the models for 15K updates, with a batch size of 2K tokens. Word embeddings are randomly initialized. We provide further details of the setup in Appendix 7.4 For the Stanford Sentiment Analysis task (SST), we tested on binary (SST-2) and fine-grained (SST-5) subtasks, following Tai al. (2015).
Results. Table 2 shows the results accuracy on the classification tasks. Our Tree Transformer outperforms sequence-based Transformer and BiLSTM baselines in all tasks by wide margin. This suggests that small datasets, our models with more appropriate structural bias can provide outstanding improvements compared to the vanilla Transformer. Furthermore, surpass Tree-LSTM significantly in all the tested tasks, which also demonstrates our method's effectiveness compared the best existing tree-encoding method.
models also
Tree-Based Models
Model
En-De En-Fr SST-5
Task
Transformer BiLSTM
Tree-LSTM Ours
Tree Transformer
29.47
45.53
47.4
SST-5
37.6
35.1
43.9
47.4
-HierEmb
29.20
44.80
46.1
SST-2
74.8
76.0
82.0
84.3
SubMask
29.05
45.07
45.7
IMDB
86.5
85.8
90.1
HierEmb -SubMask -ubMassk
28.98
44.50
45.0
SVA
94.4
95.1
96.2
98.0
Table 3: Performances of different model
Table 2: Classification results in accuracy (%)
variants IWSLT' En-De, IWSLT' 13 En-Fr and Stanford Sentiment Analysis (ene--gained) tasks. '-HierEmb': : no hicrarchical embeddings, SSubaask': no subtree masking.
Stanford Sentiment Analysis fine- fine-grained (SST-
5) and binary (SST-2), IMDB sentiment analysis, and Subject- Verb Agreement (SVA) tasks.
5.3 ANALYSIS
Model Variations. In Table 3 we examine the contributions of each component of our Tree Transformer on IWSLT' 14 English-German translation task and Stanford Sentiment Analysis (fine- grained) task. We see that removing either or both of hierarchical embeddings and subtree masking methods has negative impact the model performance.
8

---

Published as a conference paper at ICLR 2020
shows how our model performs compared to the baselines on WMT' 14 Baglish-Germaid translation task with varying amounts of training data. is apparent that our model yields substantial improvements (3.3 to 1.6 BLEU) when the training data is less than million pairs (< 20% of WMT'14), The margin of gains gradually decreases (1.0 to 1.1 BLEU) with increasing training data. We observe similar trend in the classification tasks (Table 2 where our model outperforms sequence-basee methods by around 10% absolute in accuracy. This suggests that utilizing hierarchical architectural bias can compensate for the shortage of labeled data in low- now-resource scenarios.
Effectiveness Small Datasets. Figure 5a
Training Time Analysis. Figure 5b shows the empirical training time and inference time for the Transformer, Tree-LSTM, and our Tree Transformer with respect to input sequence length. All the models are trained on a sentiment classification task on a single GPU for 1000 iterations with a batch- size of 1. We can that the training time for Tree-LSTM grows linearly with the sequence length. The training time for the vanilla and Tree Transformer are much less than that of the Tree-LSTh and remain relatively
plateau with respect the sequence length. This demonstrates our model's speed efficiency compared to Tree-LSTM or other recurrent/recrsivee methods. For inference, we take into account the parsing time of the Stanford parser (O(N)) which substantially overwhelms the overall timing.
Phrase- vs. Token-level Attentions. Table[showw how frequently a target language token attends to phrases (nodes) tokens (leaves) in the source tree. We see that although 60-66% of the source tree constituents are leaves, attentions over nodes overwhelm those over leaves (around 59% to 66%) consistently across all translation tasks, meaning that the model slightly favors phrasal attentions. The results also suggest that the attention concentrations are not correlated with the leaf/node ratio; rather, they depend on the language pairs. Leaf/node ratios might be a trivial explanation for the phenomenon, but the results indicate that certain language-dependent factors may be at play.
6 CONCLUSION
We presented novel approach to incorporate constituency parse trees an architectural bias to the attention mechanism of the Transformer network. Our method encodes trees in a bottom-up manner with constant parallel time complexity. We have shown the effectiveness of our approach on various NLP tasks involving machine translation and text classification. On machine translation, our model yields significant improvements IWSLT and WMT translation tasks. On text classification, it also shows improvements on Stanford and IMDB sentiment analysis and subject-verb agreement tasks.
REFERENCES
David Alvarez-Melis and Tommi S Jaakkola. Tree-structured decoding with doubly-recurrent neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Jacob Devlin, Ming-Wet Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint wrXiv:1810.04880) 2018.
Akiko Eriguchi, Kazuma Hashimoto, and Yoshimasa Tsuruoka. Tree-to-sequence attentional neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 823-833, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 10.18863//1/111-1100
URL https:
7/ www. ac www..b.w....c....cc...........bb org/ http://thoooooo/o1ll0000
Gottlob Frege. über sinn und bedeutung. Zeitschrifi für Philosophie Und Philoxophische Kritik, 100 (1):25-50, 1892.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional Sequence to Sequence Learning. In Proc. of ICMI., 2017.
Jetic Gü, Hassan S. Shavarani, and Anoop Sarkar. Top-down tree structured decoding with syntactic connections for neural machine translation and parsing. In Proceedings of the 2018 Conference on

---

Published as a conference paper at ICLR 2020
Empirical Methods in Natural Language Processing, pp. 401 413. Association for Computational Linguisties, 2018. /ALLattt::///c..bbboo/////aaate
Jie Hao, Xing Wang, Shuming Shi, Jinfeng Zhang, and Zhaopeng Tu. Multi-gramularity self- attention for neural machine translation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, 2019.
Jacob Harer, Chris Reale, and Peter Chin. Tree-transformer: A transformer-based method for correction of tree-structured data, arXiv preprint urXiv: 00449, 2019.
John Hewitt and Christopher D Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and
Short Papers), pp. 4129-4138, 2019.
Yoon Kim, Alexander M Rush, Lei Yu, Adhigunaa Kuncoro, Chris Dyer, and Gábor Melis. Unsupervised recurrent neural network grammars. arXiv preprint arXiv:1904.03746, 2019.
Guillaume Lample and Alexis Conneau. Cross-lingual language model pretraining. arXiv preprint arXiv:190..07221, 2019.
Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. Assessing the ability of Istms to learn syntax- sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521- 535, 2016. ISSN 2307-387X.
www.ee///////dexx...o/oo/x///xx. wwtpiipwp..p...././//pppppp php/tacc/
article/view/91
Christopher D. Manning. Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. The Stanford CoreNLP natural language processing toolkit. In Association for Computational Linguistics (ACL) System Demonstrations, pp. 55-60, 2014. URL URLhttp:
7/www.
Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation.
In Proceedings of the Third Conference on Machine Translation (WMT), 2018.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. URL tttp:://s3uu-wesst amazonaws. com/openai- understanding paper. pdf. 2018.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers). pp. 1715-1725. Association for Computational Linguisties, 2016. doi: 10.18653/v1/PPE 1/1/3///1/P11111 1162. URL http:/ www.:w/wwww......... wtq//nttologgooeogooeo
F16-11621
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp. 464 468. Association for Computational Linguistics, 2018. doi: 10.18653/v1/ N18-2074. URL http://wwwwwb..r//tttttttaaeeeee
2074
Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio. Straight to the tree: Constituency parsing with neural syntactic distance. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1171-1180. Association for Computational Linguistics, 2018. URL http://
aclweb. www.we.brgggooo... wawgg/nnthllogyyPl. 1108
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. In International Conference on Learning Representations, 2019. URL /etttps://ppereeeeee htt.i/ewwwee//eee.eeeeeeeeeeeeee httt//oorom211-11111
Haoyue Shi, Hao Zhou, Jiaze Chen, and Lei Li. On tree-based neural sentence modeling. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2018. Association for Computational pp. 4631-4641, Brussels, Belgium, htth:t::: /wwwwwa...mmmoom aclweb. org/anthology. Linguistics. doi: 10.186533/1/DI8-1444
D18 218-1499 1492
10

---

Published as a conference paper at ICLR 2020
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning. Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631-1642. Association for Computational Linguistics, 2013. URL http:// ac welweb... erg/ antho 1tw.m/hhhhooy/1111111100
Emma Strubell, Patrick Verga, Daniel Andor, David Weiss, and Andrew McCallum. Linguistically- informed self-attention for semantic role labeling. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 5027-5038, Brussels, Belgium, Octoher-November 2018. Association for Computational Linguistics. doi: 10.18653/v/ D18- 1548. URL //ww: aclweb hwrg//nnthloogy/Dee 1548
Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1556-1566, Beijing, China, July 2015. Association for Computational Linguistics. doi: 1/1155/11/155111500 URL https: www awwawllwweb.... org/ aathoooggoPPi5555
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5998-6008, 2017.
Felix Wu, Angela Fan, Alexei Baevski, Yann Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. In International Conference Learning Representations, 2019. WRRL/tttss//openreeee wwt.://wwwwweeeeeeeeeeeeeeeeeeee wttp:eeeeooooonndannmm.tammmmm
Baosong Yang, Derek F. Wong, Tong Xiao, Lidia S. Chao, and Jingbo Zhu. Towards bidirectional hierarchical representations for attention-based neural machine translation. In Proceedings of the 20/7 Conference on Empirical Methods in Natural Language Processing, pp. 1432-1444 1441, Copenhagen, Denmark, September 2017. Association for Computational Linguistics. doi: 10. 18653/v URL wtttps::///
aclweb. http://aaccooooyo///1111111111
Zhilin Yang. Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. arXiv preprint DrXiv:/906.080 2019.
Hung- Yi Lee Yaushian Wang and Yun-Nung Chen. Multirree transformer: Integrating tree structures into self-attention. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, 2019.

---

Published as a conference paper at ICLR 2020
7 APPENDIX
7.1 PROOF FOR PROPOSITION
In this section, present a proof of Proposition 1 The main argument of this proposition is that in order for H to be a legitimate transformation of the parse tree ((X), it must preserve the uniqueness of the hierarchical structure encoded by the tree. Otherwise speaking, the result of such transformation must reflect the tree (X) and only ((X), and not any other tree form. If H does not have this property, it may transform two different tree structures into an identical representation, which will make the downstream tree-encoding process ambiguous. This property also means that in a parse tree (1) every node (either leaf or nonterminal node) has at most one parent, and (2) a nonterminal node which has multiple children can tell the sibling order between its children.
For requirement (I) specifically, except for the root node which has no parent, all other nodes have one and only one parent. Therefore, Proposition D implies that if there exists a inverse- transformation I, it must be able to find the exact parent given any node in the tree. Our proposed transformation H. satisfies this property. Formally, let r E LUN be node in the tree and p(x:) E N be the parent of x. We define P(x) = {y E N/ E R(y) to be the set of all ancestors of æ. Thus, the parent of should belong to P(x). From that, we derive the parent p(zx of ar as:
(25) As implied in Equation 25 the parent p(x) is one of the ancestors of æ whose subtree does not encapsulate any of the ancestors in P(r) except itself. In other words, the parent is the immediate
p(z) y/2 E P(z) such that Ryy,) n P(z) {yz}
ancestor. In a parse tree, there is at most one node Yv that satisfies this condition. We prove this by contradiction below.
Proof Suppose there exists pf (x: = V/= + yv such that ((P))) = (V/1), i..,, x. has 2 parents. Under this assumption, there will be two different paths from the root node to one via ya and the other via Va- This makes a closed cycle. However, parse tree is an acyclic directed spanning tree, which does not have cycles. Thus, by contradiction, if ((x) is a spanning tree reflecting the true parse tree, then v'=-
ys.
For requirement (2), we can prove it by exploiting the fact that in the definition of T(X) A (C.N,, R), L is ordered according to the original word order in the text. Generally speaking, if a nonterminal node x has children (c² (c......c c²), each child node c² heads (or bears) its own subtree R(c*) which includes certain leaves R(c*) N.C. Then, the order of leaves L indicates the order of different leaf sets R(c²) n,, which in turn indicates the sibling order of the children of node x.
Formally, let L = (4,.....4, (n) where 4, is the i-th word in the input text, and is arbitrary nonterminal node whose children are (c.,...e'') (for t > 1) with any two of them being ch and Ih (ct then either:
{ (1 < 1 44 E R(c n L and Vl, E R(ckt) n L) or
(26)
(i ( j VI, E R(ch) n and Vl, E R(ch") n n.)
We proceed to prove the first clause in Equation 26 while the second clause can be similarly inferred.
Specifically, the first clause in Equation 26 implies that if there exists a leaf Ly E R(c²) n L and leaf 1y E R(c=") n L such that < j'. then < VI, E R(ck) L and Vl,- E R(c²") n L, or in other words, subtree R(c*) ) to the left side of subtree R(c We prove this by contradiction:
Proof 2 Suppose there exist L4, E R(c*) n L and 1p. 1y. E R(ch") n C such that i' < < but i" 2 jr and not both i' i" and j' j if
j this creates a closed cycle, which is described in p if j", 13- lies between the leftmost and righlmost leaves of R((c))) ) n L. As result, the subtree R(c²) does not cover a full contiguous phrase but multiple segmented phrases, which is prohibited for a parse tree. Therefore, by contradiction, there can not exist 4,- R((c)) L and 1i- R(ck") n L such that it 2 j
impossible
In general, combing the satisfactions from the above requirements, the reverse-transformation I can convert TXX)= = (C,N, R.) back to the original graph ((X):
I(H(G(X))) g(X)
(27)
12

---

Published as a conference paper at ICLR 2020
7.2 TIME COMPLEXITY ANALYSIS
In this section, we prove that given single-thread sequential computation (single CPU), our method operates (N22) time complexity. In short, the hierarchical accumulation process (Section 4.1 runs at ( log N) time, while the attention scores (Q in standard attention are computed ((N2). Overall, the tree-based attention can performs at (NV2) time complexity, same as the Transformer. We then proceed to analyze the time complexity of the hierarchical accumulation process. Formally, let X be a n-length sentence with T(X) = (N, RR) as its balance binary constituency parse tree as defined in section 4 N E m and L E Rnxd be the hidden states of elements in N and L respectively. Therefore, there are m = n - 1 non-terminal nodes in the tree, which is also the size of N.. In the upward cumulative-averuge operation U, each branch from the root to a leaf has xs log(n) nodes, the cumulative operation of these nodes can be done at (log(n)), That is, because the result y/ of each node 2; be computed as y/ yi-1 + I₁, computations for all nodes in a branch take linear time using dynamic programming, yielding (log(n) time complexity. As we have n branches in the tree, the total complexity for li is O(n log(n)). Likewise, the weighted aggregation operation V is also computed at (n log(n)) complexity. Specifically, level from the root of the tree, there i non-terminal nodes, which each has to aggregate n/i components St, to calculate the final representation of the node. Thus, at each level, there are computations. Because the total height of the tree is log(n), the time complexity of V is also On (n). Hence, the total complexity of hierarchical accumulation process is O(n log(n)). As such, the final sequential time complexity of the proposed attention layer is:
O(N2) + O((N - 1) O((N 1)N) + O(N log(N)) O(N3)
(28)
Having said that, in the era that powerful GPU-based hardware is ubiquitous. it is important to note that our models can achieve comparable parallelizability compared the Transformer, while they can leverage the essence of hierarchical structures in natural languages. The purpose of the above time complexity analysis only to show more insights about our models. That being said, could,
even though we provide numerical analysis of training speed (figure 5b) as objective training speed depends greatly on different subjective factors that may stray the actual timing away from its theoretical asymptotic time complexity. These factors are data preprocessing and batching, actual low-level and high-level programmatic implementation of the method, GPUs, CPUs, I/O hardwares, etc. For instance, standard LSTM module in Tensorflow or Pytorch may performs 10 times slower than an LSTM with CUDA CuDNN kernels, even though no extra computations are theoretical required.
7.3 OVERALL ARCHITECTURE
Figure 6 shows the overall Seq2Seq architecture of our model. In the encoder specifically, we parse the source sequence into constituency trees and then feed the leaf and node components into a stack of encoder layers. The leaf and node components are passed through the tree-based self-attention layer, where the value representation of node is incorporated with hierarchical accumulation. After that, the output representations of leaves and nodes passed through a weight- shared series of layer normalizations and and feed-forward layer. In the decoder, the query representation of the target domain attends the leaves and nodes representation of the source sequence computed by the encoder. For more insights, apply hierarchical accumulation on the key components (instead on value components) causes dramatic performance because they disrupted after being multiplied with the query components and they do not directly contribute to the representations of the outputs. Meanwhile, applying accumulation on attention scores does not yield performance benefits but increases computational burden.
Sable5ishow the exact number of parameters of the Transformer and our method. As can be seen, the increase of parameters is almost unnoticeable because the hierarchical embedding modules share weights among different attention heads.
7.4 MORE DETAILED TRAINING CONFIGURATIONS
Text Classification. We adopt the tiny size versions of tree-based models well as the transformer baseline. The models possess 2 transformer-layers, each has model dimension of 64, 4 heads. We trained the models for 15, 000 updates, with batch size of 2048 tokens. We
13

---

Published as a conference paper at ICLR 2020
AddiNomm
FFN
AddNorm
Cross Tree Attention
FFN
FFN
Nx
Nx
AddNorm
AddNNorm
AddNorm
Self Tree
Attention
Masked Attention
Leaf
Node
Target
Figure 6: Overall architecture of Tree Transformer. (Dashed lines: sharing parameters)
Model
Base
Big
Transformer
61,747,200 61,810,944 (+0.1%) 209.96,.104(40007%)
209,813,55
Ours
Table 5: Exact number of parameters for Transformer and our model, both used for WMT" 14 English-Gerne task.
used random initialized embeddings for all experiments. the Stanford Sentiment Analysis task (SST), we tested on two subtasks: binary and fine-grained (5 classes) classification the standard train/dev/test splits of 6920/872/182 and 8544/1 101/2210 respectively. We optimize every sentiment label provided in the dataset. We used learning rate of x 10 dropout 0.5 and 8000 warmup steps. For subject-veri agreement task, we trained on set of 142, 000 sentences, validated on the set of x 15, 700 sentences and tested on the set of = 1, 000, 000 sentences. For IMDB sentiment analysis, we used a training set of 25, 000 documents and test set of 25, 000 documents. As the documents predict the sentiment. For both subject-verb agreement and IMDB sentiment analysis, we trained models with 20 warmup steps, 0.01 learning rate and 0.2 dropout.
multi-sentence, they are added with dummy root node which used to
replicate most of the base training settings from Ott et al. (2018) our models, to enable fair comparison with transformer-basee Wu et al. 2019). For IWSLT experiments, we trained the models with dl 512, forward dimension dzfn 1024, approximate batch size of 4000 tokens, 60, 000 updates, learning rate 5 x 10-4, 4000 warmup steps, dropout rate 0.3, L2 weight decay 10-4, beam size 5 and length penalty 1.0 for English-German and 0.7 for English-French. The hierarchical embedding size |E' is set to 100. We used BPE tokens pre-trained with 32, 000 iterations. Note that if word is broken into multiple BPE subwords, it form a subtree with leaves as such subwords and root-node as POS tag of the word. Figure 7 visualizes how this works. The IWSLT English- German training 160, 000 sentence pairs, we used 5% the data for validation and combined for testing. Meanwhile, the IWSLT English-
Machine Translation.
methods (Vaswani al. 2017
English-German
dataset contains Mewv200..evv00111111 (.se20002st20000ss22000
(IWSLT14 CES.ST1..TE..CC.. 1e1.....DD..ee21111.1 French task has ss 200, 000 training sentence pairs, we used
for validation and IWSLT15.8 SEET1..TD..SSS.. 1312 for testing. We use the Stanford CoreNLP parser (v3.9.1 Manning et al. 2014) to parse the datasets. For WMT experiments, we trained the models with dmode! 512, feed forward dimension f/fa 2048, batch size of = 32, 000 tokens, 200. 000 updates, learning rate 7 10-1 4000 warmup steps, dropout rate 0.1, I.2 weight decay 10-1 beam size and length penalty 0.6. We take average of the last 5 checkpoints for evaluation. The WM English- German dataset contains 4.5. pairs. tested the models on newstest2014 test We used lokenized-BLEU to evaluate the models.
14

---

Published as a conference paper at ICLR 2020
S
S
NN
VP
NN
VP
He
PRP
He
PRP
V
is
V-BPE
V-BPE
studying
study @ @
ing
(a) Standard Constituency Tree
(b) A BPE constituency tree
Figure 7: Process to break standard tree (fig. 7a into BPE tree (fig. 7bp.
Training Time Analysis. For this experiment, all the examined models (Transformer, Tree Transformer and Tree-LSTM) are trained on text classification task on a GPU for 1000 training steps with batch-size of For vanilla and Tree Transformer, we used the 2-layer encoder with dimension 64. For Tree-LSTMM, we used one-layer LSTM with dimension 64. A binary constituency tree is built given each input sentence. The parser's processing time is significant. For training time, we exclude the parser's time because the parser processes the data only once and this counts towards to preprocessing procedures of the dataset. However, we include parser's time into inference time because receive surface-form text instead of trees. In practice, the parsing time substantially overshadows the computation time of the network. Thus, the overall process will be faster if more efficient parser developed.
Effectiveness on Small Datasets. We used both Transformer and Tree Transformer on base-size training settings from Ott et al. (2018). We trained the models with batch size of 32, 000 tokens, 100, 000 updates, learning rate 7 x 10 10-4, 4000 warmup steps, dropout 0.1, L2 weight decay 10 beam size and length penalty 0.6. For both sets of tasks, we take average the last checkpoints for evaluation. We used BPE tokens pre-trained with 32, 000 iterations. We randomly samples the training data into size-varying portions: 2%(90K pairs), 5%2255K pairs), 10%(450K pairs), 25%(1. (1.6111255) pairs), 50%(2.25M M pairs), 75%(3.37 pairs) and 100%(4.5M pairs).
15


Reviews:
[{"review_id": "HklbTMp0YH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel mechanism to leverage additional tree-structure information into the transformer. The proposed method consist three main component: a hierarchical accumulation strategy to aggregate the leaf node embedding information to the non-terminal nodes; a hierarchical embedding which is akin to positional embedding, however encapsulating the leaf-to-node and relative position information; a sub-tree masking strategy to filter out irrelevant information. Although the formulations seem a little bit overcomplicated/cumbersome to me, I find the figures are really helpful to understand the gists, which are intuitive and straightforward. \n\nStrengths:\n\n* Intuitive and novel ideas. The tree structure information is incorporated into the transformer in a sophisticated and elegant manner, with only constant time-complexity overhead. \n\n* Strong empirical results and well-defined ablation study. Good analysis on the performance vs dataset size and time complexity\n\nCons:\n\n* Heavy notations which could be more concise. \n\n* Implementing such an architecture without source code could be difficult.\n\nQuestions:\n\n* Comparing with the naive transformer architecture (e.g. base model), how many additional parameters are there in your model? I see that for fair comparison, the authors use the same base transformer architecture, however it would still be very helpful if they can provide the statistics of the number of parameters for the proposed model and the compared baselines. \n\n* Are all the baselines using the same parser (CoreNLP)? If not, would the difference of parsing trees be a confounding factor?\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1g_PfRoYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends transformers by enabling them to incorporate hierarchical structures like constituency trees structured attention with hierarchical accumulation. In particular, they modified the architecture of transformers such that they can learn phrase-level attention scores, and use them in the final assigned task of text classification or language translation. \nThey also explored a couple of variants of their proposed architecture: Hierarchical embeddings and Subnet masking which helped them outperform SOTA methods including Tree-LSTM (similar to this paper in principle, except that it was designed for LSTM-based models and not transformers). \n\nThe paper is well written and well-augmented with supportive figures. Particularly, Figure1 was very helpful in understanding all the complexities of the proposed model. Further, the authors justify the utility of the proposed approach covering different aspects of evaluation including comparative studies with baselines, ablation studies, phrase vs token-level attentions, training-time analysis. \n\nA limitation of this work is high inference cost. As the results indicate, parsing trees from text is the most costly step in the entire framework, and consequently, the inference time of proposed model will still be much higher than transformers. Hence, this work might still not be applicable to low-latency constraint scenarios. \n\n\nOther Comments: \n1) I did not fully understand why it would be better to mask out the non descendants in subnet masking approach. Why shouldn't a phrase node seek attention from tokens outside its scope? Probably the answer lies in the the way these trees are constructed. Nevertheless, it would be useful to provide some intuition with examples to motivate subtree masking. \n\n2) In Equation(5), the subscripts \"i-1\" should be replaced with \"i\"? Otherwise it will be sensitive to ordering of non-terminal nodes in N, and also Figure 1 wouldn't make sense.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgV33DTYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper describes an attention-based method to encode trees with constant parallel-time complexity maintaining scalability, uses this model to encode constituency parses of input sentences for the tasks of machine translation and text classification, and shows improved accuracy/bleu over models that do not encode the parses. \n\nStrengths:\n\nThe method proposed by the authors is scalable despite encoding tree structures. The models give considerable improvements on various machine translation datasets and the authors also show that the model is more sample efficient. I appreciate the charts showing training and inference time with sentence length, and the tables showing the ablations and attention distributions. \n\nWeaknesses\n\nThe authors do not use pre-trained embeddings for any of the classification models, but using these embeddings boost performance to much more than what they authors have achieved here. My main question is, if we use pre-trained embeddings, do encoding constituency parses add anything over and above them? I would like to see this method improve results over some state of the art classification models and not just over the tree-LSTM. In other words, how much classification performance does this method yield over current SOTA models, because the SST results are quite a bit below the current SOTA.\n\nThe authors achieve an accuracy of 98.2 on the IMDB dataset. Is this actually the case or is this a bug? Even models using BERT barely achieve an accuracy of 96% (http://nlpprogress.com/english/sentiment_analysis.html). Or am I looking at the wrong dataset here? Can the authors clarify?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper incorporates tree-structured information about a sentence into how transformers process it. Results are improved. The paper is clear. Reviewers liked it. Clear accept.
Decision: Accept (Poster)