We develop a general framework for weighted parsing which is built on top of grammarbased language models and employs flexible weight algebras. It generalizes previous work in that area (semiring parsing, weighted deductive parsing) and also covers applications outside the classical scope of parsing, e.g., algebraic dynamic programming. We show an algorithm which terminates and is correct for a large class of weighted grammar-based language models.
Introduction The weighted parsing problem takes as input a weighted language model (LM) and a syntactic object a. For instance, the LM can be given by some grammar G, e.g., a context-free grammar (CFG) or a linear context-free rewriting system (LCFRS), and a can be some string. Each rule r of G has a value (weight of r); the weight is an element of some weight algebra K. That algebra has a binary commutative and associative operation ⊕ on its carrier set, which is used to handle ambiguity of G. As output we expect an element k ∈ K which is the ⊕-accumulation of the weight wt(d) K of each abstract syntax tree (AST) d of a in G, i.e., k = ⊕ d∈AST(G,a) wt(d) K where wt(d) K is computed by other operations of the algebra K (using the weights of the occurring rules) and ⊕ is an extension of ⊕ to infinitely many summands (infinitary sum operation). For instance, if K = [0, 1] is the set of probabilities, ⊕ = max, ⊕ = sup, and wt(d) K is the product of all weights of occurrences of rules in d, then k is the maximal probability of an AST of a in G. Goodman (1999) developed a formal framework for weighted parsing, called semiring parsing. As weight algebras he used complete semirings (K, ⊕, ⊗, 0, 1, ⊕ ) (Eilenberg, 1974) , i.e., ⊕ is the infinitary sum operation extending ⊕. The binary operation ⊗ is used to compute wt(d) K . By appropriate choices of the complete semiring, he formalized the following problems as weighted parsing problems for a CFG G and a: the calculation of recognition, string probabilities, number of derivations, derivation forests, probability of best derivation, best derivation, and best n derivations. The algorithm which he proposed for solving the weighted parsing problem is a pipeline with two phases. In the first phase, the CFG G, a deduction system I (Shieber et al., 1995) , and the syntactic object a (i.e., a string) are combined into a single CFG G (using a construction idea of Bar-Hillel et al., 1961) . In the second phase, the value k (from above) is calculated, if G is acyclic. 1 Nederhof (2003) developed a similar framework, called weighted deductive parsing. As weight algebras he employed algebras of the form (K, min, 0, Ω, min ) where K is a totally ordered set, min = inf (infimum), inf(K) ∈ K, and Ω is a set of superior functions; a superior function f is an operation on K which is monotone nondecreasing in each argument and f (k 1 , . . . , k m ) ≥ max(k 1 , . . . , k m ) holds. The algorithm which he proposed for solving the weighted parsing problem is again a pipeline with two phases, where the first phase is the same as in the framework of Goodman (1999) and the resulting CFG G is denoted by c(G, a). In the second phase, he employed the algorithm of Knuth (1977) , which generalizes the shortest distance algorithm of Dijkstra (1959) from graphs to hypergraphs and also works if G is cyclic. If the CFG G is non-branching, i.e., a linear grammar (Khabbaz, 1974, Def. 1) , then in the second phase a graph algorithm can be used as an alternative to Knuth's algorithm; e.g., the single source shortest distance algorithm of Mohri (2002) if the weight algebra K is a complete semiring which is closed for G . In this paper, we generalize the two-phase pipeline approach of Goodman (1999) and Nederhof (2003) as follows. We specify the LM by using the general approach of initial algebra semantics (Goguen et al., 1977) . For this, we employ weighted regular tree grammars (wRTG) and evaluate the generated trees (by the unique homomorphism) in some language algebra L, which provides the set of syntactic objects as carrier set. This approach is very flexible and covers LMs for strings (CFG, LCFRS), but also trees and graphs (Drewes et al., 2016) . Our second generalization concerns the weight algebra. We consider complete multioperator monoids (Kuich, 1999) which are algebras of the form (K, ⊕, 0, Ω, ⊕ ), where Ω is a set of operations on K and ⊕ is the infinitary sum operation which extends ⊕. We call the combination of such an LM and weight algebra weighted RTG-based language model (wRTG-LM). These combinations are very general and even exceed the scope of parsing; e.g., each algebraic dynamic programming problem (Giegerich et al., 2004) , like minimum edit distance or matrix chain multiplication, can be formalized within this framework. For solving the weighted parsing problem, given a wRTG-LM and a syntactic object a, we formalize the first phase as canonical weighted deduction system, which uses a CYK-like deduction system. For the second phase (value computation algorithm), we propose a generalization of Mohri's approach to hypergraphs, in the spirit of Knuth's generalization of Dijkstra's algorithm. We prove (in sketches) that our weighted parsing algorithm is terminating and solves the weighted parsing problem for every closed wRTG-LM with a finitely decomposing language algebra. This covers the approaches of Goodman (1999) and Nederhof (2003) ; our value computation algorithm subsumes the algorithms of Knuth (1977) and Mohri (2002) . Due to space restrictions, we cannot show our detailed proofs of the theorems in this paper. Preliminaries Mathematical notions. We let N = {0, 1, 2, . . .} be the set of natural numbers and [m] = {1, . . . , m} for each m ∈ N. An alphabet is a finite, nonempty set. The powerset of a set A is denoted by P(A). Let f : A → B be a mapping; we extend it to the mapping f : P(A) → P(B) by letting f (U) = { f (a) | a ∈ U}, and we denote f also by f . A family over A is a mapping f : I → A, where I is a countable set (index set). As usual, we represent each family f over A by ( f (i) | i ∈ I) and abbreviate f (i) by f i . Ranked sets, trees, and regular tree grammars. A ranked set is a set Γ such that each γ ∈ Γ is associated with a natural number rk Γ (γ), its rank. The set of all elements of Γ with rank m ∈ N is denoted by Γ m . A ranked set Σ with Σ ⊆ Γ is rank preserving (in Γ) if Σ m ⊆ Γ m for each m ∈ N. Let H be a set. The set of trees over Γ and H is defined in the usual way, where elements of H may only occur at leaves. We denote this set by T Γ (H) and abbreviate T Γ (∅) by T Γ . Let t ∈ T Γ (H). A path in t is a sequence of positions of d from the root to a leaf. Let p be a path in t. The sequence of labels of d along p is denoted by seq (d, p) . A ranked alphabet is a ranked set which is an alphabet. A regular tree grammar (RTG) (Brainerd, 1969 ) is a tuple G = (N, Σ, A 0 , R) where N is an alphabet (nonterminals), Σ is a ranked alphabet (terminals) with N ∩ Σ = ∅, A 0 ∈ N (initial nonterminal), and R is finite set of rules where each rule has the form A → σ(A 1 , . . . , A m ) with m ∈ N, A, A 1 , . . . , A m ∈ N, and σ ∈ Σ m . Each RTG G can be considered as a context-free grammar G (with terminal alphabet Σ ∪ {(, ), comma}), which generates well-formed expressions. Thus the derivation relation ⇒ G is the usual derivation relation of G . The tree language generated by G is the set L(G) = {t ∈ T Σ | A 0 ⇒ * G t}. By viewing each rule A → σ(A 1 , . . . , A m ) of R as symbol with rank m, we can define the set AST(G) of abstract syntax trees of G to be the set of all d ∈ T R such that for each position w of d the following holds: if d has label A → σ(A 1 , . . . , A m ) at w, then the i-th successor of w (i ∈ [m]) is labeled by a rule with left-hand side A i (cf. Fig. 2 ). We define the mapping π Σ : AST(G) → T Σ such that π Σ (d) is obtained from d by replacing each label A → σ(A 1 , . . . , A m ) by σ (cf. Fig. 2 ). Hence π Σ (AST(G)) = L(G). Γ-algebras. Let Γ be a ranked set. A Γ-algebra (or: algebra) is a pair (A, φ) where A is a set (carrier set) and φ is a mapping (interpretation map-ping) which maps each γ ∈ Γ m (m ∈ N) to an mary operation φ(γ) over A, i.e., φ(γ): A m → A. In the sequel, we will sometimes identify φ(γ) and γ (as it is usual in algebra). The Γ-term algebra is the Γ-algebra (T Γ , φ Γ ) where φ Γ (γ)(t 1 , . . . , t m ) = γ(t 1 , . . . , t m ) for every m ∈ N, γ ∈ Γ m , and t 1 , . . . , t m ∈ T Γ . For each Γ-algebra (A, φ) there is exactly one homomorphism, denoted by (.) A , from the Γ-term algebra to (A, φ) (Wechler, 1992) . We write its application to an argument t ∈ T Γ as t A . Intuitively, (.) A evaluates a tree t in (A, φ), in the same way as arithmetic expressions (e.g., 3 + 2 · (4 + 5)) are evaluated in the {+, ·}-algebra (Z, +, ·) to some values (here: 21). Often we abbreviate an algebra (A, φ) by its carrier set A. For every a ∈ A we let factors (a) = {b ∈ A | b < factor * a}, where for every a, b ∈ A, b < factor a if there is a γ ∈ Γ such that b occurs in some tuple (b 1 , . . . , b m ) with φ(γ)(b 1 , . . . , b m ) = a. We call (A, φ) finitely de- composable if factors(a) is finite for every a ∈ A. Monoids. A monoid is an algebra (K, ⊕, 0) such that ⊕ is a binary, associative operation on K and 0 ⊕ k = k = k ⊕ 0 for each k ∈ K. In the rest of this paper, each occurrence of k, k 1 , k 2 , . . . is assumed to be universally quantified over K if not specified otherwise. The monoid is commutative if ⊕ is commutative; it is extremal (Mahr, 1984) if k 1 ⊕k 2 ∈ {k 1 , k 2 }; it is idempotent if k⊕k = k. It is naturally ordered if the binary relation ⊆ K × K (defined by k 1 k 2 if there is a k ∈ K such that k 1 ⊕k = k 2 ) is anti-symmetric (in which case it is a partial order, since reflexivity and transitivity hold by definition). It is complete if for each countable set I, there is an operation ⊕ I which maps each family (k i | i ∈ I) to an element of K, coincides with ⊕ when I is finite, and otherwise satisfies axioms which guarantee commutativity and associativity (Eilenberg, 1974, p. 124) . We abbreviate ⊕ (Karner, 1992) if for every k ∈ K and family (k i | i ∈ N) of elements of K the following holds: if there is an n 0 ∈ N such that for every n ∈ N with n ≥ n 0 , ⊕ i∈N:i≤n k i = k, then ⊕ i∈N k i = k. A complete monoid is completely idempotent if for every k ∈ K and countable set I it holds that ⊕ i∈I k = k. By easy calculations we obtain the following implications: (1) if K is extremal, then it is idempotent, (2) if K is completely idempotent, then it is d-complete, and (3) if K is d-complete, then it is naturally ordered. I (k i | i ∈ I) by ⊕ i∈I k i . A complete monoid is d-complete Multioperator monoids. A multioperator monoid (M-monoid) (Kuich, 1999) is an algebra (K, ⊕, 0, Ω) such that (K, ⊕, 0) is a commutative monoid and Ω is a set of operations on K which contains at least the unary identity id: K → K. We view Ω as a ranked set, and hence (K, φ) as an Ω-algebra where φ(ω) = ω for each ω ∈ Ω. Thus t K ∈ K is the evaluation of t ∈ T Ω in the algebra (K, φ). An M-monoid inherits the properties of its monoid (e.g., being complete). We denote a complete M-monoid by (K, ⊕, 0, Ω, ⊕ ). An M-monoid is distributive if for each m-ary ω ∈ Ω and every i ∈ [m], ω(k 1,i−1 , k i ⊕ k, k i+1,m ) = ω(k 1,i−1 , k i , k i+1,m ) ⊕ ω(k 1,i−1 , k, k i+1,m ) where k 1,i−1 and k i+1,m abbreviate k 1 , . . . , k i−1 and k i+1 , . . . , k m , respectively. If K is complete, then we additionally require that the above equation also holds for each countable set of summands. Next we show examples of M-monoids. • Each semiring (K, ⊕, ⊗, 0, 1) can be considered as the M-monoid (K, ⊕, 0, Ω ⊗ ) (Fülöp et al., 2009) where Knuth (1977) uses complete, distributive Mmonoids of the form (K, min, 0, Ω, min ) where K is a totally ordered set, inf(K) ∈ K, and the operations in Ω are superior functions. We will call such M-monoids superior M-monoids. We note that each superior M-monoid is dcomplete. Ω ⊗ = {mul (m) k | m ∈ N, k ∈ K} and for every m ∈ N we define mul (m) k (k 1 , . . . , k m ) = k ⊗ k 1 ⊗ · · · ⊗ k m . Note that 1 = mul (0) 1 (). • 3 Weighted RTG-based language models and the weighted parsing problem As framework for the definition of our language models we use the initial algebra approach (Goguen et al., 1977) . An RTG-based language model (RTG-LM) is a tuple (G, (L, φ)) where • G = (N, Σ, A 0 , R) is an RTG and • (L, φ) is a Γ-algebra (language algebra) such that Σ ⊆ Γ is rank preserving; the elements of L are called syntactic objects. The language generated by (G, (L, φ)) is the set from evaluating trees of L(G) in the language algebra L. For each a ∈ L, we let L(G) L = {t L | t ∈ L(G)} ⊆ L , i.e., AST(G, a) = {d ∈ AST(G) | π Σ (d) L = a} . Example 1. We consider the Γ-algebra CFG ∆ = (∆ * , φ) as language algebra where ∆ = {fruit, flies, like, bananas}, Γ = m∈N Γ m , and Γ m = { u 0 x 1 u 1 · · · x m u m | u i ∈ ∆ * }. We define φ( u 0 x 1 u 1 · · · x m u m )(a 1 , . . . , a m ) = u 0 a 1 u 1 · · · a m u m for every a 1 , . . . , a m ∈ ∆ * . We consider the RTG G = (N, Σ, S, R) with N = {S, NP, VP, PP, NN, NNS, VBZ, VBP, IN} and Σ = { δ | δ ∈ ∆} ∪ { x 1 , x 1 x 2 } ⊆ Γ, and R contains the rules shown in Fig. 1 (ignoring the numbers above the arrows for the time being). The tree in the middle of the upper row of Fig. 2 is an abstract syntax tree d ∈ AST(G). It expresses that certain insects (fruit flies) like something (bananas). We obtain π Σ (d) by dropping the non-highlighted parts of d (left of upper row). The application of the homomorphism (.) CFG ∆ : T Σ → CFG ∆ to π Σ (d) yields the string a = fruit flies like bananas. We note that there is another abstract syntax tree d ∈ AST(G), viz., d = r 1 (r 2 (r 8 ), r 5 (r 11 , r 7 (r 13 , r 4 (r 10 )))) such that π Σ (d ) CFG ∆ = a. It expresses how fruit performs a certain activity (to fly like bananas). Hence this RTG-LM is ambiguous. It should be clear from Ex. 1 that each contextfree grammar with terminal alphabet ∆ can be represented as an RTG-LM (G, CFG ∆ ), and vice versa, each RTG-LM (G, CFG ∆ ) represents a CFG. In the same way, one can characterize LCFRS and tree adjoining grammars by (1) superposing sorts to the set N of nonterminals of the RTG (in order to represent fanout and the characteristic "substitution tree / adjoining tree" of arguments, respectively), and (2) by defining ap-propriate Γ-algebras LCFRS ∆ (Kallmeyer, 2010, Def. 6.2+6 .3) and TAG ∆ (Büchse et al., 2012; Koller and Kuhlmann, 2012) , respectively. The language algebras CFG ∆ , LCFRS ∆ , and TAG ∆ are finitely decomposable. A weighted RTG-based language model (wRTG-LM) is a tuple (G, (L, φ)), (K, ⊕, 0, Ω, ⊕ ), wt , where • (G, (L, φ)) is an RTG-LM, • (K, ⊕, 0, Ω, ⊕ ) is a complete M-monoid (weight algebra), and • wt maps each rule of G with rank m to an mary operation in Ω. We lift wt to the mapping wt : T R → T Ω and denote wt also by wt. Definition 2. The weighted parsing problem is the following problem: given a wRTG-LM (G, (L, φ)), (K, ⊕, 0, Ω, ⊕ ), wt and an a ∈ L, compute the value parse(a) ∈ K where parse(a) = ⊕ d∈AST(G,a) wt(d) K . Example 3. (Ex. 1 cont.) The best derivation problem of (Goodman, 1999) consists of computing, given a syntactic object a and a grammar, the abstract syntax trees of a with maximal probability (and this probability). Let R ∞ be a ranked set such that (R ∞ ) m is infinite for each m ∈ N. In analogy to Goodman, we define the best derivation Mmonoid to be the d-complete M-monoid BD = V, max BD , (0, ∅), Ω BD , max BD , where V = [0, 1] × P(T R ∞ ) and [0, 1] is the interval of real numbers from 0 to 1 and • for every (p 1 , D 1 ), (p 2 , D 2 ) ∈ V, the value max BD ((p 1 , D 1 ), (p 2 , D 2 )) is (p i , D i ) if p i > p j for i, j ∈ {1, 2}, and (p 1 , D 1 ∪ D 2 ) if p 1 = p 2 , • Ω BD = {tc p,r | p ∈ [0, 1] and r ∈ R ∞ }, where for each p ∈ [0, 1] and r ∈ R ∞ of rank m, we define tc p,r : V m → V (tc abbreviates top concatenation) such that for every (p 1 , D 1 ), . . . , (p m , D m ) ∈ V tc p,r (p 1 , D 1 ), . . . , (p m , D m ) = (p , D ) where p = p · p 1 · . . . · p m and D = {r(d 1 , . . . , d m ) | d i ∈ D i , 1 ≤ i ≤ m}, and • for every family ((p i , D i ) | i ∈ I) over V, we define max BD i∈I (p i , D i ) = (p, D), where p = sup{p i | i ∈ I} and D = i∈I:p i =p D i . Since BD is completely idempotent, it is also dcomplete. x 1 x 2 x 1 x 2 fruit flies x 1 x 2 like x 1 bananas S → NP → NN → NNS → VP → VBP → NP → NNS → (NP, VP) (NN, NNS) (VBP, NP) (NNS) d ∈ AST(G) x 1 x 2 x 1 x 2 fruit flies x 1 x 2 like x 1 bananas t ∈ T Σ tc 1.0,r1 tc 0.5,r3 tc 1.0,r8 tc 0.4,r9 tc 0.6,r6 tc 1.0,r12 tc 0.3,r4 tc 0.6,r10 in T Ω 0.0216, {r 1 (r 3 (r 8 , r 9 ), r 6 (r 12 , r 4 (r 10 )))} 0.0144, {r 1 (r 2 (r 8 ), r 5 (r 11 , r 7 (r 13 , r 4 (r 10 ))))} max BD a = fruit flies like bananas Figure 2 : Illustration of the weighted parsing problem for the wRTG-LM (G, CFG ∆ ), BD, wt and the syntactic object a = fruit flies like bananas of ∆ * , see Ex. 3. Now we consider the finite set R of rules of the RTG G given in Ex. 1. We can assume that R ⊆ R ∞ is rank preserving. We define the mapping wt: R → Ω BD by wt(r i ) = tc p i ,r i where p i is shown in Fig. 1 above the arrow of r i . For each d ∈ AST(G, a), the second component of wt(d) BD has exactly one element. Recall d from Ex. 1, a second AST which is evaluated to a. We obtain wt(d ) BD = (0.0144, {r 1 (r 2 (r 8 ), r 5 (r 11 , r 7 (r 13 , r 4 (r 10 ))))}). Thus wt(d ) ∈ T Ω d ∈ AST(G) π Σ (d ) ∈ T Σ π Σ wt (.) CFG ∆ (.) BD (.) BD wt π Σ (.) CFG ∆ parse max BD wt(d) BD , wt(d ) BD = wt(d) BD . As one might expect, it is more likely that a refers to the preferences (to like bananas) of certain insects (fruit flies). Fig. 2 illustrates the parsing problem for the wRTG-LM ((G, CFG ∆ ), BD, wt) and a = fruit flies like bananas. In summary, each wRTG-LM consists of two components: a syntax component and a weight component. The syntax component (cf. the left of Fig. 2 ) contains the language algebra (L, φ). This is a Γ-algebra whose carrier set is the set of syntactic objects. The mapping π Σ maps each abstract syntax tree to a tree in the Σ-term algebra T Σ , which is then evaluated to a syntactic object by the unique homomorphism (.) L (recall that Σ ⊆ Γ). The weight component (cf. the right of Fig. 2 ) contains a complete M-monoid (K, ⊕, 0, Ω, ⊕ ) whose carrier set is the set of weights. The mapping wt maps each abstract syntax tree to a tree in the Ω-term algebra T Ω , which is then evaluated to a weight in K by the unique homomorphism (.) K . Weights in K are accumulated using ⊕. The weighted parsing problem takes as input a wRTG-LM and a syntactic object a, and it computes the ⊕-accumulation of the weights of each AST of a. A → del a (A) φ(del a )(w) = aw del a (n) = n + 1 A → ins a (A) φ(ins a )(w) = wa ins a (n) = n + 1 A → rep a,b (A) φ(rep a,b )(w) = awb rep a,b (n) = n A → nil φ(nil)() = $ nil() = 0 Example 4. Giegerich et al. (2004) formalized dynamic programming (Bellman, 1952 (Bellman, , 1954 in an algebraic setting, called algebraic dynamic programming (ADP). We claim that each ADP problem is a weighted parsing problem. To support this statement, we consider the computation of the minimum edit distance (med) between two words over some alphabet ∆ by deletion, insertion, and replacement, and we "simulate" its ADPspecification as wRTG-LM ((G, (L, φ)), K, wt). The rules of the RTG G and the interpretation φ are shown in the first and second columns of Fig. 3 , respectively. Thus, for each tree t ∈ L(G), t L = u$v for some u, v ∈ ∆ * . We choose the complete, distributive M-monoid (K, ⊕, ∅, Ω, ⊕ ) with K = {h(F) | F ∈ P(N)} for the singlevalued objective function h: P(N) → P(N) with h(F) = {min(F)}. We let F 1 ⊕ F 2 = h(F 1 ∪ F 2 ) for every F 1 , F 2 ∈ K, and ⊕ i∈N F i = {inf( i∈N F i )}. The set Ω is shown in the third column of Fig. 3 . Note that h satisfies Bellman's principle of optimality: h(ω(F)) = h(ω(h(F))) for each unary ω ∈ Ω and F ∈ K. Then med (u, v) = parse(u$v −1 ) for every u, v ∈ ∆ * , where v −1 is the reversal of v. This construction can be generalized to a procedure which turns every specification of an ADP problem into a weighted parsing problem. Due to space restrictions, we cannot present this procedure in its entirety. The weighted parsing algorithm The weighted parsing algorithm is supposed to solve the weighted parsing problem. As input, it takes a wRTG-LM G and a syntactic object a. Its output is intended to be parse(a). The algorithm is a pipeline with two phases (cf. Fig. 4 ) and follows the modular approach of Nederhof (2003) . First, a canonical weighted deduction system computes from G and a a new wRTG-LM G with the same weight structure as G, but a different RTG and the language algebra CFG ∅ . Second, G is the input to the value computation algorithm (Alg. 1), which computes the value V(A 0 ); this is supposed to be ⊕ d∈AST(G ) wt(d) K = parse(a). Weighted deduction systems. Parsing of some string w with some grammar G can be formalized as a deduction system D (Shieber et al., 1995) . D consists of a set of inference rules I 1 ... I m I {c 1 , . . . , c p } where m ∈ N, I, I 1 , . . . , I m are items, and c 1 , . . . , c p are side conditions. Each item represents a Boolean-valued property (of some combination of nonterminals of G and/or substrings of a = w). The meaning of an inference rule is: given that I 1 , . . . , I m and c 1 , . . . , c p are true, I is true as well. Nederhof (2003) pointed out that "a deduction system having a grammar G [...] and input string w in the side conditions can be seen as a construction c of a context-free grammar c(G, w) [...]"; also, he extended D and c(G, a) with weights. Inspired by this, we define the canonical weighted deduction system as a mapping cwds which takes two arguments: (a) a wRTG-LM G = (G, L), K, wt such that the language algebra (L, φ) is finitely decomposable and (b) a syntactic object a ∈ L. Let G = (N, Σ, A 0 , R) . Then we define cwds G, a = (G , CFG ∅ ), K, wt , where G = (N , Σ , A 0 , R ) and a) , and • for each σ ∈ Σ, the rule r = (A 0 , a) → (A 0 , σ, a) is in R and wt (r ) = id; for each r = A → σ(A 1 , . . . , A m ) in R and a 0 , a 1 , . . . , a m ∈ factors(a) with φ(σ)(a 1 , . . . , a m ) = a 0 and every • N = {(A 0 , a)} ∪ N × Σ × factors(a) ; N is finite, because L is finitely decomposable, • Σ = { x 1 . . . x m | a rule with rank m is in R}, • A 0 = (A 0 , rule A i → σ i (. . . ) (i ∈ [m]) in R, the rule r (A, σ, a 0 ) → x 1 . . . x m (A 1 , σ 1 , a 1 ), . . . , (A m , σ m , a m ) is in R and we let wt (r ) = wt(r). Note that cwds implements a CYK-like deduction system. The elements of N have a very general form. Depending on L, they can be understood as, e.g., spans of strings, occurrences of patterns in trees, or occurrences of subgraphs in graphs. We note that for every d ∈ AST(G ) it holds that π Σ (d) CFG ∅ = ε, i.e., each abstract syntax tree is evaluated to the empty string. Moreover, cwds is weight-preserving in the following sense: (1) there is a bijective mapping ψ from the set AST(G, a) to AST(G ) and (2) for every d ∈ AST(G, a) we have that wt(d) K = wt (ψ(d)) K . Value computation algorithm. This is Alg. 1. Its input is a wRTG-LM G with language algebra CFG ∅ . It maintains a mapping V, which assigns a weight to each nonterminal, and a Boolean variable changed. The output is the value V(A 0 ). The algorithm starts by assigning the weight 0 to each nonterminal (lines 1-2). Then, in a repeat-until loop (lines 3-12), the weight of each nonterminal is recomputed in every iteration of that loop as follows (where x 1,m abbreviates x 1 , . . . , x m ): V(A) = r∈R : r=(A→ x 1,m (A 1 ,...,A m )) wt (r) V(A 1 ), . . . , V(A m ) . Algorithm 1 Value computation algorithm Input: (G , CFG ∅ ), (K, ⊕, 0, Ω, ⊕ ), wt which is a wRTG-LM with G = (N , Σ , A 0 , R ) Variables: V: N → K, V ∈ K, changed ∈ B Output: V(A 0 ) 1: for each A ∈ N do 2: V(A) ← 0 3: repeat 4: changed ← false 5: for each A ∈ N do 6: V ← 0 7: for each r = (A → x 1,m (A 1 , . . . , A m )) in R do 8: V ← V ⊕ wt (r) V(A 1 ), . . . , V(A m ) 9: if V(A) V then 10: changed ← true 11: V(A) ← V 12: until changed = false The algorithm terminates after the first iteration in which no nonterminal has changed its weight. We note that in practice, a complete computation of cwds(G, a) prior to the execution of the value computation algorithm (Alg. 1) is impossible. Similar to Nederhof (2003) , we execute the value computation algorithm on an incomplete input which is extended on demand (lazy evaluation). More precisely, G is initialized so that it only contains the rules of rank 0 (and the nonterminals in their left-hand sides). Then, each time a value different from 0 is first assigned to a nonterminal A in line 11, we compute the following set of rules: each rule whose right-hand side only contains A and other nonterminals for which this computation has already been done is in that set. These new rules (and the nonterminals in their left-hand sides) are added to G . Termination and correctness We are interested in two formal properties of the value computation algorithm (Alg. 1) and of the weighted parsing algorithm (Fig. 4) : termination and correctness. The value computation algorithm computes the weights of the ASTs bottom-up and reuses the results of common subtrees (as in dynamic programming); this requires distributivity of the weight algebra. Moreover, solving the weighted parsing problem by a terminating algorithm involves the following difficulty: there may be infinitely many ASTs (due to cycles) which are evaluated to the same syntactic object a. Thus parse(a) is an infinite sum, which in general cannot be computed in finite time. Hence, a terminating algorithm can only solve the weighted parsing problem if the infinite sum is equal to the sum over some finite subset of the infinite sum's index set. We have organized this section as follows. In Subsection 5.1 we define the class of closed wRTG-LMs (similar to Mohri, 2002) and prove that the value computation algorithm (Alg. 1) is terminating and correct for closed wRTG-LMs as input. We say that the value computation algorithm is correct if after termination V(A 0 ) = ⊕ d∈AST(G ) wt (d) K . In Subsection 5.2 we prove that the weighted parsing algorithm (Fig. 4) is terminating and correct for two classes of inputs. We say that the weighted parsing algorithm is correct if it computes parse(a). Properties of the value computation algorithm Since each wRTG-LM has a finite set of rules, an infinite set of ASTs is only possible if the ASTs are cyclic in the following sense. Recall that R is the set of rules of the input G to the value computation algorithm (Alg. 1). Let ρ ∈ (R ) * . We call ρ cyclic if |ρ| ≥ 2, ρ 1 = ρ |ρ| , and for every i, j ∈ N, if 1 ≤ i < j < |ρ|, then ρ i ρ j . From now on, let ρ ∈ (R ) * be cyclic, d ∈ T R , and c ∈ N. A path p in d is (c, ρ)-cyclic if ρ occurs exactly c times in seq (d, p) . We define the set cutout(d, ρ) which contains every tree obtained from d by cutting out at least one occurrence of ρ. We illustrate cutout by an example in Fig. 5 . Definition 5. Let c ∈ N. A wRTG-LM G = (G , CFG ∅ ), K, wt is c-closed if K is distributive and d-complete, and for each d ∈ T R and cyclic string ρ ∈ (R ) * the following holds: if there is a (c, ρ)-cyclic path in d, then R ∩AST(G ) for every c ∈ N. Theorem 6. For every c ∈ N and c-closed wRTG-LM (G , CFG ∅ ), K, wt the following holds: wt (d) K ⊕ d ∈cutout(d,ρ) wt (d ) K = d ∈cutout(d,ρ) wt (d ) K . G is closed if it is c-closed for some c ∈ N. ⊕ d∈AST(G ) wt (d) K = d∈AST(G ) (c) wt (d) K . Proof (sketch). As K is distributive, we can show by induction on n ∈ N that for every B ⊆ AST(G ) AST(G ) (c) with |B| = n, adding B to the index set of ⊕ does not change the sum's value. Then, as K is d-complete, the equality holds. This theorem reflects the desired property: given that our wRTG-LM is c-closed (with c ∈ N), each (possibly infinite) sum over all ASTs can be computed as a sum over the finite set AST(G ) (c) . Theorem 7. The value computation algorithm (Alg. 1) is terminating and correct for every closed wRTG-LM G with language algebra CFG ∅ . Proof (sketch). Let G be c-closed. We note that in line 8, the value in the right-hand side of ⊕ always corresponds to the sum over the weights of some trees in (T R ) A ; this is due to the fact that K is distributive. By the form of recomputation in lines 3-12, each d ∈ (T R ) A contributes to that sum at most once. Furthermore, V only differs from V(A) if a tree from the finite set T (c) R has been used to compute V , but not V(A) (this is a consequence of G being closed). Thus, changed is only set to true finitely often and the algorithm eventually terminates. Then, after termination, V(A 0 ) = d∈AST(G ) (c) wt (d) K and Theorem 6 implies correctness. Properties of the weighted parsing algorithm We discuss two classes of wRTG-LMs for which the weighted parsing algorithm (Fig. 4) is termi-nating and correct. (1) Closed wRTG-LMs with arbitrary language algebras. Each of them is a wRTG-LM (G, (L, φ)), (K, ⊕, 0, Ω, ⊕ ), wt which is c-closed for some c ∈ N, and c-closed is defined as in Def. 5. (We note that this generalization is possible because Def. 5 does not use any property of CFG ∅ .) The following particular wRTG-LMs are closed: • wRTG-LMs with acyclic RTG, where an RTG G is acyclic if AST(G) = AST(G) (0) , • wRTG-LMs with superior, d-complete Mmonoids as weight algebras, and • wRTG-LMs with weight algebra BD if no chain rule and ε-rule has probability 1.0 (as in Ex. 3). (2) Non-looping wRTG-LMs with distributive Mmonoids as weight algebras. A wRTG-LM G is non-looping if for every syntactic object a and tree d over the set of rules of G which is evaluated to a the following holds: no proper subtree of d is evaluated to a. ADP problems can be specified by non-looping wRTG-LMs, because the syntactic objects of ADP represent (sub-)problems which have to be solved. Thus, if G is looping, then the solution of a subproblem would depend on itself, which contradicts dynamic programming. In general, non-looping is not decidable, but it is for particular language algebras, e.g., CFG ∆ . Lemma 8. For every closed or nonlooping wRTG-LM G with finitely decomposable language algebra and syntactic object a, the wRTG-LM cwds(G, a) is closed. Theorem 9. The weighted parsing algorithm (Fig. 4) is terminating and correct for every closed or nonlooping wRTG-LM with finitely decomposable language algebra. Proof. The weighted parsing algorithm terminates because (a) the computation of cwds is terminating algorithm class of valid inputs class C 1 of RTG class C 2 of weight algebras (a) Knuth (1977) C 1 × C 2 RTG superior M-monoid (b) Goodman (1999) C 1 × C 2 acyclic RTG complete semiring (c) Mohri (2002) C 2 closed for C 1 monadic RTG commutative, d-complete semiring (d) Alg. 1 closed wRTG-LM RTG distributive, d-complete M-monoid = V(A 0 ) . Comparison of value computation algorithms Here we compare our value computation algorithm (Alg. 1) to the algorithm of Knuth (1977) , the second phase of Goodman (1999) , and the algorithm of Mohri (2002) . We focus on the question of applicability of the algorithms, i.e., we identify the classes of inputs for which the algorithms are terminating and correct (class of valid inputs). In order to have a basis for a fair comparison, we understand the inputs of the algorithms of Knuth (1977) , Goodman (1999) , and Mohri (2002) as particular wRTG-LMs of the form (G , CFG ∅ ), (K, ⊕, 0, Ω, ⊕ ), wt with G = (N , Σ , A 0 , R ). An algorithm is correct for such a wRTG-LM if it returns ⊕ d∈AST(G ) wt (d) K . We employ two parameters: C 1 (subset of the class of all RTGs) and C 2 (subset of the class of all weight algebras). Tab. 1 shows the classes of valid inputs parameterized with values for C 1 and C 2 . Each valid input in rows (a)-(d) is a closed wRTG-LM. Thus, if one of the value computation algorithms (a)-(c) is applicable, then our value computation algorithm (Alg. 1) is applicable too. In particular, Alg. 1 is applicable to wRTG-LMs with the best derivation M-monoid BD as weight algebra (cf. Ex. 3), which in general is the case for neither of algorithms (a)-(c). The reason for this is that BD is not superior (opposing (a)) and RTG-LMs are in general neither acyclic (opposing (b)) nor monadic (opposing (c)). The same holds for ADP problems. We cannot give a general statement about the complexity of our value computation algorithm (Alg. 1), because the operations in the weight algebra of a wRTG-LM can be undecidable. If we abstract from the costs of particular operations, then we obtain the complexity of Mohri's algorithm. This complexity depends on the number of times the value of a nonterminal changes, which in general is not polynomial in the size of the input wRTG-LM. Mohri circumvents this problem by specifying the order in which nonterminals are processed for well-known classes of inputs, e.g., acyclic graphs or superior weight algebras. We can adapt this idea by imposing such an ordering on the iteration over the nonterminals in line 5. Thus our value computation algorithm achieves the same complexity as Knuth's algorithm (if the input is restricted to superior wRTG-LMs) or the algorithm in Goodman's second phase (if the input is restricted to acyclic wRTG-LMs), respectively. We note that although our value computation algorithm (Alg. 1) has the same complexity as the other algorithms, in average it performs more computations than those. This is because in each iteration of lines 5-11, the values of all nonterminals are recomputed. This could be avoided by using a direct generalization of Mohri's algorithm to the branching case rather than Alg. 1. However, the intricacies of such a generalization would exceed the scope of this paper.
1 2 4 5 5.1 5.2 6
Introduction Preliminaries The weighted parsing algorithm Termination and correctness Properties of the value computation algorithm Properties of the weighted parsing algorithm Comparison of value computation algorithms
Closed wRTG LMs
Richard Morbitz, Heiko Vogler: Weighted parsing for grammar-based language models (FSMNLP 2019)
Let . A wRTG-LM = ((,),,wt is -closed if is distributive and d-complete, and for each T and cyclic string the following holds: if there is a (, )-cyclic path in , then
at most times closed, distributive, d-complete
For every and -closed wRTG-LM ((,),,wt the following holds:
Richard Morbitz, Heiko Vogler: Weighted parsing for grammar-based language models (FSMNLP 2019)
Let . A wRTG-LM = ((,),,wt is -closed if is distributive and d-complete, and for each T and cyclic string the following holds: if there is a (, )-cyclic path in , then
at most times closed, distributive, d-complete
For every and -closed wRTG-LM ((,),,wt the following holds: