tensorflow中的crf

crf是什么

CRFs are a type of discriminative undirected probabilistic graphical model. They are used to encode known relationships between observations and construct consistent interpretations and are often used for labeling or parsing of sequential data, such as natural language processing or biological sequences and in puter vision.Specifically, CRFs find applications in POS tagging, shallow parsing, named entity recognition, gene finding and peptide critical functional region finding, among other tasks, being an alternative to the related hidden Markov models (HMMs). In puter vision, CRFs are often used for object recognition[6] and image segmentation.

CRFs是一种判别的无向概率图形模型。它们被用来编码观测之间已知的关系，并构造一致的解释，经常被用于标记或解析序列数据，如自然语言处理或生物序列，以及计算机视觉。具体来说，CRFs在词性标注、浅层解析、命名实体识别、基因发现和肽关键功能区域发现等方面的应用，是相关隐马尔可夫模型(HMMs)的替代方案。在计算机视觉中，CRFs常用于目标识别和图像分割。

来源：wili_Conditional random field

为什么使用crf

实体识别的应用领域，lstm＋crf是一种标配了，短期内我认为只要在attention方面没有很大的突破，这一框架都不会变化。
为什么在实体识别领域lstm后面要接crf层。
首先看BiLSTM的输出

1.50.20.090.0030.120.90.40.020.0020.20.10.10.030.20.10.080.110.080.070.0650.050.050.10.051.5\begin{array}{|c|c|c|c|c|}\hline 1.5 & {0.2} & {0.09} & {0.003} & {0.12} \\ {0.9} & {0.4} & {0.02} & {0.002} & {0.2} \\ {0.1} & {0.1} & {0.03} & {0.2} & {0.1} \\ {0.08} & {0.11} & {0.08} & {0.07} & {0.065} \\ {0.05} & {0.05} & {0.1} & {0.05} & {1.5} \\ \hline\end{array} 1.50.90.10.080.05​0.20.40.10.110.05​0.090.020.030.080.1​0.0030.0020.20.070.05​0.120.20.10.0651.5​​

为什么不在双向lstm后接一个softmax层，输出各个label的概率。而是使用crf。

理论依据softmax层的输出是相互独立的，即虽然BiLSTM学习到了上下文的信息，但是输出相互之间并没有影响，它只是在每一步挑选一个最大概率值的label输出。这样就会导致如B-person后再接一个B-person的问题。而crf中有转移特征，即它会考虑输出label之间的顺序性，所以考虑用crf去做BiLSTM的输出层。实践依据，论文 Neural Architectures for Named Entity Recognition 中已经证实过了，可以翻译版。

那么用到了哪些 crf 相关内容，以及如何用。

tensorflow中的 有关crf 的函数：

tf.contrib.crf.crf_sequence_score #计算标签序列的非规范化分数
tf.contrib.crf.crf_log_norm #计算CRF的标准化.
tf.contrib.crf.crf_log_likelihood #计算 CRF 中标签序列的对数似然.
tf.contrib.crf.crf_unary_score #计算标签序列的一元分数.
tf.contrib.crf.crf_binary_score #计算 CRF 中标签序列的二进制分数.
tf.contrib.crf.CrfForwardRnnCell #计算线性链 CRF 中的 alpha 值.
tf.contrib.crf.viterbi_decode #解码 TensorFlow 之外的标记的最高得分序列.这只能在测试时使用.

来源：w3cschool_tensorflow官方文档

看到这些可能很蒙不知道这些函数是干什么的，不急，我们先分析需求。

简单的说对于每一个输入X=(x1,x2,…,xn)X=(x ^{1},x^{2} ,…,x ^{n})X=(x1,x2,…,xn)，我们得预测结果y=(y1,y2,…,yn)\mathbf{y}=\left(y_{1}, y_{2}, \ldots, y_{n}\right)y=(y1​,y2​,…,yn​)

对此对这个预测结果定义 s(X,y)s(\mathbf{X}, \mathbf{y})s(X,y) 为该预测值的打分：
s(X,y)=∑i=0nAyi,yi+1+∑i=1nPi,yis(\mathbf{X}, \mathbf{y})=\sum_{i=0}^{n} A_{y i, y_{i+1}}+\sum_{i=1}^{n} P_{i, y_{i}}s(X,y)=i=0∑n​Ayi,yi+1​​+i=1∑n​Pi,yi​​

其中PiP_iPi​,yiy_iyi​为第i个位置softmax输出为yi的概率，AyiA_yiAy​i,yi+1y_{i+1}yi+1​为从KaTeX parse error: Expected group after '_' at position 3: yi_̲到yi+1的转移概率，当tag（B-person,B-location。。。。）个数为n的时候，转移概率矩阵为（n+2）*（n+2),因为额外增加了一个开始位置和结束位置。这个得分函数S就很好地弥补了传统BiLSTM的不足，因为我们当一个预测序列得分很高时，并不是各个位置都是softmax输出最大概率值对应的label，还要考虑前面转移概率相加最大，即还要符合输出规则（B后面不能再跟B），比如假设BiLSTM输出的最有可能序列为BBIBIOOO，那么因为我们的转移概率矩阵中B->B的概率很小甚至为负，那么根据s得分，这种序列不会得到最高的分数，即就不是我们想要的序列。

我们可以很明显的发现，生成一个良好的转移矩阵 AAA 是尤为关键的。

softmax对所有可能的标签序列产生一个序列y~\tilde{y}y~​的概率,即对于训练样本X，求出所有可能的标注序列y~\tilde{y}y~​的得分S(X,y~)S(X,\tilde{y})S(X,y~​)。

