A Logic-based Tractable Approximation of Probability
This work addresses the challenge of making probabilistic reasoning computationally feasible for agents with limited resources, representing an incremental advancement in the field.
The paper tackles the problem of approximating probabilistic reasoning for resource-bounded agents by developing a logical framework, showing that propositional probability functions can be approximated by depth-bounded Belief functions under certain conditions and that this leads to tractable uncertain reasoning under typical assumptions.
We provide a logical framework in which a resource-bounded agent can be seen to perform approximations of probabilistic reasoning. Our main results read as follows. First we identify the conditions under which propositional probability functions can be approximated by a hierarchy of depth-bounded Belief functions. Second we show that under rather palatable restrictions, our approximations of probability lead to uncertain reasoning which, under the usual assumptions in the field, qualifies as tractable.