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?
- 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)
Can approach certainty in the proposition of interest, given enough detail in
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?
- Don't have a theory of the deterministic mechanism.
- Don't have knowledge about the values of factors in the detailed theory.
- 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
- 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
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.
- Approximate solution using coarsened factor state spaces.
- Incrementally refine while there is time available.
- 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)
- Generate initial abstract network with one superstate per node.
- Evaluate the probability distribution for each node given the evidence.
- If all states for all nodes are elementary, stop.
- Split the most probable superstate in each node.
- Go to step 2.
Example: Traffic Modeling
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
- 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
- Accepting a proposition as a belief
- determining that it is sufficiently likely
- acting for all purposes as if it were the case
- probability threshold
- minimality, specificity, argument structure,...
- Computational benefits
- NOT just a matter of probability
- 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.
- Each construct in the QP language represents a constraint on the underlying probability distribution.
- 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
- closure under common operations
- Dominance-based decision making
Taxonomy of QP Languages
- 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
Two special cases:
- Probabilistic relation, binary b:
a1 > a2 implies Pr(B|a1 x) >= Pr(B|a2 x)
- 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
- Decision making
- Research issue: more degrees of freedom than we know what to do with