p(y∣X)=es(X,y)∑y~∈YXes(X,y~)p(\mathbf{y} | \mathbf{X})=\frac{e^{s(\mathbf{X}, \mathbf{y})}}{\sum_{\tilde{\mathbf{y}} \in \mathbf{Y}_{\mathbf{X}}} e^{s(\mathbf{X}, \widetilde{\mathbf{y}})}} p(y∣X)=∑y~​∈YX​​es(X,y​)es(X,y)​

p(y∣X)p(\mathbf{y} | \mathbf{X})p(y∣X)为出现正确系列的概率，我们要做的就是最大化这个对数概率。

y是正确标注序列，S(X,y)S(X,{y})S(X,y)为出现正确序列的得分。

log⁡(p(y∣X))=s(X,y)−log⁡(∑y~∈YXes(X,y~))=s(X,y)−log⁡add⁡s(X,y~)\begin{aligned} \log (p(\mathbf{y} | \mathbf{X})) &=s(\mathbf{X}, \mathbf{y})-\log \left(\sum_{\tilde{\mathbf{y}} \in \mathbf{Y}_{\mathbf{X}}} e^{s(\mathbf{X}, \tilde{\mathbf{y}})}\right) \\ &=s(\mathbf{X}, \mathbf{y})-\log \operatorname{add}_{\boldsymbol{s}}(\mathbf{X}, \widetilde{\mathbf{y}}) \end{aligned} log(p(y∣X))​=s(X,y)−log⎝⎛​y~​∈YX​∑​es(X,y~​)⎠⎞​=s(X,y)−logadds​(X,y​)​

那么我们的目标就是最大化上式（即真实标记应该对应最大概率值），因为叫损失函数，所以我们也可以对上式取负然后最小化之，这样我们就可以使用梯度下降等优化方法来求解参数。在这个过程中，我们要最大化真实标记序列的概率，也就训练了转移概率矩阵A和BiLSTM中的参数。

在预测的时候，根据训练好的参数求出所有可能的y序列对应的S得分，将最大的S得分的y输出。
y∗=argmax⁡y~∈Yxs(X,y~)(2)\mathbf{y}^{*}=\underset{\tilde{\mathbf{y}} \in \mathbf{Y} \mathbf{x}}{\operatorname{argmax}} s(\mathbf{X}, \tilde{\mathbf{y}})(2) y∗=y~​∈Yxargmax​s(X,y~​)(2)

tensorflow代码解读

我们理解了基础的业务逻辑之后，来选择tensorflow实现，首先调用tf.contrib.crf.crf_log_likelihood 函数，计算 CRF 中标签序列的对数似然，也就是上面log⁡(p(y∣X))\log (p(\mathbf{y} | \mathbf{X}))log(p(y∣X)),他是如何实现的，看源码：

def crf_log_likelihood(inputs,tag_indices,sequence_lengths,transition_params=None):"""Computes the log-likelihood of tag sequences in a CRF.Args:inputs: A [batch_size, max_seq_len, num_tags] tensor of unary potentialsto use as input to the CRF layer.tag_indices: A [batch_size, max_seq_len] matrix of tag indices for which wepute the log-likelihood.sequence_lengths: A [batch_size] vector of true sequence lengths.transition_params: A [num_tags, num_tags] transition matrix, if available.Returns:log_likelihood: A scalar containing the log-likelihood of the given sequenceof tag indices.transition_params: A [num_tags, num_tags] transition matrix. This is eitherprovided by the caller or created in this function."""# Get shape information.num_tags = inputs.get_shape()[2].value# Get the transition matrix if not provided.if transition_params is None:transition_params = vs.get_variable("transitions", [num_tags, num_tags])sequence_scores = crf_sequence_score(inputs, tag_indices, sequence_lengths,transition_params)log_norm = crf_log_norm(inputs, sequence_lengths, transition_params)# Normalize the scores to get the log-likelihood.log_likelihood = sequence_scores - log_normreturn log_likelihood, transition_params

源码中已经对输入输出有了解释，这里我再阐述一下。
为了便于下面的讲解，我们以"浙江省"为例进行实体命名，假设tar有三种：B_LOC，I_LOC，O。其中B表示开头，I表示中间，LOC表示地名，O表不是实体类。我们用数字表示这三种状态：｛0：B_LOC，1：I_LOC，2:O｝。
Args:
inputs: A [batch_size, max_seq_len, num_tags] tensor of unary potentials to use as input to the CRF layer.

参数1 ：np.array([[-3,5，-1],[1,1,3],[-1,-2,4],[0,0,0]],dtype=np.float32)；(还有一维为bacth)这个inputs十么意思呢？我们以[-3，5，-1]这一组向量为例，它表示第一个单词（也就是"浙“）在每个tag上的score（分数),也就是说"浙"是“O”的分数为-3，是"B-LOC"的分数为5，是"I-LOC"的分数为（实际情况分数值可能不是这样，我只是做个假设这里或许大家会有疑问：不是只有三个单词吗，怎么这边却有4个？因为我们假设max_lengths为4，而这里我们的句子长度只有3，所以需要补"pad"，[0,0,0]这一向量就表示"pad"，不算具体的单词，在LSTM+CRF
模型中，inputs其实是由LSTM层产生的；

tag_indices: A [batch_size, max_seq_len] matrix of tag indices for which we pute the log-likelihood.

