## Tree-Transformer: A Transformer-Based Method for Correction of Tree-Structured Data.

Jacob Harer Boston University

jharer@bu.edu

Chris Reale Draper creale@draper.com

Peter Chin Boston University spchin@cs.bu.edu

## Abstract

Many common sequential data sources, such as source code and natural language, have a natural tree-structured representation. These trees can be generated by fitting a sequence to a grammar, yielding a hierarchical ordering of the tokens in the sequence. This structure encodes a high degree of syntactic information, making it ideal for problems such as grammar correction. However, little work has been done to develop neural networks that can operate on and exploit treestructured data. In this paper we present the Tree-Transformer - a novel neural network architecture designed to translate between arbitrary input and output trees. We applied this architecture to correction tasks in both the source code and natural language domains. On source code, our model achieved an improvement of 25% F 0 5 . over the best sequential method. On natural language, we achieved comparable results to the most complex state of the art systems, obtaining a 10% improvement in recall on the CoNLL 2014 benchmark and the highest to date F 0 5 . score on the AESW benchmark of 50 43 . .

## 1 Introduction

Most machine learning approaches to correction tasks operate on sequential representations of input and output data. Generally this is done as a matter of convenience - sequential data is readily available and requires minimal effort to be used as training data for many machine learning models. Sequence-based machine learning models have produced prominent results in both translation and correction of natural language [1, 2, 3, 4, 5, 6, 7, 8].

While algorithms that use sequential data have produced good results, most of these sequential data types can be more informatively represented using a tree structure. One common method to obtain tree-structured data is to fit sequential data to a grammar, such as a Context Free Grammar (CFG). The use of a grammar ensures that generated trees encode the higher-order syntactic structure of the data in addition to the information contained by sequential data.

In this work, we trained a neural network to operate directly on trees, teaching it to learn the syntax of the underlying grammar and to leverage this syntax to produce outputs which are grammatically correct. Our model, the Tree-Transformer, handles correction tasks in a tree-based encoder and decoder framework. The Tree-Transformer leverages the popular Transformer architecture [2], modifying it to incorporate the tree structure of the data by adding a parent-sibling tree convolution block. To show the power of our model, we focused our experiments on two common data types and their respective tree representations: Abstract Syntax Trees (ASTs) for code and Constituency Parse Trees (CPTs) for natural language.

Preprint. Under review.

## 2 Related Work

## 2.1 Tree Structured Neural Networks

Existing work on tree-structured neural networks can largely be grouped into two categories: encoding trees and generating trees. Several types of tree encoders exist [9, 10, 11, 12]. The seminal work of Tai et al. [9] laid the ground work for these methods, using a variant of a Long Short Term Memory (LSTM) network to encode an arbitrary tree. A large body of work has also focused on how to generate trees [13, 14, 15, 16, 17, 18, 19, 20]. The work of Dong et al., [13] and Alvarez-Melis and Jaakkola [14] each extend the LSTM decoder popular in Neuro Machine Translation (NMT) systems to arbitrary trees. This is done by labeling some outputs as parent nodes and then forking off additional sequence generations to create their children. Only a small amount of work has combined encoding and generation of trees into a tree-to-tree system [21, 22]. Of note is Chakraborty et al. [22] who use a LSTM-based tree-to-tree method for source code completion.

To our knowledge our work is the first to use a Transformer-based network on trees, and apply Tree-to-Tree techniques to natural language and code correction tasks.

## 2.2 Code Correction

There is extensive existing work on automatic repair of software. However, the majority of this work is rule-based systems which make use of small datasets (see [23] for a more extensive review of these methods). Two successful, recent approaches in this category are that of Le et al., [24] and Long and Rinard [25]. Le et al. mine a history of bug fixes across multiple projects and attempt to reuse common bug fix patterns on newly discovered bugs. Long and Rinard learn and use a probabilistic model to rank potential fixes for defective code. Unfortunately, the small datasets used in these works are not suitable for training a large neural network like ours.

Neural network-based approaches for code correction are less common. Devlin et al. [26] generate repairs with a rule-based method and then rank them using a neural network. Gupta et al. [27] were the first to train a NMT model to directly generate repairs for incorrect code. Additionally, Harer et al. [28] use a Generative Adversarial Network to train an NMT model for code correction in the absence of paired data. The works of Gupta et al. and Harer et al. are the closest to our own since they directly correct code using an NMT system.

## 2.3 Grammatical Error Correction

Grammatical Error Correction (GEC) is the task of correcting grammatically incorrect sentences. This task is similar in many ways to machine translation tasks. However, initial attempts to apply NMT systems to GEC were outperformed by phrase-based or hybrid systems [29, 30, 31].

Initial, purely neural systems for GEC largely copied NMT systems. Yuan and Brisco [4] produced the first NMT style system for GEC by using the popular attention method of Bahdanau et al. [1]. Xie et al. [3] trained a novel character-based model with attention. Ji et al. [5] proposed a hybrid character-word level model, using a nested character level attention model to handle rare words. Schmaltz et al. [6] used a word-level bidirectional LSTM network. Chollampatt and Ng [7] created a convolution-based encoder and decoder network which was the first to beat state of the art phrased-based systems. Finally, Junczys-Dowmunt et al. [8] treated GEC as a low resource machine translation task, utilizing the combination of a large monolingual language model and a specifically designed correction loss function.

