Calculate the most probable state path using the Viterbi algorithm. This implements the Viterbi algorithm (see pgs 5557 in Durbin et al for a full explanation  this is where I took my implementation ideas from), to allow decoding of the state path, given a sequence of emissions. Arguments: o sequence  A Seq object with the emission sequence that we want to decode. o state_alphabet  The alphabet of the possible state sequences that can be generated. Definition at line 365 of file MarkovModel.py. 00365 : """Calculate the most probable state path using the Viterbi algorithm. This implements the Viterbi algorithm (see pgs 5557 in Durbin et al for a full explanation  this is where I took my implementation ideas from), to allow decoding of the state path, given a sequence of emissions. Arguments: o sequence  A Seq object with the emission sequence that we want to decode. o state_alphabet  The alphabet of the possible state sequences that can be generated. """ # calculate logarithms of the transition and emission probs log_trans = self._log_transform(self.transition_prob) log_emission = self._log_transform(self.emission_prob) viterbi_probs = {} pred_state_seq = {} state_letters = state_alphabet.letters #  initialization # # NOTE: My index numbers are one less than what is given in Durbin # et al, since we are indexing the sequence going from 0 to # (Length  1) not 1 to Length, like in Durbin et al. # # v_{0}(0) = 1 viterbi_probs[(state_letters[0], 1)] = 1 # v_{k}(0) = 0 for k > 0 for state_letter in state_letters[1:]: viterbi_probs[(state_letter, 1)] = 0 #  recursion # loop over the training squence (i = 1 .. L) for i in range(0, len(sequence)): # now loop over all of the letters in the state path for main_state in state_letters: # e_{l}(x_{i}) emission_part = log_emission[(main_state, sequence[i])] # loop over all possible states possible_state_probs = {} for cur_state in self.transitions_from(main_state): # a_{kl} trans_part = log_trans[(cur_state, main_state)] # v_{k}(i  1) viterbi_part = viterbi_probs[(cur_state, i  1)] cur_prob = viterbi_part + trans_part possible_state_probs[cur_state] = cur_prob # finally calculate the viterbi probability using the max max_prob = max(possible_state_probs.values()) viterbi_probs[(main_state, i)] = (emission_part + max_prob) # now get the most likely state for state in possible_state_probs.keys(): if possible_state_probs[state] == max_prob: pred_state_seq[(i  1, main_state)] = state break #  termination # calculate the probability of the state path # loop over all letters all_probs = {} for state in state_letters: # v_{k}(L) viterbi_part = viterbi_probs[(state, len(sequence)  1)] # a_{k0} transition_part = log_trans[(state, state_letters[0])] all_probs[state] = viterbi_part * transition_part state_path_prob = max(all_probs.values()) # find the last pointer we need to trace back from last_state = '' for state in all_probs.keys(): if all_probs[state] == state_path_prob: last_state = state assert last_state != '', "Didn't find the last state to trace from!" #  traceback traceback_seq = MutableSeq('', state_alphabet) loop_seq = range(0, len(sequence)) loop_seq.reverse() cur_state = last_state for i in loop_seq: traceback_seq.append(cur_state) cur_state = pred_state_seq[(i  1, cur_state)] # put the traceback sequence in the proper orientation traceback_seq.reverse() return traceback_seq.toseq(), state_path_prob def _log_transform(self, probability):
