Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Reasoning With Qualitative Probabilities Can Be Tractable
Moises Goldszmidt, Judea Pearl
Abstract:
We recently described a formalism for reasoning with if-then rules that re expressed with different levels of firmness [18]. The formalism interprets these rules as extreme conditional probability statements, specifying orders of magnitude of disbelief, which impose constraints over possible rankings of worlds. It was shown that, once we compute a priority function Z+ on the rules, the degree to which a given query is confirmed or denied can be computed in O(log n`) propositional satisfiability tests, where n is the number of rules in the knowledge base. In this paper, we show that computing Z+ requires O(n2 X log n) satisfiability tests, not an exponential number as was conjectured in [18], which reduces to polynomial complexity in the case of Horn expressions. We also show how reasoning with imprecise observations can be incorporated in our formalism and how the popular notions of belief revision and epistemic entrenchment are embodied naturally and tractably.
Keywords:
Pages: 112-120
PS Link:
PDF Link: /papers/92/p112-goldszmidt.pdf
BibTex:
@INPROCEEDINGS{Goldszmidt92,
AUTHOR = "Moises Goldszmidt and Judea Pearl",
TITLE = "Reasoning With Qualitative Probabilities Can Be Tractable",
BOOKTITLE = "Proceedings of the Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-92)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Mateo, CA",
YEAR = "1992",
PAGES = "112--120"
}


hosted by DSL   •   site info   •   help