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


Overview


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


Acceptance


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