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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/94/1527/CS-TR-94-1527.pdf