From Finite-State to Inversion Transductions: Toward Unsupervised Bilingual Grammar Induction

Proceedings of COLING 2012: Technical Papers, pages 2325–2340, COLING 2012, Mumbai, December 2012. From Finite-State to Inversion Transductions: Toward Unsupervised Bilingual Grammar Induction Markus SAERS Karteek ADDANKI Human Language Technology CenterDekai W U Hong Kong University of Science and Technology, Hong Kong masaers@cs.ust.hk, vskaddanki@cs.ust.hk, dekai@cs.ust.hk ABSTRACT We report a wide range of comparative experiments establishing for the first time contrastive foundations for a completely unsupervised approach to bilingual grammar induction that is cognitively oriented toward early category formation and phrasal chunking in the bootstrap- ping process up the expressiveness hierarchy from finite-state to linear to inversion transduc- tion grammars. We show a consistent improvement in terms of cross-entropy throughout the bootstrapping process, as well as promising decoding experiments using the learned grammars. Rather than relying on external resources such as parses, POS tags or dictionaries, our method is fully unsupervised (in the way this term is typically understood in the machine translation community). This means that the bootstrapping can only rely on information gathered during the previous step, which necessitates some strategy for expanding the expressiveness of the grammars. We present principled approaches for moving from finite-state to linear transduc- tion grammars as well as from linear to inversion transduction grammars. It is our belief that early, integrated category formation and phrasal chunking in this unsupervised bootstrapping process is better aligned to child language acquisition. Finally, we also report exploratory de- coding results using some of the learned grammars. This is the first step towards an end-to-end grammar-based statistical machine translation system. KEYWORDS: Grammar & Formalisms, Empirical machine translation, Multilinguality and Bilingual grammar induction. 2325 Figure1: Bootstrapping paths through the grammar hierarchy along with biparsing time com- plexities of grammar formalisms. 1 Introduction We report a wide range of comparative experiments establishing for the first time contrastive foundations for a completely unsupervised approach to bilingual grammar induction that is cognitively oriented toward early category formation and phrasal chunking in the bootstrap- ping process up the expressiveness hierarchy from finite-state to linear to inversion transduc- tion grammars. In the context of bilingual grammar induction, “unsupervised” means that a transduction gram- mar (or synchronous grammar) is learned without using any external resources such as parses, POS tags, or dictionaries. In contrast, many, if not most, tree-based statistical MT approaches rely on monolingually parsed, chunked, and/or tagged parallel corpora (e.g., Galley et al. (2006)), from which a transduction grammar is extracted. Such approaches must compensate for monolingual analyses that often are not designed optimally for expressing the relation- ship between, say, English and Chinese. Exceptions include the hierarchical phrase-based SMT method of learning ITGs (Chiang, 2005), which does not rely on external resources. However, unlike Chiang (2005) where huge numbers of (linguistically questionable) phrase translations are essentially memorized, our present work aims at inducing syntactic categories at an early stage in the learning, as occurs in child language acquisition. While only time will tell whether our more cognitively motivated approach to the induction of structural and lexical relationships between two languages will lead …

Content truncated to 500 words