Segmenting vs. Chunking Rules: Unsupervised ITG Induction via Minimum Conditional Description Length

Proceedings of Recent Advances in Natural Language Processing, pages 584–592, Hissar, Bulgaria, 7-13 September 2013. Segmenting vs. Chunking Rules: Unsupervised ITG Induction via Minimum Conditional Description Length Markus SAERS and Karteek ADDANKI and Dekai WU Human Language Technology Center Dept. of Computer Science and Engineering Hong Kong University of Science and Technology {masaers|vskaddanki|dekai}@cs.ust.hk Abstract We present an unsupervised learning model that induces phrasal inversion transduction grammars by introducing a minimum conditional description length (CDL) principle to drive search over a space defined by two opposing extreme types of ITGs. Our approach attacks the difficulty of acquiring more complex longer rules when inducing inversion transduction grammars via unsupervised bottom-up chunking, by augmenting its model search with top-down segmentation that minimizes CDL, resulting in signifi- cant translation accuracy gains. Chunked rules tend to be relatively short; long rules are hard to learn through chunking, as the smaller parts of the long rules may not necessarily be good translations themselves. Our objective criterion is a conditional adaptation of the notion of description length, that is conditioned on a fixed preexisting model, in this case the initial chunked ITG. The notion of minimum CDL (MCDL) facilitates a novel strategy for avoiding the pitfalls of premature pruning in chunking ap- proaches, by incrementally splitting an ITG with reference to a second ITG that conditions this search. 1 Introduction We describe an unsupervised approach to induc- ing phrasal inversion transduction grammars or ITGs (Wu, 1997) that employs a new theoretically well-founded minimum conditional description length (CDL) objective to explicitly drive two op- posing, extreme ITGs towards one single ITG. Given one ITG initially composed of short rules learned by bottom-up chunking of short atomic rules, our method augments it with rules that are learned through top-down segmentation of long rules initialized by memorizing the parallel cor- pus. This offers an opportunity to capture longer non-compositional translations as explicit bitermi- nal rules, which is hard for search to discover solely via bottom-up chunking. Iterative bottom- up chunking relies on composing two good trans- lations into a longer good translation, which as- sumes that the long rules learned in this way are compositional. In contrast, iteratively segment- ing an existing good translation into shorter good translations does not depend on assumptions about whether the resulting shorter rules can be further decomposed. Empirically, augmenting the chun- ked ITG with rules learned via top-down segmen- tation helps translation quality. However, the max- imum likelihood objective is inadequate for this purpose; instead, we introduce the minimum con- ditional description length (MCDL) objective to drive the search for phrasal rules simultaneously from the two opposing types of ITG constraints, both of which have individually been empirically demonstrated to match phrase reordering patterns across translations well. In so doing, we aim to also provide an obvious basis for generalization to abstract translation schemas. The necessity of MCDL as an alternative learn- ing objective to standard maximum likelihood (ML) arises because the top-down rule segmen- tation search starts in a state where likelihood is …

Content truncated to 500 words