2011 | OriginalPaper | Buchkapitel
On Stopping Evidence Gathering for Diagnostic Bayesian Networks
verfasst von : Linda C. van der Gaag, Hans L. Bodlaender
Erschienen in: Symbolic and Quantitative Approaches to Reasoning with Uncertainty
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Sequential approaches to automated test selection for diagnostic Bayesian networks include a stopping criterion for deciding in each iteration whether or not gathering of further evidence is opportune. We study the computational complexity of the problem of deciding when to stop evidence gathering in general and show that it is complete for the complexity class
NP
PP
; we show that the problem remains
NP
-complete even when it is restricted to networks of bounded treewidth. We will argue however, that by reasonable further restrictions the problem can be feasibly solved for many realistic applications.