Rule Extraction for Tree-to-Tree Transducers by Cost Minimization

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 12–22, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Rule Extraction for Tree-to-Tree Transducers by Cost Minimization Pascual Mart´ınez-G´omez1 pascual.mg@aist.go.jp Yusuke Miyao1,2,3 yusuke@nii.ac.jp 1Artificial Intelligence Research Center, AIST 2National Institute of Informatics and JST, PRESTO 3The Graduate University for Advanced Studies (SOKENDAI) Tokyo, Japan Abstract Tree transducers that model expressive linguistic phenomena often require word- alignments and a heuristic rule extractor to induce their grammars. However, when the corpus of tree/string pairs is small compared to the size of the vocabulary or the com- plexity of the grammar, word-alignments are unreliable. We propose a general rule extraction algorithm that uses cost functions over tree fragments, and formulate the extrac- tion as a cost minimization problem. As a by-product, we are able to introduce back-off states at which some cost functions generate right-hand-sides of previously unseen left- hand-sides, thus creating transducer rules “on-the-fly”. We test the generalization power of our induced tree transducers on a QA task over a large Knowledge Base, obtaining a reasonable syntactic accuracy and effectively overcoming the typical lack of rule coverage. 1 Introduction Tree transducers are general and solid theoreti- cal models that have been applied to a variety of NLP tasks, such as machine translation (Knight and Graehl, 2005), text summarization (Cohn and Lap- ata, 2009), question answering (Jones et al., 2012), paraphrasing and textual entailment (Wu, 2005). One strategy to obtain transducer rules is by exhaus- tive enumeration; however, this method is ineffec- tive when there is a high structural language vari- ability and we wish to have an expressive model. Another strategy is to heuristically extract rules from a corpus of tree/string pairs and word-alignments, as GHKM algorithm does (Galley et al., 2004); how- ever, word-alignments are difficult to estimate when the corpus is small. This would be the case, for ex- ample, of machine translation for low-resourced lan- guages where there is often small numbers of paral- lel sentences, or in Question Answering (QA) tasks where the number of Knowledge Base (KB) identi- fiers (concepts) is much larger than QA datasets. Our main contribution is an algorithm that formu- lates the rule extraction as a cost minimization prob- lem, where the search for the best rules is guided by an ensemble of cost functions over pairs of tree fragments. In GHKM, a tree fragment and a se- quence of words are extracted together if they are minimal and their word alignments do not fall out- side of their respective boundaries. However, given that alignment violations are not allowed, the qual- ity of the extracted rules degrades as the rate of misaligned words increases. In our framework, we can mimic GHKM by assigning an infinite cost to pairs of tree fragments that violate such conditions on word alignments and by adding a cost regular- izer on the size of the tree fragments. Smoother cost functions, however, would permit controlled mis- alignments, contributing to generalization. Given the generality of …

Content truncated to 500 words