Time-and-Space-Efficient Weighted Deduction (2023)

Abstract: Many NLP algorithms have been described in terms of deduction systems. Unweighted deduction allows a generic forward-chaining execution strategy. For weighted deduction, however, efficient execution should propagate the weight of each item only after it has converged. This means visiting the items in topologically sorted order (as in dynamic programming). Toposorting is fast on a materialized graph; unfortunately, materializing the graph would take extra space. Is there a generic weighted deduction strategy which, for every acyclic deduction system and every input, uses only a constant factor more time and space than generic unweighted deduction? After reviewing past strategies, we answer this question in the affirmative by combining ideas of Goodman (1999) and Kahn (1962). We also give an extension to cyclic deduction systems, based on Tarjan (1972).

## introduction many nlp algorithms have been described in terms of deduction systems, starting with the seminal paper "parsing as deduction" @xcite . in general, deduction systems are an abstraction of dynamic computation graphs that can be used to describe the structure of many algorithms, including theorem provers, dynamic programming algorithms, and structured neural networks @xcite . unweighted deduction admits a generic execution strategy known as "forward chaining." furthermore, the behavior of this strategy is wellunderstood. its runtime and space can be easily bounded based on a simple inspection of the deduction system @xcite . static analysis can sometimes find tighter bounds @xcite . for weighted deduction, however, execution should wait to propagate a derived item's weight until that weight has converged. ideally it would visit the items in topologically sorted order (i.e., dynamic programming), which is not required for the unweighted case. fortunately, toposorting is fast. thus, is there a generic weighted deduction strategy which, for every acyclic deduction system and every input, uses only a constant factor more time and space than generic unweighted deduction? in this paper, we provide this missing master strategy, which is surprisingly simple. it establishes a "don't worry, be happy" meta-theorem @xcite : asymptotic analyses of unweighted acyclic deduction systems do transfer to the weighted case. past methods do not achieve this guarantee. for some deduction systems, static analysis may be able to identify a topological ordering. but even then, one is left with increased runtime, either from visiting all possible items (which fails to exploit the sparsity of the set of items actually derived from a particular input) or visiting only the items that have been derived (which exploits sparsity, but requires a priority queue that incurs logarithmic overhead). the alternative is dynamic analysis: given the input, first identify all the items that can be derived, using unweighted deduction, and then toposort them in order to compute the weights. @xcite suggested a version of this approach that materializes the graph of dependencies among items, but acknowledged that this generally increases the asymptotic space requirements. in this paper, we show how to avoid the space increase. we give a practical two-pass weighted deduction algorithm, inspired by @xcite , that uses parent counting to efficiently enumerate the derived items in topologically sorted order. it stores the counts of edges but no longer stores the edges themselves. also, for the case where the graph may have cycles, we give a practical three-pass algorithm. the first two passes efficiently enumerate the strongly connected components in topologically sorted order @xcite , with the same time and space guarantees as above. the third pass solves for the weights in each cyclic component, which may in-crease the asymptotic runtime if cycles exist. as an application of our two-and three-pass algorithms, consider extending earley parsing @xcite to probabilistic @xcite or semiring-weighted @xcite context-free grammars. @xcite present earley-style deduction systems whose unweighted versions are easily seen to be executable in o(n 3 |g|) time and o(n 2 |g|) space on a sentence of length n and a grammar of size |g|. these bounds are tight when every substring of the sentence can be analyzed, in its left context, as every sort of constituent or partial constituent. in practical settings, however, the parse chart is often much sparser than this worst case and execution is correspondingly faster. for instance, @xcite describes "bounded-state grammars" where parsing is guaranteed to require only o(n|g|) time and o(n|g|) space. @xcite .1) simply invoked the present paper ("don't worry") to offer all the same guarantees for weighted parsing. in contrast, the various past methods would have been slower by a log factor, or consumed θ(n 3 |g|) space for some grammars, or consumed θ(n 3 |g|) runtime even for bounded-state grammars. while the solution seems obvious in retrospect (at least once the problem is framed), it has somehow gone unnoticed in the literature. it has also evaded several hundred graduate and undergraduate students in the author's nlp class over two decades. students each year are asked to design and implement a viterbi earley parser. as extra credit, they are asked if they can achieve o(n 3 ) runtime while maintaining correctness. none of them have ever spotted the kahn-based solution, though some have found the other methods mentioned above. ## unweighted forward chaining a basic strategy for unweighted deduction is forward chaining (algorithm 1), well-known in the datalog community @xcite . this is simply a reachability algorithm: it finds all of the items that can be reached from the axioms v in the b-hypergraph (v, e). if the standard assumptions of §2.5 hold, it runs in time o(| v |+| ē|) and space the agenda a is a set that supports o(1)-time push() and pop() methods. push() adds an element to the set (our code is careful to never push duplicates). pop() removes and returns some arbitrary element of the set. if pop() is implemented to use a lifo or fifo policy, then the reachability algorithm will be depth-first or breadth-first, respectively, but any policy ("queue discipline") will do provided that v is finite. since this is the unweighted case, the chart c does not need to store weights. it is simply the set of items derived so far, approaching the desired v . 10 in later algorithms, however, c will be a map from those items to the weights that they have accumulated so far, approaching the desired ω. notice that since items are seen by the iterators only after they have popped, the hyperedge v f ↢ u 1 , . . . , u k is considered only once-when the last of its input items (not necessarily u k ) pops. this "considered only once" property makes algorithm 1 more efficient, but is not required for correctness. for the weighted algorithm below, however, it is required to prevent double-counting of hyperedges. ## weighted forward chaining algorithm 2 is a first attempt to generalize to the weighted case, where c becomes a map. the pseudocode uses the following conventions: if v is not a key of c, then c[v] returns a special value ⊥ / ∈ w. we define ⊥ ⊕ v ω = ω for all ω. changing c[v] from ⊥ to a value in w adds v as a new key to the chart c. if c[v] has changed at line 10, we must have it on the agenda to ensure that its new value is propagated forward through the hypergraph. the error at line 11 occurs when we would propagate both old and new values, which in general leads to incorrect results. the major challenge of this paper is to efficiently avoid this error condition. in an acyclic system, the "obvious" way to avoid the error condition is to pop items from the agenda in topologically sorted (toposorted) order-do not pop v until every item that v depends on has already popped. if that can be arranged, then v will only pop after its value has converged; c[v] will never change again, so v will never be pushed again. we remark that toposorting is not the only option. line 11 can simply be omitted in the special case where @xmath0, ⊕ @xmath1, and all functions f are monotonic on all arguments. then c @xcite can only decrease at line 9, and propagating its new (smaller) value will in effect replace the old value. 11 separately, there exists a slightly different family of algorithms which, each time u pops from the agenda, propagates the difference between c[u] and the old value of c[u] from the last time it popped. such "difference propagation algorithms" exist for semiring-weighted deduction systems @xcite 3 ) and also exist for weighted deduction systems in which each operation ⊕ v has a corresponding operation ⊖ v that can be used to compute differences of values. the approaches in the previous paragraph are correct in the special cases where they apply. they even work for cyclic deduction systems (provided that they converge). however, they are an inefficient choice for the acyclic case-the same derived item in v could pop more than once (in fact far more), which we refer to as repropagation, 12 but in the toposorted solution, it will pop exactly once. we therefore focus on toposorting approaches. ## previous toposorted strategies assume that p is acyclic and that unweighted forward chaining terminates. we discuss previously proposed strategies that visit the finitely many derived items v in a toposorted order, and explain why these strategies do not satisfy our goals. in addition to methods based on algorithms 1 and 2, we consider algorithms that relax the items in v in a topologically sorted order. c.relax(v) recomputes c[v] based on the current state of the chart c as well as the input (v, ω): if we relax every @xmath2, after relaxing all of the items that it depends on, then c will hold the correct result of evaluation from (1). note that it is harmless to relax v / ∈ v : this will simply leave c[v] = ⊥, so it will not be added to the chart. ## two-pass weighted deduction via parent counting we now present our simple solution to the problem, in the acyclic case. as already mentioned, it allows acyclic weighted deduction systems such as the inside algorithm ( §2.4) and weighted earley's algorithm ( §1) to benefit from sparsity in the chart just as much as their unweighted versions do, without any asymptotic time or space overhead. the idea is to use a version of topological sorting @xcite that only requires following outhyperedges, as in forward chaining. we first modify our first pass (algorithm 4). an item @xmath3, but just stores the count of those incoming hyperedges in waiting_edges[v] (initially 0). ## limitations we have not discussed parallel execution beyond tensorization of a deduction system ( §2.4). but in forward chaining, one could pop multiple items from the agenda and then process them simultaneously in multiple threads, taking care to avoid write conflicts. 24 indeed, semi-naive bottom-up evaluation, a classical strategy for evaluating unweighted deduction systems @xcite , is equivalent to processing all items on the agenda in parallel at each step. for backward chaining, @xcite reviews concurrent versions of tarjan's algorithm. we have not discussed dynamic algorithms, where the axioms or their weights can be updated after or during evaluation, and one wishes to update the derived items and their weights without recomputing them from scratch @xcite . finally, §2.2 defined evaluation to return all of v . we did not discuss query-driven evaluation, which returns only v ∩ q (and corresponding weights) for a given set of query items q ⊆ v. this can allow termination even in some cases with infinite v . intuitively, we hope to backward-chain from q while also forward-chaining from v . this can be achieved by a technique such as magic sets @xcite , which transforms the deduction system p to (1) accept additional input axioms that specify the queries q, (2) derive additional items corresponding to recursive queries, (3) augment the original hyperedges so that they will derive an original item v only when it answers a query. evaluation of the new system p ′ requires only forward chaining via out() (e.g., our algorithms 4-6 and 8)-but forward chaining for (2) simulates backward chaining under p. as a result, the out() iterators of p ′ must do additional work corresponding to what the in() iterators of p did. ## conclusions often an nlp algorithm can be expressed as a weighted deduction system ( §2) that defines how various quantities should be computed from one another. such a system is usually presented as a small collection of rules that combine to generate a large or even infinite computation graph (really a hypergraph). the rules specify concisely what is to be computed, leaving the details of scheduling and data structures to generic strategies that are well-understood, reliable, and easy to analyze. we adopted a general formalism for weighted deduction systems (going beyond the usual semiringweighted case) and surveyed a range of generic strategies that can be interpreted or compiled for a given system when seeking a practical cpu implementation. all of the strategies were presented uniformly in terms of a chart c and agenda a. our main novel contribution was to exhibit a generic strategy for acyclic weighted deduction that is guaranteed to be as time-and space-efficient on every system and input as the corresponding strategy for unweighted deduction, up to a constant factor that is independent of the system and input. we also exhibited a strategy with related guarantees for the more general case of cyclic weighted deduction.