## 3 Architecture

Our Tree-Transformer architecture is based on the Transformer architecture of Vaswani et al. [2], modified to handle tree-structured data. Our major change to the Transformer is the replacement of the feed forward sublayer in both the encoder and decoder with a Tree Convolution Block (TCB). The TCB allows each node direct access to its parent and left sibling, thus allowing the network to understand the tree structure. We follow the same overall architecture for the Transformer as Vaswani et al., consisting of self-attention, encoder-decoder attention, and TCB sub layers in each layer. Our

Figure 1: Tree-Transformer model architecture.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00449v1-figure-cdc34fd3-914f-4f49-b6e0-902949cba811.jpg)

Figure 2: Tree-Transformer State Transfer

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00449v1-figure-a2c1d687-e1ce-413b-952b-21475669e329.jpg)

models follow the 6 layer architecture of the base Transformer model with sublayer outputs, d model , of size 512 and tree convolution layers, d ff , of size 2048 .

## 3.1 Parent-Sibling Tree Convolution

Tree convolution is computed for each node as:

$$T C B ( x _ { t }, x _ { p }, x _ { s } ) = r e l u ( x _ { t } W _ { t } + x _ { p } W _ { p } + x _ { s } W _ { s } + b ) W _ { 2 } + b _ { 2 }$$

The inputs x t , x p , and x s all come from the previous sublayer, x t from the same node, x p from the parent node, and x s from its left sibling. In cases where the node does not have either a parent (e.g. the root node) or a left sibling (e.g. parents first child), the inputs x p and x s are replaced with a learned vector v p and v s respectively.

In addition to the TCB used in each sub layer, we also use a TCB at the input to both the encoder and decoder. In the encoder this input block combines the embeddings from the parent, the sibling and the current node ( p , s , and t ). In the decoder, the current node is unknown since it has not yet been produced. Therefor,e this block only combines the parent and sibling embeddings, leaving out the input x t from the equation above.

The overall structure of the network is shown in Figure 1. The inputs to each TCB come from the network inputs, x/y , for the input blocks, and from the previous sublayer, sa L /a L , for all other blocks.

## 3.2 Top-Down Encoder and Decoder

Both our encoder and decoder use a top-down approach where information flows from the tree's root node down toward to the leaf nodes, as shown in Figure 2. Thus, leaf nodes have access to a large sub-tree, while parent nodes have a more limited view. An alternative approach would be to use a bottom-up encoder, where each node has access to its children, and a top-down decoder which can disseminate this information. This bottom-up/top-down model is intuitive because information flows up the tree in the encoder and then back down the decoder. However, we found that utilizing the same top-down ordering for both encoder and decoder performed better, likely because the symmetry in encoder and decoder allows decoder nodes to easily attend to their corresponding nodes in the encoder. This symmetry trivializes copying from encoder to decoder, which is particularly useful in correction tasks where large portions of the trees remain unchanged between input and output.

## 3.3 Generating Tree Structure

In order to generate each tree's structure, we treat each set of siblings as a sequence. For each set of siblings, we generate each node one at a time, ending with the generation of an end-of-sequence token. The vocabulary used defines a set of leaf and parent nodes. When a parent node is generated, we begin creation of that nodes children as another set of siblings.

## 3.4 Depth First Ordering

As with any NMT system, each output value y t is produced from the decoder and fed back to subsequent nodes as input during evaluation. Ensuring inputs y p and y s are available to each node requires that parents are produced before children and that siblings are produced in left-to-right order. To enforce this constraint, we order the nodes in a depth-first manner. This ordering is shown by the numbering on nodes in Figure 3. The self attention mechanism in the decoder is also masked according to this order, so that each node only has access to previously produced ones.

## 3.5 No Positional Encoding

The Transformer architecture utilizes a positional encoding to help localization of the attention mechanisms. Positional encoding is not as important in our model because the TCB allows nodes to easily locate its parent and siblings in the tree. In fact, we found that inclusion of a Positional Encoding caused the network to overfit, likely due to the relatively small size of the correction datasets we use. Given this, our Tree-Transformer networks do not include a Positional Encoding.

## 4 Why Tree Transformer

In this section we motivate the design of our Tree-Transformer model over other possible tree-based architectures. Our choice to build upon the Transformer model was two-fold. First, Transformerbased models have significantly reduced time-complexity relative to Recurrent Neural Network (RNN) based approaches. Second, many of the building blocks required for a tree-to-tree translation system, including self-attention, are already present in the Transformer architecture.

## 4.1 Recurrent vs Attention Tree Networks

Many previous works on tree-structured networks used RNN-based tree architectures where nodes in layer L are given access to their parent or children in the same layer [13, 14, 22]. This state transfer requires an ordering to the nodes during training where earlier nodes in the same layer must be computed prior to later ones. This ordering requirement leads to poor time complexity for tree-structured RNN's, since each node in a tree needs access to multiple prior nodes (e.g. parent and sibling). Accessing the states of prior nodes thus requires a gather operation over all past produced nodes. These gather operations are slow, and performing them serially for each node in the tree can be prohibitively expensive.

