Elamur Research⌕
☰
home / papers / 2010 / Using Universal Linguistic Knowledge to Guide Grammar Induction

Using Universal Linguistic Knowledge to Guide Grammar Induction

Paper · 2010 · Tahira Naseem, Harr Chen, Regina Barzilay et al.

Summary

Unsupervised dependency parsers often converge on structures that fit the data but are not linguistically sensible. Naseem, Chen, Barzilay and Johnson address this by injecting a small amount of cross-linguistic knowledge. They hand-write a compact set of head-dependent rules over coarse part-of-speech categories, such as verbs governing nouns or prepositions governing nouns. These rules are intended to hold across languages. Their generative Bayesian model, HDP-DEP, resembles the DMV. It can also split each coarse tag into finer language-specific subcategories using a Hierarchical Dirichlet Process. During variational inference, posterior regularization requires that a minimum share of the predicted dependencies match the universal rules. Because this holds only in expectation, language-specific exceptions remain possible. Across six Indo-European languages (English, Danish, Portuguese, Slovene, Spanish, Swedish), the method clearly beats state-of-the-art unsupervised parsers, including Headden III et al. (2009) and Berg-Kirkpatrick and Klein (2010). The result matters because it shows that cheap, reusable linguistic priors can substitute for annotated treebanks, which is especially relevant for low-resource languages.

Key points

  • The universal ruleset in Table 1 has only 13 rules over coarse categories, for example Root → Verb, Auxiliary → Verb, Noun → Adjective and Preposition → Noun.
  • A single expected-proportion threshold for rule-consistent dependencies is shared by all languages. Values roughly between 75% and 90% work well. Setting each language's threshold to its true gold proportion was not optimal.
  • On WSJ English, replacing the universal rules with English-specific rules gains 1.9% on short sentences (≤10 words) and 15.7% on longer ones. Removing all rules makes performance drop substantially.
  • HDP-DEP beats a deterministic parser that applies the same English rules by 3.8% (≤10 words) and 3.5% (≤20 words). With the 20 rules of Druck et al. (2009), it reaches 64.9% versus 61.3% for their generalized expectation approach.
  • Results are far more consistent over five random initializations than those of the baselines: HDP-DEP's standard deviation is 1.5%, compared with 8.0% for DMV and 4.5% for the system of Headden III et al. (2009).

Interesting ideas

  • I1. Soft constraints in expectation: The rules only have to cover a minimum share of the predicted structure rather than every case. This lets a model absorb prior knowledge without breaking on legitimate exceptions, and it transfers to any structured prediction task with imperfect rules.
  • I2. One knob instead of many: A single global constraint parameter replaces a separate expected value for each rule. This makes the approach portable to new languages or domains without corpus-specific tuning.
  • I3. Rules make latent refinement learnable: Splitting coarse tags into finer clusters fails in a fully unsupervised setup but succeeds once the rules steer the search. This suggests that weak structural guidance can unlock richer latent-variable models that otherwise wander.
  • I4. Compare against the rules themselves: Evaluating against a deterministic parser built from the same rules checks whether the model learns anything beyond its supervision. This is a useful sanity test for any rule-guided learner.
  • I5. Report variance over random restarts: Measuring spread across initializations shows how constraints stabilize training. This is a cheap and informative addition when evaluating unsupervised or weakly supervised systems.

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

🎓Massachusetts Institute of TechnologyCambridge · United States159 works · 65,157 citations🎓Macquarie UniversitySydney · Australia17 works · 4,827 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 Tahira Naseem, Harr Chen, Regina Barzilay and Mark Johnson. 2010. Using Universal Linguistic Knowledge to Guide Grammar Induction. Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing.

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

@inproceedings{naseem2010using,
  title = {{Using Universal Linguistic Knowledge to Guide Grammar Induction}},
  author = {Tahira Naseem, Harr Chen, Regina Barzilay and Mark Johnson},
  booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing},
  year = {2010},
  url = {https://aclanthology.org/D10-1120/}
}

