Processing math: 100%

隐马尔科夫模型(HMM)与条件随机场(CRF)笔记

2019/07/05 ML

HMM

HMM是关于时序的概率有向图模型,属于生成模型。即先求解联合概率P(x,y),再利用贝叶斯定理求条件概率P(y|x)。其描述了由一个隐藏的马尔科夫链生成不可观测的状态序列,再由各个状态生成一个观测序列的过程。

补充:概率有向图的联合概率

P(X1,X2,,XN)=Ni=1P(Xi|π(Xi))

其中π(Xi)表示Xi节点的(最近的)父节点。

HMM常用于序列标注(分词/POS/NER/SRL/语音识别/…)任务。即给定观测的序列,预测其对应的标记(状态序列)。可以假设待标注的数据是由隐马尔科夫模型(HMM)生成的,那么我们可通过HMM的学习(确定模型参数)与预测(确定最优隐状态序列)算法进行标注。

数学描述

HMM由初始状态概率分布向量π、状态转移概率分布矩阵A以及观测概率分布矩阵B确定。

下面具体描述HMM的三个组成部分。

Q={q1,q2,,qN}是所有可能的状态集合,V={v1,v2,,vM}是所有可能的观测值集合,N是可能的状态数,M是可能的观测数。I=(i1,i2,,iT)是长度为T的状态序列,O=(o1,o2,,oT)是对应的观测序列。

π=[πi]1×N其中πi=P(i1=qi),i=1,2,,N表示初始时刻t=1处于某个状态qi的概率。

A=[aij]N×N其中aij=P(it+1=qjit=qi),i=1,2,,N;j=1,2,,N表示在时刻t处于状态qi的条件下,下一时刻t+1转移到状态qj的概率。

B=[bj(k)]N×M其中bj(k)=P(ot=vkit=qj),j=1,2,,N;k=1,2,,M表示在时刻t处于状态qj的条件下,观测到vk的概率。

初始状态概率向量π和状态转移概率矩阵A确定了隐藏的马尔科夫链,生成不可观测的状态序列。观测概率矩阵B确定了如何从状态序列生成观测序列。 综上,HMM可由三元符号表示成λ=(A,B,π)

HMM具体的数值例子(例10.1 盒子和球模型)见李航的《统计学习方法》

相关假设

由上述定义可知,HMM有如下假设

  1. 齐次马尔科夫性假设。即假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态,与其他时刻的状态及观测无关,也与时刻t无关。
  2. 观测独立性假设。即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态,与其他观测及状态无关。

观测序列的生成

输入: 隐马尔可夫模型λ=(A,B,π),观测序列长度T

输出: 观测序列O=(o1,o2,,oT)

  • (1) 由初始状态概率分布π,确定初始状态i1
  • (2) 令t=1
  • (3) 由当前状态it的观测概率分布阵B,确定观测值ot
  • (4) 由状态转移概率阵A,确定下一时刻的状态it+1
  • (5) 令t=t+1,如果t<=T,跳到(3);否则终止。

HMM在分词中的应用

假设有文本(观测)序列X=x1,x2,...,xn,HMM分词的任务就是根据序列X进行推断,得到标记(状态)序列Y=y1,y2,...,yn。即计算如下概率,使其值最大:

P(y1,y2,,ynx1,x2,,xn)

由贝叶斯公式可得

P(y1,y2,,ynx1,x2,,xn)=P(y1,y2,,yn,x1,x2,,xn)P(x1,x2,,xn)

又序列是确定的,则P(x1,x2,,xn)为常值。所以只需使下式值最大

P(x1,y1,x2,y2,,xn,yn)=P(y1)P(x1y1)ni=2P(yiyi1)P(xiyi)(1)

而右式中的P(y1)P(yiyi1)P(xiyi)分别是初始状态概率向量π、状态转移概率矩阵A和观测概率矩阵B中的元素。当λ=(A,B,π)确定后,可通过维特比算法求出一个文本序列对应概率最大的分词标记序列,最终完成分词任务。

参数的确定

假设所给语料的格式如下:

  • 文本序列(字典中共有N个字)
  • 预测序列(Begin/Middle/End/Single/Other),分词任务中通常用BMES标记,此时隐状态个数为4

语料中的一个样本

  • 请问今天南京的天气怎么样
  • BEBEBESBEBME

1) 初始状态概率向量 统计每个句子开头的序列标记分别为B,S的个数,然后除以总句子的个数,即得到了初始概率向量。

