Enlarged Search Space for SITG Parsing

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 653–656, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Enlarged Search Space for SITG Parsing Guillem Gascó, Joan-Andreu Sánchez, José-Miguel Benedí Institut Tecnològic d’Informàtica, Universitat Politècnica de València Camí de Vera s/n, València, 46022, Spain ggasco@iti.upv.es , {jandreu,jbenedi}@dsic.upv.es Abstract Stochastic Inversion Transduction Grammars constitute a powerful formalism in Machine Translation for which an efficient Dynamic Programming parsing algorithm exists. In this work, we review this parsing algorithm and propose important modifications that enlarge the search space. These modifications allow the parsing algorithm to search for more and better solutions. 1 Introduction Syntax Machine Translation has received great at- tention in the last few years, especially for pairs of languages that are sufficiently non-monotonic. Sev- eral works have explored the use of syntax for Ma- chine Translation (Wu, 1997; Chiang, 2007). In (Wu, 1997), Stochastic Inverse Transduction Gram- mars (SITGs) were introduced for describing struc- turally correlated pairs of languages. SITGs can be used to simultaneously analyze two strings from dif- ferent languages and to correlate them. An efficient Dynamic Programming parsing algorithm for SITGs was presented in (Wu, 1997). This algorithm is sim- ilar to the CKY algorithm for Probabilistic Context Free Grammars. The parsing algorithm does not al- low the association of two items that have the empty string in one of their sides. This limitation restricts the search space and prevents the algorithm from ex- ploring some valid parse trees. In this paper, we review Wu’s parsing algorithm for SITGs (referred to as the original algorithm) and propose some modifications to increase the search space in order to make it possible to find these valid parse trees. 2 SITG Parsing SITGs (Wu, 1997) can be viewed as a restricted subset of Stochastic Syntax-Directed Transduction Grammars (Maryanski and Thomason, 1979). For- mally, a SITG in Chomsky Normal Form can be defined as a set of lexical rules that are noted as A → x/ǫ, A → ǫ/y, A → x/y; direct syntac- tic rules that are noted as A → [BC]; and inverse syntactic rules that are noted as A → ⟨BC⟩, where A, B, C are non-terminal symbols, x, y are terminal symbols, ǫ is the empty string, and each rule has a probability value p attached. The sum of the proba- bilities of the rules with the same non-terminal in the left side must be equal to 1. When a direct syntactic rule is used in parsing, both strings are parsed with the syntactic rule A → BC. When an inverse rule is used in parsing, one string is parsed with the syntac- tic rule A → BC, and the other string is parsed with the syntactic rule A → CB. An efficient Viterbi-like parsing algorithm that is based on a Dynamic Programming Scheme was pro- posed in (Wu, 1997). It allows us to obtain the most probable parse tree that simultaneously analyzes two strings, X = x1...x|X| and …

Content truncated to 500 words