A Survey on Recent Advances in Sequence Labeling from Deep Learning Models

POS receives a high degree of acceptance from both academia and industry, which is a standard sequence labeling task that aims at assigning a correct part-of-speech tag to each lexical item (a.k.a., word) such as noun (NN), verb (VB) and adjective (JJ). In general, part-of-speech (POS) tagging can also be viewed as a subclass division of all words in a language, which is thus also called a word class. The tagging system of part-of-speech tags is not usually uniform under different data set, e.g., PTB (Penn Treebank) [72], which includes $45$ different types of POS tags for word classification, such as for sentence “Mr. Jones is editor of the Journal”, it will be labeled with a sequence like ”NNP NNP VBZ NN IN DT NN”.

In fact, Part-of-speech can be regarded as a coarse-grained word cluster task, the goal of which is to label the form and syntactic information of words in a sentence, which is benefit for alleviating the sparseness of word-level features, and servers as an important pre-processing step in natural language processing domain for various subsequent tasks like semantic role labeling or syntax analysis.

Name entity recognition (NER, a.k.a., named entity identification or entity chunking), is a well-known classical sequence labeling task, the goal of which is to identify named entities from text belonging to pre-defined categories, which generally consists of three major categories (i.e., entity, time, and numeric) and seven sub-categories (i.e., person name, organization, location, time, date, currency, and percentage). Particularly, in this paper we mainly focus on the NER problem in English language, and a widely-adopted English taxonomy is CoNLL2003 NER corpus [97], which is collected from Reuters News Corpus that includes four different types of named entities, i.e., person (PER), location (LOC), organization (ORG) and proper nouns (MISC).

Generally, the label of a word in NER is composed of two parts, i.e., “X-Y”, where “X” indicates the position of the labeled word and “Y” refers to the corresponding category within a pre-defined taxonomy. In particular, it may be labeled with a special label (e.g., “none”), if a word cannot be classified into any pre-defined category. Generally, the widely-adopted tagging scheme in the industry is BIOES system, that is, the word labeled “B” (Begin), “I” (Inside) and “E” (End) means that it is the first, middle or last word of a named entity phrase, respectively. The word labeled “0-” (Outside) means it does not belong to any named entity phrase and “S-” (Single) indicates it is the only word that represent an entity.

Named entity recognition is a very important task in natural language processing and is a basic technology for many high-level applications, such as search engine, question and answer systems, recommendation systems, translation systems, etc. Without loss of generality, we take machine translation as example to illustrate the importance of NER for various downstream tasks. In the process of translation, if the text contains named entity with a specific meaning, the translation system usually tends to translate multiple words that make up the named entity separately, resulting in blunt or even erroneous translation results. But if the named entity is identified first, the translation algorithm will have a better understanding of the word order and semantics of the text thus can output a better translation.

The goal of the text chunking task is to divide text into syntactically related non-overlapping groups of words, i.e., phrase, such as noun phrase, verb phrase, etc. The task can be essentially regarded as a sequence labeling problem that assign specific labels to words in sentences. Similar with NER, it can also adopt the BIOES tagging system. For example, the sentence “The little dog barked at the cat.” can be divided into the following phrases: “(The little dog) (barked at) (the cat)”. Therefore, with the BIOES tagging system, the label sequence corresponding to this sentence is “B-NP I-NP E-NP B-VP E-VP B-NP E-NP”, which means that “The little dog” and “the cat” are noun phrases and “barted at” is a verb phrase.

There have been many explorations into applying the sequence labeling framework to address other problems such as dependency parsing [105, 60], semantic role labeling [82, 107], answer selection [132, 56], text error detection [93, 92], document summarization [77], constituent parsing [24], sub-event detection [4], emotion detection in dialogues [102] and complex word identification [25].

Pretrained word embeddings that learned on a large corpus of unlabeled data has become a key component in many neural NLP models. Adopting it to initialize the embedding lookup table can achieve significant improvements over randomly initialized ones, since the syntactic and semantic information within language are captured during the pretraining process. There are many published pretrained word embeddings that have been widely used, such as Word2Vec, Senna, GloVe and etc.

Word2vec [75] is a popular method to compute vector representations of words, which provides two model architectures including the continuous bag-of-words and skip-gram. Santos et al. [99] use word2vec’s skip-gram method to train word embeddings and added to their sequence labeling model. Similarly, some work [91, 92, 20] initialize the word embeddings in their model with publicly available pretrained vectors that created using word2vec. Lample et al. [52] apply skip-n-gram [63] to pretrain their word embeddings, which is a variation of word2vec that accounts for word order. Gregoric et al. [26] follow their work and also used the same embeddings.

Collobert et al. [17] propose the “SENNA” architecture in 2011, which pioneers the idea of solving natural language processing tasks from the perspective of neural language model, and it also includes a construction method of pretrained word embeddings. Many subsequent work [85, 126, 13, 35, 119, 70] adopt SENNA word embeddings as the initial input of their sequence labeling models. Besides, Stanford’s publicly available GloVe embeddings [84] that trained on $6$ billion token corpus from Wikipedia and web text are also widely used and adopted by many work  [71, 121, 65, 1, 122, 116, 55, 34, 10] to initilize their word embeddings.

The above pretrained word embedding methods only generate a single context-independent vector for each word, ignoring the modeling of polysemy problem. Recently, many approaches for learning contextual word representations [85, 86, 1] have been proposed, where bidirectional language models (LM) are trained on a large unlabeled corpus and the corresponding internal states are utilized to produce a word representation. And the representation of each word is dependent on its context. For instance, the generated embedding of the word “present” in “How many people were present at the meeting?” is different from that in “I’m not at all satisfied with the present situation”.

Peters et al. [85] propose pretrained contextual embeddings from bidirectional language models and added them to sequence labeling model, achieving pretty excellent performance on the task of NER and chunking. The method first pretrains the forward and backward neural language model separately with Bi-LSTM architecture on a large, unlabeled corpus. Then it removes the top softmax layer and concatenates the forward and backward LM embeddings to form bidirectional LM embeddings for every token in a given input sequence. Peters et al. extend their method [85] in  [86] by introducing ELMo (Embeddings from Language Models) representations. Unlike previous approaches that just utilize the top LSTM layer, the ELMo representations are a linear combination of internal states of all bidirectional LM layers, where the weight of each layer is task-specific. By adding these representations to existing models, the method significantly improves the performance across a broad range of diverse NLP tasks [10, 34, 15].

Akbik et al. [1] propose a similar method to generate pretrained contextual word embeddings by adopting a bidirectional character-aware language model, which learns to predict the next and previous character instead of word.

Devlin et al. [19] propose a pretraining language representation model called BERT, which stands for Bidirectional Encoder Representations from Transformers. It obtains new state-of-the-art results on eleven tasks and causes a sensation in the NLP communities. The core idea of BERT is to pretrain deep bidirectional representations by jointly conditioning on both left and right context in all layers. Although the sequence labeling tasks can be addressed by fine-tuning the existing pre-trained BERT model, the output hidden states of BERT can also be taken as additional word embeddings to promote the performance of sequence labeling models [67, luo2020hierarchica].

By modeling the context information, the word representations produced by ELMo and BERT can encode rich semantic information. In addition to such context modeling, a recent work proposed by He et al. [31] provide a new kind of word embedding that is both context-aware and knowledge-aware, which encode the prior knowledge of entities from an external knowledge base. The proposed knowledge-graph augmented word representations significantly promotes the performance of NER in various domains.

Although syntactic and semantic information are captured inside the pretrained word embeddings, the word morphological and shape information is normally ignored, which is extremely useful for many sequence labeling tasks like part-of-speech tagging. Recently, many researches learn the character-level representations of words through neural networks and incorporate them into the embedding module of models to exploit useful intra-word information, which can also tackle the out-of-vocabulary word problem effectively and has been verified to be helpful in numerous sequence labeling tasks. The two most common architectures to capture character-to-word representations are Convolutional Neural Networks(CNNs) and Recurrent Neural Networks(RNNs).

Santos and Zadrozny [99] initially propose the approach that using CNNs to learn character-level representations of words for sequence labeling, which is followed by many subsequent work [71, 13, 103, 10, 115, 15, 129]. The approach applies a convolutional operation to the sequence of character embeddings and produces local features of each character. Then a fixed-sized character-level embedding of the word is extracted by using the max over all character windows. The process is depicted in Fig 1.

Xin et al. [116] propose IntNet, a funnel-shaped wide convolutional neural network for learning character-level representations for sequence labeling. Unlike previous CNN-based character embedding approaches, this method delicately designs the convolutional block that comprises of several consecutive operations, and utilizes multiple convolutional layers in which feature maps are concatenated in every other ones. It helps the network to capture different levels of features and explore the full potential of CNNs to learn better internal structure of words. The proposed model achieves significant improvements over other character embedding models and obtains state-of-the-art performance on various sequence labeling datasets. Its main architecture can be shown in Fig 2.

Ling et al. [62] propose a compositional character to word (C2W) model that uses bidirectional LSTMs (Bi-LSTM) to build word embeddings by taking the characters as atomic units. A forward and a backward LSTM processes the character embeddings sequence of a word in direct and reverse order. And the representaion for a word derived from its characters is obtained by combining the final states of the bidirectional LSTM. Illustration of the proposed method is shown in Fig 3. By exploiting the features in language effectively, the C2W model yields excellent results in language modeling and part-of-speech tagging. And many work [52, 127, 26, 121, 88] follow them to apply Bi-LSTM for obtaining character-level representations for sequence labeling. Similarly, Yang et al. [120] employ GRUs for the character embedding model instead of LSTM units.

Dozat et al. [20] propose a RNN based character-level model in which the character embeddings sequence of each word is fed into a unidirectional LSTM followed by an attention mechanism. The method first extracts the hidden state and cell state of each character from the LSTM and then computes linear attention over the hidden states. The output of attention is concatenated with cell state of the final character to form the character-level word embedding for their POS tagging model.

Kann et al. [40] propose a character-based recurrent sequence-to-sequence architecture, which connects the Bi-LSTM character encoding model to a LSTM based decoder that associated with an auxiliary objective (random string autoencoding, word autoencoding or lemmatization). The multi-task architecture introduces additional character-level supervision into the model, which helps them build a more robust neural POS taggers for low-resource languages.

Bohnet et al. [8] propose a novel sentence-level character model for learning context sensitive character-based representations of words. Unlike all aforementioned token-level character model, this method feeds all characters of a sentence into a Bi-LSTM layer and concatenates the forward and backward output vector of the first and last character in the word to form its final character-level representation. This strategy allows context information to be incorporated in the initial word embeddings before flowing into the context encoder module. Similarly, Liu et al. [65] also adopt the character-level Bi-LSTM that processes all characters of a sentence instead of a word. However, their proposed model focuses on extracting knowledge from raw texts by leveraging the neural language model to effectively extract character-level information. In particular, the forward and backward character-level LSTM would predict the next and previous word at word boundaries. In order to mediate the primary sequence labeling task and the auxiliary language model task, highway networks are further employed, which transform the output of the shared character-level layer into two different representations. One is used for language model and the other can be viewed as character-level representation that combined with the word embedding for sequence labeling model.

As aforementioned, enabled by the powerful capacity to extract features automatically, deep neural network based models have the advantage of not requiring complex feature engineering. However, before fully end-to-end deep learning models [71, 52] are proposed for sequence labeling tasks, feature engineering is typically utilized in neural models [17, 35, 13], where hand-crafted features such as word spelling features that can greatly benefits POS tagging and gazetteer features that are widly used in NER are represented as discrete vectors and then integrated to the embedding module. For example, Collobert et al. [17] utilize word suffix, gazetteer and capitalization features as well as cascading features that include tags from related tasks. Huang et al. [35] adopt designed spelling features (include word prefix and suffix features, capitalization feature etc.), context features (unigram, bi-gram and tri-gram features) and gazetteer features. Chiu and Nichols [13] use character-type, capitalization, and lexicon features.

In recent two years, there have been some work [115, 23, 94, 61, 66] that focus on incorporating manual features into neural models in a more effective manner and obtain significant further improvements for sequence labeling. Wu et al. [115] propose a hybrid neural model which combines a feature auto-encoder loss component to utilize hand-crafted features, and significantly outperforms existing competitive models on the task of NER. Exploited manual features include part-of-speech tags, word shapes and gazetteers. In particular, the auto-encoder auxiliary component takes hand-crafted features as input and learns to re-construct them into output, which helps the model to preserve important information stored in these features and thus enhances the primary sequence labeling task. Their proposed method has demonstrated the utility of hand-crafted features for named entity recognition on English data. However, designing such features for low-resource languages is challenging, because gazetteers in these languages are absent. To address this proplem, Rijhwani et al. [94] propose a method of ‘”soft gazetteers” that incorporates information from English knowledge bases through cross-lingual entity linking and create continuous-valued gazetteer features for low-resource languages.

Ghaddar et al. [23] propose a novel lexical representation (called Lexical Similarity i.e., (LS) vector) for NER, indicating that robust lexical features are quiet useful and can greatly benefit deep neural network architectures. The method first embeds words and named entity types into a joint low-dimensional vector space, which is trained from a Wikipedia corpus annotated with 120 fine-grained entity types. Then a 120-dimensional feature vector (i.e., LS vector) for each word is computed offline, where each dimension encodes the similarity of the word embedding with the embedding of an entity type. The LS vectors are finally incorporated into the embedding module of their neural NER model.

Existing research [128] has proved that the global contextual information from the entire sentence is useful for modeling sequence, which is insufficiently captured at each token position in context encoder like Bi-LSTM. To solve this problem, some recent work [67, 68] have introduced sentence-level representations into the embedded module, that is, in addition to pretrained word embeddings and character-level representations, they also assign every word with a global representation learned from the entire sentence, which can be shown in Fig 4. Though these work propose different ways to get sentence representation, they all prove the superiority of adding it in the embedding module for the final performance of sequence labeling tasks.

Bi-LSTM is almost the most widely used context encoder architecture today. Concretely, it incorporates past/future contexts from both directions (forward/backward) to generate the hidden states of each token, and then jointly concatenate them to represent the global information of the entire sequence. While Hammerton [29] has studied utilizing LSTMs for NER tasks in the past, the lack of computing power limits the effectiveness of their model. With recent advances in deep learning, much research effort has been dedicated to using Bi-LSTM architecture and achieve excellent performance. Huang et al. [35] initially adopt Bi-LSTM to generate contextual representations of every word in their sequence labeling model, and produce state-of-the-art accuracy on POS tagging, chunking and NER data sets. Similarly,  [127, 62, 71, 52, 13, 8, 121, 65, 88] also choose the same Bi-LSTM architecture for context encoding. Gated Recurrent Unit(GRU) is a variant of LSTM which also addresses long-dependency issues in RNN networks, and several work utilize Bi-GRU as their context encoder architecture [120, 55, 133].

Rei [91] propose a multitask learning method that equips the Bi-LSTM context encoder module with a auxiliary training objective, which learns to predict surrounding words for every word in the sentence. It shows that the language modeling objective provides consistent performance improvements on several sequence labeling benchmark, because it motivates the model to learn more general semantic and syntactic composition patterns of the language.

Zhang et al. [126] propose a new method called Multi-Order BiLSTM which combines low order and high order LSTMs together in order to learn more tag dependencies. The high order LSTMs predict multiple tags for the current token which contains not only the current tag but also the previous several tags. The model keeps the scalability to high order models with a pruning technique, and achieves the state-of-the-art result in chunking and highly competitive results in two NER datasets.

Ma et al. [69] propose a LSTM-based model for jointly training sentence-level classification and sequence labeling tasks, in which a modified LSTM structure is adopted as their context encoder module. In particular, the method employs a convolutional neural network before LSTM to extract features from both the context and previous tags of each word. Therefore, the input for LSTM is changed to include meaningful contextual and label information.

Most of the existing LSTM based methods use one or more stacked LSTM layers to extract context features of words. However, Gregoric et al. [26] present a different architecture which employs multiple parallel independent Bi-LSTM units across the same input and promotes diversity among them by employing an inter-model regularization term. It shows that the method reduces the total number of parameters in the model and achieves significant improvements on the CoNLL 2003 NER dataset compared to other previous methods.

Kazi et al. [42] propose a novel implicitly-defined neural network architecture for sequence labeling. In contrast to traditional recurrent neural networks, this work provides a different mechanism that each state is able to consider information in both directions. The method extends RNN by changing the definition of implicit hidden layer function:

where $\xi_{t}$ denotes the input of hidden layer, $h_{t-1}$ and $h_{t+1}$ is the hidden state of last and next time step, respectively. It forgoes the causality assumption used to formulate RNN and leads to an implicit set of equations for the entire sequence of hidden states. They compute them via an approximate Newton solve and apply the Krylov Subspace method [45]. The implicitly-defined neural network architecture helps to achieve improvements on problems with complex, long-distance dependencies.

Although Bi-LSTM has been widely adopted as context encoder architecture, there are still several natural limitations, such as the shallow connections between consecutive hidden states of RNNs. At each time step, BiLSTMs consume an incoming word and construct a new summary of the past subsequence. This process should be highly non-linear so that the hidden states can quickly adapt to variable inputs while still retaining useful summaries of the past [83]. Deep transition RNNs extend conventional RNNs by increasing the transition depth of consecutive hidden states [83]. Recently, Liu et al. [67] introduce the deep transition architecture for sequence labeling and achieve a significant performance improvement on the tasks of text chunking and NER. Besides, the way of sequentially processing inputs of RNN might limit the ability to capture the non-continuous relations over tokens within a sentence. To tackle the problem, a recent work proposed by Wei et al. [114] employs self-attention to provide complementary context information on the basis of Bi-LSTM. They propose a position-aware self-attention as well as a well-designed self-attentional context fusion network, aiming to explore the relative positional information of an input sequence for capturing the latent relations among tokens. It shows that the method achieves significant improvements on the tasks of POS, NER and chunking.

Convolutional Neural Networks (CNNs) are another popular architecture for encoding context information in sequence labeling models. Compared to RNN, CNN based methods are considerably faster since it can fully leverage the GPU parallelism through the feed-forward structure. An initial work in this area is proposed by Collobert et al. [17]. The method employs a simple feed-forward neural network with a fixed-size sliding window over the input sequence embedding, which can be viewed as a simplified CNN without pooling layer. And this window approach is based on the assumption that the label of a word depends mainly on its neighbors. Santos et al. [99] follow their work and use similar structure for context feature extraction.

Shen et al. [103] propose a deep active learning based model for NER tasks. Their tagging model extracts context representations for each word using a CNN due to its strong efficiency, which is crucial for their iterative retraining scheme. The structure has two convolutional layers with kernels of width three, and it concatenates the representation at the last convolutional layer with the input embedding to form the output.

Wang et al. [113] employ stacked Gated Convolutional Neural Networks(GCNN) for named entity recognition, which extend the convolutional layer with gating mechanism. In particular, a gated convolutional layer can be written as

where $*$ denotes row convolution, $\mathbf{X}$ is the input of this layer, $\mathbf{W},\hat{\mathbf{b}},\mathbf{V},\hat{\mathbf{c}}$ are the parameters to be learned, $\sigma$ is the sigmoid function and represents element-wise product.