2) 状态转移概率矩阵 统计语料中前后序列标记间转移的个数。如统计语料中,在t1时刻标记为M的条件下,t时刻标记为E出现的次数,类似的统计可得到4*4的矩阵,再将矩阵的每个元素除以相应行对应标记的总个数,保证行的概率和为1。最终得到状态转移概率矩阵。

3) 观测概率矩阵 统计语料中在某个标记下,某个观测值出现的个数。如统计语料中,在t时刻标记为B的条件下,t时刻观测到字为”南“的次数。类似的统计得到一个4*N的矩阵,再将矩阵的每个元素除以语料中某个标记的总次数,保证行的概率和为1。最终得到观测概率矩阵。

维特比算法

由上面三组概率,确定一条概率最大的标记序列。即确定的标记序列使得式(1)的值最大。

基于上述HMM的数学描述,先给出一般的维特比算法流程。

变量δt(i),Ψt(i)的定义

定义在给定模型参数λ条件下,t时刻状态为i时,所有可能的标注序列(i1,i2,...,it)中,概率最大值记为

δt(i)=maxi1,i2,,it1P(it=i,it1,,i1,ot,,o1λ),i=1,2,,N

δt+1(i)=maxi1,i2,,itP(it+1=i,it,,i1,ot+1,,o1λ)

又当t+1时刻标注序列状态it+1确定时,则t+1时刻的观测概率P(ot+1it+1)也是确定的(观测序列已知)。 因此由式(1)的联合概率公式,δt+1(i)可进一步写成

δt+1(i)=max1jN[δt(j)aji]bi(ot+1),i=1,2,,N;t=1,2,,T1

定义t时刻状态为i时,所有可能的标注序列(i1,i2,...,it)中,概率最大值时对应的t1时刻(前一时刻)的标注序列

Ψt(i)=argmax1jN[δt1(j)aji]

基于上述两个变量的定义,维特比算法的流程如下:

输入: 模型λ=(A,B,π)和观测序列O=(o1,o2,,oT)

输出: 最优标注(状态)序列I=(i1,i2,,iT)

(1) 初始化t=1:

δ1(i)=πibi(o1),Ψ1(i)=0,i=1,2,,N

(2) 递推

δt(i)=max1jN[δt1(j)aji]bi(ot),i=1,2,,N,其中t=2,3,,T

Ψt(i)=argmax1jN[δt1(j)aji],i=1,2,,N

(3) 终止(确定最后时刻T所有可能的标注序列中概率最大时最后一个位置的标记)

iT=argmax1iN[δT(i)]

(4) 回溯 (从后往前确定一个最优标注序列)

it=Ψt+1(it+1),t=T1,T2,,1

通过上述一去一回的迭代,最终可得最优标注序列。具体数值例子(例10.3)见李航的《统计学习方法》

基于上述描述,具体看一个简单的分词实战。假设给定文本:我爱中国。序列标注有BMES四种状态。在确定标注序列时,每个字有4种可能的标注状态。如图所示

png

(1)初始化

δ1(B)=P(x1=我,y1=B)=P(y1=B)×P(x1=我|y1=B) δ1(M)=P(x1=我,y1=M)=P(y1=M)×P(x1=我|y1=M) δ1(E)=P(x1=我,y1=E)=P(y1=E)×P(x1=我|y1=E) δ1(S)=P(x1=我,y1=S)=P(y1=S)×P(x1=我|y1=S) Ψ1(B)=Ψ1(M)=Ψ1(E)=Ψ1(S)=UNK

(2) 递推

Ψ2(B)=argmaxBMES{δ1(B)×P(y2=B|y1=B),δ1(M)×P(y2=B|y1=M),δ1(E)×P(y2=B|y1=E),δ1(S)×P(y2=B|y1=S)}

δ2(B)=P(x1=我,y1=Ψ2(B),x2=爱,y2=B)=max{δ1(B)×P(y2=B|y1=B),δ1(M)×P(y2=B|y1=M),δ1(E)×P(y2=B|y1=E),δ1(S)×P(y2=B|y1=S)}×P(x2=爱|y2=B)

Ψ2(M)=argmaxBMES{δ1(B)×P(y2=M|y1=B),δ1(M)×P(y2=M|y1=M),δ1(E)×P(y2=M|y1=E),δ1(S)×P(y2=M|y1=S)}