参数2．tag_indices=np.array()（1，2，2，0）,dtype=np.int32)表示每个单词实际的
tag（1对应B-LOC，2对应i-LOC，0对应0)也就是说"浙江省"实际对应的tag为B-LOC，i_LOC，i_LOC.
sequence_lengths: A [batch_size] vector of true sequence lengths.
参数3：sequence_lengths=3，代表句子的实际长度．
transition_params: A [num_tags, num_tags] transition matrix, if available.
参数4：transition_params np.array([[-3 , 5 , -2], [3，4，1]，[1 , 2 , 3 ]] , dtype=np.float32), transition_params为状态转移矩阵，因为有三种状态，所以矩阵的size为（3*3).即
A=[A00A01A02A10A11A12A20A12A22]=[−35−2341123]A=\left[\begin{array}{lll}{A_{00}} & {A_{01}} & {A_{02}} \\ {A_{10}} & {A_{11}} & {A_{12}} \\ {A_{20}} & {A_{12}} & {A_{22}}\end{array}\right]=\left[\begin{array}{c}{-3} & {5} & {-2} \\ {3} & {4} & {1} \\ {1} & {2} & {3}\end{array}\right] A=⎣⎡​A00​A10​A20​​A01​A11​A12​​A02​A12​A22​​⎦⎤​=⎣⎡​−331​542​−213​⎦⎤​
Returns:
log_likelihood: A scalar containing the log-likelihood of the given sequence of tag indices.
包含给定序列的对数似然的标量的标记指数。
transition_params: A [num_tags, num_tags] transition matrix. This is either provided by the caller or created in this function.
转换矩阵。这是由调用方提供或在此函数中创建。

函数首先调用了 crf_sequence_score，然后调用了 crf_log_norm。我们来分析这个crf_sequence_score。

crf_sequence_score

首先，先看crf_sequence_score的源码：

def crf_sequence_score(inputs, tag_indices, sequence_lengths,transition_params):"""Computes the unnormalized score for a tag sequence.Args:inputs: A [batch_size, max_seq_len, num_tags] tensor of unary potentialsto use as input to the CRF layer.tag_indices: A [batch_size, max_seq_len] matrix of tag indices for which wepute the unnormalized score.sequence_lengths: A [batch_size] vector of true sequence lengths.transition_params: A [num_tags, num_tags] transition matrix.Returns:sequence_scores: A [batch_size] vector of unnormalized sequence scores."""# Compute the scores of the given tag sequence.unary_scores = crf_unary_score(tag_indices, sequence_lengths, inputs)binary_scores = crf_binary_score(tag_indices, sequence_lengths,transition_params)sequence_scores = unary_scores + binary_scoresreturn sequence_scores

输入就是 crf_log_likelihood的输入，不用太多解释。
crf_log_likelihood主要调用了crf_unary_score（计算一元分数）与crf_binary_score（计算二元分数），并将这两个函数的返回值相加返回。这就是：
s(X,y)=∑i=0nAyi,yi+1+∑i=1nPi,yis(\mathbf{X}, \mathbf{y})=\sum_{i=0}^{n} A_{y i, y_{i+1}}+\sum_{i=1}^{n} P_{i, y_{i}}s(X,y)=i=0∑n​Ayi,yi+1​​+i=1∑n​Pi,yi​​

的实现，也就是Ayi,yi+1A_{y i, y_{i+1}}Ayi,yi+1​​二元分数，Pi,yiP_{i, y_{i}}Pi,yi​​为一元分数。

a)调用crf_unary_score计算一元分数，来看源码：

def crf_unary_score(tag_indices, sequence_lengths, inputs):"""Computes the unary scores of tag sequences.Args:tag_indices: A [batch_size, max_seq_len] matrix of tag indices.sequence_lengths: A [batch_size] vector of true sequence lengths.inputs: A [batch_size, max_seq_len, num_tags] tensor of unary potentials.Returns:unary_scores: A [batch_size] vector of unary scores."""batch_size = array_ops.shape(inputs)[0]max_seq_len = array_ops.shape(inputs)[1]num_tags = array_ops.shape(inputs)[2]flattened_inputs = array_ops.reshape(inputs, [-1])offsets = array_ops.expand_dims(math_ops.range(batch_size) * max_seq_len * num_tags, 1)offsets += array_ops.expand_dims(math_ops.range(max_seq_len) * num_tags, 0)flattened_tag_indices = array_ops.reshape(offsets + tag_indices, [-1])unary_scores = array_ops.reshape(array_ops.gather(flattened_inputs, flattened_tag_indices),[batch_size, max_seq_len])masks = _lengths_to_masks(sequence_lengths, array_ops.shape(tag_indices)[1])unary_scores = math_ops.reduce_sum(unary_scores * masks, 1)return unary_scores

什么叫一元分数？就是在一个句子中，第i个单词对应第j个tag所得的分数用PijP_{ij}Pij​表示，然后将句子中每个单词所得的分数相加就是一元分数。

