自然语言处理：序列标注（BiLSTM-CRF）

Reference:

1. Bidirectional LSTM-CRF Models for Sequence Tagging
2. Neural Architectures for Named Entity Recognition
3. Character-based BiLSTM-CRF Incorporating POS and Dictionaries for Chinese Opinion Target Extraction
4. CRF Layer on the Top of BiLSTM
5. Bi-LSTM + CRF with character embeddings for NER and POS

Tagging Scheme

IOBES: Inside, Outside, Beginning, End, Single

Bidirectional LSTM Networks

By utilize bidirectional LSTM, we can efficiently make use of past features (via forward states) and future features (via backward states) for a specific time frame.

We train the bidirectional LSTM networks using BPTT, and specially treat at the beginning and the end of the data points. Such as reset the hidden states to 0 at the begging of each sentence.

At time $t$ for NER task:

• the input layer represents features could be one-hot-encoding for word feature, dense vector features, or sparse features.
• the output layer represents a probability distribution (distributed by softmax) over labels. It has the same dimensionality as size of labels. Using the label with the max probability as output of timestep $t$.

Why use the CRF Networks?

Despite use the $\boldsymbol h_t$ as features to make independent tagging decisions for each output $y_t$ is success in POS tagging, the independent classification decisions are limiting when there are strong dependencies across output labels.

As the NER task, since the “grammar” that characterizes interpretable sequences of tags imposes several hard constraints (e.g. I-PER cannot follow B-LOC) that would be impossible to model with independence assumptions.

The first way is to predict a distribution of tags of each time step and then use beam-like decoding to find optimal tag sequences, such as Maximum entropy classifier (Ratnaparkhi, 1996) and Maximum entropy Markov models (McCallum etal., 2000).

The second way is to focus on sentence level instead of individual positions, thus leading to Conditional Random Fields (CRF) models that the inputs and outputs are directly connected, as opposed to LSTM networks where memory cells/recurrent components are employed.

如下最右侧图，若不考虑不同位置词标注之间的关系，会出现错误的标注。

对于序列标注任务，输入词序列为观测序列，带标注的序列为隐藏状态序列。基于状态独立假设的序列标注模型，无法处理不同状态间的硬性约束，MRMM、CRF擅长解决此类问题。

MEMM假设当前状态仅与上一状态有关（马尔可夫性假设），CRF没有马尔可夫性假设，预测每个状态时考虑全局状态信息。

HMM（马尔可夫性假设、观测独立性假设） -> MEMM（马尔可夫性假设）-> CRF

CRF Networks

BiLSTM-CRF networks

Given $\boldsymbol x=(x_1,x_2,\cdots,x_n)$ and $\boldsymbol y=(y_1,y_2,\cdots,y_n)$ to represent an input sequence and a sequence of predicted tags respectively, where $n$ is the length of the input sentence.

Emission score

We consider $\boldsymbol P\in\R^{n\times k}$ to be the matrix of scores output by the BiLSTM network, where $k$ is the number of distinct tags, the element $P[i,j]$ corresponds to the score of the $j$-th tag of the $i$-th word in a sentence.

In BiLSTM-CRF networks, emission scores come from the BiLSTM layer. For instance, according the above figure, the score of $w_0$ labeled as B-Person is 1.5.

对于长度为$n$的句子，发射矩阵$P$包含$n$个$k$维的隐藏状态.

Transition score

CRF introduces a transition matrix $\boldsymbol A\in\R^{(k+2)\times(k+2)}$, that is position independent, which measure the score from $i$-th tag to $j$-th tag by the element $A[i,j]$.

In order to make the transition score matrix more robust, we will add the START and the END tags of a sentence to the set of possible tags. $\boldsymbol A$ is therefore a square matrix of size $k+2$.

Here is an example of the transition matrix score including the extra added START and END labels.

As shown in the table above, we can find that the transition matrix has learned some useful constraints.

• The label of first word in a sentence should start with “B-” or “O”, not “I-”.
• etc.

Where or how to get the transition matrix?

Transition matrix is a parameter of CRF layer. It’s initialization with random value, that will be more and more reasonable gradually with increasing training iterations.

Decoding

For a sentence has 5 words: $x_1,x_2,x_3,x_4,x_5$, the real tags $\boldsymbol y$ is:

"START B-Person I-Person O B-Organization O END"

Here, we add two more extra words which denote the start and the end of sentence: $x_0,x_6$.

A linear-chain CRF defines a global score $s(\boldsymbol x,\boldsymbol y)$ consists of 2 parts, such that:
$s(\boldsymbol x,\boldsymbol y)=s_e(\boldsymbol x,\boldsymbol y)+ s_t(\boldsymbol y) =\sum_{i=1}^nP[x_i,y_i]+\sum_{i=0}^{n}A[y_{i},y_{i+1}]$

Emission Score
$s_e(\boldsymbol x,\boldsymbol y)=P[x_0,\text{START}]+P[x_1,\text{B-Person}]+\cdots+P[x_6,\text{END}]$

where $P_0$ and $P_6$ just set them zeros, $P_1\cdots P_5$ are from the previous BiLSTM.

