This article aims to explain the principles of CRF (Conditional Random Field) in the most concise language possible. The phrase "In A Nutshell" here implies an introduction or a popular science explanation (following the example of Stephen Hawking’s The Universe in a Nutshell).
Most articles introducing CRF online, whether in Chinese or English, generally start by discussing concepts of probabilistic graphical models, then introduce the exponential formula for features, and finally declare it as CRF. The so-called "probabilistic graph" is merely a way to understand it visually. However, if the explanation fails to touch upon the core principles, providing too many metaphors only leaves the reader confused, thinking you are just showing off. (Speaking of which, I’d like to vent a bit: solving a neural network is clearly just calculating a gradient and then iterating. This is so easy to understand, yet people insist on giving it the pretentious name "Backpropagation." If you don’t clarify that its essence is differentiation and iterative solving, how many readers will actually understand it when you jump straight to "Backpropagation"?)
Alright, enough nonsense. Let’s get to the main topic.
Per-label Softmax
CRF is commonly found in tasks related to sequence labeling. Suppose our model input is Q and the output target is a sequence a_1, a_2, \dots, a_n. According to our usual modeling logic, we naturally want to maximize the probability of the target sequence: P(a_1, a_2, \dots, a_n | Q) Whether using traditional methods or deep learning, modeling the complete sequence directly is quite difficult. Therefore, we usually use some assumptions to simplify it. For instance, using a naive assumption directly gives us: P(a_1, a_2, \dots, a_n | Q) = P(a_1 | Q) P(a_2 | Q) \dots P(a_n | Q) Note that Q here is not necessarily the raw input; for example, it might be the hidden outputs q_1, q_2, \dots, q_n after multiple layers of LSTM. We assume that global correlations have already been captured by the preceding model. Thus, in the final step, we can assume the features are independent of each other, so: \begin{aligned} P(a_1 | Q) &= P(a_1 | q_1, q_2, \dots, q_n) = P(a_1 | q_1) \\ P(a_2 | Q) &= P(a_2 | q_1, q_2, \dots, q_n) = P(a_2 | q_2) \\ &\quad \vdots \\ P(a_n | Q) &= P(a_n | q_1, q_2, \dots, q_n) = P(a_n | q_n) \end{aligned} Consequently: P(a_1, a_2, \dots, a_n | Q) = P(a_1 | q_1) P(a_2 | q_2) \dots P(a_n | q_n) This gives us the most commonly used solution: directly outputting the label with the maximum probability for each position. The preceding model is usually a multi-layer BiLSTM.
Conditional Random Field
Per-label softmax is a simple and effective method, but it sometimes produces unreasonable results. For example, when using SBME tags for 4-tag word segmentation, per-label softmax cannot rule out the possibility of a sequence like "bbbb," even though this sequence violates our decoding rules (a "b" can only be followed by "m" or "e"). Therefore, some say per-label softmax doesn’t need dynamic programming, but that is incorrect. In such cases, we at least need a "0 or 1" transition matrix to set unreasonable transition probabilities to zero (e.g., P(b|b)=0), and then use dynamic programming to ensure a reasonable sequence is obtained.
The problem with the above scheme ultimately stems from the fact that we used a naive assumption of complete output independence (unigram model) during modeling, while our actual output sequences are context-dependent. This causes a mismatch between the optimization objective and the model assumptions. Can we directly take the context into account? It’s simple: use a bigram model. \begin{aligned} P_Q(a_1, a_2, \dots, a_n) &= P_Q(a_1) P_Q(a_2 | a_1) P_Q(a_3 | a_1, a_2) \dots P_Q(a_n | a_1, \dots, a_{n-1}) \\ &= P_Q(a_1) P_Q(a_2 | a_1) P_Q(a_3 | a_2) \dots P_Q(a_n | a_{n-1}) \end{aligned} Here, to make the expression look better, I have placed the input Q in the subscript. This is already very close to CRF!
Continuing to observe the above formula, it is a product of transition probabilities. However, why must we define each term as a transition probability? Thus, the CRF approach is very general. First, it defines a function f(x, y; Q) (which might be a sum of some simple feature functions, but the specific form is not actually important), and then directly sets: P_Q(a_1, a_2, \dots, a_n) = \frac{1}{Z} \exp\left(\sum_k f(a_{k-1}, a_k; Q)\right) where Z is the normalization factor. Compared to the previous formula, the difference is that P_Q(a_k | a_{k-1}) has probabilistic meaning (conditional probability), while the single term e^{f(a_{k-1}, a_k; Q)}/Z does not. Therefore, CRF is a more general form.
That is all there is to CRF.
A more complete reference link: https://zhuanlan.zhihu.com/p/28465510
Linear Chain CRF
What? Are you kidding me? This is CRF? What on earth are these P_Q(a_k | a_{k-1})? And what about f(x, y; Q)?
Dear reader, you’ve got me there. I don’t know what they are either. If you don’t believe me, look at some other tutorials online; the formulas they give look something like this (copied directly from here): \begin{aligned} p(l | s) &= \frac{\exp[\text{score}(l|s)]}{\sum_{l'} \exp[\text{score}(l'|s)]} \\ &= \frac{\exp[\sum_{j = 1}^m \sum_{i = 1}^n \lambda_j f_j(s, i, l_i, l_{i-1})]}{\sum_{l'} \exp[\sum_{j = 1}^m \sum_{i = 1}^n \lambda_j f_j(s, i, l'_i, l'_{i-1})]} \end{aligned} Here, the f are all unknown "feature functions" that need to be designed specifically for the problem, which is equivalent to saying they are unknown f(a_{k-1}, a_k; Q). So, I really don’t know what they are.
Fine, even if you are right, at least teach me how to use it.
Here I will introduce a frequently used version—the Linear Chain CRF, which is the version included in TensorFlow. Let’s first write out: \begin{aligned} &P_Q(a_1, a_2, \dots, a_n) \\ =& P_Q(a_1) P_Q(a_2 | a_1) P_Q(a_3 | a_2) \dots P_Q(a_n | a_{n-1}) \\ =& P_Q(a_1) \frac{P_Q(a_1, a_2)}{P_Q(a_1) P_Q(a_2)} P_Q(a_2) \frac{P_Q(a_2, a_3)}{P_Q(a_2) P_Q(a_3)} P_Q(a_3) \dots \frac{P_Q(a_{n-1}, a_n)}{P_Q(a_{n-1}) P_Q(a_n)} P_Q(a_n) \end{aligned} Doesn’t that look quite nice? Following the general idea of CRF, we abandon the probabilistic meaning of each term and write directly: \begin{aligned} &P_Q(a_1, a_2, \dots, a_n) \\ =& \frac{1}{Z} \exp \Big[f(a_1; Q) + g(a_1, a_2; Q) + f(a_2; Q) + \dots + g(a_{n-1}, a_n; Q) + f(a_n; Q)\Big] \end{aligned} The so-called "Linear Chain" assumes that the function g is actually independent of Q; a single g(a_{k-1}, a_k) is shared in all cases, making it nothing more than a matrix to be determined. The rest is similar to the per-label softmax case, assuming f(a_k; Q) \equiv f(a_k; q_k). According to the principle of maximum likelihood, the loss should be: \begin{aligned} &-\log P_Q(a_1, a_2, \dots, a_n) \\ =& - \sum_{k=1}^n f(a_k; q_k) - \sum_{k=2}^n g(a_{k-1}, a_k) + \log Z \end{aligned} If the preceding model uses BiLSTM to obtain the features q_k, then we get the most classic BiLSTM-CRF for sequence labeling tasks.
So, it is now not difficult to understand the CRF function provided
in TensorFlow:
https://github.com/tensorflow/tensorflow/tree/master/tensorflow/contrib/crf
Compared to per-label softmax, CRF is just a change of loss function. Of course, it also adds a mutual information matrix, and decoding requires the Viterbi algorithm. But none of that is important because TensorFlow has written it all for us.
Redesign?
Linear Chain CRF can be seen as a simplified template. Is it possible for us to refer to this template and design an improved CRF? For example, using a model to generate a mutual information matrix related to Q? It might be possible.
Only by peeling the nutshell can one better taste the nut; that is the flavor within the nutshell. Once you know the "how" and the "why," everything becomes less mysterious.
(New introduction: https://kexue.fm/archives/5542)
Please include the original address when reposting: https://kexue.fm/archives/4695
For more detailed reposting matters, please refer to: "Scientific Space FAQ"