Elamur Research⌕
☰
home / papers / 2018 / Surface Statistics of an Unknown Language Indicate How to Parse It

Surface Statistics of an Unknown Language Indicate How to Parse It

Paper · 2018 · Dingquan Wang and Jason Eisner

Summary

The paper asks whether an unparsed corpus of gold POS-tag sequences holds enough information to parse a language that has no treebank. Instead of classic grammar induction, which suffers from local optima and from likelihood objectives that track linguistic analyses poorly, Wang and Eisner frame unsupervised parsing as a supervised problem at the level of whole languages. A delexicalized neural dependency parser receives a learned summary T(u) of the target corpus's surface statistics. The parser and the feature extractor are trained jointly on many languages with treebanks, so the system learns to adapt its scoring to a new language from raw POS sequences alone. Training uses real UD treebanks plus synthetic Galactic Dependencies languages, which are made by systematically reordering subtrees. On held-out languages, the corpus-derived features raise attachment scores, and adding synthetic data raises them further. The learned features also beat earlier typological features, which need parsed data or expert input. This shows that surface word-order statistics carry real syntactic signal and that synthetic languages are useful training material for multilingual NLP.

Key points

  • Data: UD v1.2 (37 treebanks, 33 languages) and GD v1.0, a set of 53,428 synthetic treebanks built by permuting noun and verb dependents of UD trees. A subset of GD was used. The languages were split into 16 development languages (5-fold cross-validation) and 15 test languages.
  • Model: the corpus features T(u) are fed into a neural parser (the H+N system), reimplemented in PyTorch from the Kiperwasser and Goldberg (2016) code. The target language itself provides no supervision.
  • Test averages: compared with the McDonald et al. (2011) baseline, UAS rose from 60.97 to 64.55 with T(u) and to 67.11 with GD added. LAS rose from 43.09 to 47.00 and then 48.74.
  • Comparison with past work: the best method's average gain was 5.6 points relative to McDonald et al. (2011), and 20.7 points relative to the grammar-induction approach of Naseem et al. (2010).
  • Largest gains: some languages benefited most from GD, e.g. Persian (LAS 30.06 → 47.14) and Hindi (LAS 18.63 → 41.12). The paper also includes an experiment with noisy POS tags.

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

🎓Johns Hopkins UniversityBaltimore · United States240 works · 96,487 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Dingquan Wang and Jason Eisner. 2018. Surface Statistics of an Unknown Language Indicate How to Parse It. Transactions of the Association for Computational Linguistics.

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

@article{wang2018surface,
  title = {{Surface Statistics of an Unknown Language Indicate How to Parse It}},
  author = {Dingquan Wang and Jason Eisner},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2018},
  doi = {10.1162/tacl\_a\_00248},
  url = {https://doi.org/10.1162/tacl_a_00248}
}

