A Fast Algorithm for Computing Prefix Probabilities (2023)

Abstract: Multiple algorithms are known for efficiently calculating the prefix probability of a string under a probabilistic context-free grammar (PCFG). Good algorithms for the problem have a runtime cubic in the length of the input string. However, some proposed algorithms are suboptimal with respect to the size of the grammar. This paper proposes a new speed-up of Jelinek and Lafferty’s (1991) algorithm, which runs in O(n^3|N|^3 + |N|^4) , where n is the input length and |N| is the number of non-terminals in the grammar. In contrast, our speed-up runs in O(n^2|N|^3 + n^3|N|^2) .

## introduction probabilistic context-free grammars (pcfgs) are an important formalism in nlp @xcite . one common use of pcfgs is to construct a language model. for instance, pcfgs form the backbone of many neural language models, e.g., recurrent neural network grammars (rnngs; @xcite @xcite . however, in order to use a pcfg as a language model, one needs to be able to compute prefix probabilities, i.e., the probability that the yield of a derivation starts with the given string. in notation, given a string @xmath0, we seek the probability p(s * ⇒ w • • • ) where s is the distinguished start symbol of the grammar and algorithm which is derived from cky @xcite @xcite and, thus, requires the grammar to be in chomsky normal form (cnf). jelinek-lafferty runs in o(n foot_1 |n | 3 + |n | foot_2 ) time, where n is the length of the input and n is the number of non-terminals of the grammar, slower than the o(n 3 |n | 3 ) required for parsing with cky, when the number of non-terminals |n | is taken into account. the second, due to @xcite , is derived from earley parsing @xcite and can parse arbitrary pcfgs, 3 with a runtime of o(n 3 |n | 3 ). many previous authors have improved the runtime of earley's @xcite @xcite , @xcite successfully applied this speed-up to computing prefix probabilities, achieving a runtime of o(n 3 |g|), where |g| is the size of the grammar, that is, the sum of the number of symbols in all production rules. our paper provides a more efficient version of @xcite for the computation of prefix probabilities under a pcfg in cnf. specifically, we give an o(n foot_0 |n | 3 + n 3 |n | 2 ) time algorithm, which is the fastest attested in the literature for dense grammars in cnf, 4 matching the complexity of cky adapted for dense grammars by @xcite . 5 we provide a full derivation and proof of correctness, as well as an open-source implementation on github. we also briefly discuss how our improved algorithm can be extended to work for semiring-weighted cfgs. ## preliminaries we start by introducing the necessary background on probabilistic context-free grammars. definition 1. a probabilistic context-free grammar (pcfg) is a five-tuple @xmath1, σ, s, r, p), made up of: note that not every locally normalized pcfg constitutes a valid distribution over σ * . specifically, some may place probability mass on infinite trees @xcite . pcfgs that do constitute a valid distribution over σ * are referred to as tight. furthermore, if all non-terminals of the grammar can be reached from the start non-terminal via production rules, we say the pcfg is trim. definition 2. a pcfg @xmath2, σ, s, r, p) is in chomsky normal form (cnf) if each production rule in r is in one of the following forms: we represent derivations as trees whose structure corresponds to production rules, where any parent node is the non-terminal on the left-hand side of a rule and its children are the symbols from the right-hand side. the leaves of the tree, when read from left to right, form the yield. such a tree, when rooted s, is called a derivation tree. otherwise, it is called a derivation subtree. definition 5. the probability of a derivation tree (or derivation subtree) τ is the product of the probabilities of all its corresponding production rules: that is, the sum of the probabilities of all derivation trees τ starting at x that have yield w i • • • w k . definition 8. given a pcfg @xmath3, σ, s, r, p), a string @xmath4, and a non-terminal @xmath5, we define the prefix probability π, i.e., the probability of w being a prefix under g, as: in words, π is the probability of deriving w with an arbitrary continuation from x, that is, the sum of probabilities of deriving wu from x over all possible suffixes @xmath6. in the following, we write the prefix probability of deriving prefix @xmath7, x, k). definition 9. let g be a pcfg in cnf. then for non-terminals x, y, @xmath8, the left-corner expectations ξ(y | x) and ξ(y z | x) are defined as: for x -→ w k+1 ∈ r : 8: ▷ handle single word tokens 9: for @xmath9, . . . , n -ℓ : 14: ▷ k marks the end of the span 15: the left-corner expectation ξ(y | x) is hence the sum of the probabilities of partial derivation subtrees rooted in x that have y as the left-most leaf; see fig. 2a for a visualization. similarly, ξ(y z | x) is the sum of the probabilities of partial derivation subtrees that have y and z as the leftmost leaves; see fig. 2b . lemma 1. given a tight, trim pcfg in cnf and a string @xmath10, the prefix probability of a substring w i+1 • • • w k of w being derived from x can be defined recursively as follows: base case (for all @xmath11. . . n -1 and all @xmath12: the above formulation of the prefix probability is closely related to that of the inside probability from @xcite inside-outside algorithm, which can be efficiently computed using cky, see alg. 1. next, the left-corner expectations ξ as defined by eq. ( 8 ) can be computed efficiently as follows. let p denote the square matrix of dimension |n |, with rows and columns indexed by the non-terminals n (in some fixed order), where the entry at the i th row and the j th column corresponds to p(x i -→ x j _), i.e., the probability of deriving x j on the left corner from x i in one step (we use _ as a wildcard): we can find the probability of getting to nonterminal x j after k derivation steps starting from x i by multiplying p with itself k times: we can hence get the matrix p * , whose entries correspond to deriving x j from x i after any number of derivation steps, by summing over all the powers of the matrix p : foot_5 note that the entry at the i th row and j th column of p * is exactly the left-corner expectation ξ(x j | x i ). finally, we can compute the left-corner expectations ξ(y z | x) using eq. ( 9 ): lastly, for completeness, we also compute the prefix probability of the empty string, ε. for probabilistic pcfgs, this probability is simply 1 because ε is a prefix of any string: foot_6 we can now combine the quantities derived above to obtain an efficient algorithm for the computation of prefix probabilities π(i, s, k). for the full algorithm, see alg. 2. proof. first, we precompute any values that are independent of the input. in lines 1-3, we precompute all the left-corner expectations ξ(y | x) using eq. ( 14 ), which has the complexity of inverting the matrix p , i.e., o(|n | 3 ), and move the values into a map of left-corner expectations in o(|n | 2 ) (this is just for readability). in lines 4-5, we then use eq. (9) to compute ξ(y z | x), iterating once over all non-terminals x for each rule, which takes o(|r||n |), that is, o(|n | 4 ). after initializing the probabilities in lines 7-10 in o(n 2 |n |), we begin by pre-computing all the inside probabilities β in line 11 of alg. 2, which takes o(n 3 |n | 3 ) by prop. 1. computing π(k, x, k + 1) for all @xmath13. (11) in lines 12-14 takes o(n |n | 2 ) as we iterate over all positions @xmath14. and finally, computing the π chart in lines 15-19 takes o(n 3 |n | 3 ) since we iterate over all ℓ, i, @xmath15, y, @xmath16. this yields an overall time complexity of o(n 3 |n | 3 + |n | 4 ). ■ 4 our speed-up we now turn to our development of a faster dynamic program to compute all prefix probabilities. the speed-up comes from a different way to factorize π(i, x, k), which allows additional memoization. starting with the definition of the prefix probability in eq. (16a), we first expand ξ(y z | x) by eq. ( 9 ), as seen in eq. ( 16b ). then, we factor out all terms that depend on the left-corner nonterminal y in eq. ( 16c ), which we store in a chart γ, see eq. ( 16e ). we then do the same for all terms depending on x ′ , factoring them out in eq. ( 16d ) and storing them in another chart δ, see eq. ( 16f ). our improved algorithm for computing all prefix probabilities is shown in alg. 3. proof. as before, alg. 3 starts by precomputing and assigning the left-corner expectations in lines 1-3, which takes o(|n | 3 ) and o(|n | 2 ), respectively. we then initialize the prefix probabilities and compute the inside probabilities in lines 5-8, taking o(n 2 |n |). as @xcite show, one can compute β (line 9) in o(n 2 |n | 3 + n 3 |n | 2 ), thus improving the runtime of alg. 1 for dense grammars. pre-computing γ and δ in lines 10-14 ## conclusion in this paper, we have shown how to efficiently compute prefix probabilities for pcfgs in cnf, adapting jelinek-lafferty to use additional memoization, thereby reducing the time complexity from we thereby addressed one of the main limitations of the original formulation, of being slow for large grammar sizes. a proof of lem. 1 lemma 1. given a tight, trim pcfg in cnf and a string @xmath17, the prefix probability of a substring w i+1 • • • w k of w being derived from x can be defined recursively as follows: base case (for all @xmath18. . . n -1 and all @xmath19: proof. eq. ( 11 ): the base case, π(k, x, k+1), is the probability of w k+1 being the left-most terminal in the parse subtree under x. it is, therefore, simply the sum of probabilities of any non-terminal y being on the left corner of the parse subtree under x multiplied by the corresponding probability of y directly deriving w k+1 . eq. ( 10 ): given the pcfg is in cnf and assuming @xmath20, in order to derive the prefix w i+1 • • • w k we must first apply some rule x -→ y z, where the first part of the substring is then derived from y and the remainder (and potentially more) from z: after repeated substitutions ad infinitum, we get: note that, in the last step, infinite derivations do not carry any probability mass since we assumed the pcfg to be tight and trim. hence, the final form of the equation is: