tailieunhanh - Báo cáo khoa học: "Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold"

This paper shows how to use the UnfoldFold transformation to transform Projective Bilexical Dependency Grammars (PBDGs) into ambiguity-preserving weakly equivalent 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 algorithm. This transformation makes all of the techniques developed for CFGs available to PBDGs. . | Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold Mark Johnson Microsoft Research Redmond WA t-majoh@ Brown University Providence RI Mark_Johnson@Brown. edu Abstract This paper shows how to use the UnfoldFold transformation to transform Projective Bilexical Dependency Grammars PBDGs into ambiguity-preserving weakly equivalent 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 algorithm. This transformation makes all of the techniques developed for CFGs available to PBDGs. We demonstrate this by describing a maximum posterior parse decoder for PBDGs. 1 Introduction Projective Bilexical Dependency Grammars PB-DGs have attracted attention recently for two reasons. 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 accuracy of the very best statistical parsers available today 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 McDonald 2006 McDonald and Pereira 2006 . Specifically we show how to use an off-line preprocessing 168 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 . there is a one-to-one mapping between .