An alternative to the RNN type architecture is a convolutional or attention-based one, where nodes in layer L are given access to prior nodes in layer L -1 . With the dependence in the same layer removed, the gather operation can be batched over all nodes in a tree, resulting in one large gather

Figure 3: Example Constituency Parse Tree. The index of the node in depth-first ordering is shown in the bottom left of each node. Note: leaf nodes in the verb phrase do not have access to leaf nodes in the left noun phrase without self-attention

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00449v1-figure-2aaaafcc-6966-4f91-944b-e0f6e37eee8b.jpg)

operation instead of T . From our experiments, this batching resulted in a reduction in training time of two orders of magnitude on our largest dataset; from around 2 months to less than a day.

## 4.2 Conditional Probabilities and Self Attention

The Tree-Transformer's structure helps the network produce grammatically correct outputs. However, for translation/correction tasks we must additionally ensure that each output, ¯ y t , is conditionally dependent on both the input, x , and on previous outputs, y &lt;t . Conditioning the output on the input is achieved using an encoder-decoder attention mechanism [1]. Conditioning each output on previous outputs is more difficult with a tree-based system. In a tree-based model like ours, with only parent and sibling connections, the leaf nodes in one branch do not have access to leaf nodes in other branches. This leads to potentially undesired conditional independence between branches. Consider the example constituency parse trees shown in Figure 3. Given the initial noun phrase "My dog", the following verb phrase "dug a hole" is far more likely than "gave a speech". However, in a tree-based model the verb phrases do not have direct access to the sampled noun phrase, meaning both possible sentences would be considered roughly equally probable by the model.

We address the above limitation with the inclusion of a self-attention mechanism which allows nodes access to all previously produced nodes. This mechanism, along with the depth-first ordering of the node described in section 3.4, gives each leaf node access to all past produced leaf nodes. Our model fits the standard probabilistic language model given as:

$$p ( y | x ) = \prod _ { t = 1 } ^ { T } p ( y _ { t } | y _ { < t }, x )$$

where t is the index of the node in the depth first ordering.

## 5 Training

This section describes the training procedure and parameter choices used in our model. We trained our models in parallel on 4 Nvidia Tesla V-100 GPU's. Trees were batched together based on size with each batch containing a maximum 20 000 , words. We used the ADAM optimizer with inverse square root decay and a warm up of 16 000 , steps. A full list of hyperparameters for each run is included in Appendix A.

## 5.1 Regularization

The correction datasets we used in this paper are relatively small compared to typical NMT datasets. As such we found a high degree of regularization was necessary. We included dropout of 0.3 before the residual of each sub layer and attention dropout of 0.1. We also added dropout of 0.3 to each TCB after the non-linearity. We applied dropout to words in both source and target embeddings as per [8] with probabilities 0.2 and 0.1 respectively. We included label smoothing with glyph[epsilon1] ls = 0 1 .

## 5.2 Beam-Search

Because of the depth-first ordering of nodes in our model, we can use beam search in the same way as traditional NMT systems. Following equation 1, we can compute the probability of a generated

Table 1: Sate IV Results

| Architecture     |   Precision |   Recall |   F 0 . 5 |
|------------------|-------------|----------|-----------|
| 4-layer LSTM     |        51.3 |     53.4 |      51.7 |
| Transformer      |        59.6 |     86.1 |      63.5 |
| Tree-Transformer |        84.5 |     85.7 |      84.7 |

sub-tree of t nodes simply as the product of probabilities for each node. We utilize beam-search during testing with a beam width of 6. Larger beam widths did not produce improved results.

## 6 Experiments/Results

## 6.1 Code Correction

We trained our Tree-Transformer on code examples taken from the NIST SATE IV dataset [32]. SATE IV contains around 120 K C and C++ files from 116 different Common Weakness Enumerations (CWEs), and was originally designed to test static analyzers. Each file contains a bad function with a known security vulnerability and at least one good function which fixes the vulnerability. We generate Abstract Syntax Trees (ASTs) from these functions using the Clang AST framework [33, 34].

To provide a representation which is usable to our network, we tokenize the AST over a fixed vocabulary in three ways. First, high level AST nodes and data types are represented by individual tokens. Second, character and numeric literals are represented by a sequence of ASCII characters with a parent node defining the kind of literal (e.g. Int Literal, Float Literal). Finally, we use variable renaming to assign per function unique tokens to each variable and string. Our vocabulary consists of 403 tokens made up of 60 AST tokens, 23 data type tokens, 256 ASCII tokens, and 64 Variable tokens.

