Reasoning and Facts Explanation in Valuation Based Systems

Article type: Research Article

Authors: Wierzchoń, S.T. | Kłopotek, M.A. | Michalewicz, M.

Affiliations: Institute of Computer Science, Polish Academy of Sciences, 01-237 Warszawa, ul Ordona 21. e-mail:stw@ipipan.waw.pl, klopotek@ipipan.waw.pl, michalew@ipipan.waw.pl

Abstract: In the literature, the optimization problem to identify a set of composite hypotheses H, which will yield the k largest P(H|Se) where a composite hypothesis is an instantiation of all the nodes in the network except the evidence nodes [17] is of significant interest. This problem is called “finding the k Most Plausible Explanation (MPE) of a given evidence Se in a Bayesian belief network”. The problem of finding k most probable hypotheses is generally NP-hard [2]. Therefore in the past various simplifications of the task by restricting k (to 1 or 2), restricting the structure (e.g. to singly connected networks), or shifting the complexity to spatial domain have been investigated. A genetic algorithm is proposed in this paper to overcome some of these restrictions while stepping out from probabilistic domain onto the general Valuation based System (VBS) framework is also proposed by generalizing the genetic algorithm approach to the realm of Dempster-Shafer belief calculus.

Keywords: Genetic algorithm, most plausible explanation, graphoidal expert systems

DOI: 10.3233/FI-1997-303410

Journal: Fundamenta Informaticae, vol. 30, no. 3-4, pp. 359-371, 1997