Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #73367 > unrolled thread

Understanding Python Code

Back to article view | Back to comp.lang.python

Contents

  Understanding Python Code subhabangalore@gmail.com - 2014-06-18 09:36 -0700
    Re: Understanding Python Code Ian Kelly <ian.g.kelly@gmail.com> - 2014-06-18 13:15 -0600
      Re: Understanding Python Code subhabangalore@gmail.com - 2014-06-18 22:50 -0700
        Re: Understanding Python Code Ian Kelly <ian.g.kelly@gmail.com> - 2014-06-19 01:00 -0600
          Re: Understanding Python Code subhabangalore@gmail.com - 2014-06-19 02:48 -0700
            Re: Understanding Python Code Ian Kelly <ian.g.kelly@gmail.com> - 2014-06-19 08:09 -0600
              Re: Understanding Python Code subhabangalore@gmail.com - 2014-06-19 07:27 -0700
                Re: Understanding Python Code subhabangalore@gmail.com - 2014-06-19 11:44 -0700
                  Re: Understanding Python Code Ian Kelly <ian.g.kelly@gmail.com> - 2014-06-19 13:07 -0600
                    Understanding Python Code[Forward_Backward_Wikipedia] subhabangalore@gmail.com - 2014-06-21 15:05 -0700

#73367 — Understanding 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.]

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. 

[toc] | [next] | [standalone]

#73373

On Wed, Jun 18, 2014 at 10:36 AM,  <subhabangalore@gmail.com> wrote:
> 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?

These things that you describe as "calls" are not calls.  f_prev and
f_curr are data structures (in this case dicts), not functions.
Accessing "f_prev[k]" does not call f_prev or in any way cause
f_prev[k] to be computed; it just looks up what value is recorded in
the f_prev dict for the key k.

Python is an imperative language, not declarative.  If you want to
know what order these things are calculated in, just follow the
program flow.

[toc] | [prev] | [next] | [standalone]

#73391

On Thursday, June 19, 2014 12:45:49 AM UTC+5:30, Ian wrote:
> 
> 
> > 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?
> 
> 
> 
> These things that you describe as "calls" are not calls.  f_prev and
> 
> f_curr are data structures (in this case dicts), not functions.
> 
> Accessing "f_prev[k]" does not call f_prev or in any way cause
> 
> f_prev[k] to be computed; it just looks up what value is recorded in
> 
> the f_prev dict for the key k.
> 
> 
> 
> Python is an imperative language, not declarative.  If you want to
> 
> know what order these things are calculated in, just follow the
> 
> program flow.

Thank you for the reply. But as I checked it again I found,
f_prev[k] is giving values of f_curr[st] = e[st][x_i] * prev_f_sum
which is calculated later and again uses prev_f_sum.

Regards,
Subhabrata Banerjee. 

[toc] | [prev] | [next] | [standalone]

#73395

On Wed, Jun 18, 2014 at 11:50 PM,  <subhabangalore@gmail.com> wrote:
> Thank you for the reply. But as I checked it again I found,
> f_prev[k] is giving values of f_curr[st] = e[st][x_i] * prev_f_sum
> which is calculated later and again uses prev_f_sum.

f_prev is the f_curr that was calculated on the previous iteration of
the loop.  At each iteration after the first, the script calculates
f_curr based on the value of f_prev, that is, the old value of f_curr.
Then it reassigns the newly computed f_curr to f_prev, making it now
the previous, and on the next iteration it creates a new dict to store
the next f_curr.  Does that make sense?

[toc] | [prev] | [next] | [standalone]

#73410

On Thursday, June 19, 2014 12:30:12 PM UTC+5:30, Ian wrote:
> On Wed, Jun 18, 2014 at 11:50 PM,   wrote:
> 
> > Thank you for the reply. But as I checked it again I found,
> 
> > f_prev[k] is giving values of f_curr[st] = e[st][x_i] * prev_f_sum
> 
> > which is calculated later and again uses prev_f_sum.
> 
> 
> 
> f_prev is the f_curr that was calculated on the previous iteration of
> 
> the loop.  At each iteration after the first, the script calculates
> 
> f_curr based on the value of f_prev, that is, the old value of f_curr.
> 
> Then it reassigns the newly computed f_curr to f_prev, making it now
> 
> the previous, and on the next iteration it creates a new dict to store
> 
> the next f_curr.  Does that make sense?

Dear Group,

The logic seems going fine. I am just trying to cross check things once more,
so trying to generate the values and see on myself. 

