Factored A* Search for Models over Sequences and Trees

1 Introduction

The primary challenge when using A* search is to find heuris­ tic functions that simultaneously are admissible, close to ac­ tual completion costs, and efficient to calculate. In this pa­ per, we describe a family of tree and sequence models in which path costs are either defined as or bounded by a com­ bination of simpler component models, each of which scores some projection of the full structure. In such models, we can exploit the decoupled behavior over each projection to give sharp heuristics for the combined space. While we focus on models of trees and sequences within NLP applications, the approach can be applied more generally (and already has been, in the case ofbiological sequence models). All the con­ crete cases we consider here involve search over spaces which are equivalent to dynamic programming lattices, though this detail, too, is somewhat peripheral to the basic ideas.

2 Projection Models for Graphs

The core idea of factored A* search can apply to any graph search. Assume that G = (N, A) is a very large graph, with a single source nodes and a single goal node g, and that we wish to use A* search to efficiently find a best path from s to g. For concreteness, assume also that the score of a path is the

Christopher D. Manning

Department of Computer Science Stanford University Stanford, CA 94305-9040

manning@cs.stanford.edu

sum of the scores of the arcs along the path, and that lower scores are better. 1 The particular assumption in this paper is that the arc scoring function has a special factored form. Specifically, there exists a set of projections {rr1 , ... 7l'k} of nodes (and therefore also arcs and graphs) such that for any arc (x, y), its score a is given by:

Whenever the scoring function factors in this way, we have an immediate recipe for a factored A* bound, which we denote by h. Specifically, we can bound the shortest path in G from a node n to the goal g by the sum of the shortest paths inside each projection rr(G). Formally, if aa(n, g) is the length of a shortest path from n tog in a graph G, then:

This follows immediately from the optimality of the projected paths and the structure of the scoring function . These pro­ jections need not be mutually compatible, and therefore the bound may not be tight. Broadly speaking, the greater the de­ gree to which each projection prefers similar paths, the better the bound will be, and the more efficient our search will be.

3 Projection Models for Sequences

For intuition, we first consider applications to sequence mod­ els before extending to the more complex case of tree models.

3.1 Example: Multiple Sequence Alignment

A situation which fits this framework perfectly is the align­ ment of multiple genome sequences in bioinforrnatics, where such multiple sequence alignments (MSAs) are standardly evaluated by sum-of-pairs scoring [Durbin eta!., 1998]. MSA is a generalization of the longest-common-subsequence prob­ lem, in which one is given sequences like those in figure I a, and asked to produce pointwise alignments. Alignments of d sequences {s1, ... Sd} consist oft vertical timeslices which specify, for each sequence, either a successive element of the sequence or a gap (-), and are such that if the gaps are re­ moved, the rows contain the original sequences. The score of a timeslice is the sum of the scores of each of the pairs in that slice (where each pair of symbols is assigned some experimental goodness value).

1 We will talk about minimum sums, but other semi rings work as well, specifically maximum products.

The well-known dynamic program for calculating opti­ mal multiple alignments involves a lattice of position nodes n = [i 1, . . . ik] which specify an index along each sequence [Durbin et a/., 1998]. When each node is visited, each of its 2k - 1 successors p' (where each position is either in­ cremented or not) are relaxed with the best score through p combined with the score of the timeslice that the change from p top' represents. These nodes form a lattice of size O(nk), where n is the maximum length of the sequences. This be­ comes extremely inefficient as k grows.

The specific following idea has been used before ([Ikeda and lmai, 1994] is the earliest reference we could find) and it has been worked on recently ([Yoshizumi et al., 2000] in­ ter alia), though perhaps it has not received the attention it deserves in the bioinformatics literature. We present it here because ( 1) it is a good example that can be cast into our framework and (2) it gives a good starting intuition for the novel cases below. Since the score of an arc (timeslice) is a sum of pairwise goodness scores, we can define a set {7rab) of projections, one onto each pair of indices (i 0 , ib). Under 1Tab, a node [i 1, . .. , h] will project to its a and b indices, [i 0 , ib]. It is easy to see that the optimal path in this projection is just the optimal 2-way alignment of the portions of sequences a and b which are to the right of the indices ia and ib, respec­ tively. We can therefore bound the total completion cost of the k-way alignment from n onward with the sum of the pair­ wise completion costs of the 2-way alignments inside each projection.

Figure 2 shows some experimental speed-ups given by this method, compared to exhaustive search. We took several protein sequence groups from [McClure et al., 1994], and, for each set, we aligned as large a subset of each group as was possible using uniform-cost search with 1GB of mem­ ory. The left four runs show the cost (in nodes visited) of aligning these subsets with both uniform-cost search and A* search. In the right four runs, we added another sequence to the subsets and solved the multiple alignment using only the A* search. The A* savings are substantial, usually pro­ viding several orders of magnitude over uniform-cost search, and many orders of ma~nitude over the exhaustive dynamic programming approach. This verifies previous findings, and shows that factored A* bounds can be highly effective.

2 Note that the DP was never run- it would not have fit in memory - but it is easy to calculate the size of the lattice. There are also subtleties in running the uniform-cost search since the score of a times lice can be negative (we add in a worst possible negative score).

One potential worry with A* search is that the cost of com­ puting heuristics can be substantial. In this case, the O(k 2 ) pairwise alignments could be calculated very efficiently; in our experiments this pre-search phase took up much less than 1% of the total time.

3.2 Example: Finite State Transducers

We briefly describe another potential application of factored A* search for sequence models: the intersection of weighted finite-state transducers (WFSTs). 3 WFSTs are probabilistic mappings between sequences in one alphabet to sequences in another, for example a transducer might map an input of written text to an output of that text's pronunciation as a phoneme sequence. Intersections of WFSTs have been ap­ plied to various tasks in speech and NLP [Mohri, 1997], such as text-to-speech, and, most famously in the NLP lit­ erature, modeling morphophonology [Kaplan and Kay, 1994; Albro, 2000]. In these cases, each transducer constrains some small portion of the overall output sequence. The case of find­ ing the most likely intersected output of a set ofWFSTs {M;} for an input sequence w =own involves the following:

1. For each M;, create the projection JT; of the full output space 0 onto M; 's ou~ut space (note that this can be the identity projection).
2. For each index j along w and each output in JT; ( 0), compute optimal completion costs a; (j, JT;( 0)) forM; .
3. Use h(i, 0) = L; a; (j, JT;( 0)) as an A* heuristic.

While transduction intersection fits cleanly into the fac­ tored framework, the primary utility of transducers lies in their composition, not their intersection [Mohri, 1997]. In this case, transducers are chained together, with the output of one serving as the input to the next. In this case, it is worth switching from talk of summed distances to talk of multiplied probabilities. Say we have two transducers, Mt x which gives a distribution P(XII) from sequences I to se­ quences X, and Mxo, which gives P(OIX) from X to 0 .

3WFSTs are equivalent to HMMs which have emission weights assigned to their transitions (not states) and which may have epsilon transitions.

4 For simplicity, we assume all history relevant to any transducer is encoded into the state space 0.

We then wish to answer questions about their composed be­ havior. For example, we might want to find the output o which maximizes P(oli) according to this model. The com­ mon Viterbi approximation is to settle for the o from the pair (o, x) which maximizes P(o, xfi). This problem would fit neatly into the factored framework if the (usually false) conditional independence P(o , x li) = P(ofi)P(x li)) where true - in fact it would then be WFST intersection. How­ ever, something close to this does trivially hold: P(o, x li) = P(ofx , i)P(xfi). Given this, we can define another model R(o li) = maxx P(ofx, i). R is not a proper probabilistic model - it might well assign probability one to every trans­ duction - but its intersection with P (x li ) does upper-bound the actual composed model. Hence these two projections pro­ vide a factored bound for a non-factored model, with the prac­ tical utility of this bound depending on how tightly R(oli) typically bounds P(olx, i) .

