Probabilistic Horn abduction and Bayesian networks.

*(English)*Zbl 0792.68176Summary: The paper presents a simple framework for Horn-clause abduction, with probabilities associated with hypotheses. The framework incorporates assumptions about the rule base and independence assumptions amongst hypotheses. It is shown how any probabilistic knowledge representable in a discrete Bayesian belief network can be represented in this framework. The main contribution is in finding a relationship between logical and probabilistic notions of evidential reasoning. This provides a useful representation language in its own right, providing a compromise between heuristic and epistemic adequacy. It also shows how Bayesian networks can be extended beyond a propositional language. This paper also shows how a language with only (unconditionally) independent hypotheses can represent any probabilistic knowledge, and argues that it is better to invent new hypotheses to explain dependence rather than having to worry about dependence in the language.

##### MSC:

68T30 | Knowledge representation |

##### Keywords:

Horn-clause abduction; probabilistic knowledge; evidential reasoning; representation language; Bayesian networks
Full Text:
DOI

##### References:

[1] | Apt, K.R.; Bezem, M., Acyclic programs, New gen. comput., 9, 3-4, 335-363, (1991) · Zbl 0744.68034 |

[2] | Bacchus, F., Lp, a logic for representing and reasoning with statistical knowledge, Comput. intell., 6, 4, 209-231, (1990) |

[3] | Bacchus, F., () |

[4] | Barbuti, R.; Mancarella, P.; Pedreschi, D.; Turini, F., A transformational approach to negation in logic programming, J. logic program., 8, 201-228, (1990) · Zbl 0796.68056 |

[5] | Breese, J.S., Construction of belief and decision networks, () |

[6] | Charniak, E.; Goldman, R.P., A semantics for probabilistic quantifier-free first-order languages, with particular application to story understanding, (), 1074-1079 |

[7] | Charniak, E.; Shimony, S.E., Probabilistic semantics for cost based abduction, (), 106-111 · Zbl 0742.68076 |

[8] | Clark, K.L., Negation as failure, (), 293-322 |

[9] | Console, L.; Dupre, D.Theseider; Torasso, P., On the relationship between abduction and deduction, J. logic comput., 1, 5, 661-690, (1991) · Zbl 0734.68085 |

[10] | Cox, P.T.; Pietrzykowski, T., General diagnosis by abductive inference, () · Zbl 0788.68133 |

[11] | de Kleer, J., An assumption-based TMS, Artif. intell., 28, 2, 127-162, (1986) |

[12] | de Kleer, J.; Mackworth, A.K.; Reiter, R., Characterizing diagnoses, (), 324-330 |

[13] | de Kleer, J.; Williams, B.C., Diagnosing multiple faults, Artif. intell., 32, 1, 97-130, (1987) · Zbl 0642.94045 |

[14] | de Kleer, J.; Williams, B.C., Diagnosis with behavioral modes, (), 1324-1330 |

[15] | Doyle, J., Methodological simplicity in expert system construction: the case for judgments and reasoned assumptions, AI mag., 4, 2, 39-43, (1983) |

[16] | Elkan, C., Reasoning about action in first-order logic, (), 221-227 |

[17] | Genesereth, M.R., The use of design descriptions in automated diagnosis, Artif. intell., 24, 1-3, 411-436, (1984) |

[18] | Goebel, R.; Furukawa, K.; Poole, D., Using definite clauses and integrity constraints as the basis for a theory formation approach to diagnostic reasoning, (), 211-222 |

[19] | Hanks, S.; McDermott, D.V., Nonmonotonic logic and temporal projection, Artif. intell., 33, 379-412, (1987) · Zbl 0654.68107 |

[20] | Henrion, M., An introduction to algorithms for inference in belief nets, (), 129-138 |

[21] | Hobbs, J.R.; Stickel, M.E.; Martin, P.; Edwards, D., Interpretation as abduction, (), 95-103 |

[22] | Horsch, M.; Poole, D., A dynamic approach to probabilistic inference using Bayesian networks, (), 155-161 |

[23] | Jensen, F.V.; Lauritzen, S.L.; Olesen, K.G., Bayesian updating in causal probabilistic networks by local computations, Comput. stat. Q., 4, 269-282, (1990) · Zbl 0715.68076 |

[24] | Konolige, K., Abduction versus closure in causal theories, Artif. intell., 53, 2-3, 255-272, (1992) · Zbl 1193.68236 |

[25] | Kowalski, R., (), Artificial Intelligence Series |

[26] | Laskey, K.B.; Lehner, P.E., Assumptions, beliefs and probabilities, Artif. intell., 41, 1, 65-77, (1990) |

[27] | Lauritzen, S.L.; Spiegelhalter, D.J., Local computations with probabilities on graphical structures and their application to expert systems, J. R. stat. soc. ser. B, 50, 2, 157-224, (1988) · Zbl 0684.68106 |