δ2(M)=P(x1=我,y1=Ψ2(M),x2=爱,y2=M)

 δ4(B)=P(x1=我,y1=Ψ2(B),x2=爱,y2=Ψ3(B),x3=中,y3=Ψ4(B),x4=国,y4=B)  δ4(M)=P(x1=我,y1=Ψ2(M),x2=爱,y2=Ψ3(M),x3=中,y3=Ψ4(M),x4=国,y4=M)  δ4(E)=P(x1=我,y1=Ψ2(E),x2=爱,y2=Ψ3(E),x3=中,y3=Ψ4(E),x4=国,y4=E)  δ4(S)=P(x1=我,y1=Ψ2(S),x2=爱,y2=Ψ3(S),x3=中,y3=Ψ4(S),x4=国,y4=S)

(3)终止,确定最后一个位置的标记

i4=argmaxBMES{max{δ4(B),δ4(M),δ4(E),δ4(S)}}=E

(4)回溯,确定最终的标注序列

it=Ψt+1(it+1),t=3,2,1

最终可得序列SSBE

CRF

CRF结合了最大熵模型和隐马尔可夫模型的特点,是一种概率无向图模型(由无向图表示的联合概率分布,也叫马尔可夫随机场),属于判别模型。即直接求解条件概率P(yx)。在NLP中,最常用的是线性链条件随机场。

与HMM相比,CRF具有更强的建模能力。其考虑了某一时刻的状态的上下文关系(上一时刻与下一时刻的状态)

概率无向图的因子分解

给定概率无向图模型GCG上的最大团,YC表示C中的节点集合(随机变量)。那么概率无向图(联合概率P(Y))可写成所有最大团C上的势函数ΨC(YC)的连乘积形式,即

P(Y)=1ZCΨC(YC)

其中Z=YCΨC(YC)表示归一化因子,Y表示多种可能分布的集合,ΨC(YC)=exp{E(YC)}

条件随机场

X,Y表示随机变量,若Y构成一个由图G=(V,E)表示的概率无向图(马尔科夫随机场),即

P(Yv|X,Yw,wv)=P(Yv|X,Yw,wv)

对任意节点v都成立,其中wv表示在图G=(V,E)中与节点v有边连接的所有节点wwv表示节点v以外的所有节点,Yv,Yw表示节点v,w对应的随机变量。则称条件概率分布P(YX)为条件随机场

上述定义中并没有要求X,Y具有相同的结构。实际中常假设X,Y具有相同的图结构,常用的线性链结构如下图所示

png

此时 G=(V={1,2,,n},E={(i,i+1)}),i=1,2,,n1

最大团是相邻两个结点的集合。

线性链条件随机场定义如下:X=(X1,X2,,Xn),Y=(Y1,Y2,,Yn)均为线性链表示的随机变量序列,在给定随机变量序列X的条件下,若条件概率P(YX)构成条件随机场,即满足如下性质

P(Yi|X,Y1,,Yi1,Yi+1,,Yn)=P(Yi|X,Yi1,Yi+1),i=1,2,,n(i=1n时只考虑单边)

则称P(YX)为线性链条件随机场。在标注问题中,X表示观测序列,Y表示对应的标记序列(状态序列)。

(线性链)条件随机场的参数化形式

P(YX)为线性链条件随机场,则在随机变量X取值为x的条件下,随机变量Y取值为y的条件概率具有如下形式:

P(yx)=1Z(x)exp(i,kλktk(yi1,yi,x,i)+i,lμlsl(yi,x,i))

其中

Z(x)=yexp(i,kλktk(yi1,yi,x,i)+i,lμlsl(yi,x,i))

Z(x)为归一化因子,求和是针对所有可能的标注序列进行的

参数解释:

tk是定义在边上的特征函数,称为转移特征,依赖当前和前一个位置,sl是定义在节点上的特征函数,称为状态特征,依赖当前位置。λk,μl分别为tk,sl的权值,为模型待学习的参数。 通常,特征函数tk,sl取值为1或0。

更进一步地,i,kλktk(yi1,yi,x,i)表示由给定序列x预测的标注序列y中相邻标注间的状态转移的得分i,lμlsl(yi,x,i)表示某个观测序列x被标注为序列y的得分

条件随机场由tk,sl,λk,μl共同确定。

(tensorflow中的)条件随机场在NER中的应用

以序列标注任务中的命名实体识别(NER)为例,详解tensorflow中的条件随机场。

假设命名实体识别任务的网络结构如图所示:

png