4 Projection Models for Trees

Search in the case of trees is not over standard directed graphs, but over a certain kind of directed hypergraph in which arcs can have multiple sources (but have a single tar­ get). This is because multiple sub-trees are needed to form a larger tree. 5 Figure 4 shows a fragment of such a hypergraph for a small parse tree (note that all the lines going to one ar­ rowhead represent a single hyperarc). We don't give the full definitions ofhypergraph search here (see [Gallo et al. , 1993] for details), but the basic idea is that one cannot traverse an arc until all its source nodes have been visited. In the parse case, for example, we cannot build a sentence node until we build both a noun phrase node and an (adjacent) verb phrase node. The nodes in this graph are identified by a grammar

5 These directed B-hypergraphs model what has been explored as AND/OR trees in AI.

----

symbol, along with the region of the input it spans. The goal node is then a parse of the root symbol over the entire in­ put. (Hyper)paths embody trees, and the score of a path is the combination ofthe scores ofthe arcs in the tree. One fine point is that, while a standard path from a source s to a goal g through a node n breaks up into two smaller paths (s to n and n to g), in the tree case there will be an inside path and an outside path, as shown in the right of figure 5. In general , then, the completion structures that represent paths to the goal (marked by a in the figure) are specified not only by a node n and goal g, but also by the original sources .