I am trying to see this line,
prev_f_sum = sum(f_prev[k]*a[k][st] for k in states)

a[k][st], and f_prev[k] I could take out and understood.
Now as it is doing sum() so it must be over a list,
I am trying to understand the number of entities in the list, thinking whether to put len(), and see for which entities it is doing the sum.

Experimenting, if any one feels may kindly send any idea.

Regards,
Subhabrata Banerjee. 

[toc] | [prev] | [next] | [standalone]

#73433

On Thu, Jun 19, 2014 at 3:48 AM,  <subhabangalore@gmail.com> wrote:
> I am trying to see this line,
> prev_f_sum = sum(f_prev[k]*a[k][st] for k in states)
>
> a[k][st], and f_prev[k] I could take out and understood.
> Now as it is doing sum() so it must be over a list,
> I am trying to understand the number of entities in the list, thinking whether to put len(), and see for which entities it is doing the sum.

It's summing a generator expression, not a list.  If it helps to
understand it, you could rewrite that line like this:

values_to_be_summed = []
for k in states:
    values_to_be_summed.append(f_prev[k]*a[k][st])
prev_f_sum = sum(values_to_be_summed)

So the number of entities in the list is len(states).

[toc] | [prev] | [next] | [standalone]

#73436

On Thursday, June 19, 2014 7:39:42 PM UTC+5:30, Ian wrote:
> On Thu, Jun 19, 2014 at 3:48 AM, wrote:
> 
> > I am trying to see this line,
> 
> > prev_f_sum = sum(f_prev[k]*a[k][st] for k in states)
> 
> >
> 
> > a[k][st], and f_prev[k] I could take out and understood.
> 
> > Now as it is doing sum() so it must be over a list,
> 
> > I am trying to understand the number of entities in the list, thinking whether to put len(), and see for which entities it is doing the sum.
> 
> 
> 
> It's summing a generator expression, not a list.  If it helps to
> 
> understand it, you could rewrite that line like this:
> 
> 
> 
> values_to_be_summed = []
> 
> for k in states:
> 
>     values_to_be_summed.append(f_prev[k]*a[k][st])
> 
> prev_f_sum = sum(values_to_be_summed)
> 
> 
> 
> So the number of entities in the list is len(states).

Dear Group,

Thank you for your kind answer. As I put from the error I discovered it. Please see my experiment almost near to your answer. I am trying one or two questions like, why it is appending only two values at a time. If you want to assist you may kindly help me assist me.
Regards,
Subhabrata Banerjee.
*******************************************************************************
MY EXPERIMENT
*******************************************************************************
else:
		    for k in states:
			    print "YYY1",f_prev[k]
			    print "YYY2",a[k][st]
			    prev_f_sum1=f_prev[k]*a[k][st]
			    print "YYY3",prev_f_sum1
			    prev_f_sum2 = sum(f_prev[k]*a[k][st] for k in states)
			    print "YYY4",prev_f_sum2
*******************************************************************************

[toc] | [prev] | [next] | [standalone]

#73440

On Thursday, June 19, 2014 7:57:38 PM UTC+5:30, wrote:
> On Thursday, June 19, 2014 7:39:42 PM UTC+5:30, Ian wrote:
> 
> > On Thu, Jun 19, 2014 at 3:48 AM, wrote:
> 
> > 
> 
> > > I am trying to see this line,
> 
> > 
> 
> > > prev_f_sum = sum(f_prev[k]*a[k][st] for k in states)
> 
> > 
> 
> > >
> 
> > 
> 
> > > a[k][st], and f_prev[k] I could take out and understood.
> 
> > 
> 
> > > Now as it is doing sum() so it must be over a list,
> 
> > 
> 
> > > I am trying to understand the number of entities in the list, thinking whether to put len(), and see for which entities it is doing the sum.
> 
> > 
> 
> > 
> 
> > 
> 
> > It's summing a generator expression, not a list.  If it helps to
> 
> > 
> 
> > understand it, you could rewrite that line like this:
> 
> > 
> 
> > 
> 
> > 
> 
> > values_to_be_summed = []
> 
> > 
> 
> > for k in states:
> 
> > 
> 
> >     values_to_be_summed.append(f_prev[k]*a[k][st])
> 
> > 
> 
> > prev_f_sum = sum(values_to_be_summed)
> 
> > 
> 
> > 
> 
> > 
> 
> > So the number of entities in the list is len(states).
> 
> 
> 
> Dear Group,
> 
> 
> 
> Thank you for your kind answer. As I put from the error I discovered it. Please see my experiment almost near to your answer. I am trying one or two questions like, why it is appending only two values at a time. If you want to assist you may kindly help me assist me.
> 
> Regards,
> 
> Subhabrata Banerjee.
> 
> *******************************************************************************
> 
> MY EXPERIMENT
> 
> *******************************************************************************
> 
> else:
> 
> 		    for k in states:
> 
> 			    print "YYY1",f_prev[k]
> 
> 			    print "YYY2",a[k][st]
> 
> 			    prev_f_sum1=f_prev[k]*a[k][st]
> 
> 			    print "YYY3",prev_f_sum1
> 
> 			    prev_f_sum2 = sum(f_prev[k]*a[k][st] for k in states)
> 
> 			    print "YYY4",prev_f_sum2
> 
> *******************************************************************************
Dear Group,
Generally most of the issues are tackled here, but as I am trying to cross check my understanding I found another question,