在上图中我们只关注与CRF相关的部分。CRF的输入(观测序列)为一个句子经过双向LSTM后的输出特征,输出(状态序列)为每个词对应的标记。训练阶段,利用真实的(,)对,构造损失函数,通过极小化损失学习出CRF模型中的参数。预测阶段,直接将待标记的句子输入到网络中,利用维特比算法选取概率最大的序列作为最终的标记序列。

先看下tensorflow中对CRF损失函数的定义,其用于训练过程的参数估计

tf.contrib.crf.crf_log_likelihood(
    inputs,
    tag_indices,
    sequence_lengths,
    transition_params=None
)

其中inputs表示双向LSTM的输出,其形状为[batch_size, max_seq_len, num_tags],tag_indices表示输入句子中每个词对应的真实标签索引号,其形状为[batch_size, max_seq_len],sequence_lengths表示输入句子的真实长度,其形状为[batch_size],transition_params表示转移矩阵,其为待学习确定的CRF层的参数,其形状为[num_tags,num_tags]

接着看下其具体实现

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 potentials
        to use as input to the CRF layer.
    tag_indices: A [batch_size, max_seq_len] matrix of tag indices for which we
        compute 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 [batch_size] `Tensor` containing the log-likelihood of
      each example, given the 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.
  """
  # Get shape information.
  num_tags = tensor_shape.dimension_value(inputs.shape[2])

  # 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 per example.
  log_likelihood = sequence_scores - log_norm
  return log_likelihood, transition_params

crf_log_likelihood函数中先调用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 potentials
        to use as input to the CRF layer.
    tag_indices: A [batch_size, max_seq_len] matrix of tag indices for which we
        compute 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.
  """
  # If max_seq_len is 1, we skip the score calculation and simply gather the
  # unary potentials of the single tag.
  def _single_seq_fn():
    batch_size = array_ops.shape(inputs, out_type=tag_indices.dtype)[0]
    example_inds = array_ops.reshape(
        math_ops.range(batch_size, dtype=tag_indices.dtype), [-1, 1])
    sequence_scores = array_ops.gather_nd(
        array_ops.squeeze(inputs, [1]),
        array_ops.concat([example_inds, tag_indices], axis=1))
    sequence_scores = array_ops.where(math_ops.less_equal(sequence_lengths, 0),
                                      array_ops.zeros_like(sequence_scores),
                                      sequence_scores)
    return sequence_scores

  def _multi_seq_fn():
    # 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_scores
    return sequence_scores

  return utils.smart_cond(
      pred=math_ops.equal(
          tensor_shape.dimension_value(
              inputs.shape[1]) or array_ops.shape(inputs)[1],
          1),
      true_fn=_single_seq_fn,
      false_fn=_multi_seq_fn)

其中crf_unary_score表示输入观测到标记状态的得分,crf_binary_score表示标记状态间转移的得分。和上述条件随机场的参数化形式中的参数解释部分的得分相对应。

再调用crf_log_norm计算归一化因子的对数数值,两项相减得出最终的对数概率。[相关计算可参考Neural Architectures for Named Entity Recognition中的式(1)]

通过上述损失函数,利用一定的训练数据集,可学习出转移参数transition_params。

预测阶段利用学习到的转移参数transition_params调用tensorflow中的解码函数crf_decode或viterbi_decode即可得到标注序列。crf_decode与viterbi_decode实现了相同的功能,前者是基于tensor实现的,后者是基于numpy实现的。

重点看下crf_decode的使用,其定义如下

tf.contrib.crf.crf_decode(
    potentials,
    transition_params,
    sequence_length
)

其中potentials表示待预测句子经过双向LSTM的输出,transition_params为训练过程学习到的参数,sequence_length为待预测句子的实际长度

具体实现如下

