Elamur Research⌕
☰
home / papers / 2008 / Estimation of Conditional Probabilities With Decision Trees and an Application to Fine-Grained POS Tagging

Estimation of Conditional Probabilities With Decision Trees and an Application to Fine-Grained POS Tagging

Summary

The paper tackles HMM part-of-speech tagging with very large, morphologically detailed tagsets, such as the Tiger treebank tagset for German (over 700 tags) and the Czech Academic Corpus tagset (about 1200 tags). With so many tags, most tag n-grams are rare or unseen, so standard n-gram smoothing breaks down and agreement information is lost.

The authors split every tag into a vector of attributes: main category, then category-specific features such as case, number and gender. The contextual probability of a tag becomes a product of attribute probabilities. Each attribute probability is estimated by a probability estimation tree, which learns which attributes of preceding tags actually matter. Because the trees select relevant context automatically, the model can use long contexts, up to 10 preceding tags.

On German and Czech data the tagger beat TnT and SVMTool, two general-purpose state-of-the-art taggers. The work shows that generative HMM tagging can scale to fine-grained morphology through factorisation and learned context selection. The German numbers are, as far as the authors know, the first published fine-grained results with the Tiger tagset.

Key points

  • Tiger test accuracy, our tagger vs TnT (context size 10):
    • default setting: 85.00% vs 83.45%
    • refined setting: 85.92% vs 84.11%
    • refined plus lexicon: 91.07% vs 89.14%
  • Significance on Tiger: 1450 sentences were tagged better by the new tagger and 726 by TnT. A binomial test gives p < 0.001.
  • Main German error: most errors confuse nominative with accusative case. Ignoring that error, development accuracy rises from 92.17% to 94.27%.
  • Czech Academic Corpus: 652,131 tokens with an 80/10/10 split. The best development result was 88.9%, with 4 preceding tags. On test data the tagger reached 89.53% against 88.88% for TnT, a significant difference.
  • Efficiency:
    • Tagging speed is about 7000 tokens/s with context 3 and 2000 tokens/s with context 10, on an Athlon X2 4600.
    • Training with context 10 took about 4 minutes.
    • Beam pruning at a threshold of 10⁻³ had negligible effect on accuracy.

Interesting ideas

  • I1. Chain-rule factorisation of composite labels. Each feature is predicted in turn, conditioned on the context and on the features already predicted for the current tag. This turns an unseen full-tag context into a sequence of well-observed decisions. It could transfer to UD morphological feature tagging for Ukrainian or other richly inflected languages.
  • I2. Trees instead of a hand-built backoff order. Decision trees choose which context attributes to condition on, for example only the case of the preceding article. This avoids having to define a backoff ordering, which does not exist for arbitrary attribute combinations, and it is useful wherever feature interactions are sparse.
  • I3. One binary tree per feature value, then renormalise. A separate yes/no tree for each value keeps one tree from fragmenting data with splits that only separate other values. The resulting probabilities are rescaled to sum to 1. These two-class trees worked well with one fixed pruning threshold (6), so no training data had to be held out for tuning.
  • I4. Gain times sample size as the pruning rule. A node is pre-pruned when the information gain of its best test, multiplied by the size of its data subset, falls below a threshold. This simple critical-value rule beat unpruned trees and was robust to the threshold choice, which makes it a cheap default for probability estimation trees.
  • I5. Constrained context exploration. An attribute of an earlier tag may be tested only if some attribute of the nearer tag has already been used. This locality bias improved accuracy for large context windows and could help any model that searches over long histories.

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: Part-of-speech tagging

Institutions

🎓University of StuttgartStuttgart · Germany64 works · 45 339 citations

Cite

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

@inproceedings{schmid2008estimation,
  title = {{Estimation of Conditional Probabilities With Decision Trees and an Application to Fine-Grained POS Tagging}},
  author = {Schmid, Helmut and Laws, Florian},
  booktitle = {Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)},
  year = {2008},
  doi = {10.3115/1599081.1599179},
  url = {https://doi.org/10.3115/1599081.1599179}
}