Using the SATE IV dataset requires pre-processing, which we do during data generation. First, many of the SATE IV functions contain large amounts of dead code. In these cases, the bad and good functions contain largely the same code, but one path will be executed during the bad function and another in the good one. To make these cases more realistic, we removed the dead code. Second, although each file for a particular CWE contains unique functions at the text level, many of them are identical once converted to AST with renamed variables. Identical cases comes in two flavors: one where a bad function is identical to its good counterpart, and one where multiple bad functions from different files are identical. The first occurs commonly in SATE IV in cases where the bad and good functions are identical except for differing function calls. Since we operate at the function level, examples of this case are not useful and are removed. The second case occurs when bad functions differ only in variable names, strings, or function calls. To handle this, we compare all bad functions tree representations and combine identical bad functions into a single bad tree and a combination of all good trees from its component functions, with duplicate good trees removed. After pre-processing the data, we retain a total of 32 316 , bad functions and 47 346 , good functions. These are split 80/10/10 into training/validation/testing.

To our knowledge this processing of the SATE IV dataset is new. As such, we compare our network to two NMT systems operating on sequence-based representation of the data; a 4 Layer LSTM with attention and a base Transformer model. These sequence-based models use a representation with an almost identical vocabulary and tokenization to our tree representation but they operate over the tokenized sequence output of the Clang Lexer instead of the AST.

During testing, we utilized clangs source-to-source compilation framework to return the tree output of our networks to source code. We then compute precision, recall, and F 0 5 . scores of source code edits using the MaxMatch algorithm [35]. Results are given in Table 1 Our Tree-Transformer model performs better than either of the other two models we considered. We believe this is because source code is more naturally structured as a tree than as a sequence, lending itself to our tree-based model.

## 6.2 Grammar Error Correction

We applied our tree-based model as an alternative to NMT and phrase-based methods for GEC. Specifically, we encoded incorrect sentences using their constituency parse trees, and then generated corrected parse trees. Constituency parse trees represent sentences based on their syntactic structure

by fitting them to a phrase structured grammar. Words from the input sentence become leaf nodes of their respective parse trees, and these nodes are combined into phrases of more complexity as we progress up the tree. [36, 11]

A large amount of research has focused on the generation of constituency parse trees [37, 38, 39]. We utilize the Stanford NLP group's shift-reduce constituency parser [40] to generate trees for both incorrect and correct sentences in our datasets. These are represented to our network with a combined vocab consisting of 50 K word level tokens and 27 parent tokens. The parent tokens come from the part of speech tags originally defined by the Penn Treebank [41] plus a root token. Following recent work in GEC [8, 7], the word level tokens are converted into sub-words using a Byte Pair Encoding (BPE) trained on the large Wikipedia dataset [42]. The BPE segments rare words into multiple subwords, avoiding the post-processing of unknown words used in many existing GEC techniques.

We test our network on two GEC benchmarks: the commonly used NUCLE CoNLL 2014 task [43], and the AESW dataset [44]. CoNLL 2014 training data contains 57 K sentences extracted from essays written by non-native English learners. Following the majority of existing GEC work, we augment the small CoNLL dataset with the larger NIST Lang-8 corpus. The Lang-8 data contains 1 1 . M sentences of crowd sourced data taken from the Lang-8 website, making it noisy and of lower quality than the CoNLL data. We test on the 1 312 , sentences in CoNLL 2014 testing set and use the 1 381 , sentences of the CoNLL 2013 testing set as validation data. For evaluation we use the official CoNLL M2scorer algorithm to determine edits and compute precision and recall [35].

We also explore the large AESW dataset. AESW was designed in order to train grammar error identification systems. However, it includes both incorrect and corrected versions of sentences, making it useful for GEC as well. AESW contains 1 2 . M training, 143 K testing, and 147 K validation sentences. The AESW data was taken from scientific papers authored by non-native speakers, and as such contains far more formal language than CoNLL.

## 6.2.1 GEC Training

For GEC we include a few additions to the training procedure described in Section 5. First, we pre-train the network in two ways on 100 M sentences from the large monolingual dataset provided by [29]. We pre-train the decoder in our network as a language model, including all layers in the decoder except the encoder-decoder attention mechanism. We also pre-train the entire model as a denoising-autoencoder, using a source embedding word dropout of 0.4.

For loss we use the edit-weighted MLE objective defined by Junczys-Dowmunt et al. [8]:

$$M L E ( x, y ) = - \sum _ { t = 1 } ^ { T } \lambda ( y _ { t } ) \log P ( y _ { t } | x, y < t )$$

where ( x, y ) are a training pair, and λ y ( t ) is 3 if y t is part of an edit and 1 otherwise. We compute which tokens are part of an edit using the python Apted graph matching library [45, 46, 47].

During beam-search we ensemble our networks with the monolingual language-model used for pre-training as per [3]:

$$s ( y | x ) = \sum _ { t = 1 } ^ { T } \log P ( y _ { t } | x, y _ { < t } ) + \alpha \log P _ { l m } ( y _ { t } | y _ { < t } )$$

where α is chosen between 0 and 1 based on the validation set. Typically, we found an alpha of 0.15 performed best. Networks with α &gt; 0 are labeled with +Mon-Ens

## 6.2.2 CoNLL 2014 Analysis

