Bayesian networks inference advanced algorithms for triangulation abd partical abduction

Resumo

Within the field of Artificial Intelligence (AI), Expert Systems stand out due to their proven utility and their numerous applications, These systems, which try to imitate human experts in a certain knowledge domain, will need to manage the uncertainty inherent in most real life problems. One successful tool to treat uncertainty is the Probability Theory, which gives rise to Probabilistic Expert Systems (PES). Bayesian networks can be located in this PES framework. They provide a quite powerful formalism that gives a representation of the modelled world, which is intuitive (graph structure) and adaptable (belief update). Another appealing feature is their capability of being constructed either by means of experts' contribution or automatically from data, or both. In a general scheme of an Expert System, the Bayesian network (BN) is equivalent to the Knowledge Base indicating both variable relationships (presence/absence of graph arcs) and their strength (probability distributions). BNs answer queries also in the form of probabilities: given some observed facts, the user will want to know the resulting posterior probabilities for some other unobserved factors/variables of the problem. That is what basically inference in Bayesian networks will attempt to do. Moreover, the search of explanations for those given facts can also be of interest (abductive inference). Different and various inference methods, both approximate and exact, have been proposed in the literature. Nevertheless, those using a secondary structure called junction or join tree are quite broadly applied. The Join Tree (JT) is built from the corresponding BN and can be seen as the Inference Engine of the expert system. The steps necessary to perform this construction are included in a process called compilation. The complexity of compilation increases with the number of variables and depends on the graph structure. Triangulation means a particular compilation stage that is practically unavoidable and