[28] | Ledley, R.S.; Lusted, L.B., Reasoning foundations of medical diagnosis, Science, 130, 3366, 9-21, (1959) · Zbl 0115.37301 |

[29] | Lin, F.; Shoham, Y., Argument systems: a uniform basis for nonmonotonic reasoning, (), 245-255 |

[30] | Lloyd, J.W., (), Symbolic Computation Series |

[31] | Loui, R.P., Defeat among arguments: a system for defeasible inference, Comput. intell., 3, 2, 100-106, (1987) |

[32] | Loui, R.P., Defeasible decisions: what the proposal is and isn’t, (), 99-116 · Zbl 0721.68090 |

[33] | McCarthy, J.; Hayes, P.J., Some philosophical problems from the standpoint of artificial intelligence, (), 463-502 · Zbl 0226.68044 |

[34] | Neufeld, E.M.; Poole, D., Towards solving the multiple extension problem: combining defaults and probabilities, (), 305-312 |

[35] | Ng, R.T.; Subrahmanian, V.S., Non-monotonic negation in probabilistic deductive databases, (), 249-256 |

[36] | Ng, R.T.; Subrahmanian, V.S., Empirical probabilities in monadic deductive databases, (), 215-222 |

[37] | Pearl, J., Distributed revision of composite beliefs, Artif. intell., 33, 2, 173-215, (1987) · Zbl 0633.68094 |

[38] | Pearl, J., Embracing causality in default reasoning, Artif. intell., 35, 2, 259-271, (1988) |

[39] | Pearl, J., () |

[40] | Peng, Y.; Reggia, J.A., (), Symbolic Computation-AI Series |

[41] | Pollock, J.L., Defeasible reasoning, Cogn. sci., 11, 481-518, (1987) |

[42] | Poole, D., A logical framework for default reasoning, Artif. intell., 36, 1, 27-47, (1988) · Zbl 0647.68094 |

[43] | Poole, D., Representing knowledge for logic-based diagnosis, (), 1282-1290 |

[44] | Poole, D., Explanation and prediction: an architecture for default and abductive reasoning, Comput. intell., 5, 2, 97-110, (1989) |

[45] | Poole, D., Normality and faults in logic-based diagnosis, (), 1304-1310 |

[46] | Poole, D., A methodology for using a default and abductive reasoning system, Int. J. intell. syst., 5, 5, 521-548, (1990) · Zbl 0714.68091 |

[47] | Poole, D., Representing diagnostic knowledge for probabilistic Horn abduction, (), 1129-1135 · Zbl 0749.68086 |

[48] | Poole, D., Representing Bayesian networks within probabilistic Horn abduction, (), 271-278 |

[49] | Poole, D., Logic programming, abduction and probability, (), 530-538 · Zbl 0862.68018 |

[50] | Poole, D., Search for computing posterior probabilities in Bayesian networks, () |

[51] | Poole, D.; Goebel, R.; Aleliunas, R., Theorist: a logical reasoning system for defaults and diagnosis, (), 331-352 |

[52] | Poole, D.; Provan, G., What is the most likely diagnosis?, (), 89-105 |

[53] | Pople, H.E., On the mechanization of abductive logic, (), 147-152 |

[54] | Provan, G., An analysis of ATMS-based techniques for computing Dempster-Shafer belief functions, (), 1115-1120 |

[55] | Reichenbach, H., () |

[56] | Reiter, R., Equality and domain closure in first order data bases, J. ACM, 27, 235-249, (1980) · Zbl 0441.68117 |

[57] | Reiter, R., A theory of diagnosis from first principles, Artif. intell., 32, 1, 57-95, (1987) · Zbl 0643.68122 |

[58] | Reiter, R., The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression, (), 359-380 · Zbl 0755.68124 |

[59] | Reiter, R.; de Kleer, J., Foundations of assumption-based truth maintenance systems: preliminary report, (), 183-188 |

[60] | Reiter, R.; Mackworth, A.K., A logical framework for depiction and image interpretation, Artif. intell., 41, 2, 125-155, (1989) · Zbl 0689.68113 |

[61] | Shachter, R.D.; Heckerman, D., Thinking backwards for knowledge acquisition, AI mag., 8, 55-62, (1987) |

[62] | Shanahan, M., Prediction is deduction, but explanation is abduction, (), 1055-1060 · Zbl 0713.68065 |

[63] | Shimony, S.E.; Charniak, E., A new algorithm for finding MAP assignments to belief networks, (), 98-103 · Zbl 0742.68076 |

[64] | Sterling, L.; Shapiro, E., () |

[65] | van Emden, M.H., Quantitative deduction and its fixpoint theory, J. logic program., 4, 1, 37-53, (1986) · Zbl 0609.68068 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.