Computer Science – Artificial Intelligence
Scientific paper
2010-07-22
Computer Science
Artificial Intelligence
A couple of typos were fixed, as well as the notation in part of section 4, which was misleading. Theoretical and empirical re
Scientific paper
This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. First, it is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure). Such proofs extend previous complexity results for the problem. Inapproximability results are also derived in the case of trees if the number of states per variable is not bounded. Although the problem is shown to be hard and inapproximable even in very simple scenarios, a new exact algorithm is described that is empirically fast in networks of bounded treewidth and bounded number of states per variable. The same algorithm is used as basis of a Fully Polynomial Time Approximation Scheme for MAP under such assumptions. Approximation schemes were generally thought to be impossible for this problem, but we show otherwise for classes of networks that are important in practice. The algorithms are extensively tested using some well-known networks as well as random generated cases to show their effectiveness.
No associations
LandOfFree
New Results for the MAP Problem in Bayesian Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Results for the MAP Problem in Bayesian Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Results for the MAP Problem in Bayesian Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-612516