Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 168–175, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold Mark Johnson Microsoft Research Brown University Redmond, WA Providence, RI t-majoh@microsoft.com Mark Johnson@Brown.edu Abstract This paper shows how to use the Unfold- Fold transformation to transform Projective Bilexical Dependency Grammars (PBDGs) into ambiguity-preserving weakly equiva- lent Context-Free Grammars (CFGs). These CFGs can be parsed in O(n3) time using a CKY algorithm with appropriate indexing, rather than the O(n5) time required by a naive encoding. Informally, using the CKY algorithm with such a CFG mimics the steps of the Eisner-Satta O(n3) PBDG parsing al- gorithm. This transformation makes all of the techniques developed for CFGs available to PBDGs. We demonstrate this by describ- ing a maximum posterior parse decoder for PBDGs. 1 Introduction Projective Bilexical Dependency Grammars (PB- DGs) have attracted attention recently for two rea- sons. First, because they capture bilexical head-to- head dependencies they are capable of producing extremely high-quality parses: state-of-the-art dis- criminatively trained PBDG parsers rival the accu- racy of the very best statistical parsers available to- day (McDonald, 2006). Second, Eisner-Satta O(n3) PBDG parsing algorithms are extremely fast (Eisner, 1996; Eisner and Satta, 1999; Eisner, 2000). This paper investigates the relationship between Context-Free Grammar (CFG) parsing and the Eis- ner/Satta PBDG parsing algorithms, including their extension to second-order PBDG parsing (McDon- ald, 2006; McDonald and Pereira, 2006). Specifi- cally, we show how to use an off-line preprocessing step, the Unfold-Fold transformation, to transform a PBDG into an equivalent CFG that can be parsed in O(n3) time using a version of the CKY algorithm with suitable indexing (Younger, 1967), and extend this transformation so that it captures second-order PBDG dependencies as well. The transformations are ambiguity-preserving, i.e., there is a one-to- one mapping between dependency parses and CFG parses, so it is possible to map the CFG parses back to the PBDG parses they correspond to. The PBDG to CFG reductions make techniques developed for CFGs available to PBDGs as well. For example, incremental CFG parsing algorithms can be used with the CFGs produced by this transform, as can the Inside-Outside estimation algorithm (Lari and Young, 1990) and more exotic methods such as estimating adjoined hidden states (Matsuzaki et al., 2005; Petrov et al., 2006). As an example appli- cation, we describe a maximum posterior parse de- coder for PBDGs in Section 8. The Unfold-Fold transformation is a calculus for transforming functional and logic programs into equivalent but (hopefully) faster programs (Burstall and Darlington, 1977). We use it here to trans- form CFGs encoding dependency grammars into other CFGs that are more efficiently parsable. Since CFGs can be expressed as Horn-clause logic pro- grams (Pereira and Shieber, 1987) and the Unfold- Fold transformation is provably correct for such pro- grams (Sato, 1992; Pettorossi and Proeitti, 1992), it follows that its application to CFGs is provably cor- rect as well. The Unfold-Fold transformation is …

Content truncated to 500 words