Though relatively high efficiency, a major disadvantage of CNNs is that it has difficulties in capturing long-range dependencies in sequences due to the limited receptive fields, which makes fewer methods to perform sequence labeling tasks with CNNs than RNNs. In recent year, some CNN-based models modify traditional CNNs to better capture global context information and achieve excellent results for sequence labeling.

Strubell et al. [104] propose a Iterated Dilated Convolutional Neural Networks (ID-CNNs) method for the task of NER, which enables significant speed improvements while maintaining accuracy comparable to the state-of-the-arts. Dilated convolutions [123] operate on a sliding window of context like typical CNN layers, but the context need not be consecutive. The convolution is defined over a wider effective input width by skipping over several inputs at a time, and the effective input width can grow exponentially with the depth. Thus it can incorporate broader context into the representation of a token than typical CNN. Fig 5 shows the structure.

The proposed iterated dilated CNN architecture repeatedly applies the same block of dilated convolutions to token-wise representations. Repeatedly employing the same parameters prevents overfitting problem and provides the model desirable generalization capabilities.

Chen et al. [10] propose gated relation network(GRN) for NER, in which a gated relation layer that models the relationship between any two words is built on top of CNNs for capturing long-range context information. Specifically, it firstly computes the relation score vector between any two words,

where $x_{i}$ and $x_{j}$ denote the local context features from the CNN layer for the i-th and j-th word in the sequence, $\mathbf{W}_{rx}$ is the weight matrix and $b_{rx}$ is the bias vector. Note that the relation score vector $r_{ij}$ is of the same dimension as $x_{i}$ and $x_{j}$. Then the corresponding global contextual representation $r_{i}$ for the ith word is obtained by performing a weighted-summing up operation, in which a gating mechanism is adopted for adaptively selecting other dependent words.

where $\sigma$ is a gate using sigmoid function, and $\odot$ denotes element-wise multiplication. The proposed GRN model achieves significantly better performance than ID-CNN [104], owing to its stronger capacity to capture global context dependencies.

The Transformer model is proposed by Vaswani et al. [111] in 2017 and achieves excellent performance for Neural Machine Translation (NMT) tasks. The overall architecture is based solely on attention mechanisms to draw global dependencies between input, dispensing with recurrence and convolutions entirely. The initial proposed Transformer employs a sequence to sequence structure that comprises the encoder and decoder. But the subsequent research work often adopt the encoder part to serve as the feature extractor, thus our introduction here is limited to it.

The encoder is composed of a stack of several identical layers, which includes a multi-head self-attention mechanism and a position-wise fully connected feed-forward network. It employs a residual connection [30] around each of the two sub-layers to ease the training of deep neural network. And layer normalization [53] is applied after the residual connection to stabilize the activations of model.

Due to its superior performance, the Transformer is widely used in various NLP tasks and has achieved excellent results. However, in sequence labeling tasks, the Transformer encoder has been reported to perform poorly [28]. Recently, Yan et al. [118] analyze the properties of Transformer for exploring the reason why Transformer does not work well in sequence labeling tasks especially NER. Both the direction and relative distance information are important in the NER, but these information will lose when the sinusoidal position embedding is used in the vanilla Transformer. To address the problem, they propose TENER, an architecture adopting adapted Transformer Encoder by incorporating the direction and relative distance aware attention and the un-scaled attention, which can greatly boost the performance of Transformer encoder for NER. Star-Transformer is a lightweight alternative of Transformer proposed by Shao et al. [28]. It replaces the fully-connected structure with a star-shaped topology, in which every two non-adjacent nodes are connected through a shared relay node. The model complexity is reduced significantly, and it also achieved great improvements against the standard Transformer on various tasks including sequence labeling tasks.