Results for CoNLL 2014 are provided in Table 2. Our Tree-Transformer achieves significantly higher recall than existing approaches, meaning we successfully repair more of the grammar errors. However, our precision is also lower which implies we make additional unnecessary edits. We attribute this drop to the fact that our method tends to generate examples which fit a structured grammar. Thus sentences with uncommon grammar tend to be converted to a more common way of saying things. An example of this effect is provided in table 3.

Table 2: CoNLL 2014 results

| Architecture                           | Precision                         | Recall                            | F 0 . 5                           |
|----------------------------------------|-----------------------------------|-----------------------------------|-----------------------------------|
| Prior State-of-the-art Approaches      | Prior State-of-the-art Approaches | Prior State-of-the-art Approaches | Prior State-of-the-art Approaches |
| Chollampatt and Ng 2017.               | 62.74                             | 32.96                             | 53.14                             |
| Junczys-Dowmunt and Grundkiewicz. 2016 | 61.27                             | 27,98                             | 49.49                             |
| Prior Neural Approaches                | Prior Neural Approaches           | Prior Neural Approaches           | Prior Neural Approaches           |
| Ji et al. 2017                         | -                                 | -                                 | 45.15                             |
| Schmaltz et al. 2017                   | -                                 | -                                 | 41.37                             |
| Xie et al. 2016                        | 49.24                             | 23.77                             | 40.56                             |
| Yuan and Briscoe. 2016                 | -                                 | -                                 | 39.90                             |
| Chollampatt and Ng. 2018               | 65.49                             | 33.14                             | 54.79                             |
| Junczys-Dowmunt et al. 2018            | 63.0                              | 38.9                              | 56.1                              |
| This Work                              | This Work                         | This Work                         | This Work                         |
| Tree-Transformer                       | 57.39                             | 28.12                             | 47.50                             |
| Tree-Transformer +Mon                  | 58.45                             | 30.42                             | 49.35                             |
| Tree-Transformer +Mon +Mon-Ens         | 57.84                             | 33.26                             | 50.39                             |
| Tree-Transformer +Auto                 | 65.22                             | 30.38                             | 53.05                             |
| Tree-Transformer +Auto +Mon-Ens        | 59.14                             | 43.23                             | 55.09                             |

Table 3: CoNLL 2014 Example Output

| Input   | In conclusion , we could tell the benefits of telling genetic risk to the carriers relatives overweights the costs .                                                                                                                                                                                                                                                 |
|---------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Labels  | In conclusion , we can see that the benefits of telling genetic risk to the carrier 's relatives outweighs the costs . In conclusion , we can see that the benefits of disclosing genetic risk to the carriers relatives outweigh the costs. In conclusion , we can see that the benefits of revealing genetic risk to the carrier 's relatives outweigh the costs . |
| Network | In conclusion , it can be argued that the benefits of revealing genetic risk to one 's relatives outweighs the costs .                                                                                                                                                                                                                                               |

## 6.2.3 AESW Analysis

Results for AESW are provided in Table 4. We achieve the highest to date F 0 5 . score on AESW, including beating out our own sequence-based Transformer model. We attribute this to the fact that AESW is composed of samples taken from submitted papers. The more formal language used in this context may be a better fit for the structured grammar used by our model.

Table 4: AESW results

| Architecture                         | Precision        | Recall           | F 0 . 5          |
|--------------------------------------|------------------|------------------|------------------|
| Prior Approaches                     | Prior Approaches | Prior Approaches | Prior Approaches |
| Schmaltz et al. 2017 (Phrased-based) | -                | -                | 38.31            |
| Schmaltz et al. 2017 (Word LSTM)     | -                | -                | 42.78            |
| Schmaltz et al 2017 (Char LSTM)      | -                | -                | 46.72            |
| This Work                            | This Work        | This Work        | This Work        |
| Transformer (Seq to Seq)             | 52.3             | 36.2             | 48.03            |
| Tree-Transformer                     | 55.4             | 37.1             | 50.43            |

## 7 Conclusion

In this paper we introduced the Tree-Transformer architecture for tree-to-tree correction tasks. We applied our method to correction datasets for both code and natural language and showed an increase in performance over existing sequence-based methods. We believe our model achieves its success by taking advantage of the strong grammatical structure inherent in tree-structured representations. For the future we hope to apply our approach to other tree-to-tree tasks, such as natural language translation. Additionally, we intend to extend our approach into a more general graph-to-graph method.

## References

