Elamur Research⌕
☰
home / papers / 2016 / Morpho-syntactic Lexicon Generation Using Graph-based Semi-supervised Learning

Morpho-syntactic Lexicon Generation Using Graph-based Semi-supervised Learning

Paper · 2016 · Manaal Faruqui, Ryan McDonald and Radu Soricut

Summary

Morpho-syntactic lexicons record which grammatical attributes (part of speech, tense, number, etc.) each word can carry. They are expensive to build by hand, exist for few languages, and are usually small. Faruqui, McDonald and Soricut treat lexicon creation as graph-based semi-supervised learning. Word types are nodes, and a small annotated seed lexicon labels some of them. Edges link words that share an unsupervised word cluster, a short prefix or suffix, or a morphological transformation found by the Soricut and Och (2015) tool. The key idea is that edges carry features with weights learned separately for each attribute. An edge can therefore pass a value along or reverse it, for example when a suffix change signals a different tense. Classic label propagation, by contrast, assumes connected nodes are similar. All signals come from raw news text, so the method works for any language. From roughly 1,000 seed words, the authors grow lexicons over 100 times larger for 11 languages, checked against UD treebank data or human-made lexicons. Used as features, these lexicons improve morphological tagging and dependency parsing, offering a cheap path to such resources for low-resource languages.

Key points

  • A seed of about 1,000 words is expanded more than 100-fold with high quality for 11 languages of differing morphological complexity.
  • As extra features, the lexicons cut errors by an average of 15.4% in morphological tagging and 5.3% in dependency parsing across the 11 languages, on publicly available treebanks.
  • The graph has three edge types:
    • Exchange clustering of the 1M most frequent words from a year of news into 256 clusters.
    • 2- and 3-character prefixes and suffixes seen at least twice in the seed lexicon.
    • Morphological transformations such as suffix:ed:ing.
    • To keep the graph sparse, each node gets at most 100 random neighbours per feature.
  • Each attribute value is estimated as a tanh of feature-weighted neighbour values, which resembles a naive mean-field approximation of the Ising model.
    • Weights are first learned with supervision, then propagated with the weights fixed.
    • Paradigm projection then maps each word to the closest valid attribute combination; attributes are handled independently via binary relevance.
  • The features suit concatenative morphology and may perform poorly for languages like Arabic or Hebrew. Proposed future work includes joint learning and propagation, and richer features such as word embeddings and Wiktionary relations.

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

🏢GoogleMountain View · United States492 works · 440,462 citations🎓Carnegie Mellon UniversityPittsburgh · United States598 works · 191,225 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Manaal Faruqui, Ryan McDonald and Radu Soricut. 2016. Morpho-syntactic Lexicon Generation Using Graph-based Semi-supervised Learning. 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_00079

@article{faruqui2016morpho,
  title = {{Morpho-syntactic Lexicon Generation Using Graph-based Semi-supervised Learning}},
  author = {Manaal Faruqui, Ryan McDonald and Radu Soricut},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2016},
  doi = {10.1162/tacl\_a\_00079},
  url = {https://doi.org/10.1162/tacl_a_00079}
}

