Viterbi Algorithm

The Viterbi algorithm was introduced by Andrew Viterbi in 1967. Andrew Viterbi, an electrical engineer and co-founder of Qualcomm, developed the algorithm as a method for decoding convolutional codes in digital communication systems. His work was groundbreaking because it provided an efficient way to decode noisy signals in communication channels, significantly improving the reliability of data transmission.

1. Input Observations: Start with the sequence of observed data (e.g., note durations).

2. Initialize Probabilities: Set up initial probabilities and paths for the first observation.

3. Iterate Over Observations: For each observation, calculate probabilities for all possible hidden states.

4. Calculate Probabilities for Each State: Use transition and emission probabilities to compute the likelihood of reaching each state.

5. Track Most Likely Path: Store the path with the highest probability leading to each state.

6. Backtrack to Find Final Path: After processing all observations, backtrack through the stored paths to reconstruct the most likely sequence of hidden states.

7. Output Predicted Sequence: Return the predicted sequence of hidden states.

Pseudo Code:

function Viterbi(observations, states, transitionMatrix, emissionMatrix, initialProbabilities):
    # Step 1: Initialize variables
    T = length(observations)  # Length of the observation sequence
    V = {}                   # Probabilities table (stores max probabilities)
    path = {}                # Path table (stores most likely paths)

    # Initialize probabilities and paths for the first observation
    for state in states:
        V[state] = initialProbabilities[state] * emissionMatrix[state][observations[0]]
        path[state] = [state]

    # Step 2: Iterate over observations
    for t from 1 to T - 1:
        newPaths = {}  # Temporary storage for updated paths
        for currState in states:
            maxProb = -Infinity
            bestPrevState = None

            # Find the most likely previous state leading to currState
            for prevState in states:
                prob = V[prevState] * transitionMatrix[prevState][currState] * emissionMatrix[currState][observations[t]]
                if prob > maxProb:
                    maxProb = prob
                    bestPrevState = prevState

            # Update probabilities and paths
            V[currState] = maxProb
            newPaths[currState] = path[bestPrevState] + [currState]

        # Update paths for the next iteration
        path = newPaths

    # Step 3: Backtrack to find the final path
    maxFinalProb = -Infinity
    finalState = None

    # Find the state with the highest probability at the final time step
    for state in states:
        if V[state] > maxFinalProb:
            maxFinalProb = V[state]
            finalState = state

    # Return the most likely sequence of hidden states
    return path[finalState]