Worst-Case Synchronous Grammar Rules

Proceedings of NAACL HLT 2007, pages 147–154, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Worst-Case Synchronous Grammar Rules Daniel Gildea and Daniel ˇStefankoviˇc Computer Science Dept. University of Rochester Rochester, NY 14627 Abstract We relate the problem of finding the best application of a Synchronous Context- Free Grammar (SCFG) rule during pars- ing to a Markov Random Field. This representation allows us to use the the- ory of expander graphs to show that the complexity of SCFG parsing of an input sentence of length N is Ω(N cn), for a grammar with maximum rule length n and some constant c. This improves on the previous best result of Ω(Nc√n). 1 Introduction Recent interest in syntax-based methods for statis- tical machine translation has lead to work in pars- ing algorithms for synchronous context-free gram- mars (SCFGs). Generally, parsing complexity de- pends on the length of the longest rule in the gram- mar, but the exact nature of this relationship has only recently begun to be explored. It has been known since the early days of automata theory (Aho and Ullman, 1972) that the languages of string pairs gen- erated by a synchronous grammar can be arranged in an infinite hierarchy, with each rule size ≥ 4 pro- ducing languages not possible with grammars re- stricted to smaller rules. For any grammar with maximum rule size n, a fairly straightforward dy- namic programming strategy yields an O(N n+4) al- gorithm for parsing sentences of length N. How- ever, this is often not the best achievable complexity, and the exact bounds of the best possible algorithms are not known. Satta and Peserico (2005) showed that a permutation can be defined for any length n such that tabular parsing strategies must take at least Ω(Nc√n), that is, the exponent of the algorithm is proportional to the square root of the rule length. In this paper, we improve this result, showing that in the worst case the exponent grows linearly with the rule length. Using a probabilistic argument, we show that the number of easily parsable permuta- tions grows slowly enough that most permutations must be difficult, where by difficult we mean that the exponent in the complexity is greater than a constant factor times the rule length. Thus, not only do there exist permutations that have complexity higher than the square root case of Satta and Peserico (2005), but in fact the probability that a randomly chosen permutation will have higher complexity approaches one as the rule length grows. Our approach is to first relate the problem of finding an efficient parsing algorithm to finding the treewidth of a graph derived from the SCFG rule’s permutation. We then show that this class of graphs are expander graphs, which in turn means that the treewidth grows linearly with the graph size. 2 Synchronous Parsing Strategies We write SCFG rules as productions with one lefthand side nonterminal and two righthand side strings. Nonterminals in the two strings are linked with superscript indices; symbols with …

Content truncated to 500 words