Description
Part 1: International Morse Code (55 pts)
Given a model of a system’s transition and emission probabilities and a series of evidence observations, what is the most likely sequence of states that generated the observed evidence?
International Morse Code represents each letter by a unique sequence of dots and dashes. In theory, the duration of a dash is three times the duration of a dot. Each dot or dash is followed by a short silence, equal to the dot duration. The letters of a word are separated by a space equal to three dots (one dash), and the words are separated by a space equal to seven dots. The dot duration is the basic unit of time measurement in code transmission.
The chart of International Morse Code looks like:
<img src=”morse_code.png”, width=”600″, height=”500″>
1a) The HMM for letter A is shown below: <img src=”A.png”, width=”500″, height=”400″>
There are 3 states as shown on the graph. And the transition, emission, and prior probabilities are below.
A_states = ('A1', 'A2', 'A3','Aend')
A_transition_probs = {
'A1': {'A1': 0, 'A2': 1, 'A3':0,'Aend':0},
'A2': {'A1': 0, 'A2': 0, 'A3':1,'Aend':0},
'A3': {'A1': 0, 'A2': 0, 'A3':0.667,'Aend':0.333},
'Aend': {'A1': 0, 'A2': 0, 'A3':0,'Aend':1}
}
A_emission_probs = {
'A1' : [0,1],
'A2' : [1,0],
'A3' : [0,1],
'Aend' : [0,0]
}
A_prior = {'A1': 1, 'A2': 0,'A3':0,'Aend':0}
B_states = ('B1', 'B2', 'B3','B4','B5','B6','B7','Bend')
C_states = ('C1', 'C2', 'C3','C4','C5','C6','C7','Cend')
Follow A’s example, please provide the transition, prior and emission probabilities for letters B and C. (accurate to 3 decimal places)
def part_1_a(): #(10 pts)
# TODO: Fill below!
B_transition_probs = {
}
B_emission_probs = {
}
B_prior = {
}
C_transition_probs = {
}
C_emission_probs = {
}
C_prior = {
}
return B_prior, B_transition_probs, B_emission_probs, C_prior, C_transition_probs, C_emission_probs
1b) Now the evidence sequence [1,1,0,1,0,1,0,1] is received. Implement the Viterbi algorithm to get the most likely state sequences for A, B and C and output the probabilities associated with the most likely state sequences.
Hint: In order to reconstruct your most-likely path after running Viterbi, you’ll need to keep track of a back-pointer at each state, which directs you that state’s most-likely predecessor.
In the autograder, we will also test your code against other evidence_vectors.
import numpy as np
def viterbi(evidence_vector, prior, states, transition_probs, emission_probs):
sequence=[]
probability=0
"""
45 points
Input:
evidence_vector: A list of integers (0,1)
prior: A dictionary corresponding to the prior distribution over states
states: A list of all possible system states
transition_probs: A dictionary mapping states onto dictionaries mapping states onto probabilities
emission_probs: A dictionary mapping states onto their emission probabilities
Output:
sequence: A list of states that is the most likely sequence of states explaining the evidence, like
['A1', 'A2', 'A3', 'A3', 'A3']
probability: float
"""
return sequence, probability
evidence_sequence = [1,1,0,1,0,1,0,1]
B_prior, B_transition_probs, B_emission_probs, C_prior, C_transition_probs, C_emission_probs=part_1_a()
A_state_sequence,probability = viterbi(evidence_sequence, A_prior, A_states, A_transition_probs, A_emission_probs)
B_state_sequence,probability = viterbi(evidence_sequence, B_prior, B_states, B_transition_probs, B_emission_probs)
C_state_sequence,probability = viterbi(evidence_sequence, C_prior, C_states, C_transition_probs, C_emission_probs)
Part 2: Let’s add some noise!!! (45 pts)
Now the noise come in. For the emission probability, instead of having a 0/1 pair, we will have the 0.2/0.8 pair. And for transition probability, for those having 0/1 as self-transitioning/transitioning-to-another-state pair, we change it to 0.2/0.8. All other probabilities remain the same. Letter A is shown here as an example.
<img src=”noise.png”, width=”700″, height=”500″>
And the changed transition, emission probabilities for A, B and C along with the HMM for space_between_two_words and space_between_two_letters are given below.
A_transition_probs_noise = {
'A1': {'A1': 0.2, 'A2': 0.8, 'A3':0,'Aend':0},
'A2': {'A1': 0, 'A2': 0.2, 'A3':0.8,'Aend':0},
'A3': {'A1': 0, 'A2': 0, 'A3':0.667,'Aend':0.333},
'Aend': {'A1': 0, 'A2': 0, 'A3':0,'Aend':1}
}
A_emission_probs_noise = {
'A1' : [0.2,0.8],
'A2' : [0.8,0.2],
'A3' : [0.2,0.8],
'Aend' : [0,0]
}
B_transition_probs_noise = {
'B1': {'B1': 0.667, 'B2': 0.333, 'B3':0,'B4': 0, 'B5': 0, 'B6':0,'B7': 0,'Bend':0},
'B2': {'B1': 0, 'B2': 0.2, 'B3':0.8,'B4': 0, 'B5': 0, 'B6':0,'B7': 0,'Bend':0},
'B3': {'B1': 0, 'B2': 0, 'B3':0.2,'B4': 0.8, 'B5': 0, 'B6':0,'B7': 0,'Bend':0},
'B4': {'B1': 0, 'B2': 0, 'B3':0,'B4': 0.2, 'B5': 0.8, 'B6':0,'B7': 0,'Bend':0},
'B5': {'B1': 0, 'B2': 0, 'B3':0,'B4': 0, 'B5': 0.2, 'B6':0.8,'B7': 0,'Bend':0},
'B6': {'B1': 0, 'B2': 0, 'B3':0,'B4': 0, 'B5': 0, 'B6':0.2,'B7': 0.8,'Bend':0},
'B7': {'B1': 0, 'B2': 0, 'B3':0,'B4': 0, 'B5': 0, 'B6':0,'B7': 0.2,'Bend':0.8},
'Bend': {'B1': 0, 'B2': 0, 'B3':0,'B4': 0, 'B5': 0, 'B6':0,'B7': 0,'Bend':1}
}
B_emission_probs_noise = {
'B1' : [0.2,0.8],
'B3' : [0.2,0.8],
'B5' : [0.2,0.8],
'B7' : [0.2,0.8],
'B2' : [0.8,0.2],
'B4' : [0.8,0.2],
'B6' : [0.8,0.2],
'Bend': [0,0]
}
C_transition_probs_noise = {
'C1': {'C1': 0.667, 'C2': 0.333, 'C3':0,'C4': 0, 'C5': 0, 'C6':0,'C7': 0,'Cend':0},
'C2': {'C1': 0, 'C2': 0.2, 'C3':0.8,'C4': 0, 'C5': 0, 'C6':0,'C7': 0,'Cend':0},
'C3': {'C1': 0, 'C2': 0, 'C3':0.2,'C4': 0.8, 'C5': 0, 'C6':0,'C7': 0,'Cend':0},
'C4': {'C1': 0, 'C2': 0, 'C3':0,'C4': 0.2, 'C5': 0.8, 'C6':0,'C7': 0,'Cend':0},
'C5': {'C1': 0, 'C2': 0, 'C3':0,'C4': 0, 'C5': 0.667, 'C6':0.333,'C7': 0,'Cend':0},
'C6': {'C1': 0, 'C2': 0, 'C3':0,'C4': 0, 'C5': 0, 'C6':0.2,'C7': 0.8,'Cend':0},
'C7': {'C1': 0, 'C2': 0, 'C3':0,'C4': 0, 'C5': 0, 'C6':0,'C7': 0.2,'Cend':0.8},
'Cend': {'C1': 0, 'C2': 0, 'C3':0,'C4': 0, 'C5': 0, 'C6':0,'C7': 0,'Cend':1}
}
C_emission_probs_noise = {
'C1' : [0.2,0.8],
'C3' : [0.2,0.8],
'C5' : [0.2,0.8],
'C7' : [0.2,0.8],
'C2' : [0.8,0.2],
'C4' : [0.8,0.2],
'C6' : [0.8,0.2],
'Cend': [0,0]
}
space_between_two_letters_states = ('L1','Lend')
space_between_two_words_states = ('W1','Wend')
space_between_two_letters_transition_probs = {
'L1': {'L1': 0.667,'Lend':0.333},
'Lend': {'L1': 0,'Lend':1}
}
space_between_two_letters_emission_probs = {
'L1' : [0.8,0.2],
'Lend': [0,0]
}
space_between_two_letters_prior = {
'L1': 1,
'Lend': 0
}
space_between_two_words_transition_probs = {
'W1': {'W1': 0.857,'Wend':0.143},
'Wend': {'W1': 0,'Wend':1}
}
space_between_two_words_emission_probs = {
'W1' : [0.8,0.2],
'Wend': [0,0]
}
space_between_two_words_prior = {
'W1': 1,
'Wend': 0
}
2a) Suppose evidence sequence [1,1,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,0,1,0,0,0,0,0,1,1,1] is received. Only A, B, C and the 2 types of spaces are involved. A sequence will start with a letter and end with a letter. The same letter may be repeated. The sequence can be made up of one or more words. And a word can be made up of one or more letters.
The beginning of the sequence can be any letter with equal probability. After each letter there is an end or a space. It can be an inner letter space or inner word space and equal probability for end, inner letter space and inner word space. A space can transition to any letter with equal probability. When it reaches the end state, it stays at the end state.
In our experiments above we assumed that each letter would be decoded in isolation. Each evidence string decoded to one letter. Now the evidence string can decode to a string of letters and spaces. The state sequence for “A” can end with Aend or can transition to L1 (space between two letters) or W1 (space between two words). Redefine the states, prior, transition and emission probabilities given above so that your Viterbi algorithm will be able to decode strings of letters. (With noise, accurate to 3 decimal places)
def part_2_a():
#TO DO: fill in below
states=(
)
prior_probs = {
}
transition_probs={
}
emission_probs={
}
return states, prior_probs, transition_probs, emission_probs
Instead of checking all probabilities, we will check only five of them. Finish the quick_check below
def quick_check():
#TO DO: fill the probabilities, 5 points
#prior probability for C1
prior_C1=
#transition probability from A3 to L1
A3_L1=
#transition probability from B4 to B5
B4_B5=
#transition probability from W1 to B1
W1_B1=
#transition probability from L1 to L1
L1_L1=
return prior_C1,A3_L1,B4_B5,W1_B1,L1_L1
2b) Use your output in 2a and evidence_sequence to generate the most probable decoded letter sequence from the evidence sequence and its probability. Your code will also be tested against other evidence_vectors.
states, prior_probs, transition_probs, emission_probs=part_2_a()
def part_2_b(evidence_vector, prior, states, transition_probs, emission_probs):
sequence=''
probability=0
'''
TO DO: fill this (40 points)
Output:
sequence: a string of most likely decoded letter sequence (like 'A B A CAC', using uppercase)
probability: float
'''
return sequence, probability
evidence_sequence = [1,1,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,1,1,0,1,1,1]
evidence_sequence=[1,1,0,0,1,0,1,0,1]
print part_2_b(evidence_sequence,prior_probs,states,transition_probs,emission_probs)
Extra Credit
Here is a piece of code that listens for a first left mouse click and starts producing a 1 or 0 every 100 milliseconds depending on whether or not the left mouse is depressed. When it senses a “return” key, the code finishes writing the binary sequence and you can close the window. The time of pressing and depressing is rounded to the nearest 100 milliseconds.
from Tkinter import *
import sys
import time
message=''
key_start=-1
space_start=-1
def press(event):
global message,key_start,space_start
times=0
if space_start>0:
times=int(round((time.time()-space_start)*10))
key_start=time.time()
for i in range(times):
message+='0,'
msg.insert(END,'0,')
def depress(event):
global message,key_start,space_start
times=0
if key_start>0:
times=int(round((time.time()-key_start)*10))
space_start=time.time()
for i in range(times):
message+='1,'
msg.insert(END,'1,')
def end(event):
global message
print message
root=Tk()
msg=Text(root)
msg.pack()
msg.config(font=('times',20))
button=Button(root,text="press me")
button.pack()
button.bind('<Button-1>',press)
button.bind('<ButtonRelease-1>',depress)
root.bind('<Return>',end)
mainloop()
Use the program (and your skill as a Morse code keyer) to generate a few strings of 0s and 1s that represent words in Morse code. Please note the temporal variability of human input. For example, SOS’s morse code is … — … , but the user’s input might be 11100110011100011111100111111100111111001101110011.
Finish creating HMMs for the rest of the letters of the Morse alphabet. Show that your Viterbi decoder for Morse can successfully decode the examples you made above (or at least get close). You may have to tune the transition probabilities to get reliable results. Include your binary strings and your decodings of them. Below are two webpages that you might find useful. http://thelivingpearl.com/2013/01/08/morse-code-and-dictionaries-in-python-with-sound/ http://www.prooffreader.com/2014/09/how-often-does-given-letter-follow.html
Besides the decoder, you also need to submit a string (only alphabets and spaces) and its morse code equivalent as performed by a human (in 0s and 1s). Your code will be tested against our string and strings submitted by other students. The decoder that gets the best results wins the competition. We will have no noise in the system. Temporal variability means that dots can be different lengths “1” vs. “11” vs “111” and dashes can be different lengths “11111” vs. “1111111” vs. “1111111” but the system still decodes properly. For our test sentences, we will make sure that the dots and dashes have some variability in them but still maintain that a dot is approximately 1/3 the size of the dash.
def decoder(evidence_vector):
#you can define your prior, emission, transition probabilities in your own format
return sequence
def extra_credit():
#string: like "A BC"
#morse_code_equivalent: like [1,0,1]
return string, morse_code_equivalent