- [1] D. Bahdanau, K. Cho, and Y. Bengio. Neural Machine Translation by Jointly Learning to Align and Translate. International Conference on Learning Representations (ICLR) , 2015.
- [2] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention Is All You Need. Neural Information Processing Systems (NIPS) , 2017.
- [3] Z. Xie, A. Avati, N. Arivazhagan, D. Jurafsky, and A. Y. Ng. Neural Language Correction with Character-Based Attention. arXiv.org , 2016.
- [4] Z. Yuan and T. Briscoe. Grammatical error correction using neural machine translation. North American Chapter of the Association of Computational Linguistics (NAACL) , 2016.
- [5] J. Ji, Q. Wang, K. Toutanova, Y. Gong, S. Truong, and J. Gao. A Nested Attention Neural Hybrid Model for Grammatical Error Correction. Association of Computational Linguistics (ACL) , 2017.
- [6] A. Schmaltz, Y. Kim, A. M. Rush, and S. M. Shieber. Adapting Sequence Models for Sentence Correction. Empirical Methods in Natural Language (EMNLP) , 2017.
- [7] S. Chollampatt and H. T. Ng. A Multilayer Convolutional Encoder-Decoder Neural Network for Grammatical Error Correction. Association for the Advancement of Artificial Intelligence (AAAI) , 2018.
- [8] M. Junczys-Dowmunt, R. Grundkiewicz, S. Guha, and K. Heafield. Approach neural grammatical error correction as a low-resource machine translation task. North American Chapter of the Association of Computational Linguistics (NAACL-HLT) , 2018.
- [9] K. S. Tai, R. Socher, and C. D. Manning. Improved Semantic Representations From TreeStructured Long Short-Term Memory Networks. Association of Computational Linguistics (ACL) , 2015.
- [10] X. Zhu, P. Sobhani, and H. Guo. Long Short-Term Memory Over Tree Structures. International Conference on Machine Learning (ICML) , 2015.
- [11] R. Socher, C. C.-Y. Lin, A. Y. Ng, and C. D. Manning. Parsing Natural Scenes and Natural Language with Recursive Neural Networks. International Conference on Machine Learning (ICML) , 2011.
- [12] A. Eriguchi, K. Hashimoto, and Y. Tsuruoka. Tree-to-Sequence Attentional Neural Machine Translation. Association of Computational Linguistics (ACL) , 2016.
- [13] L. Dong and M. Lapata. Language to Logical Form with Neural Attention. Association of Computational Linguistics (ACL) , 2016.
- [14] D. A.-M. . T. S. Jaakkola. Tree-structured decoding with doubly-recurrent neural networks. International Conference on Learning Representations (ICLR) , 2017.
- [15] O. Vinyals, L. Kaiser, T. Koo, S. Petrov, I. Sutskever, and G. Hinton. Grammar as a Foreign Language. Neural Information Processing Systems (NIPS) , 2015.
- [16] R. Aharoni and Y. Goldberg. Towards String-to-Tree Neural Machine Translation. Association of Computational Linguistics (ACL) , 2017.
- [17] M. Rabinovich, M. Stern, and D. Klein. Abstract Syntax Networks for Code Generation and Semantic Parsing. Association of Computational Linguistics (ACL) , 2017.
- [18] E. Parisotto, A.-r. Mohamed, R. Singh, L. Li, D. Zhou, and P. Kohli. Neuro-Symbolic Program Synthesis. International Conference on Learning Representations (ICLR) , 2017.
- [19] P. Yin and G. Neubig. A Syntactic Neural Model for General-Purpose Code Generation. Association of Computational Linguistics (ACL) , 2017.
- [20] X. Zhang, L. Lu, and M. Lapata. Top-down Tree Long Short-Term Memory Networks. North American Chapter of the Association of Computational Linguistics (NAACL) , 2016.
- [21] X. Chen, C. Liu, and D. Song. Tree-to-tree Neural Networks for Program Translation. Neural Information Processing Systems (NeurIPS) , 2018.
- [22] S. Chakraborty, M. Allamanis, and B. Ray. Tree2tree neural translation model for learning source code changes. arXiv pre-print , 2018.

