Sequence Labeling Algorithm

A Sequence Labeling Algorithm is a Sequence Learning Algorithm that tags sequences in text documents.

• AKA: Sequence-Member Tagging Algorithm, Sequential Labeling Algorithm.
• Context:
  • It can be implemented by a Sequence Labeling System to solve a Sequence Labeling Task.
  • It can range from being a Supervised Sequence Labeling Algorithm, to being a Semi-Supervised Sequence Labeling Algorithm, to being an Unsupervised Sequence Labeling Algorithm.
• Example(s):
  • a Constrained Sequential Labeling (CSL) Algorithm (Chen et al., 2014).
  • a Sequential Labeling with Latent Variables Task.
  • …
• Counter-Example(s):
  • a Sequence Segmentation Task.
  • a Sequence Classification Task, (maps a Sequence to a Category).
    • a Named Entity Mention Classification Task, such as the identification of Person Mentions in a Document.
• See: Data Stream Mining Task, Online Learning Task.

---

---

References

2014

• (Chen et al., 2014) ⇒ Sheng Chen, Alan Fern, and Sinisa Todorovic (2014). "Multi-Object Tracking via Constrained Sequential Labeling". In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
  • QUOTE: In this work, rather than heuristically simplify the mid-level labeling problem to an efficiently solvable framework, we instead develop a greedy labeling approach that can operate directly on the original (unsimplified) problem. In particular, our approach conducts tracking by sequentially labeling mid-level video features with object identifiers, under hard constraints. Our new algorithm, called constrained sequential labeling (CSL), uses a flexible cost function to sequentially assign labels while directly respecting the implications of hard constraints (e.g., a person cannot be at two distinct locations)

2010

• (Wu et al., 2010) ⇒ Yu-Chieh Wu, Yue-Shi Lee, Jie-Chi Yang, and Show-Jane Yen (2010, December). "An Integrated Deterministic and Nondeterministic Inference Algorithm for Sequential Labeling". In: Asia Information Retrieval Symposium. DOI:10.1007/978-3-642-17187-1_21
  • QUOTE: In this paper, we present a new search algorithm for sequential labeling tasks based on the conditional Markov models (CMMs) frameworks.

2009

• (Sun & Tsujii, 2009) ⇒ Xu Sun, and Junichi Tsujii (2009, March). "Sequential Labeling with Latent Variables: An Exact Inference Algorithm and its Efficient Approximation". In: Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009).

2003

• (Sha & Pereira, 2003a) ⇒ Fei Sha, and Fernando Pereira. (2003). “Shallow Parsing with Conditional Random Fields.” In: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (HLT-NAACL 2003). doi:10.3115/1073445.1073473
  • QUOTE: Sequence analysis tasks in language and biology are often described as mappings from input sequences to sequences of labels encoding the analysis. In language processing, examples of such tasks include part-of-speech tagging, named-entity recognition, and the task we shall focus on here, shallow parsing.

2002

• (Collins, 2002a) ⇒ Michael Collins. (2002). “Ranking Algorithms for Named–Entity Extraction: Boosting and the voted perceptron.” In: Proceedings of the ACL Conference (ACL 2002).
  • QUOTE: The problem can be framed as a tagging task – to tag each word as being either the start of an entity, a continuation of an entity, or not to be part of an entity at all (we will use the tags S, C and N respectively for these three cases).

---