Tree-Width and the Computational Complexity of MAP Approximations in Bayesian Networks.
Johan KwisthoutPublished in: J. Artif. Intell. Res. (2015)
Keyphrases
- tree width
- bayesian networks
- computational complexity
- tree decomposition
- probabilistic reasoning
- structural properties
- constraint networks
- np complete
- shortest path
- special case
- graphical models
- maximum a posteriori
- query evaluation
- conjunctive queries
- exact and approximate
- database
- np hard
- computationally challenging
- conditional independence
- conditional probabilities
- decomposition method
- hidden variables
- answer set programming
- message passing
- belief networks
- probability distribution
- query processing
- lower bound
- social networks