With this modification, the recipe for the factored A* bound is now:

Next, we present a concrete projection model for scoring lex­ icalized trees, and construct an A* parser using the associated factored A* bound.

Generative models for parsing natural language typically model one of the kinds of structures shown in figure 3. While word-free syntactic configurations like those embodied by phrase structure trees (figure 3a) are good at capturing the broad linear syntax of a language [ Chamiak, 1996], word­ to-word affinities like those embodied by lexical dependency trees (figure 3b) have been shown to be important in resolv­ ing difficult ambiguities [Hindle and Rooth, 1993]. Since both kinds of information are relevant to parsing, the trend has been to model lexicalized phrase structure trees like fig­ ure 3c.

In our current framework, it is natural to think of a lexi­ calized tree as a pair L = (T, D) of a phrase structure tree T and a dependency tree D. In this view, generative mod­ els over lexicalized trees, of the sort standard in lexicalized PCFG parsing [Collins, 1999; Chamiak, 2000], can be re­ garded as assigning mass P(T, D) to such pairs. In the stan­ dard approach, one builds a joint model over P(T, D) , and, for a given word sequence own, one searches for the maxi­ mum posterior parse:

Since P(w) is a constant, one operationally searches instead for the maximizer of P(T, D, w).

The naive way to do this is an 0(n 5 ) dynamic program (often called a tabular parser or chart parser) that works as follows. The core declarative object is an edge, such as e = [X, i, j, h] which encapsulates all parses of the span i w J which are labeled with grammar symbol X and are headed by word Wh (i ::::: h < j) . Edges correspond to the nodes in the

1. Extract the PCFG projection and set up the PCFG parser.
2. Use the PCFG parser to find projection scores arcFo(s, e, g) for each edge.
3. Extract the dependency projection and set up the dependency parser.
4. Use the dependency parser to find projection scores aoEr(s, e, g) for each edge.
5. Combine PCFG and dependency projections into the full model.
6. Form the factored A* estimate h(s, e, g) = arcFG(s, e, g)+ aoEr(s, e, g)
7. Use the combined parser, with h(s, e, g) as an A* estimate ofa(s, e, g)

s

Figure 5: The top-level algorithm (left) and an illustration of how paths decompose in the parsing hypergraph (right).

parsing hypergraph. Two edges [X, i, j, h] and [Y, j , k, h'] can be combined whenever they are contiguous (the right one starts where the left one ends) and the grammar per­ mits the combination. For example, if there were a rewrite Z[ w,] -+ X[ Wh] Y[ w, ,], those two edges would combine to form [Z, i, k, h], and that combination would be scored by some joint model over the word and symbol configuration: P(XY, h'IZ, h) . 6 These weighted combinations are the arcs in the hypergraph.

A natural projection of a lexicalized tree L is onto its com­ ponents T and D (though, to our knowledge, this projec­ tion has not been exploited previously). In this case, the score for the combination above would be P(XY, h'l Z, h) = P(XYIZ)P(h'lh). 7

This kind of projected model offers two primary benefits. First, since we are building component models over much simpler projections, they can be designed, engineered, and tested modularly, and easily. To underscore this point, we built three PCFG models of P(T) and two lexical dependency models of P(T). In section 4.2, we discuss the accuracy of these models, both alone and in combination.

Second, our A* heuristic will be loose only to the degree that the two models prefer different structures. Therefore, the combined search only needs to figure out how to optimally reconcile these differences, not explore the entire space of legal structures. Figure 6 shows the amount of work done in the uniform-cost case versus the A* case. Clearly, the uniform-cost version of the parser is dramatically less ef­ ficient; by sentence length 15 it extracts over 800K edges, while even at length 40 the A* heuristics are so effective that only around 2K edges are extracted. At length 10, the av­ erage number is less than 80, and the fraction of edges not suppressed is better than 1/lOK (and it improves as sentence length increases). 8 The A* estimates were so effective that even with our object-heavy Java implementation of the com­ bined parser, total parse time was dominated by the initial, array-based PCFG phase (see figure 6b). 9

6 Most models, including ours, will also mention distance; we ignore this for now.

