# 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:

# Overview

• What is abstraction?
• Types of abstraction
• Distinctions in the domain of discourse
• Qualitative probability
• Constraint-based methods
• Qualitative probabilistic reasoning
• Uses of abstraction

# What is Abstraction?

• Ignoring or suppressing detail
• What for?
• computational efficiency
• representational economy
• facilitating communication
• generalizing deductive conclusions
• Useful both at design- and run-time

# Abstraction, Uncertainty, and Modeling (I)

• Consider an uncertain proposition, e.g.,
• At a finer level of detail, p decomposes into:
• p1 = amplifier busted
• p2 = power out
• p3 = speakers blown
• p4 = tuner not working
• p5 = lots of static
• ...

# 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?

• Ignorance
• Don't have a theory of the deterministic mechanism.
• Don't have knowledge about the values of factors in the detailed theory.
• Laziness
• Too much work to specify the detailed deterministic theory.
• Would have to recursively apply the detailed modeling to every detailed factor...might as well stop here.

# Types of Abstraction

• Abstracting variable definitions
• factorizations
• concept taxonomies
• Abstracting state spaces
• joint state space
• factor spaces
• Abstracting network structure
• summarizing interaction paths
• ignoring dependencies
• Abstracting probabilities
• intervals or bounds
• qualitative relationships

# Abstraction as Compilation

• Generate simplified model via compilation
• Exact or approximate compilation

# Concept Taxonomies

Problem: How can we avoid including every relevant KB concept in model?
• Use concept taxonomies to represent relationships at multiple levels of abstraction.
• Select appropriate levels for various concepts on case-specific basis.
• Construct and "solve" models at varying levels, merging conclusions.

# State-Space Abstraction

• Idea:
• Approximate solution using coarsened factor state spaces.
• Incrementally refine while there is time available.
• Issues:
• Which node to refine.
• Which states to refine.
• How to assign conditional probability distributions to abstracted states.

# 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.

# Conclusions: State-Space Abstraction

• A viable anytime strategy
• Many available options and tradeoffs
• Issues for Investigation:
• heuristic selection of nodes/states to refine
• analytical error bounds
• further empirical validation
• comparison with sampling techniques
• combining structural and state-space abstraction

# Qualitative Probability

• Defn: Qualitative reasoning
- reasoning directly in terms of the qualities of interest for a given problem or class of problems
• Full precision in degrees of belief not required for most uncertain reasoning tasks**
• Focus on the properties of belief that matter for the reasoning problem
• Design a language and inference mechanism where these properties are directly expressed and manipulated

# Acceptance

• Accepting a proposition as a belief
• determining that it is sufficiently likely
• acting for all purposes as if it were the case
• Criteria
• probability threshold
• defaults
• minimality, specificity, argument structure,...
• Computational benefits
• NOT just a matter of probability

# Decision Making

• Degrees of belief are of no interest per se
• Probabilities matter only for decisions
• Qualitative probabilities should be translatable to qualitative utilities

# Typical Planning Problem

• Given a baseline plan p (e.g., "do nothing"), find a modification pcents that improves expected utility.
• Problem is to establish relative improvement.

# Constraint-based Approaches

• Each construct in the QP language represents a constraint on the underlying probability distribution.
• Examples:
• Pr(a) is in the range [lb,ub]
• Pr(a) >= Pr(b)
• a and b marginally independent
• a positively influences b

# Semantics: Constraint Approach

• Q a qualitative probability sentence
• M(Q) the models (probability distributions) satisfying Q
• Entailment: Q1entails Q2 iff M(Q1) is a subset of M(Q2)
• Inference: Q1|-- Q2
• Important properties:
• Soundness, completeness
• Expressibility
• closure under common operations
• Dominance-based decision making

# Dependence Graphs

• Structural representation of conditional independence in a joint probability distribution
• Y contains no descendants of x implies I(x,pred(x),Y)

# Constraints in QPNs

• Relative ordinal comparisons between conditional expressions, varying the conditions
• Embedded in dependence graphs
• Two types of qualitative relation:
• qualitative influences - direct relation between variables
• qualitative synergy - interactions among influences

# 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)

# Conclusions: Qualitative Probability

• Qualitative probability approaches distinguished by task, language
• Many related approaches to acceptance, not intrinsically probabilistic
• Probability constraint logics have clearest semantics
• Ordinal methods differ on
• types of expressions that are compared
• classes of decisions qualitatively determined
• No unique notion of qualitative probability, but the space of possibilities has significant structure

# Summary: Uses of Abstraction

• Summarization, necessitated by ignorance and laziness
• Simplification, for computational efficiency and representational economy
• Anytime approximation
• Generalization of conclusions
• Validity and effectiveness depend on task
• Acceptance
• Decision making
• Research issue: more degrees of freedom than we know what to do with

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