Efficient Constituency Tree based Encoding for Natural Language to Bash Translation (2022)

Abstract: Bash is a Unix command language used for interacting with the Operating System. Recent works on natural language to Bash translation have made significant advances, but none of the previous methods utilize the problem’s inherent structure. We identify this structure andpropose a Segmented Invocation Transformer (SIT) that utilizes the information from the constituency parse tree of the natural language text. Our method is motivated by the alignment between segments in the natural language text and Bash command components. Incorporating the structure in the modelling improves the performance of the model. Since such systems must be universally accessible, we benchmark the inference times on a CPU rather than a GPU. We observe a 1.8x improvement in the inference time and a 5x reduction in model parameters. Attribution analysis using Integrated Gradients reveals that the proposed method can capture the problem structure.

## introduction semantic parsing is one of the central tasks for natural language understanding (nlu). it is defined as the task of generating meaning representations from natural language utterances @xcite . previous works @xcite @xcite have used high level languages such as python, sql and bash as meaning representations. this work focuses on generating bash commands from natural language descriptions of command-line tasks. besides being an essential task for nlu, semantic parsing into a high-level language also has realworld applications such as helping developers write programs and making programming universally accessible. the command-line interface has been regarded as an invaluable tool due to its expressiveness, efficiency and extensibility @xcite . however, it has a learning curve and requires domain knowledge. an interface with the computer using natural language, on the other hand, remedies these issues. one need not remember the syntax of hundreds of bash utilities, and instead, one can specify the task in natural language. such an interface that uses natural language such as english for specifying command-line tasks makes computing accessible to people with little domain knowledge. therefore, developing a system to generate bash commands from english is worth one's efforts. previous works on this semantic parsing task @xcite @xcite @xcite use various encoder-decoder style architectures. these methods consider the natural language component as a sequence of tokens without utilizing the inherent structure for this problem. the method proposed in this work utilizes the information from the constituency parse tree of the natural language to incorporate this problem structure into the modelling process. our approach is based on the observation that natural language invocations are complex and can be broken down into simpler segments that align with the bash command components (utilities, flags and arguments). we incorporate this observation in our method to provide an inductive bias to the transformer model @xcite , making the search space of solutions more aligned with the task at hand. the models are evaluated on the nl2bash dataset @xcite obtained from the neurips 2020 natural language context to command (nlc2cmd) contest @xcite . the proposed method outperforms the winning solution from the nlc2cmd contest in terms of generation accuracy while also achieving a speedup of 1.8x and reducing the parameter count by 5x over it. it also performs better than models like t5 @xcite and codet5 @xcite which are trained on a large amount of data and then fine-tuned on the dataset under study. our code is available at https://github.com/shikhar-s/ segmented-invocation-transformer our main contributions are the following: first, we formally describe the problem statement. section 2 describes the structure for the problem, and section 3 describes our approach to model the structure and expected gains in the inference time via a complexity analysis of the decoding phase. section 4 describes the dataset used and its preprocessing. in section 5, we describe the experiments conducted for checking the correctness and efficiency of our approach and analyzing the results. section 6 compares our work with other related works. finally, in section 7 we conclude and discuss some directions for future work. problem statement. let i be the set of all natural language invocations, c be the set of all bash figure 1 : segmenting invocation: first, the raw invocation is normalized to remove patterns and file paths. this normalized invocation is then parsed to obtain a constituency tree. then, the tree is cut at a threshold height to create subtrees. the leaves of each subtree form tokens in the segments. the task is to design an algorithm that, given an invocation @xmath0, outputs a set of bash command-confidence pairs (ĉ, δ) such that • ĉ ∈ c is the predicted bash command that performs the task specified in nlc, and for example, @xmath1. ## method we frame the problem as a translation task from english to bash. in section 3.1 we describe our approach to incorporate the structure in modelling natural language invocations. section 3.2 describes the proposed architecture and an analysis of its computational complexity at inference time. ## data and preprocessing for evaluating our method, we used the nl2bash dataset @xcite provided by the nlc2cmd contest @xcite from neurips 2020. it consists of approximately 10k paired english invocations and bash commands scraped from stack overflow covering over 100 bash utilities. the dataset was partitioned into five folds. we performed five runs. in each run, we split one fold equally for validation and testing. the remaining four folds were pooled to create the training set for the run. all results mentioned in ## related work early works on semantic parsing explored meaning representations like first-order logic, lambda cal-5 attribution matrices for the sampled instances are available at https://github.com/shikhar-s/ segmented-invocation-transformer/blob/ main/jup_notebook/attribution_viz.ipynb culus enhanced first-order logic @xcite , database query languages and operated on handcrafted rules @xcite . these were followed by statistical models that were able to learn rules from input-output parallel data @xcite @xcite . recently, there have been many advancements in generating high-level programming languages. @xcite and @xcite propose general attention based encoder-decoder style methods for semantic parsing. @xcite propose abstract syntax networks with a dynamically determined modular decoder structure that parallels the structure of the output tree. @xcite propose an architecture enhanced by a grammar model that explicitly captures the target language syntax as prior knowledge. most of the innovations in this area utilize recurrent neural networks (rnn) for modelling natural language input. the method proposed in this work enhances the transformer encoder with constituency parsing information. for natural language to bash, in particular, lin et al. (2018) created a dataset and proposed an encoder-decoder based architecture. @xcite explore several sequence to sequence models, abstract syntax networks and nearest neighbor based models for this task on a custom dataset. @xcite proposed a command-line ai assistant for this task. @xcite organized a contest in neurips 2020 for natural language to bash translation and provided a report on the state of the art architectures developed in the contest. @xcite explored the use of linux manual pages and abstract syntax tree for developing an explainable natural language to bash translation system. in contrast to these methods, our work explores the synchronous structure of this problem and uses the constituency tree to better model natural language input. constituency parse tree of natural language has been used in earlier machine translation and semantic parsing literature. @xcite note that the transformer @xcite struggles to encode hierarchical structures and propose a hierarchical accumulation mechanism that utilizes constituency parse tree to capture this structure for neural machine translation. they achieve this by adding additional parameters that capture the constituency structure of sentences. our method, in contrast, uses constituency tree information in a parameter efficient manner. @xcite construct a syntactic graph from constituency and dependency parse tree and employ a graph to sequence neural network using an rnn decoder. they report improvement over the sequence to sequence model proposed by @xcite showing that additional syntactic information helps in semantic parsing. we use a transformer and show that segmentation structure aids in natural language to bash translation. ## conclusion and future work we propose a method that utilizes information from the constituency tree to better model the structure of natural language to bash task. our experiments on the nlc2cmd data show that incorporating the problem structure in the model architecture improves both performance and parameter efficiency. we also run inference time benchmarks and find that the proposed method is faster. attribution analysis is also conducted to analyze the method. in this work, we focus on bash as the meaning representation and identify the structure for natural language to bash translation. however, we expect a similar structure for other meaning representations like sql. applying our method to natural language to sql task is left for future work. our method relies on stanford corenlp parser @xcite for constituency parsing. this is a bottleneck for fully utilizing the efficiency of our approach. it will be interesting to test faster constituency parsers @xcite which can parse around 1k sentences per second.