关于机器学习:条件随机场

条件随机场（conditional random field，CRF）是给定一组输出随机变量条件下另一组输入随机变量的条件概率分布模型，并且 假如输入随机变量形成马尔可夫随机场（概率无向图模型）。
条件随机场定义 ：设 $X$ 和 $Y$ 是随机变量，$P(Y|X)$ 是在给定 $X$ 的条件下 $Y$ 的条件概率分布。若随机变量 $Y$ 形成一个由无向图 $G=(V,E)$ 示意的马尔可夫随机场，即式(1)
$$\begin{equation}P(Y_v|X,Y_w,w\neq v) = P(Y_v|X,Y_w,w\sim v)\tag{1}\end{equation}$$
对任意结点 $v$ 成立，则条件概率分布 $P(Y|X)$ 为条件随机场。式 (1) 中，$w \neq v$ 示意结点 $v$ 以外的所有结点，$w\sim v$ 示意在图 $G=(V,E)$ 中与结点 $v$ 有边连贯的所有结点 $w$，$Y_v$，$Y_u$ 和 $Y_w$ 为结点 $v$，$u$ 和 $w$ 对应的随机变量。

线性链条件随机场定义 ：设 $X=(X_1,X_2,\cdots,X_n)$，$Y=(Y_1,Y_2,\cdots,Y_n)$ 均为线性链示意的随机变量序列，若在给定随机变量序列 $X$ 的条件下，随机变量序列 $Y$ 的条件概率分布形成条件随机场，即满足式(2)，则称 $P(Y|X)$ 为线性链条件随机场。
$$\begin{equation}P(Y_i|X,Y_1,\cdots,Y_{i-1},Y_{i+1},\cdots,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})\tag{2}\end{equation}$$
其中，$i=1,\cdots,n$，当 $i=1$ 或者 $i=n$ 时，只思考单边。

团与最大团定义 ：无向图中任意两个结点之间均有边连贯的结点子集称为团(clique)。若 $C$ 是无向图 $G$ 的一个团，并且不能再退出任何一个 $G$ 中的结点使其称为一个更大的团，则称 $C$ 为最大团(maximul clique)。
将概率无向图的联结概率分布示意为其最大团上的随机变量的函数的乘积模式的操作，称为概率无向图模型的因子合成 (factorization)。设无向图为 $G$，$C$ 为 $G$ 上的最大团，$Y_C$ 示意 $C$ 对应的随机变量，则概率无向图模型的联结概率分布 $P(Y)$ 能够写作所有最大团 $C$ 上的函数 $\Psi_C(Y_C)$ 的乘积模式，即
$$\begin{equation}P(Y)=\frac{1}{Z}\Pi_C \Psi_C(Y_C)\tag{3}\end{equation}$$
其中，$Z$ 为规范化因子，$Z=\sum_{Y}\Pi_C\Psi_C(Y_C)$，$\Psi_C(Y_C)$ 称为 势函数 (potential function)，要求是严格正的，通常定义为指数函数，即 $\Psi_C(Y_C)=exp(-E(Y_C))$。
依据概率无向图的因子合成，得出线性链条件随机场 $P(Y|X)$ 的因子合成式，当无向图为线性链模式是，最大团的大小为 2，因而 因子合成式中的因子是定义在相邻两个结点上的函数。

原始模式

设 $P(Y|X)$ 为线性链条件随机场，则在随机变量 $X$ 的取值为 x 的条件下，随机变量 $Y$ 取值为 $y$ 的条件概率如下，
$$\begin{equation}P(y|x)=\frac{1}{Z}\Pi_{t=1}^{T}\psi(y_{t-1},y_t,x)\tag{4}\end{equation}$$
其中 $x=(x_1,\cdots,x_n)$ 为输出的观测序列，状态序列（输入序列）$y=(y_1,\cdots, y_T)$，$\psi(y_{t-1},y_t,x)\geq 0$ 为势函数。对势函数进行拆分，假设 $\psi(y_{t-1},y_t,x)=\exp(\Delta_{y_{t-1},y_t,x} + \Delta_{y_t,x})$，令 $\Delta_{y_{t-1},y_t,x}=\sum_{k}\lambda_k f_{k}^{transition}(y_{t-1},y_t,x,t)$，令 $\Delta_{y_t,x}=\sum_{l}\mu_lf_l^{state}(y_t,x,t)$，则 $P(y|x)$ 能够写为，
$$\begin{equation}P(y|x)=\frac{1}{Z(x)}\exp(\sum_{t,k}\lambda_k f_{k}^{transition}(y_{t-1},y_t,x,t)+\sum_{t,l}\mu_lf_l^{state}(y_t,x,t))\tag{5}\end{equation}$$
其中，$Z(x)$ 为规范化因子，$Z(x)=\sum_{y}\exp(\sum_{t,k}\lambda_k f_{k}^{transition}(y_{t-1},y_t,x,t)+\sum_{t,l}\mu_lf_l^{state}(y_t,x,t))$，$f_{k}^{transition}$ 为转移特征函数，$f_{l}^{state}$ 为状态特征函数。在传统的做法中，状态特征函数和转移特征函数是通过人工特色工程的形式设计的，它们的取值为 1 或 0，即满足特色条件时取值为 1，否则为 0。

