# Normalizing output of Viterbi algorithm

by Jan Vainer   Last Updated May 15, 2019 18:19 PM

Viterbi algorithm can be used to solve problems in belief networks of the following kind:

$$argmax_{x_{1:t}}P(x_{1:t}| e_{1:t})$$

where $$e_{1:t} \in E^t$$ are evidence variables and $$x_{1:t} \in S^t$$ are hidden states. The formula can be rewritten in the following way.

\begin{align}argmax_{x_{1:t}}P(x_{1:t}| e_{1:t}) &= argmax_{x_{1:t}} \alpha \cdot P( e_{1:t} | x_{1:t})P(x_{1:t})\\ &= argmax_{x_{1:t}} \Pi_{i=1}^t P( e_{i} | x_{i})P(x_{i}|x_{i-1})\\ \end{align}

The first equality comes from Bayes' rule. The second from conditional independence and the fact, that normalization constant does not affect argmax. The final formula can be computed dynamically.

Question: How can we compute $$max_{x_{1:t}}P(x_{1:t}| e_{1:t})$$ if we do not know the normalizing constant? We can find the optimal path, but can we also figure out the normalized probability? In e.g. Forward algorithm, we can calculate the prob. for each possible final state and still keep polynomial complexity. Is anything similar possible with the problem at hand? (It seems like it would be exponential, but maybe there is some clever trick.)

Tags :