Elamur Research⌕
☰
home / papers / 2009 / Unsupervised Morphological Segmentation with Log-Linear Models

Unsupervised Morphological Segmentation with Log-Linear Models

Summary

The paper addresses unsupervised morphological segmentation: splitting words into morphemes without labeled data, focusing on inflectional morphology in Arabic and Hebrew. Earlier model-based systems such as Morfessor and Snyder & Barzilay's Bayesian approach rely on directed generative models, which make it hard to add overlapping features. The authors propose what they describe as the first log-linear model for this task. It scores a segmentation of the whole corpus using features for each morpheme and for its surrounding character n-grams. Two exponential priors in the spirit of MDL are added: one penalizes the size of the morpheme lexicon, the other penalizes the number of morphemes per word. The model keeps separate lexicons for prefixes, stems and suffixes. Learning combines contrastive estimation with sampling. Using only monolingual features, the system beats Snyder & Barzilay even when their system has bilingual information. On the Arabic Penn Treebank it cuts F1 error by 11% relative to Morfessor Categories-MAP. The same model also works well in supervised and semi-supervised settings. This matters for low-resource languages, where raw text is plentiful but annotation is scarce.

Key points

  • Features and lexicons: Each morpheme gets a feature, and so do its left and right n-gram contexts, with # marking word boundaries. The full model uses trigram contexts. Prefixes, stems and suffixes have separate lexicons. A stem must have at least two characters and be no shorter than any affix in the same word.
  • Priors:
    • The lexicon prior penalizes the total character length of the unique morphemes.
    • The corpus prior penalizes the morpheme count per word, normalized by word length (e.g., w-vlAv-wn contributes 3/7).
  • Arabic Penn Treebank (F1):
    • Full ATB: FULL scores 77.7, versus 74.9 for Morfessor Categories-MAP and 32.6 for Morfessor-1.0.
    • ATB-7000 (the first 7,000 words with at least two characters): FULL scores 80.2, versus 60.5 and 46.1.
  • Ablations:
    • Dropping some or all priors costs over 10 F1 points, and over 40 in some cases. Without the corpus prior the model over-segments; without the lexicon prior it under-segments.
    • Removing context features costs over 10 points.
    • Compared with unigram contexts, trigrams cut F1 error by 16% for Arabic, and bigrams cut it by 17% for Hebrew.
  • Supervised setting (Arabic, all labels): F1 reaches 90.0, versus 81.7 for S&B-MONO-S and 84.4 for S&B-BEST-S. With a quarter of the labels the model already surpasses S&B-MONO-S.

Interesting ideas

  • I1. Two opposing MDL-style penalties. One prior favors few, short morpheme types, which alone pushes toward splitting words into single characters. The other penalizes morphemes per word, which alone pushes toward no splitting. Balancing the two gives a strong bias without labels, and the pattern could carry over to other unsupervised segmentation or tokenization tasks.
  • I2. Overlapping morpheme and context features. Scoring both a candidate segment and the characters around it (constituent-context style) is easy in a log-linear model. The ablations show it matters a lot, so it is a natural fit for morphologically rich languages such as Ukrainian.
  • I3. Learning on types, evaluating on tokens. Each word type is forced to have one segmentation during training, which the authors found works better than token frequencies. Accuracy is still measured on tokens, to reflect how the system performs in real use.
  • I4. Contrastive estimation plus sampling. Contrastive estimation supplies a tractable, informative normalization term, while sampling allows global features such as lexicon size. This combination is a reusable recipe for unsupervised learning with log-linear models in general.
  • I5. One model across supervision levels. The same model moves smoothly from unsupervised to semi-supervised to supervised training. This makes it practical when only a small annotated set exists, since labels can simply be added as they become available.

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

Fields: Natural language processing

Topics Morphology Semitic languages

 Institutions

🎓University of WashingtonSeattle · United States206 works · 158,423 citations🏢MicrosoftRedmond · United States193 works · 110,465 citations

Cite

Cite as Hoifung Poon, Colin Cherry and Kristina Toutanova. 2009. Unsupervised Morphological Segmentation with Log-Linear Models. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics.

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

