engleski

Comparison of Methods for Reduction of Computational Complexity in Bayesian Networks

Bayesian networks offer great potential for use in automating large scale reasoning tasks, e.g. diagnostics. Unfortunately reasoning in richly interconnected Bayesian network is NP-hard. Hence, for many practical problems, exact computations are prohibitive. Therefore, approximate solutions are often the best that can be hoped for. Approximate algorithms are characterized by the nature of the bounds on the estimates they produce and by the reliability with which the exact answer lies within this bounds. It was shown that the evaluation of a Beyesian network within probably approximately correct bounds is also NP-hard. This paper explores some new and appealing approximation schemes for Bayesian networks in order to reduce the computational complexity of the inference process. The methods are analyzed from the theoretical viewpoint, and tested over a set of some well-known exemplar problems.

artificial intelligence; probabilistic reasoning; Bayesian networks

nije evidentirano