Elamur Research⌕
☰
home / papers / 2009 / Dependency Grammar Induction via Bitext Projection Constraints

Dependency Grammar Induction via Bitext Projection Constraints

Paper · 2009 · Kuzman Ganchev, Jennifer Gillenwater and Ben Taskar

Summary

Most languages lack the large annotated treebanks needed to train dependency parsers, but many have parallel text with English, which can be parsed accurately. Ganchev, Gillenwater and Taskar use this asymmetry. They word-align bitext, parse the English side with MSTParser trained on the Penn treebank, and project English dependencies onto Bulgarian and Spanish. Projected trees are often incomplete or wrong because of alignment and parser errors, loose translations and differing annotation conventions. The authors therefore never require a full projected tree. Instead, they use the posterior regularization framework, which asks that the model's expected share of preserved projected edges in each sentence reach a threshold. A handful of language-specific rules, for example how auxiliary verbs are analysed, can be added the same way. They apply this to a generative DMV-style model and to a discriminative edge-factored parser, then evaluate on CoNLL X shared task data. Transfer consistently beats unsupervised induction. With only 2–7 extra rules, the discriminative parser matches supervised parsers trained on roughly 30–140 annotated sentences. This makes cheap, approximate cross-lingual supervision practical for low-resource languages.

Key points

  • How often dependencies survive translation. Off-the-shelf parsers were run on two bitexts (Koehn, 2005; Tiedemann, 2007).
    • English–Bulgarian: 71.9% of projected edges matched the target parse, with about 2.7 projected edges per sentence of 5.3 tokens on average.
    • English–Spanish: 64.4%, with 5.9 projected edges per sentence of 11.5 tokens on average.
  • The core constraint. The expected proportion of preserved projected edges per sentence must be at least η. The authors used η = 0.9, a value chosen with the help of unlabeled data.
  • Generative model (DMV-style). Unsupervised, it peaked at 47.6% on Bulgarian, and that result was unstable across initializations, samples and length limits. Adding the transfer constraints stabilized EM, even from uniform initialization, but accuracy stayed below a parser supervised on 20 sentences.
  • Discriminative parser on Bulgarian. It was trained with 100 iterations of online EM and a Gaussian prior variance of 100.
    • With no rules, it was roughly equivalent to supervision on 10 sentences.
    • Adding two rules (for "da" and verb conjugations) raised it to about 60–70 sentences.
    • A few more rules about closed-class words pushed it beyond 140 sentences.
  • Experimental setup. Training for the transfer models used 10k sentences no longer than 20 words, and testing used CoNLL sentences of up to 10 words. For comparison, the earlier full-projection approach of Hwa et al. (2005) needed dozens of transformation rules.

Interesting ideas

  • I1. Constrain groups of edges in expectation, not each edge individually. Requiring only that most projected edges hold on average lets the model drop noisy ones. This could carry over to other projection tasks with imperfect alignments, such as tags, NER or semantic roles.
  • I2. Use one-sided inequality constraints. The model is penalized only for falling short of the target, not for exceeding it. This suits weak supervision, where the signal gives a lower bound rather than an exact value.
  • I3. Encode annotation-convention mismatches as a few soft rules. Instead of rewriting projected trees with many transformation rules, a few declarative expectation constraints resolve choices like auxiliary attachment. This fits cross-treebank transfer where guidelines differ, for example between UD and older schemes.
  • I4. Keep the constrained model tractable through edge-factored constraint features. Because the constraint features decompose over edges, the constrained distribution has the same form as the original model. Inference therefore reuses standard inside-outside and Eisner algorithms, so the trick plugs into existing parsers cheaply.
  • I5. Report results as supervised-sentence equivalents. Plotting the weakly supervised system against supervised parsers trained on growing numbers of annotated sentences turns accuracy into a concrete annotation cost. This is a useful way to argue the value of a method for low-resource languages.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of PennsylvaniaPhiladelphia · United States170 works · 60,739 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

Cite

