کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
398086 | 1438480 | 2011 | 18 صفحه PDF | دانلود رایگان |
One of the key computational problems in Bayesian networks is computing the maximal posterior probability of a set of variables in the network, given an observation of the values of another set of variables. In its most simple form, this problem is known as the MPE-problem. In this paper, we give an overview of the computational complexity of many problem variants, including enumeration variants, parameterized problems, and approximation strategies to the MPE-problem with and without additional (neither observed nor explained) variables. Many of these complexity results appear elsewhere in the literature; other results have not been published yet. The paper aims to provide a fairly exhaustive overview of both the known and new results.
► An overview of complexity results for the most probable explanation problem in Bayesian networks.
► Exact computation, approximation, enumeration, and fixed-parameter results are given.
► Apart from an exhaustive overview from results in the literature, some new results are included.
Journal: International Journal of Approximate Reasoning - Volume 52, Issue 9, December 2011, Pages 1452–1469