Elamur Research⌕
☰
home / papers / 2003 / Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network

Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network

Summary

The paper asks whether an English part-of-speech tagger improves when each local decision can see tags on both sides, not only the preceding ones. The authors build a cyclic dependency network. At every position, a local conditional loglinear (maxent) model predicts the current tag from the neighbouring tags on the left and right plus the surrounding words. Such a cyclic graph does not define a proper joint distribution. Even so, the product of the local scores can be maximised exactly with a Viterbi-like dynamic program.

On top of this structure they add rich lexical templates, including features over several consecutive words, detailed unknown-word features, and a Gaussian (quadratic) prior for regularisation. The prior lets them keep rare features without overfitting. On the Penn Treebank WSJ, the tagger reaches 97.24% per-token accuracy and 56.34% whole-sentence accuracy, the best single automatically learned tagger the authors knew of. The broader point is that bidirectional conditioning, heavy lexicalisation and proper regularisation work well together for sparse sequence-labelling tasks.

Key points

  • Results on the Penn Treebank WSJ: 97.24% tag accuracy and 56.34% of sentences tagged fully correctly.
  • Error reduction over previous work, on the same data splits:
    • 4.4% relative to the voted perceptron of Collins (2002);
    • 12.1% relative to the earlier loglinear tagger of Toutanova and Manning (2000).
  • The tagger also beats the combination tagger of Brill and Wu (1998), which reported 97.16% with more training data.
  • Effect of regularisation on the development set:
    • Smaller model: 5.3% fewer errors overall and 20.1% fewer on unknown words.
    • Large feature-rich model: 16.2% fewer errors after convergence, and 5.8% fewer than the unsmoothed model's best early-stopped result.
  • Training speed: smoothed models converged in 80 and 134 conjugate-gradient iterations, versus 335 and 370 for unsmoothed ones. The largest models used several hundred thousand features and took about 25 minutes per iteration on a 2GHz PC.

Interesting ideas

  • I1. Condition on both neighbours. Each local classifier predicts a label from both the left and right context, and decoding uses a modified Viterbi search. This avoids "observation bias" cases such as will to fight, where a purely left-to-right model loses useful evidence. The trick transfers to any sequence labeller, such as NER, morphological tagging or chunking.
  • I2. Prior instead of frequency cutoffs. A Gaussian prior replaces feature-frequency cutoffs and early stopping, so very rare features can be kept and still help. It also shifts weight toward general features, which benefits unknown words. This is valuable for morphologically rich languages like Ukrainian, where many word forms are rare.
  • I3. Multiword lexical templates. Templates that look jointly at several consecutive words let the model learn fixed idiomatic sequences automatically. This is a cheap way to recover what hand-written idiom lists used to provide.
  • I4. Training-curve diagnostic. Plotting dev accuracy against training iterations shows that regularised models improve almost steadily while unregularised ones peak and then decline. This is a simple check of whether a model needs early stopping or stronger regularisation.
  • I5. Report sentence-level accuracy. Whole-sentence accuracy is reported alongside per-token accuracy. It exposes differences that per-token figures hide once token accuracy approaches its ceiling.

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

Cited by

715 papers of our library cite it (of the 140884 whose bibliographies we read); 70 of them have a page here, 645 not yet.

Cite

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

@inproceedings{toutanova2003feature,
  title = {{Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network}},
  author = {Toutanova, Kristina and Klein, Dan and Manning, Christopher D. and Singer, Yoram},
  booktitle = {Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2003},
  doi = {10.3115/1073445.1073478},
  url = {https://doi.org/10.3115/1073445.1073478}
}

References

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

  1. Steven Abney, Robert E. Schapire, and Yoram Singer. 1999. Boosting applied to tagging and PP attachment. In EMNLP/VLC 1999, pages 38–45. find
  2. Thorsten Brants. 2000. TnT – a statistical part-of-speech tagger. In ANLP 6, pages 224–231. find our card
  3. Eric Brill and Jun Wu. 1998. Classifier combination for improved lexical disambiguation. In ACL 36/COLING 17, pages 191–195. find
  4. Eric Brill. 1995. Transformation-based error-driven learning and natural language processing: A case study in part-of-speech tagging. Computational Linguistics, 21(4):543–565. find our card
  5. Eugene Charniak, Curtis Hendrickson, Neil Jacobson, and Mike Perkowitz. 1993. Equations for part-of-speech tagging. In AAAI 11, pages 784–789. find
  6. Stanley F. Chen and Ronald Rosenfeld. 2000. A survey of smoothing techniques for maximum entropy models. IEEE Transactions on Speech and Audio Processing, 8(1):37–50. find
  7. Kenneth W. Church. 1988. A stochastic parts program and noun phrase parser for unrestricted text. In ANLP 2, pages 136–143. find our card
  8. Michael Collins. 2002. Discriminative training methods for Hidden Markov Models: Theory and experiments with perceptron algorithms. In EMNLP 2002. find our card
  9. Robert G. Cowell, A. Philip Dawid, Steffen L. Lauritzen, and David J. Spiegelhalter. 1999. Probabilistic Networks and Expert Systems. Springer-Verlag, New York. find
  10. David Heckerman, David Maxwell Chickering, Christopher Meek, Robert Rounthwaite, and Carl Myers Kadie. 2000. Dependency networks for inference, collaborative filtering and data visualization. Journal of Machine Learning Research, 1(1):49–75. find
  11. Mark Johnson, Stuart Geman, Stephen Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic “unification-based” grammars. In ACL 37, pages 535–541. find
  12. Dan Klein and Christopher D. Manning. 2002. Conditional structure versus conditional estimation in NLP models. In EMNLP 2002, pages 9–16. find
  13. John Lafferty, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML-2001, pages 282–289. find
  14. Sang-Zoo Lee, Jun ichi Tsujii, and Hae-Chang Rim. 2000. Part-of-speech tagging based on Hidden Markov Model assuming joint independence. In ACL 38, pages 263–169. find
  15. Mitchell P. Marcus, Beatrice Santorini, and Mary A. Marcinkiewicz. 1994. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19:313– 330. find our card
  16. Ian Marshall. 1987. Tag selection using probabilistic methods. In Roger Garside, Geoffrey Sampson, and Geoffrey Leech, editors, The Computational analysis of English: a corpus-based approach, pages 42–65. Longman, London. find
  17. Adwait Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In EMNLP 1, pages 133–142. find our card
  18. Scott M. Thede and Mary P. Harper. 1999. Second-order hidden Markov model for part-of-speech tagging. In ACL 37, pages 175–182. find
  19. Kristina Toutanova and Christopher Manning. 2000. Enriching the knowledge sources used in a maximum entropy part-of-speech tagger. In EMNLP/VLC 1999, pages 63–71. find our card
  20. Tong Zhang and Frank J. Oles. 2001. Text categorization based on regularized linear classification methods. Information Retrieval, 4:5–31. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/toutanova-2003-feature-rich-part-speech-tagging/