Module viterbi_search

Takes a list of strings, Stringseq, each element a word according to the HMM defined by A,B, states, and s0. Returns path, a list of states of length len(Stringseq)+1, representing the highest prob HMM path that accepts Stringseq, as well as the two tables built in the Viterbi computation. Note: implements the pseudocode of J&M, Figure 7.09.

trellis is the table the Viterbi algorithm fills in. Therefore, trellis will be an array of length T+1 (length of input + t=0) Each element will be a dictionary with states as keys. trellis[t][s] is the viterbi score of state s at time t [a log prob]

back (for "backtrace") will be an array with the same dimensions:

     back[t][s]

is the best state to have come FROM to get to s at t.

Parameters:

• Stringseq - a list of strings representin the sequence input observations
• A - Transition prob table of HMM
• B - Observation prob table of HMM
• states - A list of states for HMM
• s0 - Start state of HMM

Returns: a 4-tuple of trellis (the Viterbi table), back (the backtrace table), the best probability path through the HMM (list), and nice_path_string (a pretty string representation of the best path, suitable for printing).

Turn dictionaries representing bigrams probs and pronunciation models into transition_dict, an HMM transition function such that:

  transition_dict[(phone_from,word_from)][(phone_to,word_to)] = prob

This dictionary represents the kind of global phone to phone transition probs shown in J&M, Figure 7.08, including cross-word transitions.

This transition probability across words is estimated as:

  Pr(end | word_from,phone_from) *
  Pr(phone_to | start, word_to) *
  Pr(word_to | word_from)

or equivalently:

  pron_prob_dict[word_from][phone_from][end] *
  pron_prob_dict[word_to][start][phone_to] *
  bigram_prob_dict[word_from][word_to]

Thus the resulting HMM transition table has no start word and end word states.

Parameters:

• bigram_prob_dict - A dictionary of dictionaries representing bigram probs.
• pron_prob_dict - A dictionary of dictionaries representing with word keys representing bigram pronunication probs.
• states - the list of states for the current HMM.

Returns: dictionary of dictionaries

stringseq may be a list. Indicates phone list. Add '#'.

Precision specifies the precision for floats. Log probs are converted back to probs, meaning high precisions may be needed to get non-zero output. A precision level of 9 is required to reproduce the table in J&M, Fig. 7.10

A1

Value:

{'H': {'H': -1.0, 'T': -1.0, 's0': -inf}, 'T': {'H': -1.0, 'T': -1.0, 's0': -inf}, 's0': {'H': -1.0, 'T': -1.0, 's0': -inf}}

B1

Value:

{'h': {'H': 0.0, 'T': -inf, 's0': -1.0}, 't': {'H': -inf, 'T': 0.0, 's0': -1.0}}

B2

Value:

{'aa': {('aa', 'I'): 0.0, ('aa', 'on'): 0.0, ('ax', 'the'): -inf, ('ay', 'I'): -inf, ('d', 'need'): -inf, ('dh', 'the'): -inf, ('end', 'I'): -inf, ('end', 'need'): -inf, ...

A2

Value:

{('aa', 'I'): {('aa', 'I'): -inf, ('aa', 'on'): -14.3769797176, ('ax', 'the'): -inf, ('ay', 'I'): -inf, ('d', 'need'): -inf, ('dh', 'the'): -12.5600097067, ('end', 'I'): 0.0, ('end', 'need'): -inf, ...

states2

Value:

[('d', 'need'), ('iy', 'need'), ('n', 'need'), ('ax', 'the'), ('iy', 'the'), ('n', 'the'), ('dh', 'the'), ('n', 'on'), ...

A3

Value:

{'COLD': {'COLD': -0.736965594166, 'HOT': -1.32192809489, 'start0': -inf}, 'HOT': {'COLD': -1.73696559417, 'HOT': -0.51457317283, 'start0': -inf}, 'start0': {'COLD': -2.32192809489, 'HOT': -0.321928094887, ...

B3

Value:

{'1': {'COLD': -1.0, 'HOT': -2.32192809489, 'start0': -inf}, '2': {'COLD': -1.32192809489, 'HOT': -1.32192809489, 'start0': -inf}, '3': {'COLD': -3.32192809489, 'HOT': -1.32192809489, 'start0': -inf}}

phonedic

Value:

{('aa', 'I'): -inf, ('aa', 'on'): -inf, ('ax', 'the'): 0.0, ('ay', 'I'): -inf, ('d', 'need'): -inf, ('dh', 'the'): -inf, ('end', 'I'): -inf, ('end', 'need'): -inf, ...