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:

- 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

- What is abstraction?

- Types of abstraction

- Distinctions in the domain of discourse

- Qualitative probability
- Constraint-based methods
- Qualitative probabilistic reasoning

- Uses of abstraction

- Ignoring or suppressing detail

- What for?
- computational efficiency

- representational economy

- facilitating communication

- generalizing deductive conclusions

- computational efficiency
- Useful both at design- and run-time

- 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

- ...

- p1 = amplifier busted
- Can be certain about p, but uncertain about p1,...,p5

- Ignorance
- Don't have a theory of the deterministic mechanism.

- Don't have knowledge about the values of factors in the detailed theory.

- Don't have a theory of the deterministic mechanism.
- 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.

- Too much work to specify the detailed deterministic theory.

- Abstracting variable definitions
- factorizations

- concept taxonomies

- factorizations
- Abstracting state spaces
- joint state space

- factor spaces

- joint state space
- Abstracting network structure
- summarizing interaction paths

- ignoring dependencies

- summarizing interaction paths
- Abstracting probabilities
- intervals or bounds

- qualitative relationships

- intervals or bounds

- Generate simplified model via compilation

- Exact or approximate compilation

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

- Idea:
- Approximate solution using coarsened factor state spaces.

- Incrementally refine while there is time available.

- Approximate solution using coarsened factor state spaces.
- Issues:
- Which node to refine.

- Which states to refine.

- How to assign conditional probability distributions to abstracted states.

- Which node to refine.

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

- 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

- heuristic selection of nodes/states to refine

__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

- determining that it is sufficiently likely
- Criteria
- probability threshold

- defaults

- minimality, specificity, argument structure,...

- probability threshold
- 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

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

- Examples:
- Pr(a) is in the range [lb,ub]

- Pr(a) >= Pr(b)

- a and b marginally independent

- a positively influences b

- Pr(a) is in the range [lb,ub]

- 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

- Soundness, completeness
- Dominance-based decision making

- Structural representation of conditional independence in a joint probability distribution

- Y contains no descendants of x implies I(x,pred(x),Y)

- 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 - direct relation between variables

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

- 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

- types of expressions that are compared
- No unique notion of qualitative probability, but the space of possibilities has significant structure

- 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

- Acceptance
- Research issue: more degrees of freedom than we know what to do with