How does the Viterbi algorithm work?

Viterbi algorithm is a dynamic programming method for finding the most probable sequence of hidden states in a hidden Markov model (HMM) that could have generated the observed data.

Main idea:

• For each time step, the algorithm calculates the most probable path leading to each state.
• Uses recursive calculations to avoid enumerating all possible paths.

Applications include speech recognition, bioinformatics, natural language processing.

Briefly:

1. Initialize probabilities for initial states.
2. For each subsequent observation, compute the maximum transition probability from previous states considering the observation probability.
3. Record the path that yields the maximum probability.
4. At the end, select the path with the highest overall probability.

Example pseudocode:

for state in states:
    V[0][state] = start_prob[state] * emit_prob[state][obs[0]]

for t in range(1, len(obs)):
    for state in states:
        V[t][state], path[state] = max(
            (V[t-1][prev_state] * trans_prob[prev_state][state] * emit_prob[state][obs[t]], prev_state)
            for prev_state in states
        )

# Select the final state with the highest probability
max_prob, last_state = max((V[len(obs)-1][state], state) for state in states)

# Reconstruct the path
best_path = []
while last_state:
    best_path.append(last_state)
    last_state = path[last_state]
best_path.reverse()