Span-Based LCFRS -2 Parsing (2020)

Abstract: The earliest models for discontinuous constituency parsers used mildly context-sensitive grammars, but the fashion has changed in recent years to grammar-less transition-based parsers that use strong neural probabilistic models to greedily predict transitions. We argue that grammar-based approaches still have something to contribute on top of what is offered by transition-based parsers. Concretely, by using a grammar formalism to restrict the space of possible trees we can use dynamic programming parsing algorithms for exact search for the most probable tree. Previous chart-based parsers for discontinuous formalisms used probabilistically weak generative models. We instead use a span-based discriminative neural model that preserves the dynamic programming properties of the chart parsers. Our parser does not use an explicit grammar, but it does use explicit grammar formalism constraints: we generate only trees that are within the LCFRS-2 formalism. These properties allow us to construct a new parsing algorithm that runs in lower worst-case time complexity of O(l nˆ4 +nˆ6), where n is the sentence length and l is the number of unique non-terminal labels. This parser is efficient in practice, provides best results among chart-based parsers, and is competitive with the best transition based parsers. We also show that the main bottleneck for further improvement in performance is in the restriction of fan-out to degree 2. We show that well-nestedness is helpful in speeding up parsing, but lowers accuracy.

## introduction most constituency parsers are designed to predict a projective (or continuous) tree representation. this type of tree representation is not expressive enough to model (structurally) long-range dependencies that are a major concern of most syntactic theories. take for instance the sentence in figure 1 . it contains a long range dependency between "on" and "what". this is represented differently across syntactic theories. in dependency parsing, there would be a direct arc between these two words that would cause the dependency tree to be non-projective, i.e. there would be crossed dependencies @xcite . in constituency treebanks this is modelled either by using traces that are co-indexed with the moving element, as in english penn treebank @xcite , or by having a direct discontinuous constituent, as in german negra and tiger treebanks @xcite . here we adopt the discontinuous constituency approach because of its well defined formal properties, but the results are also relevant for other representations. the penn treebank trace representation can be converted to a discontinuous representation @xcite foot_0 and nonprojective dependency trees can be interpreted as lexicalised versions of discontinuous constituency trees @xcite . there are two different approaches to predicting discontinuous constituency structure directly. 2 the first approach, usually grammar-based chart parsing, limits the type of trees that are acceptable (for example tag @xcite or lcfrs @xcite ) and searches for the best tree with an exact search algorithm like cky. the second approach, usually transition-based, does not limit the type of trees but searches for the best tree only approximately with a beam search. lately, with the success of neural models, transition-based parsers have been preferred to grammar-based approaches because transition-based models do not need to make any independence assumptions and strong neural models can be used to their full potential. grammarbased methods have more difficulty incorporating rich probabilistic models due to the necessary independence assumptions needed for exact dynamic programming algorithms like cky. another disadvantage of grammar based models is that, even though their parsing algorithms are polynomial, they are significantly slower in practice due the high polynomial degrees and a large grammar constant. in this work we try to improve both speed and accuracy of chart-based parsers. the accuracy is improved by using a modified version of neural span-based scoring of non-terminal nodes @xcite which does not break the independence assumptions needed for efficient parsing. speed is improved by restricting the set of acceptable trees to the ones recognizable with an lcfrs-2 grammar formalism, but no explicit grammar is used, removing the grammar constant from the worst-case complexity. 3 additionally, the parser is implemented using an imperative approach to viterbi cky parsing (as opposed to deductive approach), similar to standard cfg cky implementations with embedded loops. by avoiding the usage of standard weighted deductive parsing @xcite . we avoid the need to maintain heap property of the agenda, further reducing the worst-case parsing complexity. this results in a fast chart-based lcfrs-2 parser that outperforms all previous chart-based parsers for discontinuous structures, and gives performance that is on par with the best transition-based parsers. ## lcfrs-trees lcfrs @xcite @xcite is a grammar formalism that works in a similar way to cfg: it applies a series of recursive rewriting rules that eventually generate a sentence. what makes it different from cfg is that it allows each non-terminal node in the derivation tree to contain more than one continuous span of words. for instance, if we look back at the example from figure 1 , we can represent the discontinuous pp as pp(what, on), or in terms of spans pp (0, 1), (4, 5) . an lcfrs rule that forms this constituent can be expressed as: pp(x, y ) → wh(x) p(y ) these individual spans are often called components and the number of them per non-terminal is called the fan-out of the non-terminal. the fan-out of an lcfrs grammar is defined by the maximal fan-out of its non-terminals. the fan-out of the grammar has significant consequences to its expressivity and the parsing complexity. for binary lcfrs the worst-case parsing complexity is o(g • n 3φ ) where g is the grammar constant (total number of lcfrs rules) and φ is the grammar's fan-out @xcite . if fan-out is 1 we get only the power of a standard cfg and a very efficient parser. if the fan-out is unrestricted (as big as the sentence being parsed), we could process any discontinuous structure but will get a non-polynomial parser. clearly, we need to restrict fan-out to some small constant number. @xcite suggested that restricting fan-out to 2 is sufficient to process a large portion of discontinuous structures in german treebanks. we adopt this proposal and show the consequences of it in the experiments section. we will refer to this grammar as lcfrs-2. another useful restriction of lcfrs is a wellnestedness property @xcite . for any lcfrs rule which contains some non-terminals a and b on its right-hand side we say that it is well-nested if there are no components a 1 and a 2 from a, and b 1 and b 2 from b that form a linear order a 1 < b 1 < a 2 < b 2 . this property allows for efficient parsing @xcite , but in our case of a binary lcfrs with fan-out 2, the effect of well-nestedness will be only proportional to some constant. @xcite state that well-nestedness holds for the majority of constituents in german treebanks. we will test it in our experiments. we will refer to this type of grammar as lcfrs-wn-2. tree-adjoining grammars (tag) @xcite are weakly equivalent to lcfrs-wn-2. ## neural span-based model we borrow and modify some ideas already popular in cfg parsing to improve lcfrs-2 chart parsing. in particular, span-based scoring is a popular approach for modelling scoring of parse trees without breaking the dynamic programming assumptions of chart parsers @xcite @xcite . in this approach words are first encoded with bi-lstm @xcite . these word encodings are afterwards used to score spans. for each span we take encodings of two words that are at its borders and pass them through feed-forward @xcite or bi-affine classifier @xcite that predicts the score for each possible label (nonterminal) occupying that span. unaries are all collapsed into a single non-terminal to simplify scoring. the score of a whole tree is defined as a sum of the scores all of its nodes. these scores are often optimised for max-margin loss @xcite ) by decoding the currently best tree according to the model and minimising the margin violation in case the predicted tree is not the gold tree. @xcite show that span labelling and span combination (parsing) part can be done independently for this model because the best label for each span does not depend on the span's children nodes, unlike the standard pcfg. computing optimal labels for each span takes o(l n 2 ) for sentence of length n and l labels (non-terminals). there are a couple of things that need to be addressed before this approach can be used for lcfrs-2 parsing. first is that non-terminals in lcfrs-2 can have two spans and applying the approach of @xcite would give labelling algorithm that runs in o(l n 4 ) which is prohibitively large considering the hidden constant factor of matrix multiplication done by the neural scoring layer. to reduce the computational complexity of span scoring we introduce independence assumption that score of some discontinuous constituent with label x and spans (a, b), (c, d) is: the second aspect of span-based models that we needed to change is the objective function. the original max-margin parsing objective proposed by @xcite maximised the margin between the gold tree and all other trees. because that approach was too slow in practice it is usually approximated by maximising only the margin between the gold and the highest scoring tree, in case highest scoring tree is not the gold tree. this approach gave good results in cfg parsing @xcite , but it was very unstable in our tests. the reason for this may be in the difference between the number of possible hypotheses between cfg and lcfrs-2 which increases quadratically from the order of o(n 3 ) to o(n 6 ). in this case, optimising for just a single margin violation may be a too weak learning signal. decreasing the scores of one bad tree alone may increase the score of another bad tree. that is why instead of the structured max-margin training we used an alternative method where we treat each triple (span start, span end, label) as a binary classification task and train the model to predict the probability of that triple being part of the gold tree. for training we use not only the triples from the gold tree but all possible triples for a given sentence. we consider the probability of the tree to be the product of probabilities of the triples coming from each of its nodes. this probability model is obviously making some independence assumptions that are not correct. for instance, the probability of a constituent with a span (1, 3) does not inform the probability of a constituent with a span (2, 5) even though it is clear that both constituents cannot exist at the same time. this model may nevertheless give good parsing results because the optimal result of these classifications would give the optimal tree. this method is much more stable in comparison to the max-margin approach of @xcite because the gradient takes into consideration the components of all possible trees at the same time instead of only the highest scoring one. in comparison to max-margin markov networks method of @xcite which also considers all trees, our approach is much faster because it does not need to build chart for each training instance. as mentioned before, we collapse all unary chains into a single non-terminal which contains sufficient information to be unchained after parsing. nodes that have more than 2 children are binarized with the same method as @xcite by labelling all new sub-nodes as ∅. again, there are some aspects to consider before applying the method of @xcite . first, binarization of lcfrs, unlike binarization of cfg, can increase the generative power by increasing the fanout @xcite . if we have a tree that can be generated with lcfrs-2 and arbitrarily choose binarization method, the binarised tree may turn out not to be within the strong generative power of lcfrs-2. hence, choosing the right binarization is important. second, different binarizations actually correspond to different latent derivations of the tree we are modelling. these latent derivations will have different probabilities and its not easy to see which one of them should be used. the approach we will pursue is to model all of them by treating every possible triple that can be extracted from every possible binarization of a gold tree to be a positive class. ## direct cky parsing algorithm the algorithms for lcfrs are usually presented, and implemented, as deductive rules. these deductive rules, combined with a deduction engine of @xcite can form a conceptually simple mechanism for parsing. in case of weighted deductive rules the modification of @xcite can be used. it modifies the method of search to explore the most probable search space first by implementing the agenda as a priority queue. almost all probabilistic lcfrs (plcfrs) parsers have been implemented in this way @xcite @xcite . however, there are many reasons not to use this approach with our span-based model. first, implementing the agenda as a priority queue adds a o(log n) multiplicative term to the worst-case complexity. second, the multiplicative grammar constant that exists in plcfrs approaches does not exist in ours since there is no explicit grammar, and the optimal label for each span is independent of the other spans. third, because of the difficulty of implementing optimal chart lookup under deductive approaches means that most plcfrs parsers optimise lookup only on the non-terminal labels and not on span indices, representing a serious bottleneck. the parsing approach we propose has instead worst-case complexity o(l n 4 +n 6 ) because it does not use an explicit grammar, nor priority queue, and it has very straightforward lookup based on indices. it consists of two parts. first part takes the scores from the neural model and computes the optimal score for each possible lcfrs-2 combination of spans of which there are n 4 . that makes its complexity o(l n 4 ) where l is the number of distinct non-terminals. the second part does the actual parsing by combining these scores to form the best tree. it is a generalisation of how non-deductive cfg cky algorithm works by having multiple embedded for loops and a multi-dimensional array to represent a chart. both chart and loops have to be adapted to lcfrs. we have two data structures involved that are both indexed by the span: a lookup table for optimal span label (and its score), and a lookup table for the optimal backpointer to children nodes (and its score). we will refer to the first one as labchart and to the second one as chart. each one of them could be used for looking up continuous spans (only 2 indices) or discontinuous spans (4 indices). we can implement them with multidimensional arrays that provide constant lookup. to find which loops are needed we borrow this is simple when we have only one rule shape as in the case of cfg, but with lcfrs we need to make sure that all rules are tested in the right order. we know that bigger spans are always composed of smaller spans. therefore we can have a top for loop that would iterate over the total span size. the for loop below it would split that total span size between left and right span in case of rules that produce discontinuous constituents. these top loops are needed only to ensure that constituents are built in a bottom-up topological order. further loops are used only to compute all other needed indices for each rule. the space in this paper is not sufficient to present the implementation for all 14 rules but the example in algorithm 1 for rule #6 should be sufficient to show how the rest of the algorithm works. the number of embedded for loops for this rule clearly corresponds to its computational complexity. by designing which rules from this schema we use we can get different generative power accompanied with a different computational complexity. algorithm 1 direct cky lcfrs-2 parsing for sizespan in [1 . . . n] do . . . for a in [0 . . . n -sizespan -1] do b ← a + sizespan // processing a continuous constituent // with the span (a, b) // using rules 3, 5 and 14 . . . for sizeleft in [1 . . . sizespan -1] do sizeright ← sizespan -sizeleft . . . for a in [0 . . . n -sizespan -1] do b ← a + sizeleft for c in [b + 1 . . . n -sizeright] do d ← c + sizeright best ← -∞ // processing a discontinuous // constituent with two components // (a, b) and (c, d) // finding best solution with // discontinuous rules 2, 4, 6, // 7,8,9,10,11,12,13 . . . // rule 6: a(x, yz) → b(x,y)c(z) // @xmath0, b), @xmath1, e), @xmath2, d) for e in [c + 1 . . . d -1] do score ← chart[a, b, c, e]+ chart[e, d] if @xmath3. . . chart[a, b, c, d] ← best + labchart[a, b, c, d] if we use only rule #3 we get a cfg parser that can be run in o(n 3 ). if we use all of the rules we get lcfrs-2 parser with complexity o(n 6 ). however, there are interesting subsets of rules in between full lcfrs-2 and cfg. well-nested lcfrs-2 is one of those subsets. it includes all lcfrs-2 rules except #10, #12, #13 and #14. well-nested lcfrs-2 still has the same complexity as a full lcfrs-2 because it contains rule #11 that is o(n 6 ). if we look at its counts in the negra treebank we can see that that rule never appears. therefore we find it also interesting to try well-nested lcfrs-2 without the rare rule. we will refer to it as lcfrs-wn-nr-2. lcfrs-wn-nr-2 can be parsed in o(n 5 ). we will not use rule types #1 and #2 in any of the approaches because we handle unary rules in a different way as previously described. the parser is implemented in scala using dynet @xcite and is available on github. 4 experiments are conducted on german and english discontinuous constituency treebanks. the reported development results are on the german negra treebank. the test set results, in addition to german negra, also contain german tiger treebank @xcite and english discontinuous penn treebank (dptb) @xcite . the treebanks were preprocessed using standard practice described in @xcite by using the treetools foot_4 package. for evaluation we have used the discodop foot_5 package with the standard settings @xcite . the architecture and hyper-parameters of the neural model are chosen to be the same as in @xcite to obtain a relatively fair comparison. that is, we use a combination of character bi-lstm to embed each word. this embedding is concatenated with the lookup table embedding for each word and passed through a two-layer bi-lstm that runs over the whole sentence. in case of mlp model we score labels for each span by passing two bi-lstm vectors at borders of the spans through a two-layer mlp. in the case of the bi-affine model we compress bi-lstm vectors with a specialised mlp for left and right index, analogous to the specialisation for head and dependent vector in @xcite , and then score labels through a bi-affine layer. max-margin approach of @xcite in the context of discontinuous parsing. ## conclusion we have presented a span-based lcfrs-2 parser that outperforms all previous lcfrs parsers. it is in addition competitive with the best transition-based parsers, outperforming them in all-constituency evaluation for both german treebanks. the results from this paper also indicate that the strong generative power of the grammar formalism is correlated with the accuracy. lcfrs-2 power is a great improvement over formalisms that are lower in the complexity hierarchy, but is still inadequate for complete coverage of discontinuity. our results also show that well-nestedness significantly limiting the coverage that could be achieved even with an ideal scoring model.