Offsets的作用用。因为我们把inputs展开变成一维向量flattened_inputs了，flattened_inputs为[-3 , 5 , -1 , 1 , 3 , -1 , -2 , 4 , 0 , 0 , 0]，如果没展开之前我们需要查找每个单词对应的tag怎么0找？
很简单，根据tag_indices的值为[1，2，2，0],它告诉我们那么我们第一个字"浙"实际的 tag 是1，所以"浙"得到的分数为 5（从inputs中得出),第二个字“江“实际的 tag 是 2，所以“江“得到的分数是3，第三个字"省"实际的 tag 是1，所以"省"得到的分数是 4，结束标志实际的tag 是 O，得到的分数为0。那么当我们把inputs展开之后变成flattened_inputs，我们又怎么知道每个单词实际对应的tag呢？答案是加上偏置offsets！对于第一个单词，offset当然是0，第二个单词的offset为3，第三个单词的offet为6……也就是以num_tags（这里为3）为间隔。所以最后得到的offsets为{0，3，6，9}。
然后与之前的taglndices相加，得到{1，5，7，9}，这就是新的索引，然后到flattened_inputs（值为[-3,5，-1,1,1,3，-1，-2,4，0，0，0]）查找，我们也可以得到"浙"的分数为5，“江“的分数为3，"省"的分数为4，与前面没展开的分析结果一致，也就是说最后的unary_scores为{5，3，4，0}。至于为什么要把inputs和tag_indlces展开？只是为了能在一维数组上进行操作，方便。Masks的作用。一句话，就是清除掉无用的"PAD"句子长度不足max_lengths需要补"PAD"),那么具体是怎么实现的呢？是通过lengths_to_mask()函数。我们以实际的几个例子来说明lengths_to_masks()函数的作用:比如max_length为4，而当前的句子的长度为2，也就是说需要补两个"PAD。那么我们就需要创建一个这样的向量[1,1,0,0]后面的两个"PAD"就会被去除掉，再比如当前的句子为"浙江人“的长度为3，而max_length为4。那么就需要需要补一个"PAD"，那么我们就需要创建一个这样的masks：[1，1，1，0]然后进行math_ops.reduce_sum，将unary_scores（值为{5，3，4，0}）与masks（值为{1 , 1 ，1，0}）点积就可以得到"浙江省’'的一元分数51+31+41+00=12。

b)调crf_binary_score()计算二元分数

什么叫二元分数？就是从第i个tag转移到第j个tag所得的分数，用Ai,jA_{i,j}Ai,j​表示，然后将句子中每个位置的状态转移所得的分数相加就是二元分数。

def crf_binary_score(tag_indices, sequence_lengths, transition_params):"""Computes the binary scores of tag sequences.Args:tag_indices: A [batch_size, max_seq_len] matrix of tag indices.sequence_lengths: A [batch_size] vector of true sequence lengths.transition_params: A [num_tags, num_tags] matrix of binary potentials.Returns:binary_scores: A [batch_size] vector of binary scores."""# Get shape information.num_tags = transition_params.get_shape()[0]num_transitions = array_ops.shape(tag_indices)[1] - 1# Truncate by one on each side of the sequence to get the start and end# indices of each transition.start_tag_indices = array_ops.slice(tag_indices, [0, 0],[-1, num_transitions])end_tag_indices = array_ops.slice(tag_indices, [0, 1], [-1, num_transitions])# Encode the indices in a flattened representation.flattened_transition_indices = start_tag_indices * num_tags + end_tag_indicesflattened_transition_params = array_ops.reshape(transition_params, [-1])# Get the binary scores based on the flattened representation.binary_scores = array_ops.gather(flattened_transition_params,flattened_transition_indices)masks = _lengths_to_masks(sequence_lengths, array_ops.shape(tag_indices)[1])truncated_masks = array_ops.slice(masks, [0, 1], [-1, -1])binary_scores = math_ops.reduce_sum(binary_scores * truncated_masks, 1)return binary_scores

我们重点讲以下几个部分

start_tag_indices和end_tag_indices.
start_tag_indices相当于yiy_iyi​ ，end_tag_indices（start_tag_indices左移一个单元）相当于yi+1y_{i+1}yi+1​。为什么这么说呢？start_tag_indices得出来的值为{1，2，1}，end_tag_indices得出来的值为{2，1，0}。那么start_tag_indices的第一个元素1和endtagindices的第二个元素2组合起来就表示从第0个位置，tag为1，转移到第1立置，tag为2所得的分数。这里start_tag_indices的第一个元素将是Y0Y_{0}Y0​,end_tag_indices的第一个元素就是y1y_{1}y1​ 。至于为什么要将transitionin_dices和transition_params展平的可以参考前面一元分数的分析，这里不在赘述。也就是说最后我们可以通过transition_params句子得到每次状态转移的分数，未进行reduce_sum的binary_scores的结果为{1，3，1}。truncated_masks的作用。truncated_masks 就是将masks截取[1：]部分，得到
｛1 ，1，0}，只有三个元素（分别表示从第0个位置转移到第1个位置，第1个位置转移到第2个位置，第2位置转移到第3位置。4个单词，状态转移3次）。进行math_ops.reduce_sum后，最后的二元分数等于binary_scores与
truncatedmasks的，点积，即11+31+1*0=4。

调用crf_log_norm计算规范因子Z(X)

规范因子 Z(X) 是什么？先看上面的公式：

log⁡(p(y∣X))=s(X,y)−log⁡(∑y~∈YXes(X,y~))=s(X,y)−log⁡add⁡s(X,y~)\begin{aligned} \log (p(\mathbf{y} | \mathbf{X})) &=s(\mathbf{X}, \mathbf{y})-\log \left(\sum_{\tilde{\mathbf{y}} \in \mathbf{Y} \mathbf{X}} e^{s(\mathbf{X}, \tilde{\mathbf{y}})}\right) \\ &=s(\mathbf{X}, \mathbf{y})-\log \operatorname{add}_{s}(\mathbf{X}, \tilde{\mathbf{y}}) \end{aligned} log(p(y∣X))​=s(X,y)−log⎝⎛​y~​∈YX∑​es(X,y~​)⎠⎞​=s(X,y)−logadds​(X,y~​)​