References

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

  1. Mark C. Baker. 2001. The Atoms of Language: The Mind’s Hidden Rules of Grammar. Basic Books. find
  2. Emily M. Bender. 2009. Linguistically naı̈ve != language independent: Why NLP needs linguistic typology. In Proceedings of the EACL 2009 Workshop on the Interaction between Linguistics and Computational Linguistics: Virtuous, Vicious or Vacuous?, pages 26–32. find
  3. Taylor Berg-Kirkpatrick and Dan Klein. 2010. Phylogenetic grammar induction. In Proceedings of ACL, pages 1288–1297. find
  4. Christopher M. Bishop. 2006. Pattern Recognition and Machine Learning. Information Science and Statistics. Springer. find
  5. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of CoNLL, pages 149–164.
  6. David Burkett and Dan Klein. 2008. Two languages are better than one (for syntactic parsing). In Proceedings of EMNLP, pages 877–886. find
  7. Andrew Carnie. 2002. Syntax: A Generative Introduction (Introducing Linguistics). Blackwell Publishing. find
  8. Ming-Wei Chang, Lev Ratinov, and Dan Roth. 2007. Guiding semi-supervision with constraint-driven learning. In Proceedings of ACL, pages 280– 287. find
  9. Shay B. Cohen and Noah A. Smith. 2009a. Shared logistic normal distributions for soft parameter tying in unsupervised grammar induction. In Proceedings of NAACL/HLT, pages 74–82.
  10. Shay B. Cohen and Noah A. Smith. 2009b. Variational inference for grammar induction with prior knowledge. In Proceedings of ACL/IJCNLP 2009 Conference Short Papers, pages 1–4. find
  11. Michael Collins. 1999. Head-driven statistical models for natural language parsing. Ph.D. thesis, University of Pennsylvania. find
  12. Hal Daumé III and Lyle Campbell. 2007. A bayesian model for discovering typological implications. In Proceedings of ACL, pages 65–72. find
  13. Gregory Druck, Gideon Mann, and Andrew McCallum. 2009. Semi-supervised learning of dependency parsers using generalized expectation criteria. In Proceedings of ACL/IJCNLP, pages 360–368. find
  14. Thomas S. Ferguson. 1973. A bayesian analysis of some nonparametric problems. Annals of Statistics, 1(2):209–230. find
  15. Jenny Rose Finkel, Trond Grenager, and Christopher D. Manning. 2007. The infinite tree. In Proceedings of ACL, pages 272–279. find
  16. Kuzman Ganchev, Jennifer Gillenwater, and Ben Taskar. 2009. Dependency grammar induction via bitext projection constraints. In Proceedings of ACL/IJCNLP, pages 369–377.
  17. Kuzman Ganchev, João Graça, Jennifer Gillenwater, and Ben Taskar. 2010. Posterior regularization for structured latent variable models. Journal of Machine Learning Research, 11:2001–2049. find
  18. João Graça, Kuzman Ganchev, Ben Taskar, and Fernando Pereira. 2009. Posterior vs. parameter sparsity in latent variable models. In Advances in NIPS, pages 664– 672. find
  19. João Graça, Kuzman Ganchev, and Ben Taskar. 2007. Expectation maximization and posterior constraints. In Advances in NIPS, pages 569–576. find
  20. Aria Haghighi and Dan Klein. 2006. Prototype-driven grammar induction. In Proceedings of ACL, pages 881–888. find
  21. William P. Headden III, Mark Johnson, and David Mc-Closky. 2009. Improving unsupervised dependency parsing with richer contexts and smoothing. In Proceedings of NAACL/HLT, pages 101–109. find
  22. Dan Klein and Christopher Manning. 2004. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Proceedings of ACL, pages 478–485. find
  23. Jonas Kuhn. 2004. Experiments in parallel-text based grammar induction. In Proceedings of ACL, pages 470–477. find
  24. Percy Liang, Slav Petrov, Michael Jordan, and Dan Klein. 2007. The infinite PCFG using hierarchical Dirichlet processes. In Proceedings of EMNLP/CoNLL, pages 688–697. find
  25. Percy Liang, Michael I. Jordan, and Dan Klein. 2009a. Learning from measurements in exponential families. In Proceedings of ICML, pages 641–648. find
  26. Percy Liang, Michael I. Jordan, and Dan Klein. 2009b. Probabilistic grammars and hierarchical Dirichlet processes. The Handbook of Applied Bayesian Analysis. find
  27. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of english: The penn treebank. Computational Linguistics, 19(2):313–330.
  28. Frederick J. Newmeyer. 2005. Possible and Probable Languages: A Generative Perspective on Linguistic Typology. Oxford University Press. find
  29. Slav Petrov and Dan Klein. 2007. Learning and inference for hierarchically split PCFGs. In Proceeding of AAAI, pages 1663–1666. find
  30. Benjamin Snyder, Tahira Naseem, and Regina Barzilay. 2009. Unsupervised multilingual grammar induction. In Proceedings of ACL/IJCNLP, pages 73–81. find
  31. Lydia White. 2003. Second Language Acquisition and Universal Grammar. Cambridge University Press. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/naseem-2010-universal-linguistic-knowledge-guide-grammar/