July 15, 2004

Complexity of Bayesian Network Inference

sprinkler grass cloudy wet
  • It is known that exact inference in Bayesian Networks is NP-Hard with respect to the network size.
    • Cooper, G.F. (1990). The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence, 42, 393-405
  • Approximate Bayesian Network inference scales well with network size, but is NP-Hard with respect to the hard-bound accuracy of the estimates.
    • Dagum P., & Luby, M. (1993). Approximating probabilistic inference in Bayesian belief networks is NP-Hard. Artificial Intelligence, 60 141-153.
Posted by djp3 at July 15, 2004 5:21 PM | TrackBack (0)
Post a comment

Post a comment