对于训练过程来说，我们的目标是极大化log⁡(p(y∣X))\log (p(\mathbf{y} | \mathbf{X}))log(p(y∣X))这一项。而这一项中的s(X,y)s(X,y)s(X,y)，我们已经通过前面crf_sequencescore()函数得到．现在只需计算log⁡(∑y~∈YXes(X,y~))\log \left(\sum_{\tilde{\mathbf{y}} \in \mathbf{Y} \mathbf{X}} e^{s(\mathbf{X}, \tilde{\mathbf{y}})}\right)log(∑y~​∈YX​es(X,y~​))这一项，这一项要求我们遍历所有可能的sequence_tag，求得对应的分数s(X,y~){s(\mathbf{X}, \tilde{\mathbf{y}})}s(X,y~​)。
我们令Z(X)=∑y~∈YXes(X,y~)Z(X)=\sum_{\tilde{\mathbf{y}} \in \mathbf{Y} \mathbf{X}} e^{s(\mathbf{X}, \tilde{\mathbf{y}})}Z(X)=∑y~​∈YX​es(X,y~​)那么这一项这么算呢？
第一种方法，暴力穷尽每一种可能的sequence_tag.但这种方法时间复杂度太大，
在句子长度比较长或tag种类交多的时候是不可行的。
第二种方法，采用前向一后向算法．这也是crf_log_norm()函数所采用的方法，这个函数是重点也是难点．

