Writing a Machine Learning Function

HardPython

Problem

St. Jude Children's Research Hospital genomic analysis pipelines can model an observed sequence as emissions from hidden biological states. Implement the Viterbi algorithm to return the most likely sequence of hidden state IDs for a Hidden Markov Model.

Formal Specification

Implement viterbi_decode(start_probs, transition_probs, emission_probs, observations).

start_probs[i] is the probability that state i starts the sequence.
transition_probs[i][j] is the probability of moving from state i to state j.
emission_probs[i][k] is the probability that state i emits observation k.
observations contains integer observation IDs.

Return a list of state IDs, one per observation, with maximum total probability. If multiple paths have the same probability, return the path selected by choosing the smallest predecessor state ID at each tie.

Use log probabilities internally. A probability of 0 represents an impossible transition or emission and must not cause a math-domain error.

Constraints

1 <= len(start_probs) <= 200
len(transition_probs) == len(emission_probs) == len(start_probs)
transition_probs is a square state-by-state matrix
0 <= len(observations) <= 2,000
0.0 <= every probability <= 1.0
Each observation ID is a valid index in every emission probability row
At least one valid state path exists for every non-empty observation sequence

Function Signature

def viterbi_decode(start_probs, transition_probs, emission_probs, observations):