Bilexical Grammars and a Cubic-time Probabilistic Parser

Computational linguistics has a long tradition of lexicalized grammars, in which each grammatical rule is specialized for some individual word. The earliest lexicalized rules were word-specific subcategorization frames. It is now common to find fully lexicalized versions of many grammatical formalisms, such as context-free and tree-adjoining grammars [Schabes et al. 1988]. Other formalisms, such as dependency grammar [Mel’cuk 1988] and head-driven phrase-structure grammar [Pollard & Sag 1994], are explicitly lexical from the start. Lexicalized grammars have two well-known advantages. Where syntactic acceptability is sensitive to the quirks of individual words, lexicalized rules are necessary for linguistic description. Lexicalized rules are also computationally cheap for parsing written text: a parser may ignore those rules that do not mention any input words. More recently, a third advantage of lexicalized grammars has emerged. Even when syntactic acceptability is not sensitive to the particular words chosen, syntactic distribution may be [Resnik 1993]. Certain words may be able but highly unlikely to modify certain other words. Such facts can be captured by a probabilistic lexicalized grammar, where they may be used to resolve ambiguity in favor of the most probable analysis, and also to speed parsing by avoiding (“pruning”) unlikely search paths. Accuracy and efficiency can therefore both benefit. Recent work along these lines includes [Charniak 1995, Collins 1996, Eisner 1996b, Collins 1997], who reported state-of-the-art parsing accuracy. Related models are proposed without evaluation in [Lafferty et al. 1992, Alshawi 1996]. This recent flurry of probabilistic lexicalized parsers has focused on what one might call bilexical grammars, in which each grammatical rule is specialized for not one but two individual words. The central insight is that specific words subcategorize to some degree for other specific words: tax is a good object for the verb raise. Accordingly, these models estimate, for example, the probability that (a phrase headed by) word y modifies word x, for any two words x, y in the vocabulary V . At first blush, probabilistic bilexical grammars appear to carry a substantial computational penalty. Chart parsers derived directly from CKY or Earley’s algorithm take time O(n min(n, |V |)), which amounts to O(n) in practice. Such algorithms implicitly or explicitly regard the grammar as a context-free grammar in which a noun phrase headed by tiger bears the special nonterminal NPtiger. Such ≈ O(n ) algorithms are explicitly used by [Alshawi 1996, Collins 1996], and almost certainly by [Charniak 1995] as well. The present paper formalizes an inclusive notion of bilexical grammars, and shows that they can be parsed in time only O(ngtm) ≈ O(n), where g, t, and m are bounded by the grammar and are typically small. (g is the maximum number of senses per input word, t measures the degree of lexical interdependence that the grammar allows among the several children of a word, and m bounds the number of modifier relations that the parser need distinguish for a given pair of words.) The new algorithm also reduces space requirements to O(ngt) ≈ O(n), from the ≈ O(n) required by CKY-style approaches to bilexical grammar. The parsing algorithm finds the highest-scoring analysis or analyses generated by the grammar, under a probabilistic or other measure. Non-probabilistic grammars may be treated as a special case.