7 As a probabilistic model, this formulation is mass deficient, as­ signing mass to pairs which are incompatible, either because they do not generate the same terminal string or do not embody compat­ ible bracketings. Therefore, the total mass assigned to valid struc­ tures will be less than one. We could imagine fixing this by renor­ malizing. In particular, this situation fits into the product-of-experts framework [Hinton, 2000], with one semantic expert and one syn­ tactic expert that must agree on a single structure. However, since we are presently only interested in finding most-likely parses, no global renormalization constants need to be calculated. In any case, the question of mass deficiency impacts only parameter estimation, not inference, which is our focus here.

4.1 Specific Projection Models for Parsing

To test our factored parser, we built several component mod­ els, which were intended to show the modularity of the ap­ proach. We merely sketch the individual models here; more details can be found in [Klein and Manning, 2003]. For P(T), we built successively more accurate PCFGs. The simplest, PCFG-BASIC, used the raw treebank grammar, with nontermi­ nals and rewrites taken directly from the training trees [Char­ niak, 1996]. In this model, nodes rewrite atomically, in a top-down manner, in only the ways observed in the training data. For improved models of P(T), tree nodes' labels were annotated with various contextual markers. In PCFG-PA, each node was marked with its parent's label as in [Johnson, 1998]. It is now well known that such annotation improves the accu­ racy of PCFG parsing by weakening the PCFG independence assumptions. For example, the NP in figure 3a would actu­ ally have been labeled NP'S. Since the counts were not frag­ mented by head word or head tag, we were able to directly use the MLE parameters, without smoothing. 10 The best PCFG model, PCFG-LING, involved selective parent split­ ting, order-2 rule markovization (similar to [Collins, 1999; Charniak, 2000]), and linguistically-derived feature splits.

8 Note that the uniform-cost parser does enough work to exploit the shared structure of the dynamic program, and therefore edge counts appear to grow polynomially. However, the A* parser does so little work that there is minimal structure-sharing. Its edge counts therefore appear to grow exponentially over these sentence lengths, just like a non-dynamic-programming parser's would. With much longer sentences, or a less efficient estimate, the polynomial behav­ ior would reappear.

9 There are other ways of speeding up lexicalized parsing with­ out sacrificing search optimality. Eisner and Satta [Eisner and Satta, 1999] propose a clever O(n 4 ) modification which separates this pro­ cess into two steps by introducing an intermediate object. However, even the 0(n 4 ) formulation is impractical for exhaustive parsing with broad-coverage, lexicalized treebank grammars. The essential reason is that the non-terminal set is just too large. We did imple­ ment a version of this parser using their O(n 4 ) formulation, but, be­ cause of the effectiveness of the A* estimate, it was only marginally faster; as figure 6b shows, the combined search time is very small.

10 This is not to say that smoothing would not improve perfor­ mance, but to underscore how the factored model encounters less sparsity problems than a joint model.

Models of P(D) were lexical dependency models, which deal with part-of-speech tagged words: pairs (w, t). First the head (w11 , t11 ) of a constituent is generated, then succes­ sive right dependents (wd, ld) until a STOP token o is gen­ erated, then successive left dependents until o is generated again. For example, in figure 3, first we choose fell-VBD as the head of the sentence. Then, we generate in-IN to the right, which then generates September-NN to the right, which generates o on both sides. We then return to in-IN, gener­ ate o to the right, and so on. The dependency models re­ quired smoothing, as the word-word dependency data is very sparse. In our basic model, DEP-BASI~, w~ generat~ ~ de­ pendent conditioned on the head and dtrectl~n, requtr~ng a model of P(wd, tdiwh, fh, dir). This was estimated usmg a back-offmodel which interpolated the sparse bilexical counts with the denser but less specific counts given by ignoring the head word or by first generating the dependent tag and then generating the dependent word given only the dependent tag. The interpolation parameters were estimated ~n hel?-o~t data. The resulting model can thus capture classical bilexi­ cal selection, such as the affinity between payrolls and fell, as well as monolexical preferences, such as the tendency for of to modify nouns. In the enhanced dependency model, DEP­ VAL we condition not only on direction, but also on distance and ~alence. Note that this is (intentionally) very similar to the generative model of[ Collins, 1999] in broad structure, but substantially less complex.

4.2 Parsing Performance

