Hello,

I like the OpenBayes toolbox and am using it in a project for my (starting) research involving Probabilistic-Logic Models. Keep up the good work!

In december I added augmented Bayesian nets and an EM-algorithm to the toolbox because I needed to test some ideas for an upcoming paper. So I was enthusiast to hear about a new EM-method added to the toolbox. However, I think there are some errors in the new EM-algorithm (in particular the DetermineLikelihood and the DetermineLikelihood2 functions).

I)The method DetermineLikelihood (the default one) has two theoretical faults in my opinion:
a) The method used takes only the parents in account when estimating a missing value while known children can have an influence too.
b) The node's own initial CPT has to be taken in account, which is not always the case in the current method.
I have included a longer and detailed explanation of these points below.

II)The method DetermineLikelihood2 seems correct after fixing two little errors:
a) The function SetObs resets the previous call of SetObs, so by first calling self.engine.SetObs(known) and later self.engine.SetObs(copy_states), you lose the known-information. Adding a statement copy_states.update(known) seems to fix this.
b) The variable 'like' is possibly 'nan'; more precisely when an impossible combination is given as observation. A check
if str(like) == 'nan':like=0
seems to fix this.

I hope my statements are correct and helped in developing the OpenBayes toolbox.

Kind regards,
Wannes Meert
DTAI-KULeuven

ps: If wanted, I can share my code, but it's not yet documented and your EM-method seems faster ;-)


-------
Longer explanation of why I think the default method contains errors follows now:

For example the network:
Vertices:
a (discrete, 2)
c (discrete, 2)
b (discrete, 2)

Edges:
0: a (discrete, 2) -> b (discrete, 2)
1: b (discrete, 2) -> c (discrete, 2)

print the initial parameters
a [ 0.2 0.80000001]
b [[ 0.5 0.5]
[ 0.5 0.5]]
c [[ 1. 0.]
[ 0. 1.]]

Suppose you have the data-item [{'a':0,'b':'?','c':0}]

Problem a)
Then the current EM-method will give you the following counts for node b:
counts_b [[ 0.5 0]
[ 0.5 0]]
It is, however, impossible to have a 0.5 count for P(b=1|a=0) because in this data-item we have c=0 and therefor b has to be 0. Node b and c are not independent so we have to take the value of c in account while estimating the missing value for b.

The method just uses P(b=1|a=0) to calculate the count for P(b=1|a=0) while it should calculate P(b=1,a=0|Data,InitVals)=P(b=1,a=0|a=0,c=0,InitVals). Ignoring the InitVals this gives P(b=1,a=0|a=0,c=0)=P(b=1|a=0,c=0)*P(a=0|a=0,c=0) = P(b=1|a=0,c=0) = P(c=0|b=1,a=0)*P(b=1|a=0)/P(c=0|a=0) and since b d-separates a and c and P(c=0|b=1)=0 this gives zero instead of 0.5.

Problem b)
For node c we get the following counts:
counts_b [[ 0.5 0.5]
[ 0 0]]
But these are the chances that P(b=0|a=0) and P(b=1|a=0) while it should be the chances that P(c=0,b=0|a=0)=P(c=0|b=0,a=0)*P(b=0|a=0) and P(c=0,b=1|a=0)=P(c=0|b=1,a=0)*P(b=1|a=0) and since b d-separates a and c and P(c=0|b=1)=0 this forces the count to be zero. So the initial CPT of node c isn't taken in account while estimating the count for node c.

Hello unknown!

Your remarks are very interesting and they combine with the fact that we used an intrinsic way of performing inference inside the EM algorithm which is why our algorithm is faster than yours. I guess you are probably right. Your example has convinced me and therefore we should change the implementation of EM.

Here is what I propose :
- François Debrouchoven (the guy that wrote the EM and SEM algorithms) has been contacted and will be responsible for making the changes to the code.
- Your implementation of the EM algorithm interests us and we would like to see it (if that's ok with you). If you could post your name (or contact me via email) we could arrange for your code (or a mixture between your code and ours) to be part of OpenBayes.

So you have two choices:
1)Either you decide to take part in the implementation of the new EM algorithm (in which case you will collaborate with françois), or
2) (if you don't have time to spare for OpenBayes), you could just send us your code together with some comments and explanations and françois will make the necessary adjustments. In this case you will only have to reply to some mails each time we have some questions.

Thank you for enthusiasm in this project!
Kosta

PS : Could you please post your name and/or email address? Otherwise we cannot reach you.
To palliate for messages without names, from now on you must login in order to post new messages.

Hi,

I didn't notice I posted under the obadmin name, but I did write my name (hidden) before the example ;-). In any case, I've created a login so you should be able to reach me (username: wannes)

Using Bayesian nets isn't my full-time project, rather a part of an idea so I don't know if I will be able to contribute a lot. But I'm certainly willing to help with the EM-algorithm. François is welcome to contact me so we can share some ideas.

This weekend or in the beginning of next week, I will clean up my code and share it with you guys.

Kind regards,
Wannes Meert

--
Wannes Meert
DTAI-KULeuven
http://www.cs.kuleuven.be/~wannes/

Ok,

Helping us just a little bit with the EM algorithm is already a great deal! We thank you in advance. This is the only way an open-source project can move on since we all have other things to do for a living.

François has a lot of paperwork to do because he is leaving for the states this week but he will contact you some time this week.

Sorry I did not pay attention to your name...

Keep me in touch as soon as your code is clean

Kosta

Hello,

Thank you very much for your remarks!

I'm leaving tomorrow for the US, so I won't have much time this week to look at and correct my code, but I'll do it as soon as possible, I'll contact you probably in the beginning of next week.

Thank you again,

François

I have merged my algorithm with François' EMLearningEngine class, so it is easy to test (I've called my method LearnEMParamsWM() ). I've also adjusted the MultinomialDistribution class so it can handle Augmented Bayesian Nets. This is a simple extension but in my opinion it gives a more robust learning algorithm (less chance to have a zero by zero division). My EM algorithm uses the augmented Bayesian net so both files are needed.

You can find the two files in my folder on OpenBayes.org, performing a diff with the original code will show what I have added/altered.

Kind regards,
wannes

Excellent work wannes !!!

I just took a look on your code and it seems perfect from a first point of view. Do I have your permission to modify a little bit the files you sent me and integrate them in the next public version of OpenBayes (in 1-2 weeks)?

For the moment users can test the files by getting them from your folder and copying them to their openbayes directory.

Thank you wannes, keep up the good work!

kosta

Hello,

I have now had more time to look at your remarks, and you are absolutely correct. I tried to speed up my algorithm, and I made a big theoretical error. Thank you very much for helping us. Your code works very good, so thanks very much for that too.

I'm fixing now a little bug in the ConnexeInferenceJTree class, and that will allow us to use your code in the SEM algorithm.

Thank you again, and do not hesitate to warn us if you see another bug and/or possible improvement.

François