We introduce an incremental-refinement approach to probabilistic inference called bounded conditioning. Bounded conditioning monotonically refines the bounds on probabilities in a belief network with computation, and converges on a final probability of interest with the allocation of a complete resource fraction. As such, the approach holds promise as a useful inference technique for reasoning under the general conditions of uncertain and varying reasoning resources. The algorithm can solve a great portion of a probabilistic bounding problem in complex belief networks through breaking the world into a set of mutually exclusive, tractable subproblems and ordering their solution by the expected effect that each subproblem will have on the final answer. We introduce the algorithm, discuss its worst-case characterization, and present its performance on a complex belief network for reasoning about problems in the intensive-care unit.