| [23]   | M. Monperrus. Automatic software repair: A bibliography. ACM Computing Surveys (CSUR) 2018.                                                                                                                                                                            |
|--------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [24]   | X. B. D. Le, D. Lo, and C. Le Goues. History driven program repair. Software Analysis, Evolution, and Reengineering (SANER) , 2016.                                                                                                                                    |
| [25]   | F. Long and M. Rinard. Automatic patch generation by learning correct code. Principles of Programming Languages (POPL) , 2016.                                                                                                                                         |
| [26]   | Devlin, Jacob, Uesato, Jonathan, Singh, Rishabh, and Kohli, Pushmeet. Semantic Code Repair using Neuro-Symbolic Transformation Networks. arXiv:1710.11054 , 2017.                                                                                                      |
| [27]   | R. Gupta, S. Pal, A. Kanade, and S. Shevade. Deepfix: Fixing common c language errors by deep learning. Association for the Advancement of Artifical Intelligence (AAAI) , pages 1345-1351, 2017.                                                                      |
| [28]   | J. Harer, O. Ozdemir, T. Lazovich, C. P. Reale, R. L. Russell, L. Y. Kim, and P. Chin. Learning to Repair Software Vulnerabilities with Generative Adversarial Networks. Neural Information Processing Systems (NeuroIPS) , 2018.                                      |
| [29]   | M. Junczys-Dowmunt and R. Grundkiewicz. Phrase-based Machine Translation is State-of-the- Art for Automatic Grammatical Error Correction. Empirical Methods in Natural Language (EMNLP) , 2016.                                                                        |
| [30]   | S. Chollampatt and H. T. Ng. Connecting the Dots: Towards Human-Level Grammatical Error Correction. The 12th Workshop on Innovative Use of NLP for Building Educational Applications. Association for Computational Linguistics (ACL) , 2017.                          |
| [31]   | D. Dahlmeier, H. T. Ng, and S. M. Wu. Building a Large Annotated Corpus of Learner English - The NUS Corpus of Learner English. North American Chapter of the Association of Computational Linguistics (NAACL) , 2013.                                                 |
| [32]   | V. Okun, A. Delaitre, and P. Black. Report on the static analysis tool exposition (sate) iv. Technical Report , 2013.                                                                                                                                                  |
| [33]   | C. Lattner and V. S. Adve. LLVM - A Compilation Framework for Lifelong Program Analysis &Transformation. CGO , 2004.                                                                                                                                                   |
| [34]   | Clang library. clang.llvm.org , 2011.                                                                                                                                                                                                                                  |
| [35]   | Offical scorer for conll 2014 shared task. https://github.com/nusnlp/m2scorer/ releases , 2014.                                                                                                                                                                        |
| [36]   | C. Goller and A. Kuchler. Learning task-dependent distributed representations by backpropaga- tion through structure. International Conference on Neural Networks (ICNN'96) , 1996.                                                                                    |
| [37]   | D. Chen and C. D. Manning. A fast and accurate dependency parser using neural networks. Emperical Methods in Natural Language Processing (EMNLP) , 2014.                                                                                                               |
| [38]   | R. Socher, J. Bauer, and A. Y. Manning, Christopher D.and Ng. Parsing with compositional vector grammars. Association for Computational Linguistics (ACL) , 2013.                                                                                                      |
| [39]   | D. Klein and C. Manning. Accurate unlexicalized parsing. Association for Computational Linguistics (ACL) , 2003.                                                                                                                                                       |
| [40]   | Shift-reduce constituency parser. https://nlp.stanford.edu/software/srparser. html , 2014.                                                                                                                                                                             |
| [41]   | Penn treebank ii tags. https://web.archive.org/web/20130517134339/http://bulba. sdsu.edu/jeanette/thesis/PennTags.html , 2016.                                                                                                                                         |
| [42]   | B. Heinzerling and M. Strube. BPEmb: Tokenization-free Pre-trained Subword Embeddings in 275 Languages. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018) , 2018.                                               |
| [43]   | H. Ng, S. Wu, T. Briscoe, C. Hadiwinoto, R. Susanto, and C. Bryant. The conll-2014 shared task on grammatical error correction. Conference on Computational Natural Language Learning, Association for Computational Linguistics (ACL) , 2014.                         |
| [44]   | V. Daudaravicius, R. Banchs, E. Volodine, and C. Napoles. Areport on the automatic evaluation of scientific writing shared task. 11th Workshop on Innovative Use of NLP for Building Educational Applications, Association for Computational Linguistics (ACL) , 2016. |

- [45] Apted python library. https://pypi.org/project/apted/ , 2015.
- [46] M. Pawlik and N. Augsten. Tree edit distance: Robust and memory-efficient. Information Systems 56 , 2016.
- [47] M. Pawlik and N. Augsten. Efficient computation of the tree edit distance. ACM Transactions on Database Systems , 2015.

## Appendix A hyperparameters

Hyperparameters utilized are listed in tables 5 and 6. Default hyperparameters are listed at the top of each table. A blank means the run utilized the default hyperparameter. Explanation of hyperparemeters follows.

- · N - number of layers
- · d model - size of sublayer outputs - see [2]
- · d ff - size of inner layer in TDB/FF for Tree-Transformer/Transfomer
- · h - Number of attention heads
- · d k - Size of keys in attention mechanism
- · d v - Size of values in attention mechanism
- · p drop - Dropout probability between sub-layers
- · p dattn - Dropout probability on attention mechanism - see [2]
- · p dff - Dropout probability on inner layer of TDB/FF for Tree-Transformer/Transfomer
- · p des - Source embedding word dropout probability
- · p det - Target embedding word dropout probability
- · glyph[epsilon1] ls - Label Smoothing glyph[epsilon1]
- · lr - Learning Rate, We use isr learning rate as per [2]. As such this learning rate will never be fully met, maximum learning rate depends upon warmup.
- · warmup - number of steps for linearly LR warmup
- · train steps - total number of steps for training
- · Mon - Initialized from monolingual pre-trained network
- · Auto - Initialized from autoencoder pre-trained network
- · Mon-Ens - Ensemble trained network with monolingual netword during beam search as per [3]
- · EW-MLE - Use edit-weight MLE objective function as per [8]
- · Time (Hours) - Total training time

Table 5: Model Parameters

