Abstraction Techniques for Probabilistic Reasoning

Michael P. Wellman

University of Michigan
Dept of Electrical Engineering & Computer Science
Artificial Intelligence Laboratory

Tutorial prepared for the Summer Institute on Probability in AI, Corvallis, OR, July 1994.

This document includes only the text outline of the tutorial. For a hardcopy, contact the author. Material presented in this tutorial draws substantially from:

Copyright 1994, Michael P. Wellman


What is Abstraction?

Abstraction, Uncertainty, and Modeling (I)

Abstraction, Uncertainty, and Modeling (II)

Can approach certainty in the proposition of interest, given enough detail in conditional predecessors.

Abstraction, Uncertainty, and Modeling (III)

Conversely, leaving out conditional predecessors induces uncertainty in the proposition of interest.

Abstraction, Uncertainty, and Modeling (IV)

Degrees of belief are summary measures of the uncertainty induced by leaving out details in the model.

Why Omit Details?

Types of Abstraction

Abstraction as Compilation

Applying Justified Compilation

Concept Taxonomies

Problem: How can we avoid including every relevant KB concept in model?

State-Space Abstraction

Anytime Abstraction Procedure

procedure Abstract-Iter (network, evidence)
  1. Generate initial abstract network with one superstate per node.
  2. Evaluate the probability distribution for each node given the evidence.
  3. If all states for all nodes are elementary, stop.
  4. Split the most probable superstate in each node.
  5. Go to step 2.

State-Space Refinement

Probability Assignments

Example: Traffic Modeling

Tested Networks

Anytime Approximation

Testing the "Average Policy"

Conclusions: State-Space Abstraction

Structural Abstraction

Qualitative Probability

Qualitative Approaches


Decision Making

A Qualitative Probabilistic Network

QPN: Engine Doesn't Start

QPN: Radio Doesn't Work

Typical Planning Problem

Constraint-based Approaches

Semantics: Constraint Approach

Taxonomy of QP Languages

Dependence Graphs

Ordinal Comparisons

Constraints in QPNs

Qualitative Influences

Two special cases:
  1. Probabilistic relation, binary b:
    a1 > a2 implies Pr(B|a1 x) >= Pr(B|a2 x)
  2. Functional relation, b = f(a,x):
    a1 > a2 implies f(a1,x) >= f(a2,x) (conceptually, [[partialdiff]]f/[[partialdiff]]a >= 0)

Chaining Influences: General Case

Conclusions: Qualitative Probability

Summary: Uses of Abstraction

Author: Michael Wellman (wellman@engin.umich.edu)
Last Updated: 8/8/94