Can I transform the Viterbi score from tensorflow into a probability? I understand the Viterbi algorithm as it is explained in Wikipedia
However, the TensorFlow implementation is different:
  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

In the "traditional" Viterbi algorithm we basically keep multiplying probabilities and take the maximum. But the Viterbi score of Tensorflow is consistently greater than 1 and increases with sequence length.

*

*Where is the Tensorflow implementation coming from?

*How can the Viterbi score retrieved by Tensorflow be consistently >1 and increase with the sequence length?

*Is there a way of transforming the TensorFlow Viterbi score into a probability? I want to compare the confidence of several sequence predictions in a Deep Learning architecture whose final layer is a CRF.

 A: This is doable, and fortunately the code to do it is already written.
Bear in mind that the Viterbi algorithm on a CRF uses potentials, not probabilities. These are not required to sum to 1. The Wikipedia article's language is tailored to Viterbi on an HMM, so it keeps talking about probabilities.


Where is the Tensorflow implementation coming from?

It's doing the familiar Viterbi algorithm, but working with log-potentials instead of potentials. Normally the two key operations in the Viterbi algorithm are $(\max, \times)$. In log-space, these become $(\max, +)$.


How can the Viterbi score retrieved by Tensorflow be consistently >1 and increase with the sequence length?

This ties back to the log-space idea. If we were working with probabilities, they would be consistently < 1 and decrease with the sequence length. But log-potentials can be any real number, and they keep getting added together. It seems that yours are non-negative.


Is there a way of transforming the TensorFlow Viterbi score into a probability?

Yes, certainly! You'll have to do a bit of extra work to get it, using the crf_log_norm function.
Remember that we use the Viterbi algorithm to find the highest-probability sequence $y^* = \arg\min_{y} p(y \mid x)$. But it does this by finding the sequence with the highest unnormalized probability $u(y \mid x)$—the 'Viterbi score' you got is the log of this. The relationship is that $p(y \mid x) = \frac{u(y \mid x)}{Z(x)}$. The Viterbi algorithm doesn't bother computing the normalizing constant $Z(x) = \sum_{y'} u(y' \mid x)$.
You're interested in $p(y^* \mid x)$. You already have $\log u(y^* \mid x)$. And there's a function in that library called crf_log_norm to compute $\log Z(x)$. All that remains is to compute the difference and then exponentiate.
\begin{align}
\log p(y^* \mid x) &= \log u(y^* \mid x) - \log Z(x) \\
p(y^* \mid x) &= \frac{u(y^* \mid x)}{Z(x)}
\end{align}

Just a reminder, though, computing $Z(x)$ with the forward algorithm is somewhat expensive: $O(nk^2)$ for $n$ tokens and $k$ possible states at each position. If you're comparing multiple possible taggings for one sequence, try to only compute $Z(x)$ once.