内积模式

对式 (5) 取对数，
$$\begin{equation}\begin{aligned}\log P(y|x)&=\sum_{t,k}\lambda_k f_{k}^{transition}(y_{t-1},y_t,x,t)+\sum_{t,l}\mu_lf_l^{state}(y_t,x,t)-\log Z(x)\\&=\sum_{t}(\sum_{i=1}^{K+L}w_i f_i(y_{t-1},y_t,x, t))-\log Z(x)\end{aligned}\tag{6}\end{equation}$$
其中，为了简便，对转移特色和状态特色用对立的符号示意，

$$
\begin{equation}f_i(y_{t-1},y_t,x,t) =
\begin{cases}
f^{transition}_i(y_{t-1},y_t,x,t),i=1,\cdots,K \\ f^{state}_l(y_t,x,t), i=K+l;l=1,\cdots,L
\end{cases}\tag{7}\end{equation}
$$

$$
\begin{equation}w_i =
\begin{cases}
\lambda_i,i=1,\cdots,K \\ \mu_l, i=K+l;l=1,\cdots,L
\end{cases}\tag{8}\end{equation}
$$

令 $f_i(y,x)=\sum_{t=1}^{T}f_i(y_{t-1},y_t,x,t)$，$F(y,x)=(f_1(y,x),\cdots,f_{K+L}(y,x))^T$，$w=(w_1,\cdots,w_{K+L})^T$。
则条件随机场的对数模式 $\log P(y|x)$ 能够写为 $w$ 和 $F$ 内积的模式
$$\begin{equation}\log P(y|x)=w\cdot F(y,x) – \log Z(x)\tag{9}\end{equation}$$

引入神经网络

式 (4) 的对数模式为，
$$\begin{equation}\log P(y|x)=\sum_{t=1}^T\log(\psi(y_{t-1},y_t,x_t)) – \log Z(x)\tag{10}\end{equation}$$
其中，$\psi(y_{t-1},y_t,x)$ 能够了解为依据 $y_{t-1},y_t,x$ 提取的特色的加权和，这一部分能够应用神经网络代替人工特色工程。
引入神经网络示意转移特征函数 $f^{transition}$ 和状态特征函数 $f^{state}$，能够将条件随机场的对数模式简化为，
$$\begin{equation}\log P(y|x)=\sum_{t}f^{transition}(y_{t-1},y_t,x)+\sum_{t}f^{state}(y_t,x)-\log Z(x)\tag{11}\end{equation}$$
思考到以后深度学习模型中，RNN 或者层叠 CNN 或是 Bert 等模型曾经可能使得 $f^{state}$ 充沛地捕获各个 y 与输入 x 的分割，因而，无妨思考转移特征函数 $f^{transition}$ 与 x 无关，那么能够进一步简化为，
$$\begin{equation}\log P(y|x)=\underbrace{\sum_{t}f^{transition}(y_{t-1},y_t)}_{(a)}+\underbrace{\sum_{t}f^{state}(y_t,x)}_{(b)}-\underbrace{\log Z(x)}_{(c)}\tag{12}\end{equation}$$
对上式取负，应用极大似然法，求解参数。
因而，损失函数的计算分为三局部，别离对应式中的 (a)、(b) 和(c)。