def crf_decode(potentials, transition_params, sequence_length):
  """Decode the highest scoring sequence of tags in TensorFlow.

  This is a function for tensor.

  Args:
    potentials: A [batch_size, max_seq_len, num_tags] tensor of
              unary potentials.
    transition_params: A [num_tags, num_tags] matrix of
              binary potentials.
    sequence_length: A [batch_size] vector of true sequence lengths.

  Returns:
    decode_tags: A [batch_size, max_seq_len] matrix, with dtype `tf.int32`.
                Contains the highest scoring tag indices.
    best_score: A [batch_size] vector, containing the score of `decode_tags`.
  """
  # If max_seq_len is 1, we skip the algorithm and simply return the argmax tag
  # and the max activation.
  def _single_seq_fn():
    squeezed_potentials = array_ops.squeeze(potentials, [1])
    decode_tags = array_ops.expand_dims(
        math_ops.argmax(squeezed_potentials, axis=1), 1)
    best_score = math_ops.reduce_max(squeezed_potentials, axis=1)
    return math_ops.cast(decode_tags, dtype=dtypes.int32), best_score

  def _multi_seq_fn():
    """Decoding of highest scoring sequence."""

    # For simplicity, in shape comments, denote:
    # 'batch_size' by 'B', 'max_seq_len' by 'T' , 'num_tags' by 'O' (output).
    num_tags = tensor_shape.dimension_value(potentials.shape[2])

    # Computes forward decoding. Get last score and backpointers.
    crf_fwd_cell = CrfDecodeForwardRnnCell(transition_params)
    initial_state = array_ops.slice(potentials, [0, 0, 0], [-1, 1, -1])
    initial_state = array_ops.squeeze(initial_state, axis=[1])  # [B, O]
    inputs = array_ops.slice(potentials, [0, 1, 0], [-1, -1, -1])  # [B, T-1, O]
    # Sequence length is not allowed to be less than zero.
    sequence_length_less_one = math_ops.maximum(
        constant_op.constant(0, dtype=sequence_length.dtype),
        sequence_length - 1)
    backpointers, last_score = rnn.dynamic_rnn(  # [B, T - 1, O], [B, O]
        crf_fwd_cell,
        inputs=inputs,
        sequence_length=sequence_length_less_one,
        initial_state=initial_state,
        time_major=False,
        dtype=dtypes.int32)
    backpointers = gen_array_ops.reverse_sequence(  # [B, T - 1, O]
        backpointers, sequence_length_less_one, seq_dim=1)

    # Computes backward decoding. Extract tag indices from backpointers.
    crf_bwd_cell = CrfDecodeBackwardRnnCell(num_tags)
    initial_state = math_ops.cast(math_ops.argmax(last_score, axis=1),  # [B]
                                  dtype=dtypes.int32)
    initial_state = array_ops.expand_dims(initial_state, axis=-1)  # [B, 1]
    decode_tags, _ = rnn.dynamic_rnn(  # [B, T - 1, 1]
        crf_bwd_cell,
        inputs=backpointers,
        sequence_length=sequence_length_less_one,
        initial_state=initial_state,
        time_major=False,
        dtype=dtypes.int32)
    decode_tags = array_ops.squeeze(decode_tags, axis=[2])  # [B, T - 1]
    decode_tags = array_ops.concat([initial_state, decode_tags],   # [B, T]
                                   axis=1)
    decode_tags = gen_array_ops.reverse_sequence(  # [B, T]
        decode_tags, sequence_length, seq_dim=1)

    best_score = math_ops.reduce_max(last_score, axis=1)  # [B]
    return decode_tags, best_score

  return utils.smart_cond(
      pred=math_ops.equal(tensor_shape.dimension_value(potentials.shape[1]) or
                          array_ops.shape(potentials)[1], 1),
      true_fn=_single_seq_fn,
      false_fn=_multi_seq_fn)

关于命名实体网络结构中CRF部分可参考https://github.com/carlos9310/BERT-BiLSTM-CRF-NER.git中bert_base/train/bert_lstm_ner.py中的add_blstm_crf_layer函数中crf_layer与crf_decode的具体调用(该网络结构在设计时有缺陷,限制了最大文本序列的长度。如果某个实体在长文本的后面,那么在实体识别前会截断过长的部分。利用viterbi_decode进行解码且对文本长度无限制的版本见https://github.com/crownpku/Information-Extraction-Chinese)

 def add_blstm_crf_layer(self, crf_only):
        """
        blstm-crf网络
        :return:
        """
        if self.is_training:
            # lstm input dropout rate i set 0.9 will get best score
            self.embedded_chars = tf.nn.dropout(self.embedded_chars, self.dropout_rate)

        if crf_only:
            logits = self.project_crf_layer(self.embedded_chars)
        else:
            # blstm
            lstm_output = self.blstm_layer(self.embedded_chars)
            # project
            logits = self.project_bilstm_layer(lstm_output)
        # crf
        loss, trans = self.crf_layer(logits)
        # CRF decode, pred_ids 是一条最大概率的标注路径
        pred_ids, _ = crf.crf_decode(potentials=logits, transition_params=trans, sequence_length=self.lengths)
        return (loss, logits, trans, pred_ids)