References

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

  1. https://www.wiktionary.org/Kanerva, Juha Kuokkala, Veronika Laippala, Alessandro Lenci, Krister Lindén, Nikola Ljubešić, Teresa Lynn, Christopher Manning, Héctor Alonso Martı́nez, Ryan McDonald, Anna Missilä, Simonetta Montemagni, Joakim Nivre, Hanna Nurmi, Petya Osenova, Slav Petrov, Jussi Pii… ↗
  2. Malin Ahlberg, Markus Forsberg, and Mans Hulden. 2014. Semi-supervised learning of morphological paradigms and lexicons. In Proc. of EACL.
  3. Malin Ahlberg, Markus Forsberg, and Mans Hulden. 2015. Paradigm classification in supervised learning of morphology. In Proc. of NAACL. find
  4. Enrique Alfonseca, Marius Pasca, and Enrique Robledo-Arnuncio. 2010. Acquisition of instance attributes via labeled and related instances. In Proc. of SIGIR. Ebru Arisoy, Murat Saraçlar, Brian Roark, and Izhak Shafran. 2010. Syntactic and sub-lexical features for Turkish discriminative language mod… find
  5. Carmen Banea, Janyce M. Wiebe, and Rada Mihalcea. 2008. A bootstrapping method for building subjectivity lexicons for languages with scarce resources. In Proc. of LREC. find
  6. Yoshua Bengio, Olivier Delalleau, and Nicolas Le Roux. 2006. Label propagation and quadratic criterion. In Semi-Supervised Learning. find
  7. MIT Press. Laurent Besacier, Etienne Barnard, Alexey Karpov, and Tanja Schultz. 2014. Automatic speech recognition for under-resourced languages: A survey. Speech Communication, 56:85–100. find
  8. Bernd Bohnet and Joakim Nivre. 2012. A transition-based system for joint part-of-speech tagging and labeled non-projective dependency parsing. In Proc. of EMNLP.
  9. Chris Callison-Burch and Mark Dredze. 2010. Creating speech and language data with amazon’s mechanical turk. In Proc. of NAACL Workshop on Creating Speech and Language Data with Amazon’s Mechanical Turk.
  10. Alexander Clark. 2003. Combining distributional and morphological information for part of speech induction. In Proc. of EACL.
  11. Mathias Creutz and Krista Lagus. 2007. Unsupervised models for morpheme segmentation and morphology learning. ACM Transactions on Speech and Language Processing (TSLP), 4(1):3. find
  12. Dipanjan Das and Slav Petrov. 2011. Unsupervised part-of-speech tagging with bilingual graph-based projections. In Proc. of ACL.
  13. Dipanjan Das and Noah A. Smith. 2012. Graph-based lexicon expansion with sparsity-inducing penalties. In Proc. of NAACL. find
  14. Marie-Catherine De Marneffe, Timothy Dozat, Natalia Silveira, Katri Haverinen, Filip Ginter, Joakim Nivre, and Christopher D. Manning. 2014. Universal stanford dependencies: A cross-linguistic typology. In Proceedings of LREC.
  15. Vera Demberg. 2007. A language-independent unsupervised model for morphological segmentation. In Proc. of ACL. Pascal Denis and Benoı̂t Sagot. 2009. Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art POS tagging with less human effort. In Proc. of PACLIC. find
  16. Paramveer S. Dhillon, Partha Talukdar, and Koby Crammer. 2012. Metric learning for graph-based domain adaptation. In Proc. of COLING. find
  17. Markus Dreyer and Jason Eisner. 2011. Discovering morphological paradigms from plain text using a Dirichlet process mixture model. In Proc. of EMNLP. find
  18. Matthew S. Dryer. 2013. Prefixing vs. Suffixing in Inflectional Morphology. Max Planck Institute for Evolutionary Anthropology. find
  19. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121–2159. find
  20. Kais Dukes and Nizar Habash. 2010. Morphological annotation of quranic Arabic. In Proc. of LREC.
  21. Greg Durrett and John DeNero. 2013. Supervised learning of complete morphological paradigms. In Proc. of NAACL.
  22. Saso Dzeroski, Tomaz Erjavec, and Jakub Zavrel. 2000. Morphosyntactic tagging of Slovene: Evaluating taggers and tagsets. In Proc. of LREC. find
  23. Tomaz Erjavec. 2004. Multext-east version 3: Multilingual morphosyntactic specifications, lexicons and corpora. In Proc. of LREC. Günes Erkan and Dragomir R. Radev. 2004. Lexrank: Graph-based lexical centrality as salience in text summarization. Journal of Artificial Intelligence Research, 22(1):45… find
  24. Ramy Eskander, Nizar Habash, and Owen Rambow. 2013. Automatic extraction of morphological lexicons from morphologically annotated corpora. In Proc. of EMNLP. Manaal Faruqui and Sebastian Padó. 2010. Training and evaluating a German named entity recognizer with semantic generalization. In Proc. of K… find
  25. Manaal Faruqui, Yulia Tsvetkov, Graham Neubig, and Chris Dyer. 2016. Morphological inflection generation using character sequence to sequence learning. arXiv:1104.2086.
  26. Chun-Sung Ferng and Hsuan-Tien Lin. 2011. Multi-label classification with error-correcting codes. In Proc. of ACML. Johannes Fürnkranz, Eyke Hüllermeier, Eneldo Loza Mencı́a, and Klaus Brinker. 2008. Multilabel classification via calibrated label ranking. Machine learning, 73(2):133–153. find
  27. Dan Garrette, Jason Mielens, and Jason Baldridge. 2013. Real-world semi-supervised learning of POS-taggers for low-resource languages. In Proc. of ACL. find
  28. Nadia Ghamrawi and Andrew McCallum. 2005. Collective multi-label classification. In Proc. of CIKM. Jesús Giménez and Lluı́s Marquez. 2004. Svmtool: A general POS tagger generator based on support vector machines. In Proc. of LREC.
  29. Shantanu Godbole and Sunita Sarawagi. 2004. Discriminative methods for multi-labeled classification. In Proc. of KDD. find
  30. Andrew B. Goldberg, Xiaojin Zhu, and Stephen J. Wright. 2007. Dissimilarity in graph-based semi-supervised classification. In Proc. of AISTATS. find
  31. Yoav Goldberg, Reut Tsarfaty, Meni Adler, and Michael Elhadad. 2009. Enhancing unlexicalized parsing performance using a wide coverage lexicon, fuzzy tag-set mapping, and EM-HMM-based lexical probabilities. In Proc. of EACL. find
  32. Spence Green and John DeNero. 2012. A class-based agreement model for generating accurately inflected translations. In Proc. of ACL. Jan Hajič and Barbora Hladká. 1998. Tagging inflective languages: Prediction of morphological categories for a rich, structured tagset. In Proc. of COLING. Jan Hajic… find
  33. Daniel Hsu, Sham Kakade, John Langford, and Tong Zhang. 2009. Multi-label prediction via compressed sensing. In Proc. of NIPS. Stéphane Huet, Guillaume Gravier, and Pascale Sébillot. 2008. Morphosyntactic resources for automatic speech recognition. In Proc. of LREC. find
  34. Ann Irvine and Alexandre Klementiev. 2010. Using mechanical turk to annotate lexicons for less commonly used languages. In Proc. of NAACL Workshop on Creating Speech and Language Data with Amazon’s Mechanical Turk.
  35. Ernst Ising. 1925. Beitrag zur theorie des ferromag-netismus. Zeitschrift für Physik A Hadrons and Nuclei, 31(1):253–258. find
  36. Reinhard Kneser and Hermann Ney. 1993. Improved clustering techniques for class-based statistical language modelling. In Proc. of Eurospeech. find
  37. Dimitrios Kokkinakis, Maria Toporowska-Gronostaj, and Karin Warmenius. 2000. Annotating, disambiguating & automatically extending the coverage of the Swedish SIMPLE lexicon. In Proc. of LREC. find
  38. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In Proc. of ACL. Sandra Kübler, Ryan McDonald, and Joakim Nivre. 2009. Dependency parsing. Synthesis Lectures on Human Language Technologies.
  39. Morgan & Claypool Publishers. Yue Lu, Malu Castellanos, Umeshwar Dayal, and ChengXiang Zhai. 2011. Automatic construction of a context-aware sentiment lexicon: An optimization approach. In Proc. of WWW. Sven Martin, Jörg Liermann, and Hermann Ney. 1998. Algorithms for bigram and trigram word cluste…
  40. Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig. 2013. Linguistic regularities in continuous space word representations. In Proc. of NAACL.
  41. Einat Minkov, Kristina Toutanova, and Hisami Suzuki. 2007. Generating complex morphology for machine translation. In Proc. of ACL. find
  42. Saif Mohammad, Cody Dunne, and Bonnie Dorr. 2009. Generating high-coverage semantic orientation lexicons from overtly marked words and a thesaurus. In Proc. of EMNLP. find
  43. Robert Moore. 2015. An improved tag dictionary for faster part-of-speech tagging. In Proc. of EMNLP. Thomas Müller and Hinrich Schuetze. 2015. Robust morphological tagging with word representations. In Proceedings of NAACL. Thomas Müller, Helmut Schmid, and Hinrich Schütze. 2013. Efficient higher… find
  44. Pradeep Muthukrishnan, Dragomir Radev, and Qiaozhu Mei. 2011. Simultaneous similarity learning and feature-weight learning for document clustering. In Proc. of TextGraphs. find
  45. Karthik Narasimhan, Regina Barzilay, and Tommi Jaakkola. 2015. An unsupervised method for uncovering morphological chains. Transactions of the Association for Computational Linguistics, 3:157–167. find
  46. Garrett Nicolai, Colin Cherry, and Grzegorz Kondrak. 2015. Inflection generation as discriminative string transduction. In Proc. of NAACL. find
  47. Sonja Nießen and Hermann Ney. 2004. Statistical machine translation with scarce resources using morphosyntactic information. Computational Linguistics, 30(2). Kemal Oflazer and Ìlker Kuruöz. 1994. Tagging and morphological disambiguation of Turkish text. In Proc. of ANLP. find
  48. Olutobi Owoputi, Brendan O’Connor, Chris Dyer, Kevin Gimpel, Nathan Schneider, and Noah A. Smith. 2013. Improved part-of-speech tagging for online conversational text with word clusters. In Proc. of NAACL.
  49. Tommi A Pirinen. 2011. Modularisation of finnish finite-state language description—towards wide collaboration in open source development of a morphological analyser. In Proc. of NODALIDA. find
  50. Hoifung Poon, Colin Cherry, and Kristina Toutanova. 2009. Unsupervised morphological segmentation with log-linear models. In Proc. of NAACL.
  51. Adwait Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. of EMNLP.
  52. Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. 2011. Classifier chains for multi-label classification. Machine Learning, 85(3):333–359. Haşim Sak, Tunga Güngör, and Murat Saraçlar. 2008. Turkish language resources: Morphological parser, morphological disambiguator and web corpus.… find
  53. Helmut Schmid. 1994. Probabilistic part-of-speech tagging using decision trees. In Proc. of the International Conference on New Methods in Language Processing. find
  54. Kiril Ivanov Simov, Petya Osenova, Sia Kolkovska, Elisaveta Balabanova, and Dimitar Doikoff. 2004. A language resources infrastructure for Bulgarian. In Proc. of LREC. find
  55. Noah A. Smith, David A. Smith, and Roy W. Tromble. 2005. Context-based morphological disambiguation with random fields. In Proc. of EMNLP. find
  56. Benjamin Snyder and Regina Barzilay. 2008. Unsupervised multilingual learning for morphological segmentation. In Proc. of ACL.
  57. Radu Soricut and Franz Och. 2015. Unsupervised morphology induction using word embeddings. In Proc. of NAACL. find
  58. Amarnag Subramanya and Jeff Bilmes. 2008. Soft-supervised learning for text classification. In Proc. of EMNLP. find
  59. Amarnag Subramanya and Partha Pratim Talukdar. 2014. Graph-based semi-supervised learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 8(4). find
  60. Amarnag Subramanya, Slav Petrov, and Fernando Pereira. 2010. Efficient graph-based semi-supervised learning of structured tagging models. In Proc. of EMNLP. Oscar Täckström, Ryan McDonald, and Jakob Uszkoreit. 2012. Cross-lingual word clusters for direct transfer of linguistic structure. In Proc.…
  61. Hiroya Takamura, Takashi Inui, and Manabu Okumura. 2007. Extracting semantic orientations of phrases from dictionary. In Proc. of NAACL. find
  62. Partha Pratim Talukdar and William Cohen. 2013. Scaling graph-based semi-supervised learning to large number of labels using count-min sketch. In Proc. of AISTATS. find
  63. Partha Pratim Talukdar and Fernando Pereira. 2010. Experiments in graph-based semi-supervised learning methods for class-instance acquisition. In Proc. of ACL. find
  64. Partha Pratim Talukdar, Derry Wijaya, and Tom Mitchell. 2012. Acquiring temporal constraints between relations. In Proc. of CIKM. find
  65. Michael Thelen and Ellen Riloff. 2002. A bootstrapping method for learning semantic lexicons using extraction pattern contexts. In Proc. of ACL. Viktor Trón, Péter Halácsy, Péter Rebrus, András Rung, Péter Vajda, and Eszter Simon. 2006. Morphdb.hu: Hungarian lexical database and morphological…
  66. Grigorios Tsoumakas and Ioannis Katakis. 2006. Multi-label classification: An overview. Dept. of Informatics, Aristotle University of Thessaloniki, Greece. find
  67. Joseph Turian, Lev Ratinov, and Yoshua Bengio. 2010. Word representations: a simple and general method for semi-supervised learning. In Proc. of ACL.
  68. Jakob Uszkoreit and Thorsten Brants. 2008. Distributed word clustering for large scale class-based language modeling in machine translation. In Proc. of ACL. find
  69. Leonid Velikovich, Sasha Blair-Goldensohn, Kerry Hannan, and Ryan McDonald. 2010. The viability of web-derived polarity lexicons. In Proc. of NAACL. find
  70. Fei Wang, Shijun Wang, Changshui Zhang, and Ole Winther. 2007. Semi-supervised mean fields. In Proc. of AISTATS. find
  71. Kilian Q. Weinberger, John Blitzer, and Lawrence K. Saul. 2005. Distance metric learning for large margin nearest neighbor classification. In Proc. of NIPS. find
  72. Richard Wicentowski. 2004. Multilingual noise-robust supervised morphological analysis using the word-frame model. In Proc. of SIGPHON. find
  73. David Yarowsky and Richard Wicentowski. 2000. Minimally supervised morphological analysis by multimodal alignment. In Proc. of ACL. find
  74. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proc. of ACL. find
  75. Yi Zhang and Jeff G. Schneider. 2011. Multi-label output codes using canonical correlation analysis. In Proc. of AISTATS. find
  76. Min-Ling Zhang and Zhi-Hua Zhou. 2005. A k-nearest neighbor based algorithm for multi-label classification. In Proc. of IEEE Conference on Granular Computing. find
  77. Xiaojin Zhu. 2005. Semi-supervised Learning with Graphs. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA, USA. AAI3179046. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/faruqui-2016-morpho-syntactic-lexicon-generation-graph/