一元概率

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)
  # Use int32 or int64 based on tag_indices' dtype.
  if tag_indices.dtype == dtypes.int64:
    offsets = math_ops.cast(offsets, dtypes.int64)
  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 = array_ops.sequence_mask(sequence_lengths,
                                  maxlen=array_ops.shape(tag_indices)[1],
                                  dtype=dtypes.float32)

  unary_scores = math_ops.reduce_sum(unary_scores * masks, 1)
  return unary_scores

crf_unary_score计算一元概率，输入一个维度为 [batch_size] 的向量，向量中的每一个元素是一个 sequence 中所有的实在标签概率之和。对应式中的 (b) 项。输出 inputs 的维度为 [batch_size, max_seq_len, num_tags]，个别为 BiLSTM 或者是 Bert 的输入，num_tags 为标签数，inputsi[k] 示意的是，以后 batch 中的第 i 个序列，其地位 j 对应的输入属于类别 k 的概率。flattened_inputs将 input 变为一维，tag_indices为实在的标签，维度为 [batch_size, max_seq_len]，offsets 的维度为 [batch_size, max_seq_len], offsetsi = (batch_size i + max_seq_len j) * num_tags，因而，offsets + tag_indices 中(i，j)地位的值示意的是，以后 batch 中的第 i 个序列，其地位 j 对应的输入属于类别 tag_indicesi 的概率位于 flatten_inputs，拉平后失去 flattened_tag_indices，通过 gather 函数，失去所有的一元概率。最初，应用sequence_mask 依据序列的真是长度，生成 mask，失去所有无效的一元概率之和unary_scores。

二元概率

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_indices
  flattened_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 = array_ops.sequence_mask(sequence_lengths,
                                  maxlen=array_ops.shape(tag_indices)[1],
                                  dtype=dtypes.float32)
  truncated_masks = array_ops.slice(masks, [0, 1], [-1, -1])
  binary_scores = math_ops.reduce_sum(binary_scores * truncated_masks, 1)
  return binary_scores

crf_binary_score计算二元概率，输入维度为 [batch_size]，向量中的每个元素是一个 sequence 中所有的转移概率之和。对应式中的(a) 项。序列的长度为 num_transitions，则会产生 num_transitions- 1 此转移，转移的起始下标start_tag_indices 对应 0，$\cdots$，num_transitions-2，完结下标 end_tag_indices 对应 1，$\cdots$，num_transitions-1。应用与 crf_unary_score 相似的原理取出对应地位的转移概率，进行 mask 操作求和，返回binary_scores。

log normalization factor

  def _multi_seq_fn():
    """Forward computation of alpha values."""
    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)
    # Sequence length is not allowed to be less than zero.
    sequence_lengths_less_one = math_ops.maximum(constant_op.constant(0, dtype=sequence_lengths.dtype),
        sequence_lengths - 1)
    _, alphas = rnn.dynamic_rnn(
        cell=forward_cell,
        inputs=rest_of_input,
        sequence_length=sequence_lengths_less_one,
        initial_state=first_input,
        dtype=dtypes.float32)
    log_norm = math_ops.reduce_logsumexp(alphas, [1])
    # Mask `log_norm` of the sequences with length <= zero.
    log_norm = array_ops.where(math_ops.less_equal(sequence_lengths, 0),
                               array_ops.zeros_like(log_norm),
                               log_norm)
    return log_norm

normalization factor $Z$ 的计算形式，
$$\begin{equation}Z=\sum_y \Pi_{t=1}^T\psi(y_{t-1},y_t,x)\tag{13}\end{equation}$$
应用前向算法计算 $Z$，令
$$\begin{equation}\alpha_j(y_j=s)=\sum_{y1,\cdots,y_{j-1}}(\Pi_{t=1}^{j-1}\psi(y_{t-1},y_t,x))\psi(y_{j-1},y_j=s,x)\tag{14}\end{equation}$$
则有
$$\begin{equation}\begin{aligned}\alpha_{j+1}(y_{j+1}=s^{‘})&=\sum_{y_1,\cdots,y_j}(\Pi_{t=1}^{j}\psi(y_{t-1},y_t,x))\psi(y_{j},y_{j+1}=s^{‘},x)\\&=\sum_{s=1}^{N}(\sum_{y1,\cdots,y_{j-1}}(\Pi_{t=1}^{j-1}\psi(y_{t-1},y_t,x))\psi(y_{j-1},y_j=s,x))\psi(y_{j}=s,y_{j+1}=s^{‘},x)\\&=\sum_{s=1}^N\alpha_j(y_j=s)\psi(y_{j}=s,y_{j+1}=s^{‘},x)\\&=\sum_{s=1}^N\alpha_j(y_j=s)\exp(f^{transition}(y_j=s,y_{j+1}=s^{‘})+\underbrace{f^{state}(y_{t+1},x)}_{与 y_j 无关})\\&=\sum_{s=1}^N\underbrace{\alpha_j(y_j=s)}_{(a)}\underbrace{\exp(f^{transition}(y_j=s,y_{j+1}=s^{‘}))}_{(b)}\underbrace{\exp(f^{state}(y_{t+1},x))}_{(c)}\end{aligned}\tag{15}\end{equation}$$