下面我们着重介绍CRF的前向一后向算法。这一部分的理论基础主要参考李航老师的《统计学习方法》中第11.3小节：条件随机概率计算问题一一前向一后向算法
首先我们对于于每个位置i=0，1…，n+1，定义前向向量∂i(x)\partial_{i}(x)∂i​(x)
∂0(y∣x)={1,y=start⁡0,否者\partial_{0}(y | x)=\left\{\begin{array}{ll}{1,} & {y=\operatorname{start}} \\ {0,} & 否者\end{array}\right. ∂0​(y∣x)={1,0,​y=start否者​
在我们这个例子中，y的种类只有三种（即num_tag=3），所以∂0(y∣x)\partial_{0}(y|x)∂0​(y∣x)，可以写成:
∂0(y∣x)=[100]\partial_{0}(y | x)=\left[\begin{array}{l}{1} \\ {0} \\ {0}\end{array}\right] ∂0​(y∣x)=⎣⎡​100​⎦⎤​
递推公式为（其实就是动态规划的思想）
∂iT(yi∣x)=∂i−1T(yi−1∣x)Mi(yi−1,yi∣x),i=1,2,…,n+1(1.1)\partial_{i}^{T}\left(y_{i} | x\right)=\partial_{i-1}^{T}\left(y_{i-1} | x\right) M_{i}\left(y_{i-1}, y_{i} | x\right), \quad i=1,2, \ldots, \mathrm{n}+1 \\(1.1) ∂iT​(yi​∣x)=∂i−1T​(yi−1​∣x)Mi​(yi−1​,yi​∣x),i=1,2,…,n+1(1.1)
请记住和理解（1.1）式，等下我们会用到。那么这个公式中的每一项都是什么意思呢？
∂i(yi∣x)\partial_{i}\left(y_{i} | x\right)∂i​(yi​∣x)表示在位置i的标记是 yiy_iyi​ 并且到 位首 i 的前部分标记序列的非规范化概率（也就是取值范围不是[0，1]之间我们可以把它称为得分），yiy_iyi​可取的值有m个，所以∂i(y∣x)\partial_{i}(y|x)∂i​(y∣x)是m维列向量。
Mi(yi−1,yi∣x)M_{i}\left(y_{i-1}, y_{i} | x\right)Mi​(yi−1​,yi​∣x)这一项比较难理解·它是一组列向量，用文字不好表述，一下面我们用图来直观的表达这一过程

Mi(yi−1,yi∣x)M_{i}\left(y_{i-1}, y_{i} | x\right)Mi​(yi−1​,yi​∣x)就是从第i-1的位置到i的位置，每种颜色线条的组合成的列向量，我们吧前几个写出来：
M1(y0,y1=O∣x)=[a11a21]=[a1100]M1(y0,y1=B−LOC⁡∣x)=[a12a32]=[a1200]M1(y0,y1=I−LOC∣x)=[a13a23a33]=[a1300]\begin{array}{l}{M_{1}\left(y_{0}, y_{1}=O | x\right)=\left[\begin{array}{l}{a_{11}} \\ {a_{21}}\end{array}\right]=\left[\begin{array}{c}{a_{11}} \\ {0} \\ {0}\end{array}\right]} \\ {M_{1}\left(y_{0}, y_{1}=B-\operatorname{LOC} | x\right)=\left[\begin{array}{c}{a_{12}} \\ {a_{32}}\end{array}\right]=\left[\begin{array}{c}{a_{12}} \\ {0} \\ {0}\end{array}\right]} \\ {M_{1}\left(y_{0}, y_{1}=I-L O C | x\right)=\left[\begin{array}{c}{a_{13}} \\ {a_{23}} \\ {a_{33}}\end{array}\right]=\left[\begin{array}{c}{a_{13}} \\ {0} \\ {0}\end{array}\right]}\end{array} M1​(y0​,y1​=O∣x)=[a11​a21​​]=⎣⎡​a11​00​⎦⎤​M1​(y0​,y1​=B−LOC∣x)=[a12​a32​​]=⎣⎡​a12​00​⎦⎤​M1​(y0​,y1​=I−LOC∣x)=⎣⎡​a13​a23​a33​​⎦⎤​=⎣⎡​a13​00​⎦⎤​​

M1(x)=M1(y0,y1=O∣x)+M1(y0,y1=B−LOC∣x)+M1(y0,y1=I−LOC∣x)=[a11a12a13000000]\begin{array}{l}{M_{1}(x)=M_{1}\left(y_{0}, y_{1}=O | x\right)+M_{1}\left(y_{0}, y_{1}=B-L O C | x\right)+M_{1}\left(y_{0}, y_{1}=I-L O C | x\right)} \\ {\quad \quad \quad=\left[\begin{array}{c}{a_{11}} & {a_{12}} & {a_{13}} \\ {0} & {0} & {0} \\ {0} & {0} & {0}\end{array}\right]}\end{array} M1​(x)=M1​(y0​,y1​=O∣x)+M1​(y0​,y1​=B−LOC∣x)+M1​(y0​,y1​=I−LOC∣x)=⎣⎡​a11​00​a12​00​a13​00​⎦⎤​​

M2(y1,y2=O∣x)=[b11b21]M2(y1,y2=B−LOC∣x)=[b12b22]M2(y1,y2=I−LOC∣x)=[b13b23b33]\begin{array}{l}{M_{2}\left(y_{1}, y_{2}=O | x\right)=\left[\begin{array}{l}{b_{11}} \\ {b_{21}}\end{array}\right]} \\ {M_{2}\left(y_{1}, y_{2}=B-L O C | x\right)=\left[\begin{array}{l}{b_{12}} \\ {b_{22}}\end{array}\right]} \\ {M_{2}\left(y_{1}, y_{2}=I-L O C | x\right)=\left[\begin{array}{l}{b_{13}} \\ {b_{23}} \\ {b_{33}}\end{array}\right]}\end{array} M2​(y1​,y2​=O∣x)=[b11​b21​​]M2​(y1​,y2​=B−LOC∣x)=[b12​b22​​]M2​(y1​,y2​=I−LOC∣x)=⎣⎡​b13​b23​b33​​⎦⎤​​

M2(y1,,y2∣x)=M2(y1,y2=O∣x)+M2(y1,,y2=B−LOC∣x)+M2(y1,y2=I−LOC∣x)=[b11b12b12b21b22b22b31b32b32]\begin{aligned} M_{2}\left(y_{1,}, y_{2} | x\right)=& M_{2}\left(y_{1}, y_{2}=O | x\right)+M_{2}\left(y_{1,}, y_{2}=B-L O C | x\right)+M_{2}\left(y_{1}, y_{2}=I-L O C | x\right) \\ &=\left[\begin{array}{lll}{b_{11}} & {b_{12}} & {b_{12}} \\ {b_{21}} & {b_{22}} & {b_{22}} \\ {b_{31}} & {b_{32}} & {b_{32}}\end{array}\right] \end{aligned} M2​(y1,​,y2​∣x)=​M2​(y1​,y2​=O∣x)+M2​(y1,​,y2​=B−LOC∣x)+M2​(y1​,y2​=I−LOC∣x)=⎣⎡​b11​b21​b31​​b12​b22​b32​​b12​b22​b32​​⎦⎤​​
以次类推。
下面通过计算 和 来理解下面动态规划的过程。
根据递归公式：

由此我们可以得到：
∂nT(yn∣x)=∂0T(y0∣x)M1(x)∗M2(x)∗…∗Mn(x)(1,2)\partial_{n}^{T}\left(y_{n} | x\right)=\partial_{0}^{T}\left(y_{0} | x\right) M_{1}(x) * M_{2}(x) * \ldots * M_{n}(x)\\(1,2) ∂nT​(yn​∣x)=∂0T​(y0​∣x)M1​(x)∗M2​(x)∗…∗Mn​(x)(1,2)
这与（1,1）公式是相同的意思，但是不同的表述形式。
通过前面的几轮推导，我们应该对前向算法有个较深刻的认识了。那么∂n(yn∣x)\partial_{n}(y_{n}|x)∂n​(yn​∣x)与我们最后要求的Z(X)=∑y~∈YXes(X,y~)Z(X)=\sum_{\tilde{\mathbf{y}} \in \mathbf{Y} \mathbf{X}} e^{s(\mathbf{X}, \tilde{\mathbf{y}})}Z(X)=∑y~​∈YX​es(X,y~​)有什么关系呢？由前向向量的定义不难得到
Z(X)=∑y~∈YXes(X,y~).1(1,3)Z(X)=\sum_{\tilde{\mathbf{y}} \in \mathbf{Y} \mathbf{X}} e^{s(\mathbf{X}, \tilde{\mathbf{y}})} . 1\\(1,3)Z(X)=y~​∈YX∑​es(X,y~​).1(1,3)
111是元素均为1的m维列向量。请记住式（1,3),等下我们会用到。
同时对于（1,3)式，你或许觉得难以理解，那我们以之前的实体命名识别例子进行说明：Z(x)Z(x)Z(x)将被表述成：
Z(x)=∂4T(y4=O∣x)+∂4T(y4=B−LOC⁡∣x)+∂4T(y4=I−LOC⁡∣x)\mathrm{Z}(\mathrm{x})=\partial_{4}^{T}\left(y_{4}=O | x\right)+\partial_{4}^{T}\left(y_{4}=B-\operatorname{LOC} | x\right)+\partial_{4}^{T}\left(y_{4}=I-\operatorname{LOC} | x\right) Z(x)=∂4T​(y4​=O∣x)+∂4T​(y4​=B−LOC∣x)+∂4T​(y4​=I−LOC∣x)
根据（1,2）式和（1,3）式，我们知道要求规范化因子Z(x)Z(x)Z(x)就必须先求出每一步的Mi(x)M_i(x)Mi​(x),那么Mi(x)M_i(x)Mi​(x)应该怎么计算呢？

本来是想按前面那张图分析怎么计算，但发现计算量有点大，于是为了更清晰直
观地说明这一过程（减少计算量）我们把前面的例子改下，改为只有两个特征，为B-LOC,I-LOC（少了特征O)同时，把一元特征值和二元特征值也改了下．如下图:

简单解释一下图中Mi(x)M_i(x)Mi​(x)如何来的。
根据《添加学习方法》中的（11.22）公式，我们可得Mi(yi−1,yi∣x)M_{i}\left(y_{i-1}, y_{i} | x\right)Mi​(yi−1​,yi​∣x)计算公式，即：
Mi(yi−1,yi∣x)=exp⁡(Wi(yi−1,yi∣x))M_{i}\left(y_{i-1}, y_{i} | x\right)=\exp \left(W_{i}\left(y_{i-1}, y_{i} | x\right)\right)Mi​(yi−1​,yi​∣x)=exp(Wi​(yi−1​,yi​∣x))

exp，高等数学里以自然常数e为底的指数函数,exe^xex

那么Wi(yi−1,yi∣x)W_{i}\left(y_{i-1}, y_{i} | x\right)Wi​(yi−1​,yi​∣x)又是怎么得出的。（11,23）公式告诉我们：
Mi(yi−1,yi∣x)=exp⁡(Wi(yi−1,yi∣x))M_{i}\left(y_{i-1}, y_{i} | x\right)=\exp \left(W_{i}\left(y_{i-1}, y_{i} | x\right)\right) Mi​(yi−1​,yi​∣x)=exp(Wi​(yi−1​,yi​∣x))

上式成立的原因式因为我们只有两种特征：一元特征，二元特征。有理上面的表达式我们计算
W1(y0=start ,y1=B−LOC∣x)=unary- score⁡(y1=B−LOC)+binarys - core (y0=start ,y1=B−LOC)=4+0=4\begin{aligned} W_{1}\left(y_{0}=\right.&\left.\text { start }, y_{1}=B-L O C | x\right) \\ &=\text {unary- } \operatorname{score}\left(y_{1}=B-L O C\right)+\text { binarys - core }\left(y_{0}=\text { start }, y_{1}=B-L O C\right) \\ &=4+0 \\ &=4 \end{aligned} W1​(y0​=​ start ,y1​=B−LOC∣x)=unary- score(y1​=B−LOC)+ binarys - core (y0​= start ,y1​=B−LOC)=4+0=4​
所以M1(y0=start⁡,y1=B−LOC∣x)=e4M_{1}\left(y_{0}=\operatorname{start}, y_{1}=B-L O C | x\right)=e^{4}M1​(y0​=start,y1​=B−LOC∣x)=e4
同理
W1(y0=start, y1=I−LOC∣x)=unary- score⁡(y1=1−LOC)+binary-  score (y0=start, y1=I−LOC)=5+0=5所以M1(y0=start ,y1=I−LOC∣x)=e5\begin{aligned} W_{1}\left(y_{0}=\right.&\left.\text { start, } y_{1}=I-L O C | x\right) \\ &=\text { unary{-} } \operatorname{score}\left(y_{1}=1-L O C\right)+\text { binary{-} } \text { score }\left(y_{0}=\text { start, } y_{1}=I-L O C\right) \\ &=5+0 \\ &=5 \\ \text { 所以} M_{1}\left(y_{0}=\right.&\left.\text { start }, y_{1}=I-L O C | x\right)=e^{5} \end{aligned} W1​(y0​= 所以M1​(y0​=​ start, y1​=I−LOC∣x)= unary- score(y1​=1−LOC)+ binary-  score (y0​= start, y1​=I−LOC)=5+0=5 start ,y1​=I−LOC∣x)=e5​
我们把M1M_1M1​写成矩阵形式：
M1(x)=[e4e500]M_{1}(\mathbf{x})=\left[\begin{array}{}{e^{4}} & {e^{5}} \\ {0} & {0}\end{array}\right] M1​(x)=[e40​e50​]
M2xM_2{x}M2​x的计算
M2xM_2{x}M2​x的计算与M1xM_1{x}M1​x一样，如下：