Cite as Kuzman Ganchev, Jennifer Gillenwater and Ben Taskar. 2009. Dependency Grammar Induction via Bitext Projection Constraints. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{ganchev2009dependency,
  title = {{Dependency Grammar Induction via Bitext Projection Constraints}},
  author = {Kuzman Ganchev, Jennifer Gillenwater and Ben Taskar},
  booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
  year = {2009},
  doi = {10.3115/1687878.1687931},
  url = {https://doi.org/10.3115/1687878.1687931}
}

References

37 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. A. Abeillé. 2003. Treebanks: Building and Using Parsed Corpora. Springer. find
  2. H. Alshawi, S. Bangalore, and S. Douglas. 2000. Learning dependency translation models as collections of finite state head transducers. Computational Linguistics, 26(1). find
  3. J. Atserias, B. Casas, E. Comelles, M. González, L. Padró, and M. Padró. 2006. Freeling 1.3: Syntactic and semantic services in an open-source nlp library. In Proc. LREC, Genoa, Italy. find
  4. P. F. Brown, S. Della Pietra, V. J. Della Pietra, and R. L. Mercer. 1994. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263–311. find
  5. C. Chelba, D. Engle, F. Jelinek, V. Jimenez, S. Khudanpur, L. Mangu, H. Printz, E. Ristad, R. Rosenfeld, A. Stolcke, and D. Wu. 1997. Structure and performance of a dependency language model. In Proc. Eurospeech. find
  6. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  7. G. Druck, G. Mann, and A. McCallum. 2009. Semi-supervised learning of dependency parsers using generalized expectation criteria. In Proc. ACL. find
  8. J. Eisner. 1996. Three new probabilistic models for dependency parsing: an exploration. In Proc. CoLing.
  9. H. Fox. 2002. Phrasal cohesion and statistical machine translation. In Proc. EMNLP, pages 304–311.
  10. K. Ganchev, J. Graca, J. Blitzer, and B. Taskar. 2008. Multi-view learning over structured and non-identical outputs. In Proc. UAI. find
  11. J. Graça, K. Ganchev, and B. Taskar. 2008. Expectation maximization and posterior constraints. In Proc. NIPS. find
  12. J. Graça, K. Ganchev, and B. Taskar. 2009. Postcat - posterior constrained alignment toolkit. In The Third Machine Translation Marathon. find
  13. A. Haghighi, A. Ng, and C. Manning. 2005. Robust textual inference via graph matching. In Proc. EMNLP. find
  14. R. Hwa, P. Resnik, A. Weinberg, C. Cabezas, and O. Kolak. 2005. Bootstrapping parsers via syntactic projection across parallel texts. Natural Language Engineering, 11:11–311. find
  15. D. Klein and C. Manning. 2004. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Proc. of ACL. find
  16. P. Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In MT Summit. find
  17. S. Lee and K. Choi. 1997. Reestimation and best-first parsing algorithm for probabilistic dependency grammar. In In WVLC-5, pages 41–55. find
  18. G. Mann and A. McCallum. 2007. Simple, robust, scalable semi-supervised learning via expectation regularization. In Proc. ICML. find
  19. G. Mann and A. McCallum. 2008. Generalized expectation criteria for semi-supervised learning of conditional random fields. In Proc. ACL, pages 870 – 878. find
  20. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. ACL, pages 91–98.
  21. I. Mel’čuk. 1988. Dependency syntax: theory and practice. SUNY. inci. find
  22. P. Merlo, S. Stevenson, V. Tsang, and G. Allaria. 2002. A multilingual paradigm for automatic verb classification. In Proc. ACL. find
  23. R. M. Neal and G. E. Hinton. 1998. A new view of the EM algorithm that justifies incremental, sparse and other variants. In M. I. Jordan, editor, Learning in Graphical Models, pages 355–368. Kluwer. find
  24. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. ACL.
  25. J. Nivre, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, and D. Yuret. 2007. find
  26. The CoNLL 2007 shared task on dependency parsing. In Proc. EMNLP-CoNLL.
  27. F. J. Och and H. Ney. 2000. Improved statistical alignment models. In Proc. ACL.
  28. C. Quirk, A. Menezes, and C. Cherry. 2005. Dependency treelet translation: syntactically informed phrasal smt. In Proc. ACL.
  29. L. Shen, J. Xu, and R. Weischedel. 2008. A new string-to-dependency machine translation algorithm with a target dependency language model. In Proc. of ACL.
  30. N. Smith and J. Eisner. 2006. Annealing structural bias in multilingual weighted grammar induction. In Proc. ACL. find
  31. J. Tiedemann. 2007. Building a multilingual parallel subtitle corpus. In Proc. CLIN. find
  32. K. Toutanova, D. Klein, C. Manning, and Y. Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proc. HLT-NAACL.
  33. Y. Tsuruoka and J. Tsujii. 2005. Bidirectional inference with the easiest-first strategy for tagging sequence data. In Proc. HLT/EMNLP.
  34. H. Yamada and Y. Matsumoto. 2003a. Statistical dependency analysis with support vector machines. In Proc. IWPT, pages 195–206.
  35. H. Yamada and Y. Matsumoto. 2003b. Statistical dependency analysis with support vector machines. In Proc. IWPT.
  36. D. Yarowsky and G. Ngai. 2001. Inducing multilingual pos taggers and np bracketers via robust projection across aligned corpora. In Proc. NAACL. find
  37. D. Yarowsky, G. Ngai, and R. Wicentowski. 2001. Inducing multilingual text analysis tools via robust projection across aligned corpora. In Proc. HLT.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ganchev-2009-dependency-grammar-induction-bitext-projection/