An Order of Magnitude Calculus

Nic WilsonUAI 1995

TL;DR

This paper introduces a novel "order of magnitude calculus" that provides a formal framework for reasoning with imprecise, qualitative information. This calculus offers a rigorous semantics for order-of-magnitude probabilities and utilities, leading to a more expressive decision theory than existing approaches.

What Problem Does This Paper Address?

Reasoning about uncertain information is fundamental in artificial intelligence. While probabilistic methods are powerful, they often require precise numerical probabilities and utilities, which can be difficult or impossible to obtain in real-world scenarios with poor quality data or expert knowledge. Existing qualitative approaches, like those based on kappa functions, lack the expressiveness to fully capture the nuances of order-of-magnitude reasoning, particularly concerning the relationships between different orders of magnitude and the concept of "ambiguity." This paper aims to bridge this gap by developing a formal calculus that can handle these qualitative distinctions rigorously.

Methods

The core of the paper is the development of an "order of magnitude calculus" built upon a system of "extended reals" ($\mathbb{R}^*$). These extended reals are rational functions of a small positive parameter $\epsilon$, allowing for the representation of infinitesimal values. The order of magnitude calculus, denoted $\mathbb{R}^\circ$, uses pairs $(\sigma, n)$ where $\sigma \in \{+, -, 0\}$ and $n$ is an integer, to represent quantities of order $\epsilon^n$.

Key methodological contributions include:

  • Extended Reals ($\mathbb{R}^*$): A number system that includes infinitesimals, providing a foundation for representing quantities of different orders of magnitude.
  • Order of Magnitude Calculus ($\mathbb{R}^\circ$): An algebraic structure with operations (addition, multiplication, negation, inversion) designed to mimic arithmetic on extended reals but operating on qualitative "orders." This calculus includes special elements like $(0, n)$ to ensure closure under addition, representing sets of possibilities.
  • Semantics via Subsets of $\mathbb{R}^*$: The paper defines a precise meaning for elements of $\mathbb{R}^\circ$ by mapping them to subsets of $\mathbb{R}^*$. This allows for soundness and completeness proofs, ensuring that the calculus accurately reflects reasoning about extended reals.
  • Order of Magnitude Probability and Utility: The calculus is applied to define probability and utility functions that take values in $\mathbb{R}^\circ$. These are shown to be equivalent to generalized kappa functions, providing a formal semantics for them.
  • Order of Magnitude Decision Theory: A decision theory is constructed based on these order-of-magnitude probabilities and utilities, offering a more nuanced approach than existing methods.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Formalizing "Order of Magnitude": The paper provides a rigorous mathematical framework for reasoning about quantities that are "of order $\epsilon^n$," moving beyond informal descriptions.
  • Bridging Qualitative and Quantitative: The extended reals $\mathbb{R}^*$ act as a bridge, allowing qualitative order-of-magnitude reasoning in $\mathbb{R}^\circ$ to be grounded in a quantitative, albeit infinitesimal, system.
  • Closure and Ambiguity: The introduction of elements like $(0, n)$ in $\mathbb{R}^\circ$ is crucial for ensuring closure under addition, directly addressing the "ambiguity" that arises when combining quantities of different orders. This is a key improvement over prior approaches.
  • Semantics for Kappa Functions: The work provides a formal, semantically grounded interpretation for kappa functions, which are widely used in qualitative reasoning but previously lacked such a rigorous foundation.
  • More Expressive Decision Theory: The proposed decision theory is shown to be more expressive than existing ones (like Pearl's for kappa functions) because it can distinguish between different orders of magnitude of utilities and probabilities, and handle ambiguity more effectively.

Key Results

  • Soundness and Completeness: The paper establishes soundness and completeness results for the order of magnitude calculus, demonstrating that it accurately reflects reasoning about extended reals and is as powerful as possible within its framework.
  • Equivalence to Kappa Functions: Order-of-magnitude probability functions are shown to be equivalent to generalized kappa functions, providing a formal semantics for them.
  • Justification of Pearl's Theory: The paper provides a formal justification for an amended version of Pearl's decision theory for kappa functions, while also highlighting its limitations compared to the proposed calculus.
  • Preference Ordering: A key result is Theorem 3, which states that comparing two options using order-of-magnitude expected utility is equivalent to comparing their probabilistic interpretations for all possible assignments of extended probabilities and utilities.

Limitations and Future Work

  • Limitations of Pearl's Theory: The paper points out that Pearl's original decision theory for kappa functions has limitations: it cannot represent infinitesimal utilities, doesn't distinguish between positive and negative infinitesimal benefits, and has a less nuanced handling of ambiguity.
  • Future Work: The authors suggest exploring extensions to the calculus, such as adding elements representing non-negative elements of order at most $n$, or a squaring operation. They also propose investigating applications in other AI areas like Qualitative Physics and Constraint-based reasoning. The methods developed in the paper are expected to be useful for analyzing more sophisticated calculi.

Summary updated

BibTeX
@inproceedings{wilson1995order,
  author = {Nic Wilson},
  title = {{An Order of Magnitude Calculus}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1995},
}
Figure