f_curr[st] = e[st][x_i] * prev_f_sum

Here, if I give one print command and see the results, 
print "$$2",f_curr

It is showing an iterative update like,
$$2 {'Healthy': 0.3},
$$2 {'Healthy': 0.3, 'Fever': 0.04000000000000001}

I was trying to ask how the size is being updated, from 1 to 2 back to 1 again 2... is it for any loop then which one, I tried to change but not being able 
to if any one of the esteemed members may kindly help me.

Regards,
Subhabrata Banerjee.

[toc] | [prev] | [next] | [standalone]

#73441

On Thu, Jun 19, 2014 at 12:44 PM,  <subhabangalore@gmail.com> wrote:
> Dear Group,
> Generally most of the issues are tackled here, but as I am trying to cross check my understanding I found another question,
>
> f_curr[st] = e[st][x_i] * prev_f_sum
>
> Here, if I give one print command and see the results,
> print "$$2",f_curr
>
> It is showing an iterative update like,
> $$2 {'Healthy': 0.3},
> $$2 {'Healthy': 0.3, 'Fever': 0.04000000000000001}
>
> I was trying to ask how the size is being updated, from 1 to 2 back to 1 again 2... is it for any loop then which one, I tried to change but not being able
> to if any one of the esteemed members may kindly help me.

That statement is inside the for loop that builds the f_curr dict. One
state gets calculated on each iteration. The first time it prints, one
state has been added. The second time it prints, two states have been
added. You only have two states, so at that point the loop is done.
The next time it prints, it's on the next iteration of the outer (i,
x_i) loop and it's building a new f_curr dict. So then you see it
adding one state and then the second state to the new dict. And so on
and so forth until the outer loop completes.

[toc] | [prev] | [next] | [standalone]

#73485 — Understanding Python Code[Forward_Backward_Wikipedia]

On Friday, June 20, 2014 12:37:01 AM UTC+5:30, Ian wrote:
> On Thu, Jun 19, 2014 at 12:44 PM,   wrote:
> 
> > Dear Group,
> 
> > Generally most of the issues are tackled here, but as I am trying to cross check my understanding I found another question,
> 
> >
> 
> > f_curr[st] = e[st][x_i] * prev_f_sum
> 
> >
> 
> > Here, if I give one print command and see the results,
> 
> > print "$$2",f_curr
> 
> >
> 
> > It is showing an iterative update like,
> 
> > $$2 {'Healthy': 0.3},
> 
> > $$2 {'Healthy': 0.3, 'Fever': 0.04000000000000001}
> 
> >
> 
> > I was trying to ask how the size is being updated, from 1 to 2 back to 1 again 2... is it for any loop then which one, I tried to change but not being able
> 
> > to if any one of the esteemed members may kindly help me.
> 
> 
> 
> That statement is inside the for loop that builds the f_curr dict. One
> 
> state gets calculated on each iteration. The first time it prints, one
> 
> state has been added. The second time it prints, two states have been
> 
> added. You only have two states, so at that point the loop is done.
> 
> The next time it prints, it's on the next iteration of the outer (i,
> 
> x_i) loop and it's building a new f_curr dict. So then you see it
> 
> adding one state and then the second state to the new dict. And so on
> 
> and so forth until the outer loop completes.

Dear Group,

Thank you for the kind help. I could solve other portions of the code easily.
As this algorithm is an important algorithm so is its Wikipedia note, so I changed subject line bit, in case future users try to solve any questions, they may get the helps.
Thank you again especially to Ian. 

Regards,
Subhabrata Banerjee.
S

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web