class CrfForwardRnnCell(rnn_cell.RNNCell):
  """Computes the alpha values in a linear-chain CRF.

  See http://www.cs.columbia.edu/~mcollins/fb.pdf for reference.
  """def __init__(self, transition_params):"""Initialize the CrfForwardRnnCell.

    Args:
      transition_params: A [num_tags, num_tags] matrix of binary potentials.
          This matrix is expanded into a [1, num_tags, num_tags] in preparation
          for the broadcast summation occurring within the cell.
    """
    self._transition_params = array_ops.expand_dims(transition_params, 0)
    self._num_tags = tensor_shape.dimension_value(transition_params.shape[0])

  @property
  def state_size(self):
    return self._num_tags

  @property
  def output_size(self):
    return self._num_tags

  def __call__(self, inputs, state, scope=None):
    """Build the CrfForwardRnnCell.

    Args:
      inputs: A [batch_size, num_tags] matrix of unary potentials.
      state: A [batch_size, num_tags] matrix containing the previous alpha
          values.
      scope: Unused variable scope of this cell.

    Returns:
      new_alphas, new_alphas: A pair of [batch_size, num_tags] matrices
          values containing the new alpha values.
    """
    state = array_ops.expand_dims(state, 2)

    # This addition op broadcasts self._transitions_params along the zeroth
    # dimension and state along the second dimension. This performs the
    # multiplication of previous alpha values and the current binary potentials
    # in log space.
    transition_scores = state + self._transition_params
    new_alphas = inputs + math_ops.reduce_logsumexp(transition_scores, [1])

    # Both the state and the output of this RNN cell contain the alphas values.
    # The output value is currently unused and simply satisfies the RNN API.
    # This could be useful in the future if we need to compute marginal
    # probabilities, which would require the accumulated alpha values at every
    # time step.
    return new_alphas, new_alphas

CrfForwardRnnCell(rnn_cell.RNNCell)基于 RNN 的架构，在工夫步 t 接管一个输出 $x_t$，输入 $o_t$，生成新的 hidden state $h_t$。
其中，$x_t$ 为 $f^{state}(y_t,x)$，$h_t$ 即为前向算法中的 $\alpha_t=(\alpha_t(y_t=1),\cdots,\alpha_t(y_t=N))^T$，如图所示，在更新 $\alpha$ 时，应用的是加法而非乘法，这是因为，所有的计算都是在 log 空间中计算的，对应式 (15) 中的 $\log(a) + \log(b) = log(ab)$，所以 transition_scores = state + self._transition_params 计算失去的矩阵，其第 i 行第 j 列的元素是 $\log(\alpha_{t-1}(y_{t-1}=i)\times \exp(f^{transition}(y_{t-1}=i,y_t=j)))$，math_ops.reduce_logsumexp(transition_scores, [1])先 $\exp$ 再求和再取对数，失去 $\log(\alpha_{t-1}^T F(y_{t-1},y_t))$，再加上 inputs，理论是 $\log(\sum ab)+ \log (c)$，即 $\log((\sum ab)c)$，因而失去的新的 $\alpha_{t+1}$（hidden state）后果也是在 log 空间中的，不便下一个工夫步的计算。
inputs 的维度是 [batch_size, num_tags]，state 的维度为 [batch_size,num_tags]，transition_params 的维度为[num_tags,num_tags]。

预测

条件随机场的预测应用维特比算法

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记录非规范化概率，backpointers记录门路。

参考

1. http://www.cs.columbia.edu/~m…
2. LSTM-Based NeuroCRFs for Name Entity Recognition
3. 统计学习办法