References

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

  1. Brants, Sabine, Stefanie Dipper, Silvia Hansen, Wolfgang Lezius, and George Smith. 2002. The TIGER treebank. In Proceedings of the Workshop on Treebanks and Linguistic Theories, Sozopol. find
  2. Brants, Thorsten. 2000. TnT - a statistical part-of-speech tagger. In Proceedings of the Sixth Applied Natural Language Processing Conference ANLP-2000, Seattle, WA. find our card
  3. Breiman, L., J. H. Friedman, R. A. Olshen, and C. J. Stone. 1984. Classification and Regression Trees. Wadsworth and Brooks, Pacific Grove CA. find
  4. Ferri, C., P. Flach, and J. Hernández-Orallo. 2003. Improving the AUC of probabilistic estimators trees. In Proceedings of 14th European Conference on Machine Learning (ECML’03), pages 121–132. find
  5. Giménez, Jesús and Lluı́s Màrquez. 2004. SVMTool: A general POS tagger generator based on support vector machines. In Proceedings of the IV International Conference on Language Resources and Evaluation (LREC’04), pages 43–46, Lisbon, Portugal. find our card
  6. Hajič, Jan and Barbora Vidová-Hladká. 1998. Tagging inflective languages: Prediction of morphological categories for a rich, structured tagset. In Proceedings of ACL-COLING’98, Montreal, Canada. find
  7. Hajič, Jan, Pavel Krbec, Karel Oliva, Pavel Květoň, and Vladimı́r Petkevič. 2001. Serial combination of rules and statistics: A case study in czech tagging. In Proceedings of the 39th Annual Meeting of the ACL, Toulouse, France. find
  8. Hladká, Barbora Vidová, Jan Hajic, Jirı́ Hana, Jaroslava Hlavácová, Jirı́ Mı́rovský, and Jan Votrubec. 2007. Czech Academic Corpus 1.0 Guide. Karolinum Press, Prag, Czechia. find
  9. Kempe, André. 1994. Probabilistic tagging with feature structures. In Proceedings of the 15th International Conference on Computational Linguistics (COLING 1994), pages 161–165, Kyoto, Japan. find
  10. Magerman, David M. 1994. Natural Language Processing as Statistical Pattern Recognition. Ph.D. thesis, Stanford University. find
  11. Màrquez, Lluı́s. 1999. POS Tagging : A Machine Learning Approach based on Decision Trees. Ph.D. thesis, Dep. LSI, Universitat Politecnica de Catalunya (UPC), Barcelona, Spain, July. find
  12. Mingers, John. 1989. An empirical comparison of pruning methods for decision tree induction. Machine Learning, 4:227–243. find
  13. Provost, Foster and Pedro Domingos. 2003. Tree induction for probability-based ranking. Machine Learning, 52(3):199–215. find
  14. Quinlan, J. Ross. 1993. C4.5 : Programs for Machine Learning. Morgan Kaufmann, San Mateo , CA. find our card
  15. Schmid, Helmut. 1994. Probabilistic part-of-speech tagging using decision trees. In Proceedings of the International Conference on New Methods in Language Processing, pages 44–49, Manchester, UK. find
  16. Spoustová, Drahomı́ra, Jan Hajič, Jan Votrubec, Pavel Krbec, and Pavel Květoň. 2007. The best of two worlds: Cooperation of statistical and rule-based taggers for czech. In Proceedings of the Workshop on Balto-Slavonic Natural Language Processing, pages 67–74, Prague, Czech Republic, June. find
  17. Toutanova, Kristina, Dan Klein, Christopher Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proceedings of HLT-NAACL 2003, pages 252–259, Edmonton, Canada. find our card
  18. Votrubec, Jan. 2006. Morphological tagging based on averaged perceptron. In Proceedings of the 15th Annual Conference of Doctoral Students (WDS), pages 191–195. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/schmid-2008-estimation-conditional-probabilities-decision-trees/