References

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

  1. Timothy Dozat and Christopher D. Manning. 2017. Deep biaffine attention for neural dependency parsing. In Proceedings of the International Conference on Learning Representations.
  2. Željko Agić, Anders Johannsen, Barbara Plank, Héctor Martínez Alonso, Natalie Schluter, and Anders Søgaard. 2016. Multilingual projection for parsing truly low-resource languages. Transactions of the Association for Computational Linguistics, 4:301–312.
  3. Matthew S. Dryer and Martin Haspelmath, editors. 2013. The World Atlas of Language Structures Online. Max Planck Institute for Evolutionary Anthropology. http://wals.info/. ↗
  4. Waleed Ammar, George Mulcaire, Miguel Ballesteros, Chris Dyer, and Noah Smith. 2016. Many languages, one parser. Transactions of the Association of Computational Linguistics, 4:431– 444.
  5. Jack Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards B, 71(4):233–240. find
  6. Sumit Basu, Chuck Jacobs, and Lucy Vanderwende. 2013. Powergrading: A clustering approach to amplify human effort for short answer grading. Transactions of the Association for Computational Linguistics, 1:391–402. find
  7. Jason Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of the 16th International Conference on Computational Linguistics, pages 340– 345.
  8. Glenn Carroll and Eugene Charniak. 1992. Two experiments on learning probabilistic dependency grammars from corpora. In Working Notes of the Workshop on Statistically-Based NLP Techniques, pages 1–13. find
  9. Jason Eisner and Damianos Karakos. 2005. Bootstrapping without the boot. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 395–402. find
  10. Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014. On the properties of neural machine translation: Encoder-decoder approaches. In Proceedings of Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation, pages 103– 111.
  11. Jason Eisner and Dingquan Wang. No date. On evaluating cross-lingual generalization. To be posted on arXiv. find
  12. Noam Chomsky. 1965. Aspects of the Theory of Syntax. MIT Press, Cambridge, MA. find
  13. Kuzman Ganchev, Jennifer Gillenwater, and Ben Taskar. 2009. Dependency grammar induction Robert Frank and Shyam Kapur. 1996. On the use of triggers in parameter setting. Linguistic Inquiry, 27:623–660. dependency parsing with richer contexts and smoothing. In Proceedings of Human Language Technologi… find
  14. Edward Gibson and Kenneth Wexler. 1994. Triggers. Linguistic Inquiry, 25(3):407–454. find
  15. Rebecca Hwa, Philip Resnik, Amy Weinberg, Clara Cabezas, and Okan Kolak. 2005. Bootstrapping parsers via syntactic projection across parallel texts. Natural Language Engineering, 11(3):311–325. find
  16. Jennifer Gillenwater, Kuzman Ganchev, João Gra ca, Fernando Pereira, and Ben Taskar. 2010. Sparsity in dependency grammar induction. In Proceedings of the ACL 2010 Conference Short Papers, pages 194–199. find
  17. Yong Jiang, Wenjuan Han, and Kewei Tu. 2017. Combining generative and discriminative approaches to unsupervised dependency parsing via dual decomposition. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1689–1694. find
  18. Kevin Gimpel and Noah A. Smith. 2012. Concavity and initialization for unsupervised dependency parsing. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 577–581. find
  19. Damianos Karakos, Jason Eisner, Sanjeev Khudanpur, and Carey E. Priebe. 2007. Cross-instance tuning of unsupervised document clustering algorithms. In Human Language Technologies: Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics, pag… find
  20. Xavier Glorot and Yoshua Bengio. 2010. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 9, pages 249–256. find
  21. Matthew Gormley and Jason Eisner. 2013. Non-convex global optimization for latent-variable models. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 444–454. find
  22. Joo-Kyung Kim, Young-Bum Kim, Ruhi Sarikaya, and Eric Fosler-Lussier. 2017. Cross-lingual transfer learning for POS tagging without cross-lingual resources. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2832–2838. find
  23. Edouard Grave and Noémie Elhadad. 2015. A convex and feature-rich discriminative approach to dependency grammar induction. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1375–… find
  24. Diederik Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the International Conference on Learning Representations.
  25. Alex Graves. 2012. Supervised Sequence Labelling with Recurrent Neural Networks. Springer. find
  26. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional LSTM feature representations. Transactions of the Association of Computational Linguistics, 4:313–327.
  27. Jiang Guo, Wanxiang Che, David Yarowsky, Haifeng Wang, and Ting Liu. 2016. A representation learning framework for multi-source transfer parsing. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 2734–2740. find
  28. Dan Klein and Christopher Manning. 2004. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, pages 478–485. find
  29. William P. Headden III, Mark Johnson, and David McClosky. 2009. Improving unsupervised Sandra Kübler, Ryan McDonald, and Joakim Nivre. 2009. Dependency Parsing. Morgan and Claypool. ceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Lo… find
  30. Ophélie Lacroix, Lauriane Aufrant, Guillaume Wisniewski, and François Yvon. 2016. Frustratingly easy cross-lingual transfer for transition-based dependency parsing. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Te… find
  31. Ryan McDonald. 2006. Discriminative Learning and Spanning Tree Algorithms for Dependency Parsing. Ph.D. thesis, University of Pennsylvania. find
  32. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 91–98.
  33. Karim Lari and Steve J. Young. 1990. The estimation of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech and Language, 4(1):35–56. find
  34. Ryan McDonald, Slav Petrov, and Keith Hall. 2011. Multi-source transfer of delexicalized dependency parsers. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 62–72.
  35. Yann LeCun, Sumit Chopra, Raia Hadsell, and Fu Jie Huang. 2007. A tutorial on energy-based learning. In Gökhan Bakır, Thomas Hofmann, Bernhard Schölkopf, Alexander J. Smola, Ben Taskar, and S. V. N. Vishwanathan, editors, Predicting Structured Data. MIT Press. find
  36. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, pages 3111–3119.
  37. Haitao Liu. 2010. Dependency direction as a means of word-order typology: A method based on dependency treebanks. Lingua, 120(6):1567–1578. find
  38. Tahira Naseem, Regina Barzilay, and Amir Globerson. 2012. Selective sharing for multilingual dependency parsing. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, pages 629–637.
  39. David Mareček. 2016. Delexicalized and minimally supervised parsing on universal dependencies. In Statistical Language and Speech Processing: 4th International Conference, SLSP 2016, Pilsen, Czech Republic, October 11-12, 2016, Proceedings, pages 30–42, Cham. find
  40. Tahira Naseem, Harr Chen, Regina Barzilay, and Mark Johnson. 2010. Using universal linguistic knowledge to guide grammar induction. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1234–1244.
  41. David Mareček and Milan Straka. 2013. Stop-probability estimates computed on a large corpus improve unsupervised dependency parsing. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 281–290. find
  42. Dat Quoc Nguyen, Dai Quoc Nguyen, Dang Duc Pham, and Son Bao Pham. 2014. RDRPOSTagger: A ripple down rules-based part-of-speech tagger. In Proceedings of the Demonstrations at the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 17–20. find
  43. David Mareček. 2016. Twelve years of unsupervised dependency parsing. In Proceedings of the 16th ITAT Conference Information Technologies—Applications and Theory, pages 56–62. find
  44. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553.
  45. Héctor Martínez Alonso, Željko Agić, Barbara Plank, and Anders Søgaard. 2017. Parsing universal dependencies without training. In Pro-Joakim Nivre, Željko Agić, Maria Jesus Aranzabe, Masayuki Asahara, Aitziber Atutxa, Miguel Ballesteros, John Bauer, Kepa Bengoetxea, Riyaz Ahmad Bhat, Cristina Bosc… find
  46. Mohammad Sadegh Rasooli and Michael Collins. 2015. Density-driven cross-lingual transfer of dependency parsers. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 328–338. find
  47. Hiroshi Noji, Yusuke Miyao, and Mark Johnson. 2016. Using left-corner parsing to encode universal structural constraints in grammar induction. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 33–43. find
  48. Noah A. Smith. 2006. Novel Estimation Methods for Unsupervised Discovery of Latent Structure in Natural Language Text. Ph.D. thesis, Johns Hopkins University. find
  49. Mohammad Sadegh Rasooli and Michael Collins. 2017. Cross-lingual syntactic transfer with limited resources. Transactions of the Association for Computational Linguistics, 5:279–293. find
  50. Rudolf Rosa and Zdeněk Žabokrtský. 2015a. KL cpos 3 – a language similarity measure for delexicalized parser transfer. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 243–249. find
  51. Rudolf Rosa and Zdeněk Žabokrtský. 2015b. Mstparser model interpolation for multi-source delexicalized transfer. In Proceedings of the 14th International Conference on Parsing Technologies, pages 71–75. find
  52. Sebastian Ruder, Ivan Vulić, and Anders Søgaard. 2017. A survey of cross-lingual word embedding models. Computing Research Repository, arXiv:1706.04902. find
  53. David A. Smith and Jason Eisner. 2009. Parser adaptation and projection with quasi-synchronous grammar features. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 822–831. find
  54. Noah A. Smith and Jason Eisner. 2005. Guiding unsupervised grammar induction using contrastive estimation. In International Joint Conference on Artificial Intelligence (IJCAI) Workshop on Grammatical Inference Applications, pages 73–82. find
  55. Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the Web. Technical Report 1999-66, Stanford InfoLab.
  56. Noah A. Smith and Jason Eisner. 2006. Annealing structural bias in multilingual weighted grammar induction. In Proceedings of the International Conference on Computational Linguistics and the Association for Computational Linguistics, pages 569–576. find
  57. Mark A. Paskin. 2001. Cubic-time parsing and learning algorithms for grammatical bigram. find
  58. Mark A. Paskin. 2002. Grammatical bigrams. In Advances in Neural Information Processing Systems, pages 91–97. find
  59. Valentin I. Spitkovsky, Hiyan Alshawi, and Daniel Jurafsky. 2012. Three dependency-and-boundary models for grammar induction. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 688–698. find
  60. Dingquan Wang and Jason Eisner. 2016. The Galactic Dependencies treebanks: Getting more data by synthesizing new languages. Transactions of the Association of Computational Linguistics, 4:491–505. Data available at https://github.com/gdtreebank/ gdtreebank. ↗
  61. Valentin I. Spitkovsky, Hiyan Alshawi, and Daniel Jurafsky. 2013. Breaking out of local optima with count transforms and model recombination: A study in grammar induction. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1983–1995. find
  62. Dingquan Wang and Jason Eisner. 2017. Fine-grained prediction of syntactic typology: Discovering latent structure with supervised learning. Transactions of the Association for Computational Linguistics, 5:147–161.
  63. Dingquan Wang and Jason Eisner. 2018. Synthetic data made to order: The case of parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1325–1337, Brussels. find
  64. Oscar Täckström, Dipanjan Das, Slav Petrov, Ryan McDonald, and Joakim Nivre. 2013a. Token and type constraints for cross-lingual part-of-speech tagging. Transactions of the Association for Computational Linguistics, 1:1–12. find
  65. Qin Iris Wang, Dale Schuurmans, and Dekang Lin. 2008. Semi-supervised convex training for dependency parsing. In Proceedings of the 46th Annual Meeting of Annual Meeting of the Association for Computational Linguistics and the 2008 Conference of the North American Chapter of the Association for Comp… find
  66. Oscar Täckström, Ryan McDonald, and Joakim Nivre. 2013b. Target language adaptation of discriminative transfer parsers. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1061–1071.
  67. David Yarowsky, Grace Ngai, and Richard Wicentowski. 2001. Inducing multilingual text analysis tools via robust projection across aligned corpora. In Proceedings of the First International Conference on Human Language Technology Research.
  68. Ben Taskar, Vassil Chatalbashev, Daphne Koller, and Carlos Guestrin. 2005. Learning structured prediction models: A large margin approach. In Proceedings of the 22nd International Conference on Machine Learning, pages 896–903. find
  69. Ben Taskar, Dan Klein, Michael Collins, Daphne Koller, and Christopher Manning. 2004. Max-margin parsing. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing. find
  70. Deniz Yuret. 1998. Discovery of Linguistic Relations Using Lexical Attraction. Ph.D. thesis, Massachusetts Institute of Technology. find
  71. Yuan Zhang and Regina Barzilay. 2015. Hierarchical low-rank tensors for multilingual transfer parsing. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1857–1867.
  72. Jörg Tiedemann. 2014. Rediscovering annotation projection for cross-lingual parser induction. In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 1854–1864. find
  73. Jörg Tiedemann, Željko Agić, and Joakim Nivre. 2014. Treebank translation for cross-lingual parser induction. In Proceedings of the Eighteenth Conference on Computational Natural Language Learning, pages 130–140. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wang-2018-surface-statistics-unknown-language-indicate/