HMM, MEMM, and CRF are known as the three classic probabilistic graphical models. In the era of machine learning before deep learning, they were widely used in various sequence labeling tasks. An interesting phenomenon is that in the era of deep learning, HMM and MEMM seem to have "faded away," leaving only CRF on the stage. I believe that NLP practitioners, even if they haven’t implemented it themselves, have heard of using BiLSTM+CRF for tasks like Chinese word segmentation and Named Entity Recognition (NER), yet almost no one hears about BiLSTM+HMM or BiLSTM+MEMM. Why is this?
Today, let us study MEMM and, through a comparison with CRF, gain a deeper understanding of the ideas and design of probabilistic graphical models.
Model Derivation
MEMM stands for Maximum Entropy Markov Model. It must be said that this name might intimidate 80% of beginners: "I don’t understand Maximum Entropy yet, and I don’t know Markov; isn’t the combination of the two like a divine script?" In fact, whether it is MEMM or CRF, their models are much simpler than their names suggest. Their concepts and designs are very simple and natural, and not difficult to understand.
Reviewing CRF
As a comparison, let’s review CRF. I say "review" because I have previously written an article introducing CRF. Readers who are not yet familiar with CRF can first read the previous work "A Brief Introduction to Conditional Random Fields (CRF) with a Pure Keras Implementation". For simplicity, the CRF and MEMM introduced in this article are the simplest "linear chain" versions.
This article uses sequence labeling as an example. That is, given an input sequence \boldsymbol{x}=(x_1,x_2,\dots,x_n), we hope to output a label sequence of the same length \boldsymbol{y}=(y_1,y_2,\dots,y_n). Thus, we are modeling the probability distribution: P(\boldsymbol{y}|\boldsymbol{x})=P(y_1,y_2,\dots,y_n|\boldsymbol{x})\label{eq:target} CRF treats \boldsymbol{y} as a whole and calculates a total score. The calculation formula is as follows: \begin{aligned}f(y_1,y_2,\dots,y_n;\boldsymbol{x})=&\,f(y_1;\boldsymbol{x})+g(y_1,y_2)+\dots+g(y_{n-1},y_n)+f(y_n;\boldsymbol{x})\\ =&\,f(y_1;\boldsymbol{x}) + \sum_{k=2}^n \big(g(y_{k-1},y_k)+f(y_k;\boldsymbol{x})\big)\end{aligned} The characteristic of this scoring function is that it explicitly considers the association between adjacent labels. Here, g(y_{k-1},y_k) is called the transition matrix. Now that the score is calculated, the probability is the softmax of the score, so the final probability distribution is set as: P(\boldsymbol{y}|\boldsymbol{x})=\frac{e^{f(y_1,y_2,\dots,y_n;\boldsymbol{x})}}{\sum\limits_{y_1,y_2,\dots,y_n}e^{f(y_1,y_2,\dots,y_n;\boldsymbol{x})}}\label{eq:crf-p}
If limited only to concepts, the introduction to CRF ends here. In summary, the target sequence is treated as a whole, a scoring function is designed for the target, and then a global softmax is performed on the scoring function. This modeling philosophy is consistent with ordinary classification problems. The difficulty of CRF lies in the code implementation because the denominator in the above formula involves the summation over all possible paths, which is not an easy task. However, in terms of conceptual understanding, I believe there is nothing particularly difficult.
The Simpler MEMM
Now let’s introduce MEMM, which can be seen as an extremely simplified seq2seq model. For the target in Eq. \eqref{eq:target}, it considers the decomposition: P(y_1,y_2,\dots,y_n|\boldsymbol{x})=P(y_1|\boldsymbol{x})P(y_2|\boldsymbol{x},y_1)P(y_3|\boldsymbol{x},y_1,y_2)\dots P(y_n|\boldsymbol{x},y_1,y_2,\dots,y_{n-1}) Then, assuming that label dependence only occurs at adjacent positions: P(y_1,y_2,\dots,y_n|\boldsymbol{x})=P(y_1|\boldsymbol{x})P(y_2|\boldsymbol{x},y_1)P(y_3|\boldsymbol{x},y_2)\dots P(y_n|\boldsymbol{x},y_{n-1})\label{eq:p-f} Next, following the design of the linear chain CRF, we can set: P(y_1|\boldsymbol{x})=\frac{e^{f(y_1;\boldsymbol{x})}}{\sum\limits_{y_1}e^{f(y_k;\boldsymbol{x})}},\quad P(y_k|\boldsymbol{x},y_{k-1})=\frac{e^{g(y_{k-1},y_k)+f(y_k;\boldsymbol{x})}}{\sum\limits_{y_k}e^{g(y_{k-1},y_k)+f(y_k;\boldsymbol{x})}}\label{eq:memm} This gives us the MEMM. Since MEMM has already decomposed the overall probability distribution into a product of step-by-step distributions, calculating the loss only requires summing the cross-entropy of each step.
The Relationship Between the Two
Substituting Eq. \eqref{eq:memm} back into Eq. \eqref{eq:p-f}, we get: P(\boldsymbol{y}|\boldsymbol{x})=\frac{e^{f(y_1;\boldsymbol{x})+g(y_1,y_2)+\dots+g(y_{n-1},y_n)+f(y_n;\boldsymbol{x})}}{\left(\sum\limits_{y_1}e^{f(y_1;\boldsymbol{x})}\right)\left(\sum\limits_{y_2}e^{g(y_1,y_2)+f(y_2;\boldsymbol{x})}\right)\dots\left(\sum\limits_{y_n}e^{g(y_{n-1},y_n)+f(y_n;\boldsymbol{x})}\right)}\label{eq:memm-p}
Comparing Eq. \eqref{eq:memm-p} and Eq. \eqref{eq:crf-p}, we can find that the difference between MEMM and CRF lies only in the calculation method of the denominator (i.e., the normalization factor). We call Eq. \eqref{eq:crf-p} of CRF globally normalized, while Eq. \eqref{eq:memm-p} of MEMM is called locally normalized.
Model Analysis
In this section, we analyze the advantages, disadvantages, improvements, and effects of MEMM.
Advantages and Disadvantages of MEMM
A clear feature of MEMM is its simple implementation and fast speed. Because it only needs to perform softmax independently at each step, MEMM is fully parallelizable, and its speed is basically the same as direct step-by-step Softmax. For CRF, the denominator in Eq. \eqref{eq:crf-p} is not so easy to calculate; it eventually transforms into a recursive calculation that can be computed in \mathcal{O}(n) time (for details, please refer to "A Brief Introduction to Conditional Random Fields (CRF) with a Pure Keras Implementation"). Recursion implies serial processing; therefore, when the main part of our model is a highly parallelizable architecture (such as pure CNN or pure Attention architectures), CRF will significantly slow down the training speed of the model. Later, we will compare the training speeds of MEMM and CRF (of course, it is only the training that is slower; in the prediction stage, the speeds of MEMM and CRF are the same).
As for the disadvantages, they certainly exist. As mentioned earlier, MEMM can be seen as an extremely simplified seq2seq model. Since this is the case, it inherits all the drawbacks of ordinary seq2seq models. A prominent problem in seq2seq is exposure bias, which in MEMM is referred to as label bias. Roughly speaking: when training MEMM, for the prediction of the current step, it is assumed that the true label of the previous step is known. In this way, if a label A can only be followed by label B, the model only needs to optimize the transition matrix to achieve this, without needing to optimize the influence of the input \boldsymbol{x} on B (i.e., f(B;\boldsymbol{x}) is not well optimized). However, in the prediction stage, the true label is unknown. We might not be able to predict the previous label A with high confidence, and since f(B;\boldsymbol{x}) was not strengthened during training, the current step B cannot be accurately predicted either. This may lead to incorrect prediction results.
Bidirectional MEMM
Label bias might be hard to understand, but we can look at the shortcomings of MEMM from another perspective: in fact, compared to CRF, a clearly less elegant aspect of MEMM is its asymmetry—it performs probability decomposition from left to right. My experiments show that if this asymmetry can be resolved, the performance of MEMM can be slightly improved. My idea is: perform MEMM from right to left as well. At this time, the corresponding probability distribution is: P(\boldsymbol{y}|\boldsymbol{x})=\frac{e^{f(y_1;\boldsymbol{x})+g(y_1,y_2)+\dots+g(y_{n-1},y_n)+f(y_n;\boldsymbol{x})}}{\left(\sum\limits_{y_n}e^{f(y_n;\boldsymbol{x})}\right)\left(\sum\limits_{y_{n-1}}e^{g(y_n,y_{n-1})+f(y_{n-1};\boldsymbol{x})}\right)\dots\left(\sum\limits_{y_1}e^{g(y_2,y_1)+f(y_1;\boldsymbol{x})}\right)} Then calculate a cross-entropy and average it with the cross-entropy from the left-to-right Eq. \eqref{eq:memm-p} as the final loss. In this way, the model considers both left-to-right and right-to-left directions simultaneously without adding parameters, making up for the defect of asymmetry. To distinguish it, I call it Bi-MEMM, analogous to the naming of Bi-LSTM.
Note: The term Bi-MEMM did not first appear here. According to my research, the first to propose the concept of Bi-MEMM was the paper "Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data", where Bi-MEMM refers to a bidirectional decoding strategy for MEMM, which has a different meaning from the Bi-MEMM in this blog.
Experimental Results Demonstration
To verify and compare the effects of MEMM, I implemented both CRF and
MEMM in bert4keras
and wrote two scripts: Chinese word segmentation
(task_sequence_labeling_cws_crf.py) and Chinese Named
Entity Recognition (task_sequence_labeling_ner_crf.py). In
these two scripts, switching from CRF to MEMM is very simple; you only
need to replace ConditionalRandomField with
MaximumEntropyMarkovModel.
Detailed experimental data will not be posted here as they are just numbers. Below are some relative comparison results:
1. Under the same experimental parameters, Bi-MEMM is always better than MEMM, and MEMM is always better than Softmax;
2. Under the same experimental parameters, CRF is basically not worse than Bi-MEMM;
3. When the encoding model’s capability is strong, CRF and Bi-MEMM perform equally; when the encoding model is weak, CRF is better than Bi-MEMM by about 0.5%;
4. When using a 12-layer BERT-base model as the encoding model, Bi-MEMM is 25% faster than CRF; when using a 2-layer BERT-base model, Bi-MEMM is 1.5 times faster than CRF.
(Note: Since I found that Bi-MEMM always performs slightly better
than MEMM and the training time for both is basically the same, the
MaximumEntropyMarkovModel in bert4keras defaults to
Bi-MEMM.)
Thinking and Extension
Based on the above conclusions, the "decline" of MEMM in the deep learning era seems understandable—MEMM has no advantage over CRF except for faster training speed. The prediction speeds of the two are the same, and most of the time we are mainly concerned with prediction speed and performance; a slightly slower training speed is acceptable. The comparison results of these two models are representative. It can be said that this is exactly the difference between all global normalization and local normalization models: Global normalization models usually perform better, but their implementation is usually relatively difficult; local normalization models usually do not exceed global normalization models in performance, but they excel in ease of implementation and extensibility.
How are they easy to extend? Here are two examples.
The first example: suppose the number of labels is very large, such
as when using sequence labeling for text correction or text generation
(relevant examples can be found in the paper "Fast Structured Decoding
for Sequence Models"). The number of labels is the vocabulary size
|V|. Even with subword methods, the
vocabulary size is at least ten or twenty thousand. At this time, the
number of parameters in the transition matrix reaches hundreds of
millions (|V|^2), making it difficult
to train. Readers might think of low-rank decomposition. Indeed,
low-rank decomposition can control the number of parameters in the
transition matrix to 2d|V|, where d is the dimension of the intermediate layer.
Unfortunately, for CRF, low-rank decomposition cannot change the fact
that the calculation of the normalization factor is large, because the
normalization factor of CRF still needs to be restored to a |V|\times|V| transition matrix to continue
the calculation. Therefore, for scenarios with a huge number of labels,
CRF cannot be used directly. Fortunately, for MEMM, low-rank
decomposition can effectively reduce the computational load during
training, allowing it to still be used effectively. The
MaximumEntropyMarkovModel included in bert4keras has
already integrated low-rank decomposition. Interested readers can check
the source code for details.
The second example: the CRF and MEMM introduced above only consider associations between adjacent labels. What if I want to consider more complex adjacency associations? For example, considering the association of y_k with both y_{k-1} and y_{k-2} simultaneously? At this point, the global normalization approach of CRF becomes very difficult to operate, ultimately because the normalization factor is hard to calculate. However, the local normalization approach of MEMM is easy to carry out. In fact, the hierarchical labeling approach for information extraction I designed previously can also be said to be a locally normalized probabilistic graphical model similar to MEMM, and the associations it considers are even more complex.
Summary
This article introduces and briefly extends MEMM, which is a classic case of probabilistic graphical models like CRF. Its main difference from CRF lies in the normalization method. Then, I made a simple comparison between the two through experiments and concluded that MEMM trains faster but does not outperform CRF. Nevertheless, I believe MEMM still has its merits, so I concluded by conceiving some extensions for MEMM.
If reprinting, please include the original address: https://kexue.fm/archives/7213
For more detailed reprinting matters, please refer to: "Science Space FAQ"