(PDF paper, 83Kb)
In contrast with classical reasoning, where a solution is either
correct or incorrect, approximate reasoning tries to compute
solutions which are close to the ideal solution, without necessarily
being perfect. Such approximate reasoning can be used to exchange
solution quality for computation time, known as anytime reasoning.
In this paper we study approximate versions of diagnostic
reasoning. Traditionally, diagnostic reasoning is characterised in
terms of the logical entailment relation. In this paper we study the
effects of replacing the logical entailment relation with an approximate
version of the entailment relation, in particular an approximate
version of Boolean Constraint Propagation (BCP).
We characterise the cheapest versions of approximate BCP which allows single
components and entire systems to be diagnosed correctly. From these
upperbounds surprisingly low values follow which are needed to correctly
diagnose many of the typical circuit examples from the literature. A
particularly interesting property that we discovered is that the point at which
approximate diagnosis coincides with classical diagnosis is entirely determined
by the nature of the individual components, and not by either the size or the
structural complexity of the overall device.
@InProceedings{KR00,
author = "A. Verberne and F. van Harmelen and A. ten Teije",
title = "Anytime Diagnostic Reasoning using
Approximate Boolean Constraint Propagation",
booktitle = "Proceedings of the Seventh International Conference on
Principles of Knowledge Representation and Reasoning
({KR'00})",
year = 2000,
address = "Boulder, Colorado",
month = "April",
pages = "",
keywords = {Approximate Reasoning, Diagnostic Reasoning},
urlPaper = "http://www.cs.vu.nl/~frankh/postscript/KR00.pdf"
}
Back to list of papers