What is the complexity of Viterbi algorithm ?

  • Viterbi algorithm is a dynamic programming approach to find the most probable sequence of hidden states given the observed data, as modeled  by a HMM. 
  • Without dynamic programming, it becomes an exponential problem as there are exponential number of possible sequences for a given observation(How – explained in answer below).
  • Let the transition probabilities(state transition) be denoted by p(y_{j}|y_{i}), and the output probabilities be denoted by p(o_{t}|y_{j})
  • Here let us call Q_{t,s} the most probable sequence of hidden states of length t that finishes in the state y_s and generates the output o_{1},...,o_{t} and q_{t,s} be the probability of this sequence which can be computed  from the equation below

        \[q_{t,s}\,=\,max_{k}\,q_{t-1, k}*p(y_s|y_k)*p(o_{t}|y_{s})\,\forall y\]


  • Say we have K states y_1,\hdots,y_K, observation sequence of length T , then we need to find q_{t,y} \forall t \epsilon T and \forall y and maximum in each iteration is obtained by checking for all states y. This leave us with a complexity^{*} of O(K^{2}T)
  • Space complexity: Next question could be what is the extra storage or memory complexity of Viterbi Algorithm –With DP, we always maintain an extra array to store the intermediate computations for reuse to avoid re-work. Here, we maintain a matrix q which is K*T in size. We also maintain argmax in every iteration which is also of same size. Hence the memory complexity is O(K*T)

*Hint: To answer such a question one must either remember the exact answer or the algorithm itself. In general, to compute complexity one can check how many times we have terms like “for all” . 

Leave a Reply

Your email address will not be published. Required fields are marked *