Viterbi decoding for the most likely hidden path

Find the single most likely state sequence

Given an HMM with initial probabilities pi, transitions A, and emissions B, the Viterbi algorithm finds the state path that maximizes p(path, obs). It also returns that joint probability.

The recursion keeps, for each time t and state j, the best probability delta_t(j) of any path ending in j, plus a back-pointer to the previous state that achieved it. After the last step, it backtracks from the best final state.

Implement viterbi(pi, A, B, obs), which returns (path, prob).

• path is a list of T state indices.
• prob is the joint probability p(path, obs) of that path, as a float.

Constraints

• Inputs are validated like a forward-algorithm HMM: stochastic rows, consistent shapes, observations in 0..M-1.
• The observation sequence must not be empty. Otherwise raise ValueError.
• Ties may be broken in any consistent way, but the returned probability must equal the maximum over all paths.
• Do not modify the inputs.

Hints