最后总结下CRF在上述NER中的过程。首先,待标注的句子中的每个词/字,经过向量化后输入到双向LSTM中,得到的输出张量可看成CRF中的状态函数sl的得分(或HMM中的观测概率矩阵),随机初始化(学习到)的transition_params可看成转移函数tk的得分(或HMM中的状态转移概率矩阵),由上述确定下的参数,最终预测出概率最高的标注序列。由于CRF考虑到标注序列的前后关系,增加了输出约束,可有效避免不符合逻辑关系的标注序列出现。

补充(crf_decode与viterbi_decode一致性验证)

transition表示训练阶段学习到的转移参数,以NER为例,其表示不同tag间转移的几率。给的代码表示有3种不同的tag。

score表示预测时,根据训练得到的网络结构和参数,计算某个批次中的某句话中的每一个字属于不同tag的几率。给的代码表示一个批次中只有一句话,且该句话有4个字,每个字给出了属于不同tag的几率。

crf_decode与viterbi_decode基于上述两个参数解码出一个最佳的标记序列。其核心思想是基于动态规划与回溯进行解码的。(viterbi = 动态规划+回溯)

具体代码如下,两个解码函数返回同样的结果。

import tensorflow as tf
import numpy as np
from tensorflow.contrib.crf import viterbi_decode
from tensorflow.contrib.crf import crf_decode

score = [[
    [1, 2, 3],
    [2, 1, 3],
    [1, 3, 2],
    [3, 2, 1]
]]  # (batch_size, time_step, num_tabs)
transition = [
    [2, 1, 3],
    [1, 3, 2],
    [3, 2, 1]
]   # (num_tabs, num_tabs)
lengths = [len(score[0])]   # (batch_size, time_step)

print(f'lengths:{lengths}')
print(f'shape of np.array(score[0]):{np.array(score[0]).shape}')
print(f'shape of np.array(transition):{np.array(transition).shape}')

# numpy
print("[numpy]")
np_op = viterbi_decode(
   score=np.array(score[0]),
   transition_params=np.array(transition))
print(np_op[0])
print(np_op[1])
print("=============")

# tensorflow
score_t         = tf.constant(score, dtype=tf.int64)
transition_t    = tf.constant(transition, dtype=tf.int64)
lengths_t       = tf.constant(lengths, dtype=tf.int64)
tf_op = crf_decode(
    potentials=score_t,
    transition_params=transition_t,
    sequence_length=lengths_t)
with tf.Session() as sess:
    paths_tf, scores_tf = sess.run(tf_op)
    print(f'shape of score_t:{score_t.shape}')
    print(f'shape of transition_t:{transition_t.shape}')
    print(f'shape of lengths_t:{lengths_t.shape}')
    print("[tensorflow]")
    print(paths_tf)
    print(scores_tf)

其中基于numpy写的viterbi算法比较简洁,具体如下:

def viterbi_decode(score, transition_params):
  """Decode the highest scoring sequence of tags outside of TensorFlow.

  This should only be used at test time.

  Args:
    score: A [seq_len, num_tags] matrix of unary potentials.
    transition_params: A [num_tags, num_tags] matrix of binary potentials.

  Returns:
    viterbi: A [seq_len] list of integers containing the highest scoring tag
        indices.
    viterbi_score: A float containing the score for the Viterbi sequence.
  """
  trellis = np.zeros_like(score)
  backpointers = np.zeros_like(score, dtype=np.int32)
  trellis[0] = score[0]

  for t in range(1, score.shape[0]):
    v = np.expand_dims(trellis[t - 1], 1) + transition_params
    trellis[t] = score[t] + np.max(v, 0)
    backpointers[t] = np.argmax(v, 0)

  viterbi = [np.argmax(trellis[-1])]
  for bp in reversed(backpointers[1:]):
    viterbi.append(bp[viterbi[-1]])
  viterbi.reverse()

  viterbi_score = np.max(trellis[-1])
  return viterbi, viterbi_score

其中trellis保存的是到每一个字标记为不同tag时对应的总分数最大。backpointers记录的是由上一个字到当前字标记为不同tag时对应的总分数最大时上一个字对应的tag的索引,到遍历完所有字时,可确定最后一个字对应的tag索引,然后根据最后一个字的索引,从backpointers中回溯其上一个字对应的tag的索引,直到回溯到第一个字,最终得到每个字对应的tag使总的分数最大。

以上便是viterbi算法的大致流程。

参考

Search

    Post Directory

    文章目录