BME - TUW at SR ’20: Lexical grammar induction for surface realization (2020)

Abstract: We present a system for mapping Universal Dependency structures to raw text which learns to restore word order by training an Interpreted Regular Tree Grammar (IRTG) that establishes a mapping between string and graph operations. The reinflection step is handled by a standard sequence-to-sequence architecture with a biLSTM encoder and an LSTM decoder with attention. We modify our 2019 system (Kovács et al., 2019) with a new grammar induction mechanism that allows IRTG rules to operate on lemmata in addition to part-of-speech tags and ensures that each word and its dependents are reordered using the most specific set of learned patterns. We also introduce a hierarchical approach to word order restoration that independently determines the word order of each clause in a sentence before arranging them with respect to the main clause, thereby improving overall readability and also making the IRTG parsing task tractable. We participated in the 2020 Surface Realization Shared task, subtrack T1a (shallow, closed). Human evaluation shows we achieve significant improvements on two of the three out-of-domain datasets compared to the 2019 system we modified. Both components of our system are available on GitHub under an MIT license.

## introduction this paper describes our participation in the t1a subtask of the 2020 surface realization shared task @xcite , which requires systems to map universal dependency graphs of lemmata to raw sentences by reconstructing word forms and word order. we extend the word order restoration component of @xcite by making it sensitive to lemmata in addition to parts-of-speech and by performing the word order restoration step separately for each clause of a sentence. the paper is structured as follows: section 2 briefly describes the data and the task as well as the architecture that we modify. section 3 presents our new method for rule generation for creating lexical grammars, section 4 describes the hierarchical approach for breaking up the word order restoration task into clause-level subtasks. section 6 presents a summary of both automatic and human evaluations, section 7 discusses potential future work. the irtg-based system for word order restoration can be downloaded from https://github.com/adaamko/surface_realization , the inflection system was trained using the framework under https://github.com/juditacs/deep-morphology . both components are available for download under an mit license. the system presented in this paper, a substantial extension of the solution of @xcite , offers a fully rule-based, explainable, and language-independent solution for the word order restoration component of the shallow surface realization task and uses an independent ml system for reconstructing word forms. in last year's evaluation, the top rule-based systems were consistently outperformed by the best-performing ims @xcite and cmu @xcite systems (see @xcite for evaluation details). both of these solutions rely on deep learning models for the word order restoration component of the task. still, an important similarity between their approaches and ours is that they also take the divide-and-conquer approach of determining word order separately for each head and all its dependents. in future work this will allow detailed comparison between the atomic decisions of our system and the state-of-the-art (see section 7 for some proposals). ## hierarchical surface realization our approach to rule induction presented in the previous section yields a large number of rules. the grammar for an average sentence in the en ewt dataset would contain over 1000 irtg rules, making the parsing process prohibitively slow. we reduce the average complexity of the task by cutting ud graphs along edges that connect clauses of a sentence, thereby splitting them up into smaller graphs for which our grammar-based approach can be performed separately. the resulting word sequences can then be arranged relative to each other by performing word order restoration on the ud graph of the main clause, this time including dependents of the predicate from other clauses and interpreting them as representing their clauses. we shall now explain this method in detail and illustrate it with an example. a simple example of an ud graph of multiple clauses, taken from the en ewt-ud test set, is shown in figure 3 and corresponds to the sentence click here to view it. we begin by cutting the graph on any of the edges that may encode dependency relationships between clauses: acl, advcl, ccomp, xcomp, conj. in this case, the edge click advcl ---→ view is found and the graph is split into two new ud graphs that correspond to the fragments click here and view it. what follows are three separate runs of the word order restoration algorithm described in the previous section. the first two receive as their input the ud graphs click advmod -----→ here and view obj --→ it to determine the word order of each fragment. to arrange them with respect to each other, we run our algorithm on the ud graph click advcl ---→ view, the edge connecting the clauses, and interpret the outcome not as an order of the two words but as that of their respective clauses. this approach also enforces that non-clausal dependents of the root of a clause group together with respect to each clausal dependent, which we considered an advantage based on initial experiments with the one-step approach: arguments of a predicate separated by an intervening clause were the errors that we observed would make longer sentences entirely incomprehensible. our algorithm is defined recursively, since a dependent clause may itself have clausal dependents. on a sample of 500 english sentences held out from the training dataset, we invoked the core word order restoration method 1794 times, or about 3.6 times per sentence (a single dependent clause would warrant 3 invocations). even in such a small sample, we see one example each for recursions of depth 4, 5, and even 6, the latter caused by the following sentence (roots of clauses are marked by indices corresponding to depth): perhaps had we not gone 1 into this restaurant believing 2 zahav was going 3 to be golden 4 as its name suggests 5 (and as the many golden reviews seem 5 to attest 6 ), we would have enjoyed 0 a decent little expensive experience. the reduction in average complexity of the grammars can also be illustrated using the same sample of 500 english sentences: before introducing the hierarchical approach, the 500 irtg grammars contained more than 400 000 rules, or over 800 rules per grammar on average, resulting in an average parse time of over 4 seconds per sentence (excluding the 42 sentences for which parsing did not finish in 60 seconds, these can be parsed using a simplified grammar, see section 5 for details). under the clause-based approach, 1794 irtg grammars are built to handle the 500 sentences, these contain less than 200 rules on average, and parsing time for individual clauses is just above 700 ms, which brings the per sentence parse time to 2.7 seconds. note that we did not analyze the runtime of our entire system, these statistics are based on net parse times reported by the alto library, run on a system with 56 intel xeon e5-2697 v3 2.6ghz cpus. we expect that the greatest bottleneck in overall performance is the per-sentence generation of grammars and invocations of alto, but for now we chose to keep this architecture as one that makes both debugging and introspection relatively straightforward. ## overall architecture our full solution for the surface realization task is a pipeline of the grammar-based word order restoration system presented in sections 3-4 and the dl-based reinflection model used in @xcite . for each language we begin by processing all training and test data to build a shared vocabulary for the given language, mapping lemmata to integers so that they can be represented in alto input and grammar files without the need to transform special characters. after performing the counting of subgraphs that is the training step of the grammar induction system, the model is kept in memory to efficiently serve lookup requests through a rest api to one or several instances of our tool performing word order restoration for datasets of the same language. when processing the test ud graphs, the core word order restoration algorithm is invoked for each subclause, as described in section 4. the set of dependency edges used to split clauses is configurable and in all our experiments contained the relations acl, advcl, ccomp, xcomp, and conj. the irtg rules generated are written to an alto grammar file, the ud graph is written to a file using the penman notation foot_1 , one of the formats handled by alto. next, the parser is invoked as a subprocess with a configurable timeout per sentence, set to 120 seconds in our experiments. in case of a timeout, a new irtg is generated keeping only those rules that generate subgraphs with a single edge, i.e. we retry with a much simpler grammar that can only add edges to the ud graph one-by-one. under the clause-based approach this affected only 1% of all clauses in the test datasets. finally, the linearized sentences are printed in the conllu format and processed by the lstm-based reinflection model trained using the parameters in @xcite , and a simple postprocessing step which uses simple pattern matching to detect urls in lemmata and replaces their 'inflected' forms in the final output with the original url. we do not perform detokenization, our final for each dataset, system outputs were scored on both their readability and their semantic similarity to the reference sentences. on the russian and spanish out-of-domain datasets derived from wikipedia, our system significantly outperforms the original submission of @xcite according to both metrics. ## conclusion and future work we have presented a modification of a language-independent surface realization system with a fully rule-based component for word order restoration. our main contribution is a new mechanism for generating mappings between graph and string operations using irtg grammars that choose for a word and its dependencies the most specific patterns observed in the training data. unlike the original system, our solution makes little use of rule weights, their sole function is currently to ensure that shorter derivations for a ud graph are preferred over longer ones. we believe that our method may be improved by introducing non-determinism in the generated grammars via some weighting scheme that allows seemingly non-optimal patterns to be chosen over those that were observed most frequently. given the large number of parameters of our system, we also suggest the use of additional, silver-standard training data, which would be available in virtually unlimited quantities for all languages for which a high quality ud parser is available. finally, the most important next step should be the thorough quantitative and qualitative analysis of the performance gap between our method for word order restoration and that of the stateof-the-art. observing and quantifying correct and incorrect decisions of the grammar and updating the induction mechanism accordingly is what we consider the greatest potential of our rule-based and thus fully explainable solution.