search

eBay / bayesian-belief-networks

Pythonic Bayesian Belief Network Package, supporting creation of and exact inference on Bayesian Belief Networks specified as pure python functions.
Other
1.13k stars 256 forks source link

Sumproduct algorithm returning marginal probabilities of 1 #1

Closed alexmojaki closed 10 years ago

alexmojaki commented 11 years ago

The attached script 'ebay_alarm_problem.py' ( https://www.dropbox.com/s/ux5vznts6mn70qg/ebay_alarm_problem.py ) is created to analyse the ALARM Bayesian network (found here: http://www.bnlearn.com/bnrepository/#alarm ). As can be seen, when a bbn object is created using build_bbn, or when a factor_graph object is created and the inference method is set to 'sample', the marginals obtained by querying are reasonable. However, if the 'sumproduct' inference method is used on the factor_graph object, the query returns multiple marginal probabilities with a value of 1 for the same variable, on several variables. This is clearly incorrect. Since the ALARM network is not a polytree, could it be that the algorithm is failing because the software does not convert the network to a junction tree? The README file lists "Automated conversion to Junction Trees" under "Other Features", but there is no mention of this in the code.

nnewey commented 11 years ago

Hi Alex

I will take a look. There is a bug in the graph validation that may be causing this.

Regards

Neville

On Nov 13, 2013, at 7:18 AM, alexmojaki notifications@github.com<mailto:notifications@github.com> wrote:

The attached script 'ebay_alarm_problem.py' ( https://www.dropbox.com/s/ux5vznts6mn70qg/ebay_alarm_problem.py ) is created to analyse the ALARM Bayesian network (found here: http://www.bnlearn.com/bnrepository/#alarm ). As can be seen, when a bbn object is created using build_bbn, or when a factor_graph object is created and the inference method is set to 'sample', the marginals obtained by querying are reasonable. However, if the 'sumproduct' inference method is used on the factor_graph object, the query returns multiple marginal probabilities with a value of 1 for the same variable, on several variables. This is clearly incorrect. Since the ALARM network is not a polytree, could it be that the algorithm is failing because the software does not convert the network to a junction tree? The README file lists "Automated conversion to Junction Trees" u nder "Other Features", but there is no mention of this in the code.

— Reply to this email directly or view it on GitHubhttps://github.com/eBay/bayesian-belief-networks/issues/1.

thakadu commented 11 years ago

Ok I took a look and yes, the issue is that for graphs with cycles, the intention is that the build_bbn should always be used instead of the factor_graph. I should have made that clear in the documentation so I will change it. Secondly, when setting the inference method to 'sumproduct' on a factor_graph with cycles an error should be raised as it doesn't make sense to run the sumproduct algo. on a factor graph with cycles. The "Automated conversion to Junction Trees" happens in the BBN class, not in the factor_graph class.

Going forward there really is no need to ever use the factor_graph class directly, unless you specifically want to use sampling, but for any smallish graph, if you want exact inference, the intended usage is to use the bbn class.

Thanks for finding this fixes to docs and exception error to come.

alexmojaki commented 11 years ago

Wow, it's great to see such a quick response. This is an awesome library, glad to see it's being kept alive. As requested separately by nnewey, I added the code that produced that example and others. You now have a thorough repository of large examples :-)

nnewey commented 11 years ago

Thanks so much for the contribution Alex. Should be merged now.

Cheers

On Nov 13, 2013, at 11:54 PM, alexmojaki notifications@github.com<mailto:notifications@github.com> wrote:

Wow, it's great to see such a quick response. This is an awesome library, glad to see it's being kept alive. As requested separately by nnewey, I added the code that produced that example and others. You now have a thorough repository of large examples :-)

— Reply to this email directly or view it on GitHubhttps://github.com/eBay/bayesian-belief-networks/issues/1#issuecomment-28465391.