Anytime reasoning with probabilistic inequalities

We present a novel approach for anytime reasoning with probabilistic inequalities. In our anytime approach, the accuracy of results improve gradually as computation time increases, providing a trade-off between resource consumption and output quality. Our approach can be used for computing probabilities of arbitrary propositional clauses, is tractable in providing the initial approximate answers, and provides exact answers in the limiting case. Reasoning is made tractable by restricting it to a set of clauses in a control set that can be gradually enlarged as more resources are made available. We present three strategies that differ in the way constraints are generated from the clauses in the control set. We provide examples of our approach using an ignorant belief network