Advances in Using Grammars with Latent Annotations for Discontinuous Parsing (2020)

Abstract: We present new experiments that transfer techniques from Probabilistic Context-free Grammars with Latent Annotations (PCFG-LA) to two grammar formalisms for discontinuous parsing: linear context-free rewriting systems and hybrid grammars. In particular, Dirichlet priors during EM training, ensemble models, and a new nonterminal scheme for hybrid grammars are evaluated. We find that our grammars are more accurate than previous approaches based on discontinuous grammar formalisms and early instances of the discriminative models but inferior to recent discriminative parsers.

## introduction many tasks in natural language processing, such as machine translation, information extraction, and sentiment analysis, benefit from syntactic analysis @xcite @xcite . often syntax is represented by means of constituents. languages with a flexible word order such as german require constituents that are discontinuous, i.e., constituents that cover words which do not constitute a continuous interval in the sentence. to this end, generalizations of context-free grammars such as tree adjoining grammars @xcite and linear context-free rewriting systems (lcfrs, @xcite have been proposed. although the parsing complexity with these formalisms is polynomial in the length of the input sentence (for a fixed grammar), they are often considered too slow to be practically useful. also the accuracy of lcfrs-based parsers does not match up to their continuous counterparts. instead, a wide range of models that either apply transition systems with a reordering mecha-nism or are based on a dependency-to-constituency transformation have been proposed in recent years @xcite @xcite @xcite @xcite @xcite . there are two notable exceptions: van cranenburgh et al. (2016) considers a discontinuous extension of the data-oriented parsing approach. @xcite studies the extension of two grammar formalisms with latent annotations: lcfrs and hybrid grammars @xcite , which is a synchronous grammar formalism that couples a string generating grammar (specifically: lcfrs) and a tree generating grammar (specifically: simple definite clause programs; @xcite . in particular, gebhardt (2018) analyses the effect of a generalization of @xcite , which adaptively refines the grammar's nonterminals by automatic splitting and merging. although this refinement strategy showed vast improvements over the respective unrefined grammar, some choices in the experimental setup of gebhardt (2018) can be enhanced: in this work, we address the above points by (i) comparing the likelihood-based objective to a maximum-a-posteriori (map) objective, (ii) evaluating ensemble models, and (iii) proposing a new nonterminal naming scheme for hybrid grammars. we hypothesize that these steps are complementary in improving the accuracy of the parsing model. although we do not expect to reach or even surpass the performance of recent discriminative approaches (in particular those utilizing neural nets), we suppose that these experiments foster the understanding of the limits of the different architectures. ## model we consider models based on lcfrs and hybrid grammars. @xcite and @xcite give formal definitions of these formalisms, respectively. baseline grammars are induced from the training data using the induction techniques of @xcite and @xcite , respectively. lcfrs are either binarized right-to-left (r2ℓ) or head-outward (ho) with vertical and horizontal markovization set to 1. for hybrid grammars the induction is parametrized such that the lcfrs-component has fanout 2. the baseline grammars are refined using a variant of @xcite , which is described in @xcite . this algorithm consists of multiple split/merge cycles in each of which the em algorithm is used to fit the rule weights to the training data. to obtain map training, we modify the em algorithm by including a dirichlet prior (see @xcite . this is implemented by incrementing each rule count by a non-negative default value in the "expectation" phase. gebhardt (2018) reports that lcfrs outperform hybrid grammars but conjectures that this might be an artifact of the choice of nonterminals in the baseline grammar. the nonterminal naming schemes child and strict labeling for hybrid grammars (originally introduced by @xcite name a nonterminal based on the subset of tree nodes u foot_1 that is generated by the nonterminal. as illustrated in fig. 1 , in strict labeling the roots of maximum subtrees formed by u are used in the label, where consecutive sibling nodes are joined. in child labeling, sequences of sibling nodes of @xmath0. @xcite supposes that these strategies either lead to a number of nonterminals that is too small or too large for favorable automatic refinement. we explore a trade-off by markovizing (cf. @xcite the strict labeling strategy. where strict labeling uses sequences @xmath1, we now use the parent node p of n 1 • • • n k , the first node n 1 , and a cut-off marker . each nonterminal label then consists of sequences @xmath2. after split/merge refinement, the grammars are used to parse unseen sentences. since exact parsing is np-hard already for pcfg-la (see @xcite , we follow the literature and apply an approximate tractable objective called max-ruleproduct (short: mrp, which projects weights from the refined grammar to a sentence-specific coarse one and computes the the most probable derivation of the latter, see @xcite . @xcite presents experiments with ensemble models, where different pcfg-la are obtained from the same training data by changing the random seed. during parsing the mrp objective is applied where each rule weight of the coarse grammar is set to the product of the weights that result from projecting with the individual grammars. this ensemble grammar showed significantly improved accuracy over the best single grammar. we instantiate this approach for lcfrs and hybrid grammars using 4 random seeds. f1 and labelled discontinuous f1 using discodop 3 @xcite with the included proper.prm parameter file. in the tables we list average f1 scores and standard deviation over 4 grammars with different random seeds, except for ensemble experiments where we execute just one run combining those 4 grammars. properties of baseline grammars. we induce baseline grammars from the training data and display their properties in training objective. we use the split/merge algorithm to refine the baseline grammars using both a likelihood-based and a map-based objective with default count 1.0 during em training foot_2 . differences between both training modes are displayed in ensemble models. comparing the (disc.) f1scores of the ensemble model with the averages of the individual grammars, we always see an improvement, which in many cases is also well above the standard deviation. ## discussion and conclusions the experiments provide further evidence that the split/merge method is applicable and effective beyond pcfg. the use of priors and ensembles of grammars is mostly beneficial and complementary. from the performance differences between child labeling and markovized strict labeling, we can surmise that the initial nonterminal granularity matters as the split/merge method cannot fully recover important splits or at least during parsing the mrp objective relies on guidance by the baseline nonterminal structure. more generally, the performance differences between the considered grammars indicate that a careful choice of the grammar formalism and the extraction algorithm is not redundant despite split/merge refinement. interestingly, the pseudo-projective approach by @xcite outperforms our strictly discontinuous one. he uses a linguistically motivated (de)projectivization strategy foot_5 that seems to address the sparsity of discontinuous constituents in the data very well. hence, we may conjecture that true discontinuous grammar formalisms that make available a large number of discontinuous productions (based on scarce evidence) may rarely benefit from the additional expressiveness. to substantiate this claim certainly a controlled experiment is necessary as differences may as well be artefacts of the handling of lexical and fall-back rules by versley (2016). however, a similar observation was made concerning (discontinuous) tree substitution grammars @xcite . also a recent study by @xcite finds that a very restricted mode of discontinuity, which can be simulated by a series of continuous combinations, is more accurate than more expressive modes. the research on discontinuous parsing with latent variable grammars may also be extended by considering spectral algorithms (cf. cohen, 2017, for an overview). in particular, @xcite use latently annotated lcfrs obtained by spectral algorithms to parse the topical structure of forum threads. yet, the application of spectral algorithms for discontinuous syntactic parsing has not been investigated.