Unsupervised Multilingual Grammar Induction

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 73–81, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Unsupervised Multilingual Grammar Induction Benjamin Snyder, Tahira Naseem, and Regina Barzilay Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {bsnyder, tahira, regina}@csail.mit.edu Abstract We investigate the task of unsupervised constituency parsing from bilingual par- allel corpora. Our goal is to use bilin- gual cues to learn improved parsing mod- els for each language and to evaluate these models on held-out monolingual test data. We formulate a generative Bayesian model which seeks to explain the observed par- allel data through a combination of bilin- gual and monolingual parameters. To this end, we adapt a formalism known as un- ordered tree alignment to our probabilistic setting. Using this formalism, our model loosely binds parallel trees while allow- ing language-specific syntactic structure. We perform inference under this model us- ing Markov Chain Monte Carlo and dy- namic programming. Applying this model to three parallel corpora (Korean-English, Urdu-English, and Chinese-English) we find substantial performance gains over the CCM model, a strong monolingual baseline. On average, across a variety of testing scenarios, our model achieves an 8.8 absolute gain in F-measure. 1 1 Introduction In this paper we investigate the task of unsuper- vised constituency parsing when bilingual paral- lel text is available. Our goal is to improve pars- ing performance on monolingual test data for each language by using unsupervised bilingual cues at training time. Multilingual learning has been suc- cessful for other linguistic induction tasks such as lexicon acquisition, morphological segmentation, and part-of-speech tagging (Genzel, 2005; Snyder and Barzilay, 2008; Snyder et al., 2008; Snyder 1Code and the outputs of our experiments are available at http://groups.csail.mit.edu/rbg/code/multiling induction. et al., 2009). We focus here on the unsupervised induction of unlabeled constituency brackets. This task has been extensively studied in a monolingual setting and has proven to be difficult (Charniak and Carroll, 1992; Klein and Manning, 2002). The key premise of our approach is that am- biguous syntactic structures in one language may correspond to less uncertain structures in the other language. For instance, the English sentence I saw [the student [from MIT]] exhibits the classic problem of PP-attachment ambiguity. However, its Urdu translation, literally glossed as I [[MIT of] student] saw, uses a genitive phrase that may only be attached to the adjacent noun phrase. Know- ing the correspondence between these sentences should help us resolve the English ambiguity. One of the main challenges of unsupervised multilingual learning is to exploit cross-lingual patterns discovered in data, while still allowing a wide range of language-specific idiosyncrasies. To this end, we adapt a formalism known as un- ordered tree alignment (Jiang et al., 1995) to a probabilistic setting. Under this formalism, any two trees can be embedded in an alignment tree. This alignment tree allows arbitrary parts of the two trees to diverge in structure, permitting language-specific grammatical structure to be pre- served. Additionally, a computational advantage …

Content truncated to 500 words