Lexicalization of Probabilistic Linear Context-free Rewriting Systems (2020)

Abstract: In the field of constituent parsing, probabilistic grammar formalisms have been studied to model the syntactic structure of natural language. More recently, approaches utilizing neural models gained lots of traction in this field, as they achieved accurate results at high speed. We aim for a symbiosis between probabilistic linear context-free rewriting systems (PLCFRS) as a probabilistic grammar formalism and neural models to get the best of both worlds: the interpretability of grammars, and the speed and accuracy of neural models. To combine these two, we consider the approach of supertagging that requires lexicalized grammar formalisms. Here, we present a procedure which turns any PLCFRS G into an equivalent lexicalized PLCFRS G’. The derivation trees in G’ are then mapped to equivalent derivations in G. Our construction for G’ preserves the probability assignment and does not increase parsing complexity compared to G.

## introduction constituency parsing is a syntactical analysis in nlp that aims to enhance sentences with, usually tree-shaped, phrase structures (for an example cf. the left of fig. 1 ). formalisms such as context-free grammars (cfg) are used in this setting because they are conceptually simple, interpretable, and parsing is tractable (cubic in sentence length). discontinuous constituents span non-contiguous sets of positions in a sentence. the resulting phrase structures do not take the shape of a tree anymore, as they contain crossing branches (cf. the left of fig. 1 ), and cannot be modeled by cfg. as a countermeasure, many corpora (e.g., the penn treebank (ptb)) denote these phrase structures as trees nevertheless and introduce designated notations for discontinuity, which is then often ignored in parsing. however, discontinuity occurs in about 20 % of the sentences in the ptb, and parsing discontinuous constituents can improve accuracy @xcite . for this, so-called "mildly context-sensitive" grammar formalisms have been investigated, e.g., tree-adjoining grammars @xcite and linear context-free rewriting systems (lcfrs; @xcite . their increased expressiveness comes at the cost of a higher parsing complexity: given a sentence of length n, parsing is in o(n 6 ) for tag and o(n 3•fanout (g) ) for an lcfrs g. the fanout is grammar-specific and reflects the degree of discontinuity in the rules of g. the expressiveness of tag equals that of lcfrs with fanout 2. an lcfrs derivation of a discontinuous phrase is shown in the right of fig. 1 . supertagging has been used for more efficient parsing with lexical tag @xcite . a tag is lexical if each rule contains one word. a supertagger selects for each position of the input sentence a subset of the rules of the tag; these are the so-called supertags. parsing is then performed with the much smaller grammar of supertags. recently, the performance of supertagging has been improved by using neural classifiers for the selection of supertags @xcite . the goal of our research is to use supertagging for parsing with lcfrs, because they are more expressive than tag. in this paper, we lay the theoretical foundations for a supertagging-based lcfrs parser. as lcfrs obtained from corpora such as the ptb are usually not lexical, we employ a lexicalization procedure. it can be seen as an instance of the technique for lexicalization of multiple context-free tree grammars @xcite . however, our approach is more concise and does not increase the fanout of the grammar (thus preserving parsing vp vbz is vp vbn scheduled np np dt a nn hearing pp in on np dt the nn issue np nn today np 2 figure 1 : left: a discontinuous phrase structure tree of the sentence a hearing is scheduled on the issue today. right: an lcfrs derivation of the discontinuous noun phrase a hearing on the issue. ## preliminaries the set of non-negative (resp. positive) integers is denoted by n (resp. n + ). we abbreviate {1, ..., n} by [n] for each @xmath0. let a be a set; the set of (finite) strings over a is denoted by a * . an alphabet is a finite and non-empty set. let s be some set whose elements we call sorts. an s -sorted set is a tuple (a, sort) where a is a set and sort: @xmath1. usually, we identify (a, sort) with a, and denote sort by sort a and sort -1 (s) by a s for each @xmath2. the usual notation for sets (∈, ⊆, ∪, . . .) is used with sorted sets in the intuitive manner. now let a be an (s * × s )-sorted set. the set of trees over a is the s -sorted set t a where lcfrs. linear context-free rewriting systems extend the rule-based string rewriting mechanism of cfg to string tuples; we describe the gener-ation process by compositions. let @xmath3, . . . , s k , @xmath4; a σ-composition is a tuple (u 1 , . . . , u s ) where each u 1 , . . . , u s is a non-empty string over σ and variables of the form x j i where @xmath5. each of these variables must occur exactly once in u 1 • • • u s and they are ordered such that x 1 i occurs before x 1 i+1 and x j i occurs before x j+1 i for each @xmath6. we denote the set of σ-compositions by c σ (s 1 •••s k ,s) ; we drop the superscript in the case σ = ∅ (then c (s 1 •••s k ,s) is finite); we drop the subscript if we admit any configuration of k, s 1 , . . . , s k and s. we associate with each composition (u 1 , . . . , u s ) ∈ c σ (s 1 •••s k ,s) a function from k string tuples, where the i-th tuple is of length s i , to a string tuple of length s. this function is denoted by (u 1 , . . . , u s ) . intuitively, it replaces each variable of the form x j i in u 1 , . . . , u s by the j-th component of the i-th argument. an lcfrs is a tuple @xmath7, σ, s , r) where • n is a finite n + -sorted set (non-terminals), • σ is an alphabet (terminals), • @xmath8, and • r is a finite (n * × n)-sorted set (rules). each rule is of the form @xmath9, . . . , b k ), where @xmath10, a, b 1 , . . . , b @xmath11, and )) . the sort of the rule is (b 1 • • • b k , a); we call a the left-hand side (lhs), b 1 , . . . , b k the right-hand side (rhs) and c the rule's composition. we drop the parentheses around the rhs if @xmath12. we call rules of the form • @xmath13, • @xmath14, and • @xmath15, ..., b k ) where @xmath16, and denote the set of these rules in r by r (t) , r (m) and r (b) , respectively. a rule is called lexical, if its composition contains at least one terminal. ## lexicalizing lcfrs for the remainder, we assume (without loss of generality; cf. @xcite a plcfrs (g, µ) where @xmath17, σ, s , r) is terminal-and initialseparated, i.e. each rule is either of the form @xmath18, . . . , b k ) where @xmath19.e. c contains no terminal symbols) and none of b 1 , . . . , b k is s . starting with (g, µ), we incrementally construct a lexical plcfrs in three steps: the first two steps are direct instances of the lexicalization for multiple context-free tree grammars as introduced by @xcite . ## unlexicalizing derivations the ultimate goal of parsing is to obtain derivations of the original grammar (g, µ), which are quite different from the derivations of the transformed grammar ((n pt , σ, s , r pt ), µ pt ). therefore we seek a transformation from t r pt to t r . @xcite have introduced deterministic linear and non-deleting tt r from t r pt to t r ft , from t r ft to t r dc , and from t r dc to t r ; they were used to show ldtt r -equivalence of the corresponding grammars. the composition of these transducers yields a transduction from t r pt to t r . however, for recovering derivations, these transducers are not adequate, as a derivation in t r ft or t r dc may have multiple possible originals in t r dc or t r , respectively. we want to be able to obtain all of these derivations, as this may be beneficial for np 2 → (x 1 1 , x 1 2 ) (np 1 , pp) np 1 → (a hearing) @xmath20, on x 1 2 ) (np 1 , (pp, on)) np 1 → (a hearing) (pp, on) → (the x 1 1 ) ((np 1 , the)) (np 1 , the) → (issue) figure 3: propagation of terminals. left: derivation of a (partly lexicalized) lcfrs before the application of step 3. right: derivation after step 3, where the is propagated from the leaf to the pp rule and on is propagated from there to the np 2 rule, thus lexicalizing it. we define the linear and non-deleting tt t← - @xmath21, r ft , r dc , * , δ), where δ is the smallest set such that, for each rule @xmath22, ..., b k ) ∈ r dc \r (t) dc and ρ ∈ f(r), the transition * r[ρ](x 1 , ..., and δ is the smallest set that contains, m) and @xmath23, the transition ## conclusion based on @xcite , we have introduced a procedure which constructs for every plcfrs g an equivalent lexicalized plcfrs g . moreover, we have described how to recover from each derivation of g all corresponding derivations of g. in future work, we will use our approach to implement a supertagging-based lcfrs parser. the 11th international conference on parsing technologies, iwpt '09, pages 1-12, stroudsburg, pa, usa. association for computational linguistics. hiroyuki seki, takashi matsumura, mamoru fujii, and tadao kasami. 1991. on multiple context-free grammars. 88(2):191-229. ashish vaswani, yonatan bisk, kenji sagae, and ryan musa. 2016. supertagging with lstms. in proceedings of the 2016 conference of the north american chapter of the association for computational linguistics: human language technologies, pages 232-237. krishnamurti vijay-shanker, david jeremy weir, and aravind k. joshi. 1987. characterizing structural descriptions produced by various grammatical formalisms. in proceedings of the 25th annual meeting on association for computational linguistics, acl '87, pages 104-111, stroudsburg, pa, usa. association for computational linguistics.