Report Number: CS-TR-94-1527
Institution: Stanford University, Department of Computer Science
Title: From Knowledge to Belief
Author: Koller, Daphne
Date: October 1994
Abstract: When acting in the real world, an intelligent agent must make
decisions under uncertainty. The standard solution requires
it to assign degrees of belief to the relevant assertions.
These should be based on the agent's knowledge. For example,
a doctor deciding on the treatment for a patient should use
information about that patient, statistical correlations
between symptoms and diseases, default rules, and more.
The random-worlds method induces degrees of belief from very
rich knowledge bases, expressed in a language that augments
first-order logic with statistical statements and default
rules (interpreted as qualitative statistics). The method is
based on the principle of indifference, treating all possible
worlds as equally likely. It naturally derives important
patterns of reasoning such as specificity, inheritance,
indifference to irrelevant information, and a default
assumption of independence. Its expressive power and
intuitive semantics allow it to deal well with examples that
are too complex for most other reasoning systems.
We use techniques from finite model theory to analyze the
computational aspects of random worlds. The problem of
computing degrees of belief is undecidable in general.
However, for unary knowledge bases, a tight connection to the
principle of maximum entropy often allows us to compute
degrees of belief.