转载自苏剑林的文章
https://kexue.fm/archives/5542
对比下普通逐镇softmax和CRF的异同
逐帧softmax
CRF主要是用于序列标注问题，可以简单理解为给序列的每一帧都进行分类。可以很自然的想到用softmax做多分类。
但是这种方法没有考虑到输出上下文的关联。
条件随机场
然而，当我们设计标签时，比如用 s、b、m、e 的 4 个标签来做字标注法的分词，目标输出序列本身会带有一些上下文关联，比如 s 后面就不能接 m 和 e，等等。逐标签 softmax 并没有考虑这种输出层面的上下文关联，所以它意味着把这些关联放到了编码层面，希望模型能自己学到这些内容，但有时候会“强模型所难”。
而 CRF 则更直接一点，它将输出层面的关联分离了出来，这使得模型在学习上更为“从容”：
数学上的理解
当然，如果仅仅是引入输出的关联，还不仅仅是 CRF 的全部，CRF 的真正精巧的地方，是它以路径为单位，考虑的是路径的概率。
模型概要
假设输入有n帧，每一帧的标签有k种可能，那么理论上就会有$k^n$种可能。可以讲这种可能性用网络图进行可视化。在下图中，每个点代表一个标签的可能性，点之间的连线表示标签之间的关联，每一种标注结果，都对应着图中的一条完整路径。**
在序列标注任务重，我们的正确答案是唯一的。比如“今天天气不错”，如果对应的分词结果是“今天/天气/不/错”，那么目标输出序列就是 bebess，除此之外别的路径都不符合要求。
换言之，在序列标注任务中，我们的研究的基本单位应该是路径，我们要做的事情，是从 k^n 条路径选出正确的一条，那就意味着，如果将它视为一个分类问题，那么将是 k^n 类中选一类的分类问题。
这就是逐帧 softmax 和 CRF 的根本不同了：前者将序列标注看成是 n 个 k 分类问题，后者将序列标注看成是 1 个 k^n 分类问题。
具体来讲，在 CRF 的序列标注问题中，我们要计算的是条件概率：
为了得到这个概率，CRF包含了两个假设：
假设一：
该分布式指数族分布
这个假设意味着存在函数$f(y_1, …, y_n; x)$使得
其中Z(x)是归一化因子，因为这个是条件分布，所以，归一化因子和x有关。这个f函数可以看作是一个打分函数，打分函数取指数并且归一化后得到概率分布。
假设二：
输出之间的关联发生在相邻的位置，并且关联是指数加性的，
这个假设意味着函数$f(y_1, …, y_n; x)$可以 进一步简化为：
这时候，可以看到，我们只需要对每一个标签和相邻标签进行打分即可，然后将所有的打分求和得到总分。打分函数分为两种，一种是转移特征函数g，一种是状态特征函数h。
线性CRF
虽然已经进行了很多的简化，但是3式表示的模型还是太复杂，难以求解。于是考虑到当前深度学习模型中，RNN 或者层叠 CNN 等模型已经能够比较充分捕捉各个 y 与输出 x 的联系，因此，我们不妨考虑函数 g 跟 x 无关，那么：
这个时候，g实际上是一个有限的，待训练的参数矩阵而已，而单标签的打分函数h，我们可以通过RNN或者CNN建模。
模型的概率分布变成：
归一化因子
为了训练CRF模型，我们用最大似然方法，也就是用
作为损失函数，可以算出它等于
其中第一项是原来概率式的分子的对数，它目标的序列的打分，虽然它看上去挺迂回的，但是并不难计算。真正的难度在于分母的对数logZ(x)这一项。
归一化因子，在物理上也叫配分函数，在这里它需要我们对所有可能的路径的打分进行指数求和，而我们前面已经说到，这样的路径数是指数量级的（$k^n$），因此直接来算几乎是不可能的。
事实上，归一化因子难算，几乎是所有概率图模型的公共难题。幸运的是，在CRF模型中，由于我们只考虑了临近标签的联系（马尔可夫假设），因此我们可以递归地算出归一化因子，这使得原来是指数级的计算量降低为线性级别。具体来说，我们将计算到时刻t的归一化因子记为Zt，并将它分为k个部分
其中Z(1)t,…,Z(k)t分别是截止到当前时刻t中、以标签1,…,k为终点的所有路径的得分指数和。那么，我们可以递归地计算
它可以简单写为矩阵形式
其中$Z_t=[Z^{(1)}_t,…,Z^{(k)}_t]$；而G是对$g(y_i,y_j)$各个元素取指数后的矩阵，即$G=e^{g(y_i,y_j)}$；而$H(y_{t+1}|x)$是编码模型$h(y_{t+1}|x)$（RNN、CNN等）对位置t+1的各个标签的打分的指数，即$H(y_{t+1}|x)$=$e^h(y_{t+1}|x)$，也是一个向量。式(10)中，$Z_tG$这一步是矩阵乘法，得到一个向量，而⊗是两个向量的逐位对应相乘。
归一化因子的递归计算图示。从t到t+1时刻的计算，包括转移概率和j+1节点本身的概率
归一化因子的递归计算图示。从t到t+1时刻的计算，包括转移概率和j+1节点本身的概率
如果不熟悉的读者，可能一下子比较难接受(10)式。读者可以把n=1,n=2,n=3时的归一化因子写出来，试着找它们的递归关系，慢慢地就可以理解(10)式了。
归一化因子的递归计算图示。从t到t+1时刻的计算，包括转移概率和j+1节点本身的概率
动态规划
那么剩下的最后一步，就是模型训练完成后，如何根据输入找出最优路径来。跟前面一样，这也是一个从$k^n$条路径中选最优的问题，而同样地，因为马尔可夫假设的存在，它可以转化为一个动态规划问题，用viterbi算法解决，计算量正比于n。