Transition Score
$s_t(\boldsymbol y)=A[\text{START},\text{B-Person}] + A[\text{B-Person},\text{I-Person}] + \cdots + A[\text{O},\text{END}]$

these score are actually the parameters of CRF layer.

Illustration of the scoring of a sentence with linear-chain CRF:

Now that we understand the scoring function of the CRF, we need to do 2 things:

• Find the sequence of tags with the best score.
• Compute a probability distribution over all the sequence of tags (total score).

The simplest way to measure the total score is that: enumerating all the possible paths and sum their scores. However, it is very inefficient, with $n^k$ complexity. The recurrent nature of our formula makes it the perfect candidates to apply dynamic programming.

Find the sequence of tags with the best score (best path)

Let’s suppose that $c_t(y_t,\boldsymbol x)$ is the solution for time steps $t,\cdots,n$ for sequences that start with $y_t$:

$\begin{aligned} c_t(y_t,\boldsymbol x) &={\arg\max}_{y_t,\cdots, y_n}s(y_t,\cdots y_n,\boldsymbol x)\\[1ex] &={\arg\max}_{y_t,\cdots, y_n}P[x_t,y_t]+A[y_t,y_{t+1}]+s(y_{t+1},\cdots,y_n,\boldsymbol x)\\[1ex] &=\arg\max\nolimits_{y_{t+1}}P[x_t,y_t]+A[y_t,y_{t+1}]+c_{t+1}(y_{t+1},\boldsymbol x) \end{aligned}$
The best score and path are:
$s(\boldsymbol x,\boldsymbol y^*)=c_0(y_0=\text{START},\boldsymbol x)，\quad\boldsymbol y^*=\arg\max_{\tilde{\boldsymbol y}\in Y} s(\boldsymbol x,\tilde{\boldsymbol y})$
As we perform $n$ step, final cost is $O(nk^2)$, much less than $O(k^n)$.

类似于CRF解码（已知模型、观测求最可能的状态序列）的维特比算法

Probability distribution over the sequence of tags (total path)

The final step of a linear chain CRF is to apply a softmax to the scores of all possible sequences to get the probability $p(\boldsymbol y)$ of a given sequence of tags $\boldsymbol y$. To do that, we need to compute the partition factor:

$Z=\sum_{\tilde{\boldsymbol y}}\exp(s(\boldsymbol x, \tilde{\boldsymbol y}))$
Let’s call $Z_t(y_t)$ the sum of scores for all sequences that start at time step $t$ with tag $y_t$. Then, $Z_t$ verifies:
$\begin{aligned} Z_t(y_t) &=\sum_{y_{t+1},\cdots,y_n}\exp({s(y_t,\cdots,y_n,\boldsymbol x)})\\[.5ex] &=\sum_{y_{t+1}}\exp({P[x_{t+1},y_{t+1}]+A[y_t,y_{t+1}]})\sum_{y_{t+2},\cdots,y_n} \exp({s(y_{t+1},\cdots,y_n,\boldsymbol x)})\\[.5ex] &=\sum_{y_{t+1}}\exp({P[x_{t+1},y_{t+1}]+A[y_t,y_{t+1}]})\cdot Z_{t+1}(y_{t+1}) \end{aligned}$
Then, we can easily define the probability of a given sequence of tags as:

$p(\boldsymbol y|\boldsymbol x)=\frac{1}{Z}\exp(s(\boldsymbol x,\boldsymbol y)),\quad Z=\sum_{y_1}Z_1(y_1)$

Loss function

CRF loss function is consist of the real path score and the total score of all the possible paths. The real path should having the highest score among those of all possible paths.

The loss function of CRF model as below (minimize loss function):
$L(\theta)=-\log p(\boldsymbol y|\boldsymbol x) =-s(\boldsymbol x,\boldsymbol y) + \text{logadd}_{\tilde{\boldsymbol y}\in Y}\ s(\boldsymbol x,\tilde{\boldsymbol y})$

where the score $s(\boldsymbol x,\boldsymbol y)$ of real path should be the one with largest percentage in all the scores, $Y$ represents all possible tag sequences, even those that do not verify the IOB format for a sentence $\boldsymbol x$.

During the training process, the parameter values of our BiLSTM-CRF model will be updated again and again to keep increasing the percentage of the score of the real path.

Bi-LSTM-CRF Networks

Combine a Bi-LSTM network and a CRF network to form a Bi-LSTM-CRF model. This network can efficiently use past input features via a Bi-LSTM layer and sentence level tag information via a CRF layer.

We construct our neural network by using hidden state of Bi-LSTM layer as input sequence of CRF layer. We can use the concatenation hidden states (forward + backward), denoted as $\boldsymbol h_t$ of $x_t$ to predict the tag of corrected $x_t$ directly, since it contains the context information.

We feed those hidden states $\boldsymbol h=(\boldsymbol h_1,\boldsymbol h_2,\cdots,\boldsymbol h_n)$ into CRF layer:
$\boldsymbol P=\boldsymbol W_s\boldsymbol h + \boldsymbol b_s$

where $\boldsymbol W_s$ and $\boldsymbol b_s$ are the parameters.

转载：https://blog.csdn.net/sinat_34072381/article/details/105869963