@inproceedings{poon2009unsupervised,
  title = {{Unsupervised Morphological Segmentation with Log-Linear Models}},
  author = {Hoifung Poon, Colin Cherry and Kristina Toutanova},
  booktitle = {Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  doi = {10.3115/1620754.1620785},
  url = {https://doi.org/10.3115/1620754.1620785}
}

References

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

  1. Galen Andrew. 2006. A hybrid markov/semi-markov conditional random field for sequence segmentation. In Conference on Empirical Methods in Natural Language Processing (EMNLP). find
  2. Michael R. Brent, Sreerama K. Murthy, and Andrew Lundberg. 1995. Discovering morphemic suffixes: A case study in minimum description length induction. In Proceedings of the 15th Annual Conference of the Cognitive Science Society. find
  3. Tim Buckwalter. 2004. Buckwalter Arabic morphological analyzer version 2.0. find
  4. Mathias Creutz and Krista Lagus. 2007. Unsupervised models for morpheme segmentation and morphology learning. ACM Transactions on Speech and Language Processing, 4(1). find
  5. Sajib Dasgupta and Vincent Ng. 2007. High-performance, language-independent morphological segmentation. In Proceedings of Human Language Technology (NAACL). find
  6. Vera Demberg. 2007. A language-independent unsupervised model for morphological segmentation. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, Prague, Czech Republic. find
  7. John Goldsmith. 2001. Unsupervised learning of the morphology of a natural language. Computational Linguistics, 27(2):153–198. find
  8. Sharon Goldwater, Thomas L. Griffiths, and Mark Johnson. 2006. Interpolating between types and tokens by estimating power-law generators. In Advances in Neural Information Processing Systems 18. find
  9. Sharon Goldwater, Thomas L. Griffiths, and Mark Johnson. 2007. Distributional cues to word segmentation: Context is important. In Proceedings of the 31st Boston University Conference on Language Development. find
  10. Alan Groves and Kirk Lowery, editors. 2006. The Westminster Hebrew Bible Morphology Database. Westminster Hebrew Institute, Philadelphia, PA, USA. find
  11. Nizar Habash and Owen Rambow. 2005. Arabic tokenization, part-of-speech tagging and morphological disambiguation in one fell swoop. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics. our card
  12. Zellig S. Harris. 1955. From phoneme to morpheme. Language, 31(2):190–222. find
  13. Samarth Keshava and Emily Pitler. 2006. A simple, intuitive approach to morpheme induction. In Proceedings of 2nd Pascal Challenges Workshop, Venice, Italy. find
  14. Dan Klein and Christopher D. Manning. 2001. Natural language grammar induction using a constituent-context model. In Advances in Neural Information Processing Systems 14. find
  15. Mikko Kurimo, Mathias Creutz, and Ville Turunen. 2007. Overview of Morpho Challenge in CLEF 2007. In Working Notes of the CLEF 2007 Workshop. find
  16. Hoifung Poon and Pedro Domingos. 2008. Joint unsupervised coreference resolution with markov logic. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 649– 658, Honolulu, HI. ACL. our card
  17. Ronald Rosenfeld. 1997. A whole sentence maximum entropy language model. In IEEE workshop on Automatic Speech Recognition and Understanding. find
  18. Sunita Sarawagi and William Cohen. 2004. Semimarkov conditional random fields for information extraction. In Proceedings of the Twenty First International Conference on Machine Learning. find
  19. Patrick Schone and Daniel Jurafsky. 2001. Knowlege-free induction of inflectional morphologies. In Proceedings of Human Language Technology (NAACL). find
  20. Noah A. Smith and Jason Eisner. 2005. Contrastive estimation: Training log-linear models on unlabeled data. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics. our card
  21. Benjamin Snyder and Regina Barzilay. 2008a. Cross-lingual propagation for morphological analysis. In Proceedings of the Twenty Third National Conference on Artificial Intelligence. find
  22. Benjamin Snyder and Regina Barzilay. 2008b. Unsupervised multilingual learning for morphological segmentation. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics. our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/poon-2009-unsupervised-morphological-segmentation-log-linear/