Understanding a Python Code

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.]

The code generally I understood 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.