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.
--
https://mail.python.org/mailman/listinfo/python-list
