viterbi – Machine Learning Interviews

What is the complexity of Viterbi algorithm ?

Posted on February 16, 2019February 19, 2019 by MLNerds

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)…

How do you find the most probable sequence of POS tags from a sequence of text?

Posted on February 16, 2019March 7, 2019 by MLNerds

This problem can be solved with a HMM. Using a HMM involves finding the transition probabilities (what is the probability of going from one POS tag to another and emission/output probabilities (what is the probability of observing a word given a POS tag) as explained in the question How do you train an hMM. Once…