Understanding Python Code
subhabangalore at gmail.com
subhabangalore at gmail.com
Wed Jun 18 12:36:32 EDT 2014
Dear Group,
I have a Python code taken from Wikipedia.("http://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm")
The code is pasted below.
>>> states = ('Healthy', 'Fever')
>>> end_state = 'E'
>>> observations = ('normal', 'cold', 'dizzy')
>>> start_probability = {'Healthy': 0.6, 'Fever': 0.4}
>>> transition_probability = {
'Healthy' : {'Healthy': 0.69, 'Fever': 0.3, 'E': 0.01},
'Fever' : {'Healthy': 0.4, 'Fever': 0.59, 'E': 0.01},
}
>>> emission_probability = {
'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
>>> def fwd_bkw(x, states, a_0, a, e, end_st):
L = len(x)
print "$$1",L
fwd = []
f_prev = {}
# forward part of the algorithm
for i, x_i in enumerate(x):
print "$$2",i,x_i
f_curr = {}
for st in states:
if i == 0:
# base case for the forward part
prev_f_sum = a_0[st]
print "$$3",prev_f_sum
else:
prev_f_sum = sum(f_prev[k]*a[k][st] for k in states) ##?
print "$$4",prev_f_sum
f_curr[st] = e[st][x_i] * prev_f_sum
print "$$5",f_curr[st]
fwd.append(f_curr)
f_prev = f_curr
print "$$6",f_prev
p_fwd = sum(f_curr[k]*a[k][end_st] for k in states)
print "FORWARD IS:",p_fwd
bkw = []
b_prev = {}
# backward part of the algorithm
for i, x_i_plus in enumerate(reversed(x[1:]+(None,))):
print "##1:",i,x_i_plus
b_curr = {}
for st in states:
if i == 0:
# base case for backward part
b_curr[st] = a[st][end_st]
print "##2:",b_curr[st]
else:
b_curr[st] = sum(a[st][l]*e[l][x_i_plus]*b_prev[l] for l in states) ##?
print "##3:",b_curr
bkw.insert(0,b_curr)
b_prev = b_curr
print "##4:",b_prev
p_bkw = sum(a_0[l] * e[l][x[0]] * b_curr[l] for l in states)
print "BACKWARD IS:",p_bkw
# merging the two parts
posterior = []
for i in range(L):
posterior.append({st: fwd[i][st]*bkw[i][st]/p_fwd for st in states})
assert p_fwd == p_bkw
return fwd, bkw, posterior
>>> def example():
return fwd_bkw(observations,
states,
start_probability,
transition_probability,
emission_probability,
end_state)
>>> for line in example():
print(' '.join(map(str, line)))
$$1 3
$$2 0 normal
$$3 0.6
$$5 0.3
$$3 0.4
$$5 0.04
$$6 {'Healthy': 0.3, 'Fever': 0.04000000000000001}
$$2 1 cold
$$4 0.223
$$5 0.0892
$$4 0.1136
$$5 0.03408
$$6 {'Healthy': 0.0892, 'Fever': 0.03408}
$$2 2 dizzy
$$4 0.07518
$$5 0.007518
$$4 0.0468672
$$5 0.02812032
$$6 {'Healthy': 0.007518, 'Fever': 0.028120319999999997}
FORWARD IS: 0.0003563832
##1: 0 None
##2: 0.01
##2: 0.01
##4: {'Healthy': 0.01, 'Fever': 0.01}
##1: 1 dizzy
##3: {'Healthy': 0.00249}
##3: {'Healthy': 0.00249, 'Fever': 0.00394}
##4: {'Healthy': 0.00249, 'Fever': 0.00394}
##1: 2 cold
##3: {'Healthy': 0.0010418399999999998}
##3: {'Healthy': 0.0010418399999999998, 'Fever': 0.00109578}
##4: {'Healthy': 0.0010418399999999998, 'Fever': 0.00109578}
BACKWARD IS: 0.0003563832
{'Healthy': 0.3, 'Fever': 0.04000000000000001} {'Healthy': 0.0892, 'Fever': 0.03408} {'Healthy': 0.007518, 'Fever': 0.028120319999999997}
{'Healthy': 0.0010418399999999998, 'Fever': 0.00109578} {'Healthy': 0.00249, 'Fever': 0.00394} {'Healthy': 0.01, 'Fever': 0.01}
{'Healthy': 0.8770110375573259, 'Fever': 0.1229889624426741} {'Healthy': 0.623228030950954, 'Fever': 0.3767719690490461} {'Healthy': 0.2109527048413057, 'Fever': 0.7890472951586943}
>>>
As I was trying to understand it. [It is a Machine Learning topic, which has no connection with the question here,
I am just trying to put the Python confusion.]
Generally I understood the code and to understand it in a better way,
I had put one print after the places I am having questions.
But two question still remains. I have put the places of question with "##?" mark.
The questions are,
i) prev_f_sum = sum(f_prev[k]*a[k][st] for k in states)
here f_prev is called,
f_prev is assigned to f_curr ["f_prev = f_curr"]
f_curr[st] is again being calculated as, ["f_curr[st] = e[st][x_i] * prev_f_sum"] which again calls "prev_f_sum"
I am slightly confused which one would be first calculated and how to proceed next?
ii) The similar aspect happens again,
b_curr[st] = sum(a[st][l]*e[l][x_i_plus]*b_prev[l] for l in states)
here, b_prev is used, which is defined in
b_prev = b_curr
If any one of the esteemed members may kindly guide me to understand
this code.
Apology for any indentation error, etc.
Thanking in Advance,
Regards,
Subhabrata Banerjee.
More information about the Python-list
mailing list