Reasoning with BKBs – Algorithms and Complexity

Bayesian Knowledge Bases (BKB) are a rule-based probabilistic model that extends the well-known Bayes Networks (BN), by naturally allowing for context-specific independence and for cycles in the directed graph. We present a semantics for BKBs that facilitate handling of marginal probabilities, as we...

Full description

Saved in:
Bibliographic Details
Published in:Annals of mathematics and artificial intelligence 2004-03, Vol.40 (3/4), p.403-425
Main Authors: Rosen, Tzachi, Shimony, Solomon Eyal, Santos Jr, Eugene
Format: Article
Language:English
Subjects:
Algorithms
Bayesian analysis
Complexity
Graph theory
Importance sampling
Knowledge bases (artificial intelligence)
Probabilistic models
Reasoning
Semantics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Bayesian Knowledge Bases (BKB) are a rule-based probabilistic model that extends the well-known Bayes Networks (BN), by naturally allowing for context-specific independence and for cycles in the directed graph. We present a semantics for BKBs that facilitate handling of marginal probabilities, as well as finding most probable explanations.Complexity of reasoning with BKBs is NP hard, as for Bayes networks, but in addition, deciding consistency is also NP-hard. In special cases that problem does not occur. Computation of marginal probabilities in BKBs is another hard problem, hence approximation algorithms are necessary – stochastic sampling being a commonly used scheme. Good performance requires importance sampling, a method that works for BKBs with cycles is developed.
ISSN:1012-2443
1573-7470
DOI:10.1023/B:AMAI.0000012874.65239.b0