Elamur Research⌕
☰
home / papers / 2005 / Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data

Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data

Paper · 2005 · Yoshimasa Tsuruoka and Jun'ichi Tsujii

Summary

The paper targets a weakness of sequential classifiers such as MEMMs in tagging tasks like POS tagging and chunking. With a fixed left-to-right or right-to-left order, the local classifier can see tags on only one side of the current word. Dependency networks condition on both sides, but they can lock onto label combinations that look consistent locally yet are unlikely overall.

The authors treat the decomposition direction of each edge as a hidden choice. They train separate maximum entropy classifiers for every pattern of neighbour-tag availability. A dynamic program then finds the best tag sequence and its decomposition structure together in polynomial time.

Because full search is slow, they also propose a greedy "easiest-first" decoder. It repeatedly commits the single most confident word and then re-scores that word's neighbours.

On English POS tagging and chunking, both bidirectional variants beat unidirectional decoding. On CoNLL-2000 chunking they match strong SVM and perceptron systems. The easiest-first decoder stays fast, which matters for large-scale text processing.

Key points

  • Number of classifiers. A k-th order Markov model needs 2^(2k) local classifier types: 4 for first-order and 16 for second-order. Each type differs only in which neighbouring tags it may see.
  • Chunking test results (WSJ Section 20, 2012 sentences):
    • Easiest-first (IOB2, second-order) reached F = 93.63.
    • Full bidirectional (Start/End, first-order) reached F = 93.70.
    • Both exceed the best CoNLL-2000 shared task score of 93.48.
  • Development-set speed versus accuracy:
    • Easiest-first, IOB2, first-order: 2,441 tokens/sec at F = 93.11.
    • Full bidirectional, Start/End, second-order: 4 tokens/sec.
    • Dependency networks collapsed to about 88.3 F with the Start/End representation.
  • Local classifiers. All local classifiers are maximum entropy models, so the system is effectively a "bidirectional MEMM."

Interesting ideas

  • I1. Leave the hardest decisions for last. The greedy decoder tags confident tokens first, so ambiguous words such as unknown words get tag context from both sides. This ordering principle could carry over to Ukrainian morphological tagging, where many word forms are ambiguous.
  • I2. Train one model per context pattern. Instead of a single classifier, a separate model is trained for each combination of known and unknown neighbour tags. These models can be trained fully in parallel with the memory of one model, a cheap alternative to CRFs with rich higher-order features.
  • I3. Decoding as an ensemble over structures. Choosing the highest-probability decomposition amounts to picking among many taggers. The authors suggest other combination rules, such as summing probabilities over outputs that share a label sequence, as future work.
  • I4. Any confidence score can drive easiest-first. Since only a confidence ranking is needed, non-probabilistic classifiers such as SVMs could be used, with their margins serving as confidence. This makes the strategy portable to many local-classifier types.
  • I5. Report speed next to accuracy. The tokens-per-second column exposes trade-offs that F-score alone hides, for example 4 versus 2,441 tokens/sec. This is a useful evaluation habit for production taggers.

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

🎓The University of TokyoTokyo · Japan45 works · 8,692 citations🎓University of ManchesterManchester · United Kingdom30 works · 43,942 citations🏛️Japan Science and Technology AgencyTokyo · Japan7 works · 1,755 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Part-of-speech tagging · 91 works

Cite

Cite as Yoshimasa Tsuruoka and Jun'ichi Tsujii. 2005. Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data. Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing.

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

@inproceedings{tsuruoka2005bidirectional,
  title = {{Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data}},
  author = {Yoshimasa Tsuruoka and Jun'ichi Tsujii},
  booktitle = {Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  doi = {10.3115/1220575.1220634},
  url = {https://doi.org/10.3115/1220575.1220634}
}

References

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

  1. Yasemin Altun, Ioannis Tsochantaridis, and Thomas Hofmann. 2003. Hidden markov support vector machines. In Proceedings of ICML 2003, pages 3–10. find
  2. Adam L. Berger, Stephen A. Della Pietra, and Vincent J. Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71.
  3. Thorsten Brants. 2000. TnT – a statistical part-of-speech tagger. In Proceedings of the 6th Applied NLP Conference (ANLP).
  4. Xavier Carreras and Lluis Marquez. 2003. Phrase recognition by filtering and ranking with perceptrons. In Proceedings of RANLP-2003. find
  5. Stanley F. Chen and Ronald Rosenfeld. 1999. A gaussian prior for smoothing maximum entropy models. Technical Report CMUCS -99-108, Carnegie Mellon University. find
  6. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP 2002, pages 1–8.
  7. Jesus Gimenez and Lluis Marquez. 2003. Fast and accurate part-of-speech tagging: The SVM approach revisited. In Proceedings of RANLP 2003, pages 158–165. find
  8. Jun’ichi Kazama and Jun’ichi Tsujii. 2003. Evaluation and extension of maximum entropy models with inequality constraints. In Proceedings of EMNLP 2003. find
  9. Taku Kudo and Yuji Matsumoto. 2001. Chunking with support vector machines. In Proceedings of NAACL 2001.
  10. Taku Kudoh and Yuji Matsumoto. 2000. Use of support vector learning for chunk identification. In Proceedings of CoNLL-2000, pages 142–144. find
  11. John Lafferty, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML 2001, pages 282–289. find
  12. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1994. Building a large annotated corpus of english: The penn treebank. Computational Linguistics, 19(2):313–330.
  13. Erik F. Tjong Kim Sang and Sabine Buchholz. 2000. Introduction to the conll-2000 shared task: Chunking. In Proceedings of CoNLL-2000 and LLL-2000, pages 127–132.
  14. Erik F. Tjong Kim Sang and Jorn Veenstra. 1999. Representing text chunks. In Proceedings of EACL 1999, pages 173–179.
  15. Libin Shen and Aravind K. Joshi. 2003. A SNoW based Supertagger with Application to NP Chunking. In Proceedings of ACL 2003, pages 505–512. find
  16. Kristina Toutanova, 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.
  17. Tong Zhang, Fred Damereau, and David Johnson. 2002. Text chunking based on a generalization of winnow. Journal of Machine Learning Research, 2:615–638. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/tsuruoka-2005-bidirectional-inference-easiest-first-strategy/