Abstraction Techniques for Probabilistic Reasoning

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:

• MP Wellman, Some varieties of qualitative probability. Fifth International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, pages 437-442, July 1994.
• MP Wellman and C-L Liu, State-space abstraction for anytime evaluation of probabilistic networks. Tenth Conference on Uncertainty in Artificial Intelligence, pages 567-574, July 1994.

Copyright © 1994, Michael P. Wellman

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.,
  p = "car radio broken".
  
• 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
    
  • ...
• Can be certain about p, but uncertain about p1,...,p5

Abstraction, Uncertainty, and Modeling (II)

Abstraction, Uncertainty, and Modeling (III)

Abstraction, Uncertainty, and Modeling (IV)

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

Applying Justified Compilation

Concept Taxonomies

• 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

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

• 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

Structural 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

Qualitative Approaches

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

A Qualitative Probabilistic Network

QPN: Engine Doesn't Start

QPN: Radio Doesn't Work

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

Taxonomy of QP Languages

Dependence Graphs

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

Ordinal Comparisons

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

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

• 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