In this section, we describe our various projection models and test their empirical performance. There are two ways to mea­ sure the accuracy of the parses produced by our system. First, the phrase structure of the PCFG and the phrase structure pro­ jection of the combination parsers can be compared to the treebank parses. The parsing measures standardly used for this task are labeled precision and recall. 11 We also report F 1, the harmonic mean of these two quantities. Second, for the dependency and combination parsers, we can score the dependency structures. A dependency structure D is viewed as a set of head-dependent pairs (h, d), with an extra depen­ dency (root, x) where root is a special symbol and x is the head of the sentence. Although the dependency model gen­ erates part-of-speech tags as well, these are ignored for de­ pendency accuracy. Punctuation is not scored. Since all de­ pendency structures over n non-punctuation terminals con­ tain n dependencies (n - 1 plus the root dependen~y), we report only accuracy, which is identical to both preciSIOn and recall. It should be stressed that the "correct" dependency structures, though generally correct, are generated from t?e PCFG structures by linguistically motivated, but automatic, and only heuristic rules.

Figure 7 shows the relevant scores for the various PCFG and dependency parsers alone. The valence model increases the dependency model's accuracy from 76.3% to 85.0%, and each successive enhancement improves the F 1 of the PCFG models from 72.7% to 77.7% to 82.9%. The combination parser'~ performance is given in figure 8. As each individ­ ual model is improved, the combination F 1 is also improved, from 79.1% with the pair of basic models to 86.7% with the pair of top models. The dependency accuracy also goes up: from 87.2% to 91 .0%. Note, however, that even the pair of ba­ sic models has a combined dependency accuracy higher than the enhanced dependency model alone, and the top three have combined F 1 better than the best PCFG model alone. For the top pair, figure 6c illustrates the relative F 1 of _the combina­ tion parser to the PCFG component alone, showmg the unsur­ prising trend that the addition of the dependency model helps more for longer sentences, which, on average, contain more attachment ambiguity. The top F 1 of 86.7% is greater than that of the lexicalized parsers presented in [Magerman, 1995; Collins, 1996], but less than that of the newer, more com­ plex, parsers presented in [Chamiak, 2000; Collins, 1999], which reach as high as 90.1% F 1. However, it is worth point­ ing out that these higher-accuracy parsers incorporate many finely wrought enhancements which could presumably be ap­ plied to benefit our individual models. 12

ll A tree T is viewed as a set of constituents c(T). Constituents in the correct and the proposed tree must have the same start, end, and label to be considered identical. For this measure, the lexical heads of nodes are irrelevant. The actual measures used are detailed in [Magerman, 1995], and involve minor normalizations like there­ moval of punctuation in the comparison.

4.3 Factored Bounds for Non-Projection Models

Arbitrary tree models will not be factored projection models. For example, while our parsing model was expressly designed so that P(T, D) = P(T)P(D), to our knowledge no other model over lexicalized trees with this decomposition has been proposed. Nonetheless, non-factored models can still have factored bounds. Given any model P(A, B), we can imagine bounds R(A) and R(B) that obey:

Trivially, R(A) R(B) 1 will do. To get a non-trivial bound, consider a joint (local) model P(XY, h'IZ, h) of lexicalized tree rewrites. Early lexical­ ized parsing work [Chamiak, 1997] used models of ex­ actly this form. We can use the chain rule to write P(XY, h'IZ, h) = P(XYJZ, h)P(h'IXY, Z, h). Then, we can form R(XYJZ) = maxh P(XYJZ, h) and R(h'lh) = maxxr.z P(h'IXY, Z, h). This technique allows one to use factored A* search for non-factored models, though one might reasonably expect such bounds to be much less sharp for non-factored models than for factored models. A particu­ lar application ofthis method for future work would be the ex­ act parsing of the models in [Chamiak, 1996; Collins, 1999; Chamiak, 2000], as the details of their estimation suggest that their word dependency and phrase structure aspects would be approximately factorizable.

5 Conclusion

Not all models will factor, nor will all models which fac­ tor necessarily have tight factored bounds (for example MSA with many sequences or parsing if the component models do not prefer similar structures). However, when we can design factored models or find good factored bounds, the method of factored A* search has proven very effective. For the MSA problem, A* methods allow exact alignment of up to 9 pro­ tein sequences (though 5-6 is more typical) of length 100300, when even three-way exhaustive alignment can easily exhaust memory. For the parsing problem, we have presented here the first optimal lexicalized parser which can exactly parse sentences of reasonable length using large real-world Penn Treebank grammars. The projected models can be de­ signed and improved modularly, with improvements to each model raising the combined accuracy. Finally, we hope that this framework can be profitably used on the other sequence models we outlined, and on any large space which can nat­ urally be viewed as a composition of (possibly overlapping) projections.

12 For example, the dependency distance function of [Collins, I 999] registers punctuation and verb counts, and both smooth the PCFG production probabilities.

Acknowledgements

We would like to thank Lillian Lee, Fernando Pereira, and Dan Melamed for advice and discussion about this work.