W2(y1=B−LOC,y2=B−LOC∣x)=unary-  score (y2=B−LOC)+binary −score (y1=B−LOC,y2=B−LOC)=1+1=2所以M2(y1=B−LOC,y1=B−LOC∣x)=e2\begin{aligned} W_{2}\left(y_{1}=\right.&\left.B-L O C, y_{2}=B-L O C | x\right) \\ &=\text { unary{-} } \text { score }\left(y_{2}=B-L O C\right)+\text { binary }_{-} \text {score }\left(y_{1}=B-L O C, y_{2}=B-L O C\right) \\ &=1+1 \\ &=2 \\ \text { 所以} M_{2} &\left(y_{1}=B-L O C, y_{1}=B-L O C | x\right)=e^{2} \end{aligned} W2​(y1​= 所以M2​​B−LOC,y2​=B−LOC∣x)= unary-  score (y2​=B−LOC)+ binary −​score (y1​=B−LOC,y2​=B−LOC)=1+1=2(y1​=B−LOC,y1​=B−LOC∣x)=e2​
同理
W2(y1=B−LOC,y2=I−LOC∣x)=unary Score (y2=I−LOC)+binary −score (y1=B−LOC,y2=I−LOC)=2+2=4所以 M2(y1=B−LOC,y1=I−LOC∣x)=e4\begin{aligned} W_{2}\left(y_{1}=\right.&\left.B-L O C, y_{2}=I-L O C | x\right) \\ &=\text { unary Score }\left(y_{2}=I-L O C\right)+\text { binary }{-} \text {score }\left(y_{1}=B-L O C, y_{2}=I-L O C\right) \\ &=2+2 \\ &=4 \\ \text { 所以 } M_{2}\left(y_{1}=B-L O C, y_{1}=\right.&I-L O C | x)=e^{4} \end{aligned} W2​(y1​= 所以 M2​(y1​=B−LOC,y1​=​B−LOC,y2​=I−LOC∣x)= unary Score (y2​=I−LOC)+ binary −score (y1​=B−LOC,y2​=I−LOC)=2+2=4I−LOC∣x)=e4​

最后可得：
M2(x)=[e2e4e4e3]M_{2}(\mathbf{x})=\left[\begin{array}{}{e^{2}} & {e^{4}} \\ {e^{4}} & {e^{3}}\end{array}\right] M2​(x)=[e2e4​e4e3​]
M3M_3M3​计算公式：
由前面的推导我们可以直接计算：
M3(x)=[e2e3e4e2]M_{3}(\mathrm{x})=\left[\begin{array}{}{e^{2}} & {e^{3}} \\ {e^{4}} & {e^{2}}\end{array}\right] M3​(x)=[e2e4​e3e2​]
有了M1M_1M1​，M2M_2M2​，M3M_3M3​，我们可以利用（1,1）可得：
∂3(y3∣x)=∂0T(y0∣x)M1(x)M2(x)M3(x)=[10]∗[e4e500]∗[e2e4e4e3]∗[e2e3e4e2]=[e3+e11+e12+e12e9+e12+e10+e10]\begin{aligned} \partial_{3}\left(y_{3} | x\right)=& \partial_{0}^{T}\left(y_{0} | x\right) M_{1}(x) M_{2}(x) M_{3}(x) \\=\left[\begin{array}{}{1} & {0}\end{array}\right] *\left[\begin{array}{}{e^{4}} & {e^{5}} \\ {0} & {0}\end{array}\right] *\left[\begin{array}{}{e^{2}} & {e^{4}} \\ {e^{4}} & {e^{3}}\end{array}\right] *\left[\begin{array}{}{e^{2}} & {e^{3}} \\ {e^{4}} & {e^{2}}\end{array}\right] \\=&\left[\begin{array}{}{e^{3}+e^{11}+e^{12}+e^{12}} \\ {e^{9}+e^{12}+e^{10}+e^{10}}\end{array}\right] \end{aligned} ∂3​(y3​∣x)==[1​0​]∗[e40​e50​]∗[e2e4​e4e3​]∗[e2e4​e3e2​]=​∂0T​(y0​∣x)M1​(x)M2​(x)M3​(x)[e3+e11+e12+e12e9+e12+e10+e10​]​

同时代入：
Z(x)=∂3T(y3∣x)⋅[11]=[e8+e11+e12+e12e9+e12+e10+e10]⋅[11]=e8+e11+e12+e12+e9+e12+e10+e10\begin{aligned} \mathrm{Z}(\mathrm{x}) &=\partial_{3}^{T}\left(y_{3} | x\right) \cdot\left[\begin{array}{l}{1} \\ {1}\end{array}\right] \\ &=\left[e^{8}+e^{11}+e^{12}+e^{12} \quad e^{9}+e^{12}+e^{10}+e^{10}\right] \cdot\left[\begin{array}{l}{1} \\ {1}\end{array}\right] \\=e^{8}+e^{11}+e^{12}+e^{12}+e^{9}+e^{12}+e^{10}+e^{10} \end{aligned} Z(x)=e8+e11+e12+e12+e9+e12+e10+e10​=∂3T​(y3​∣x)⋅[11​]=[e8+e11+e12+e12e9+e12+e10+e10]⋅[11​]​
就得到了ZxZ{x}Zx
cs.columbia.edu/~mcollins/fb.pdf

def crf_log_norm(inputs, sequence_lengths, transition_params):"""Computes the normalization for a CRF.Args:inputs: A [batch_size, max_seq_len, num_tags] tensor of unary potentialsto use as input to the CRF layer.sequence_lengths: A [batch_size] vector of true sequence lengths.transition_params: A [num_tags, num_tags] transition matrix.Returns:log_norm: A [batch_size] vector of normalizers for a CRF."""# Split up the first and rest of the inputs in preparation for the forward# algorithm.first_input = array_ops.slice(inputs, [0, 0, 0], [-1, 1, -1])first_input = array_ops.squeeze(first_input, [1])rest_of_input = array_ops.slice(inputs, [0, 1, 0], [-1, -1, -1])# Compute the alpha values in the forward algorithm in order to get the# partition function.forward_cell = CrfForwardRnnCell(transition_params)_, alphas = rnn.dynamic_rnn(cell=forward_cell,inputs=rest_of_input,sequence_length=sequence_lengths - 1,initial_state=first_input,dtype=dtypes.float32)log_norm = math_ops.reduce_logsumexp(alphas, [1])return log_norm

crf与其他的对比imooc./article/27795