Reasoning about Beliefs and Actions under Computational Resource Constraints
Eric Horvitz
Medical Computer Science Group
Stanford University
Stanford, CA 94305
pdf file.
Abstract:
Although many investigators affirm a desire to build reasoning systems
that behave consistently with the axiomatic basis defined by
probability theory and utility theory, limited resources for
engineering and computation can make a complete normative analysis
impossible. We attempt to move discussion beyond the debate over the
scope of problems that can be handled effectively to cases where it is
clear that there are insufficient computational resources to perform
an analysis deemed as complete. Under these conditions, we stress the
importance of considering the expected costs and benefits of applying
alternative approximation procedures and heuristics for computation
and knowledge acquisition. We discuss how knowledge about the
structure of user utility can be used to control value tradeoffs for
tailoring inference to alternative contexts. We address the notion of
real-time rationality, focusing on the application of knowledge about
the expected timewise-refinement abilities of reasoning strategies to
balance the benefits of additional computation with the costs of
acting with a partial result. We discuss the benefits of applying
decision theory to control the solution of difficult problems given
limitations and uncertainty in reasoning resources.
Keywords: Rationality, bounded resources, metareasoning, decision theory, flexible computation, bounded optimality.
Appeared originally in the Proceedings of the Third Workshop on Uncertainty
in Artificial Intelligence, Seattle WA, pp. 429-444. July 1987. AAAI and
Association for Uncertainty in Artificial Intelligence, Mountain View, CA.
Author Email: horvitz@camis.stanford.edu