| Architecture                                                                                                                 | N               | d model         | d ff            | h                         | d k                       | d v                       | p drop                    | p dattn                   | p dff                     | p des                     | p det                     | glyph[epsilon1] ls        |
|------------------------------------------------------------------------------------------------------------------------------|-----------------|-----------------|-----------------|---------------------------|---------------------------|---------------------------|---------------------------|---------------------------|---------------------------|---------------------------|---------------------------|---------------------------|
| default                                                                                                                      | 6               | 512             | 2048            | 8                         | 64                        | 64                        | 0.3                       | 0.1                       | 0.3                       | 0.2                       | 0.1                       | 0.1                       |
| Sate IV                                                                                                                      | Sate IV         | Sate IV         | Sate IV         | Sate IV                   | Sate IV                   | Sate IV                   | Sate IV                   | Sate IV                   | Sate IV                   | Sate IV                   | Sate IV                   | Sate IV                   |
| LSTM Transformer                                                                                                             | 4               |                 |                 | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer | 1024 N/a Tree-Transformer |
| GEC Pretraining                                                                                                              | GEC Pretraining | GEC Pretraining | GEC Pretraining | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           |
|                                                                                                                              |                 |                 |                 | Monolingual Autoencoder   | Monolingual Autoencoder   | Monolingual Autoencoder   | Monolingual Autoencoder   | Monolingual Autoencoder   | Monolingual Autoencoder   | Monolingual Autoencoder   | Monolingual Autoencoder   | Monolingual Autoencoder   |
| Conll 2014                                                                                                                   | Conll 2014      | Conll 2014      | Conll 2014      | Conll 2014                | Conll 2014                | Conll 2014                | Conll 2014                | Conll 2014                | Conll 2014                | Conll 2014                | Conll 2014                | Conll 2014                |
| Tree-Transformer Tree-Transformer +Mon Tree-Transformer +Mon +Mon-Ens Tree-Transformer +Auto Tree-Transformer +Auto +Mon-Ens |                 |                 |                 |                           |                           |                           |                           |                           |                           |                           |                           |                           |
| Aesw                                                                                                                         | Aesw            | Aesw            | Aesw            | Aesw                      | Aesw                      | Aesw                      | Aesw                      | Aesw                      | Aesw                      | Aesw                      | Aesw                      | Aesw                      |
| Transformer Tree-Transformer                                                                                                 |                 |                 |                 |                           |                           |                           |                           |                           |                           |                           |                           |                           |

Table 6: Training Parameters

| Architecture                                                                                                                 | lr                      | warmup          | train steps     | Mon                       | Auto                      | Mon-Ens                   | EW-MLE          | Time (Hours)    |
|------------------------------------------------------------------------------------------------------------------------------|-------------------------|-----------------|-----------------|---------------------------|---------------------------|---------------------------|-----------------|-----------------|
| default                                                                                                                      | d - 0 . 5 model         | 4000            | 100k            | -                         | -                         | -                         | -               |                 |
| Sate IV                                                                                                                      | Sate IV                 | Sate IV         | Sate IV         | Sate IV                   | Sate IV                   | Sate IV                   | Sate IV         | Sate IV         |
| LSTM Transformer Tree-Transformer                                                                                            |                         |                 |                 |                           |                           |                           |                 | 40 18 22        |
| GEC Pretraining                                                                                                              | GEC Pretraining         | GEC Pretraining | GEC Pretraining | GEC Pretraining           | GEC Pretraining           | GEC Pretraining           | GEC Pretraining | GEC Pretraining |
| Monolingual Autoencoder                                                                                                      |                         |                 | 500k 500k       |                           |                           |                           |                 | 38 50           |
| Conll 2014                                                                                                                   | Conll 2014              | Conll 2014      | Conll 2014      | Conll 2014                | Conll 2014                | Conll 2014                | Conll 2014      | Conll 2014      |
| Tree-Transformer Tree-Transformer +Mon Tree-Transformer +Mon +Mon-Ens Tree-Transformer +Auto Tree-Transformer +Auto +Mon-Ens | 16000 16000 16000 16000 | 16000           |                 | glyph[check] glyph[check] | glyph[check] glyph[check] | glyph[check] glyph[check] | 3 3 3 3 3       | 26 26 26 26 26  |
| Aesw                                                                                                                         | Aesw                    | Aesw            | Aesw            | Aesw                      | Aesw                      | Aesw                      | Aesw            | Aesw            |
| Transformer Tree-Transformer                                                                                                 | 16000                   | 16000           |                 | glyph[check] glyph[check] |                           | glyph[check] glyph[check] | 3 3             | 19 25           |
Jacob Harer Chris Reale Peter Chin
Tree-Transformer: A Transformer-Based Method for Correction of Tree-Structured Data
Many common sequential data sources, such as source code and natural
language, have a natural tree-structured representation. These trees can be
generated by fitting a sequence to a grammar, yielding a hierarchical ordering
of the tokens in the sequence. This structure encodes a high degree of
syntactic information, making it ideal for problems such as grammar correction.
However, little work has been done to develop neural networks that can operate
on and exploit tree-structured data. In this paper we present the
Tree-Transformer \textemdash{} a novel neural network architecture designed to
translate between arbitrary input and output trees. We applied this
architecture to correction tasks in both the source code and natural language
domains. On source code, our model achieved an improvement of $25\%$
$\text{F}0.5$ over the best sequential method. On natural language, we achieved
comparable results to the most complex state of the art systems, obtaining a
$10\%$ improvement in recall on the CoNLL 2014 benchmark and the highest to
date $\text{F}0.5$ score on the AESW benchmark of $50.43$.