CRF In A Nutshell
This post tries to explain the principle behind CRF (Conditional Random Field) as concisely as possible. "In a Nutshell" here roughly means "a primer" or "a popular-science introduction" (Hawking wrote a book called The Universe in a Nutshell, so I'm shamelessly imitating that here).
Most articles online that introduce CRF, whether in Chinese or English, tend to start with some concepts from probabilistic graphical models, then introduce the exponential formula for features, and then just declare "this is CRF." The so-called "probabilistic graph" is really just a way of building intuition — but if the explanation misses the actual point, piling on more vivid analogies just confuses people further, making them think you're merely showing off. (Speaking of which, let me take another jab: solving a neural network is really just computing a gradient and iterating — that's easy enough to understand. But instead, people give it a fancy-sounding name, "backpropagation." If you don't first explain that its essence is differentiation plus iterative solving, and just throw the term "backpropagation" at people, how many readers would actually get it?)
Alright, enough rambling — let's get to the point.
Per-Tag Softmax
CRF commonly shows up in sequence labeling tasks. Suppose our model's input is $Q$ and the output target is a sequence $a_1,a_2,\dots,a_n$. Following 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 methods, directly modeling the full sequence is quite difficult, so we usually introduce some simplifying assumptions. For instance, using the naive independence assumption directly gives
$$P(a_1,a_2,\dots,a_n|Q)=P(a_1|Q)P(a_2|Q)\dots P(a_n|Q)$$more
Note that here Q is not necessarily the raw input — for example, it could be the hidden output after several layers of LSTM, $q_1,q_2,\dots,q_n$ — and we assume that global dependencies have already been captured by the preceding model. So in this final step, we can treat the features as mutually independent, giving us
$$\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}$$
and therefore
$$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 scheme: directly output, for each tag position, the tag with maximum probability. The preceding model is typically a multi-layer bidirectional LSTM.
Conditional Random Field
Per-tag softmax is simple and effective, but it can sometimes produce unreasonable results. For example, when using the sbme scheme for 4-tag word segmentation, per-tag 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"). So when people say per-tag softmax doesn't need dynamic programming, that's not quite right — in this scenario we need, at minimum, a "zero-or-one" transition matrix that directly sets the invalid transition probabilities to zero (e.g., $P(b|b)=0$), and then use dynamic programming to guarantee a valid output sequence.
The reason the scheme above runs into trouble is, at bottom, that when we modeled the problem, we used the naive assumption of fully independent outputs (a unigram model), while our actual output sequence is context-dependent — creating a mismatch between the optimization objective and the model's assumptions. Can we bring context into the picture directly? Sure — just 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}$$
To make the expression look nicer, I've moved the input $Q$ into the subscript. This is already very close to CRF!
Let's look at the expression above a bit more. It's a product of transition probabilities — but why must every term be defined as a transition probability? CRF's approach is much more general: it first defines a function $f(x,y;Q)$ (which might be a sum of some simple feature functions, but the specific form isn't really 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 a normalizing factor. Compared with the previous expression, the difference is that $P_Q(a_k|a_{k-1})$ has genuine probabilistic meaning (a conditional probability), whereas the individual term $e^{f(a_{k-1},a_k;Q)}/Z$ does not. So CRF is a more general form.
And that's really all there is to CRF.
A more thorough reference: 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})$'s? And what about $f(x,y;Q)$?
Dear reader, you've got me there — I genuinely don't know what those are either. Don't believe me? Go look at some online tutorials — the formulas they give tend to look something like this (copied directly from here):
$$\begin{aligned}p(l | s) =& \frac{\exp[score(l|s)]}{\sum_{l’} \exp[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$'s are all unknown "feature functions" that need to be designed specifically for each problem — which is basically just another way of saying they're an unknown $f(a_{k-1},a_k;Q)$. So yes, I genuinely don't know what that is.
Fine, let's say you're right. Could you at least teach me how to actually use it?
Let me introduce a commonly used version — the linear-chain CRF — which is exactly the version bundled with TensorFlow. Let's first write
$$\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 rather elegant? Following CRF's general approach, we drop the requirement that each term have probabilistic meaning, and simply write
$$\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}$$
By "linear chain," we mean we simply assume that the function $g$ actually has nothing to do with $Q$ — every case shares the same $g(a_{k-1},a_k)$, so it's really just a matrix to be determined. Everything else is much like the per-tag softmax case, where we take $f(a_k;Q)\equiv f(a_k;q_k)$. Following the maximum-likelihood principle, 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 a bidirectional LSTM to produce the features $q_k$, then we arrive at the most classic architecture for sequence labeling tasks: BiLSTM-CRF.
So now it's not hard to understand the CRF functions bundled with TensorFlow:
https://github.com/tensorflow/tensorflow/tree/master/tensorflow/contrib/crf
Compared with per-tag softmax, CRF really just swaps in a different loss function. Of course, there's also an extra mutual-information-like matrix, and decoding requires the Viterbi algorithm. But none of that matters much, since TensorFlow has already implemented it all for us.
Redesigning It?
Linear-chain CRF can be thought of as a simplified template. Could we perhaps use this template as a reference and design an improved version of CRF? For instance, could a model generate a mutual-information-like matrix that depends on Q? That may well be possible.
You have to crack open the nutshell to really taste the nut — that's the flavor of "in a nutshell." Once you know not just the "what" but the "why," things stop being so mysterious.
(A newer introduction: https://kexue.fm/archives/5542)
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.