The softmax function that also called normalized exponential function, is a generalization of logic functions and has been widely used in a variety of probability-based multi-classification methods. It maps a $K$-dimensional vector $z$ into another $K$-dimensional real vector $\sigma(z)$ such that each element has a range between $0$ and $1$ and the sum of all elements equals $1$. The form of the function is usually given by the following formula

where $j=1,\dots,K$.

Many models for sequence labeling treat the problem as a set of independent classification tasks, and utilize a softmax layer as a linear classifier to assign optimal label for each word in a sequence [8, 26, 62, 42, 27, 69, 43, 44]. Specifically, given the output representation $h_{t}$ of the context encoder at time step $t$, the probability distribution of the t-th word’s label can be obtained by a fully connected layer and a final softmax function

where the weight matrix $\mathbf{W}\in{R^{d\times|T|}}$ maps $h_{t}$ to the space of labels, $d$ is the dimension of $h_{t}$ and $|T|$ is the number of all possible labels.

The above methods of independently inferring word labels in a given sequence ignore the dependencies between labels. Typically, the correct label to each word often depends on the choices of nearby elements. Therefore, it is necessary to consider the correlation between labels of adjacent neighborhoods to jointly decode the optimal label chain of the entire sequence. CRF model [45] has been proven to be powerful in learning the strong dependencies across output labels, thus most of the neural network-based models for sequence labeling employ CRF as the inference module [71, 121, 65, 88, 91, 85, 1, 125, 9, 22].

Specifically, let $\mathbf{Z}=[\hat{\mathbf{z}}_{1},\hat{\mathbf{z}}_{2},\ldots,\hat{\mathbf{z}}_{n}]^{\top}$ be the output of context encoder of the given sequence $\hat{\mathbf{x}}$, the probability $\Pr(\hat{\mathbf{y}}|\hat{\mathbf{x}})$ of generating the whole label sequence $y_{i}\in\hat{\mathbf{y}}$ with regard to $\mathbf{Z}$ is

where $\mathbf{Y}(\mathbf{Z})$ is the set of possible label sequences for $\mathbf{Z}$; $\phi(y_{j-1},y_{j},\hat{\mathbf{z}}_{j})\!=\!\exp(\mathbf{W}_{y_{j-1},y_{j}}\hat{\mathbf{z}}_{j}+b_{y_{j-1},y_{j}}),$ $\mathbf{W}_{y_{j-1},y_{j}}$ and $b_{y_{j-1},y_{j}}$ indicate the weighted matrix and bias parameters corresponding to the label pair $(y_{j-1},y_{j})$, respectively.

Semi-Markov conditional random fields (semi-CRFs) [100] is an extension of conventional CRFs, in which labels are assigned to the segments of input sequence rather than to individual words. It extracts features of segments and models the transition between them, suitable for segment-level sequence labeling tasks such as named entity recognition and phrase chunking. Compared to CRFs, the advantage of semi-CRFs is that it can make full use of segment-level information to capture the internal properties of segments, and higher-order label dependencies can be taken into account. However, since it jointly learns to determine the length of each segment and the corresponding label, the time complexity becomes higher. Besides, more features is required for modeling segments with different lengths and automatically extracting meaningful segment-level features is an important issue for Semi-CRFs. With advances in deep learning, some models combining neural networks and Semi-CRFs for sequence labeling have been studied.

Kong et al. [46] propose Segmental Recurrent Neural Networks (SRNNs) for segment-level sequence labeling problems, which adopts a semi-CRF as the inference module and learns representations of segments through Bi-LSTM. Based on the recurrent nature of RNN, this method further designs a dynamic programming algorithm to reduce the time complexity. A parallel work Gated Recursive Semi-CRFs (grSemi-CRFs) proposed by Zhuo et al. [134] employs a Gated Recursive Convolutional Neural Network (grConv) [14] to extract segment features for semi-CRF. The grConv is a variant of recursive neural network that learns segment-level representations by constructing a pyramid-like structure and recursively combining adjacent segment vectors. The follow-up work proposed by Kemos et al. [43] utilize the same grConv architecture for extracting segment features in their neural semi-CRF model. It takes characters as the basic input unit but does not require any correct token boundaries, which is different from existing character-level models. The model is based on semi-CRF to jointly segment (tokenize) and label characters, being robust for languages with difficult or noisy tokenization. Sato et al. [101] design Segment-level Neural CRF for segment-level sequence labeling tasks. The method applies a CNN to obtain segment-level representations and constructs segment lattice to reduce search space.

The aforementioned models only adopt segment-level labels for segment score calculation and model training. An extension [122] proposed by Ye et al. demonstrates that incorporating word-level labels information can be beneficial for building semi-CRFs. The proposed Hybrid Semi-CRFs(HSCRF) model utilizes word-level and segment-level labels simultaneously to derive the segment scores. Besides, the methods of integrating CRF and HSCRF output layers into an unified network for jointly training and decoding are further presented. The Hybrid Semi-CRFs model is also adopted as baseline for subsequent work  [66].

RNN is extremely suitable for feature extraction of sequential data, so it is widely used for encoding contextual information in sequence labeling models. Some studies demonstrate that RNN structure can also be adopted in the inference module for producing optimal label sequence. In addition to the learned representations output from context encoder, the information of former predicted labels also serves as an input. Thus the corresponding label of each word is generated based on both the features of input sequence and the previous predicted labels, making long-range label dependencies captured. However, unlike the global normalized CRF model, the RNN-based reasoning method greedily decodes the label from left to right, so it’s a local normalized model that might suffer from label bias and exposure bias problems [2].

Shen et al. [103] employ a LSTM layer on top of the context encoder for label decoding. As dipicted in Fig 6, the decoder LSTM takes the last generated label as well as the contextual representation of current word as inputs, and computes the hidden state which will be passed through softmax function to finally decode the label. Zheng et al. [130] adopt a similar LSTM structure as the inference module of their sequence labeling model.

Unlike the above two studies, Vaswani et al. [110] utilize a LSTM decoder that can be considered as parallel with the context encoder module. The LSTM only accepts the last label as input to produce a hidden state, which will be combined with the word context representation for label decoding. Zhang et al. [127] introduce a novel joint labeling strategy based on LSTM decoder. The output hidden state and contextual representation are not integrated before the labeling decision is made but independently estimate the labeling probability. Those two probabilities are then merged by weighted averaging to produce the final result. Specifically, a parameter is dynamically computed by a gate mechanism to adaptively balance the involvement of the two parts. Experiments show that the proposed label LSTM could significantly improve the performance.

Zhai et al. [124] propose a neural sequence chunking model based on an encoder-decoder-pointer framework, which is suitable for tasks that need assign labels to meaningful chunks in sentences, such as phrase chunking and semantic role labeling. The architecture is illustrated in Fig 7. The proposed model divides original sequence labeling task into two steps: (1) Segmentation, identifying the scope of each chunk; (2) Labeling, treating each chunk as a complete unit to label. It adopts a pointer network [112] to process the segmentation by determining the ending point of each chunk and the LSTM decoder is utilized for labeling based on the segmentation results. The model proposed by Li et al. [55] also employs the similar architecture for their text segmentation model, where a seq2seq model equipped with pointer network is designed to infer the segment boundaries.

We will introduce three widely used datasets for part-of-speech tagging: WSJ, UD and Rit-Twitter.

We will introduce three widely used datasets for NER : CoNLL 2002, CoNLL 2003 and OntoNotes.

Accuracy depicts the ratio of the number of correctly classified instances and the total number of instances, which can be computed using the following equation

where $TP,TN,FP,FN$ denote True positive, True negative, False positive, False negative, respectively.

F1-score indicates the fraction of correctly classified instances for each class within the dataset, which can be computed as follows

where $PREC$ is precision that is computed by $PREC=\frac{TP}{TP+FP}$, $REC$ is recall that can be computed by $REC=\frac{TP}{TP+FN}$, and $C$ denotes the total number of classes.