Transcript COMP201 Java Programming - Department of Computer Science

COMP 538
Reasoning and Decision under Uncertainty
Introduction
Readings: Pearl (1998, Chapter 1
Shafer and Pearl, Chapter 1
COMP 538 Introduction / Slide 2
Objectives


Course objectives
Course contents
COMP 538 Introduction / Slide 3
Uncertainty
 Uncertainty: the quality or state of being not clearly known.
 Uncertainty appears in many tasks




Partial knowledge of the state of the world
Noisy observations
Phenomena that is not covered by our models
Inherent randomness
COMP 538 Introduction / Slide 4
Probability and Decision Theory
 Well-known and well-understood framework for
uncertainty
 Clear semantics
 Provides principled answers for:
 Combining evidence
 Predictive & Diagnostic reasoning
 Incorporation of new evidence
 Intuitive (at some level) to human experts
 Can be learned
COMP 538 Introduction / Slide 5
Course Objectives

When applied to real-world problems, probability theory and
decision theory suffer from

Complexity of model construction
 Complexity of problem solving

This course covers methodologies developed recently in AI
community for dealing with those complexity problems.

The methodologies combine ideas from several disciplines
Artificial Intelligence, Machine Learning
Decision Theory, Theory of Computer Science
Statistics, Information Theory, Operations Research
COMP 538 Introduction / Slide 6
Complexity Problem of Applying Probability Theory

Example:


Patients in hospital are described by several attributes:

Background: age, gender, history of diseases, …

Symptoms: fever, blood pressure, headache, …

Diseases: pneumonia, heart attack, …
A joint probability distribution needs to assign a number to each
combination of values of these attributes, exponential model
size.


20 attributes require 2020 ( roughly 106 ) numbers
Real applications usually involve hundreds of attributes
COMP 538 Introduction / Slide 7
Complexity Problem of Applying Probability Theory

Because of the exponential model size problem, it was believed
that probability theory is not practical for dealing with uncertainty
in AI.

Alternative uncertainty calculi were introduced: uncertainty
factors, non-monotonic logic, fuzzy logic, etc.
COMP 538 Introduction / Slide 8
Complexity Problem of Applying Probability Theory



Bayesian networks alleviate the exponential model size problem.
Key idea: use conditional independence to factorize model into
smaller parts.
MINVOLSET
Example: Alarm network PULMEMBOLUS INTUBATION
KINKEDTUBE
VENTMACH
DISCONNECT
37 variables
PAP
SHUNT
VENTLUNG
VENITUBE
237
Model size:
Size of factored model: 509
PRESS
MINOVL
ANAPHYLAXIS
Model construction and
problem solving
becomes possible
SAO2
TPR
HYPOVOLEMIA
LVEDVOLUME
CVP
PCWP
LVFAILURE
STROEVOLUME
FIO2
VENTALV
PVSAT
ARTCO2
INSUFFANESTH
CATECHOL
HISTORY
ERRBLOWOUTPUT
CO
HR
HREKG
HRBP
BP
EXPCO2
ERRCAUTER
HRSAT
COMP 538 Introduction / Slide 9
Advantages of Bayesian Networks

Semantics



Model construction by expert


Probability theory provides the glue whereby the parts are
combined, ensuring that the system as a whole is consistent.
Alternative approaches suffer from several semantic deficiencies
(Pearl 1988, Chapter 1).
Appealing graphical interface allows experts to build model for
highly interacting variables.
Model construction from data

Probability foundation allows model construction from data by well
established statistical principles such as maximum likelihood
estimation and Bayesian estimation.
COMP 538 Introduction / Slide 10
Fielded Applications

Expert systems



Monitoring



Space shuttle engines (Vista project)
Freeway traffic
Sequence analysis and classification



Medical diagnosis
Fault diagnosis (jet-engines, Windows 98)
Speech recognition
Biological sequences
Information access
 Collaborative filtering
 Information retrieval
See tutorial by Breese and Koller (1997) and online resources for application
samples.
COMP 538 Introduction / Slide 11
Course Content/Bayesian Networks

Concept and semantics of Bayesian networks

Inference: How to answer queries efficiently

Learning: How to learn/adapt Bayesian network models from
data

Causal models: How to learn causality from statistical data
Detailed discussion of those topics can take one whole course
(DUKE). We will focus on the main ideas and skip the details so
that we can study other related topics.
COMP 538 Introduction / Slide 12
Bayesian networks and classical multivariate models

Special cases of Bayesian networks: many of the classical
multivariate models from



statistics, systems engineering, information theory, pattern
recognition and statistical mechanics
Examples: mixture models, factor analysis, hidden Markov
models, Kalman filters, Ising models.
Bayesian networks provide a way to view all of these models
as instances of a common underlying formalism.
COMP 538 Introduction / Slide 13
Course Content/Special models

Latent class analysis:



Statistical method for finding subtypes of related cases.
With proper generalization, might provide a statistical
foundation for Chinese medicine diagnosis.
Hidden Markov models:

A temporal model widely used in pattern recognition:
handwriting recognition, speech recognition.
COMP 538 Introduction / Slide 14
Decision Making under Uncertainty

Typical scenario: whether to take umbrella

Decision theory provides basis
for rational decision making:
Maximum expected utility principle.
Decision analysis: applying of decision theory.
Suffers from exponential model size.


COMP 538 Introduction / Slide 15
Course Content/Simple Decision Making

Influence diagrams



Generalization of Bayesian network.
Alleviate the complexity problem of decision analysis
Topics:


Evaluation: How to compute optimal decisions in an
influence diagram.
Value of information: Whether it is worthwhile to collect more
information to reduce uncertainty.
COMP 538 Introduction / Slide 16
Sequential Decision Making under Uncertainty

Agent/robot needs to execute multiple actions in
order to achieve a goal

Uncertainty originates from noisy sensor and
inaccurate actuators/uncontrollable enviroment
factors

What is the best way to reach goal with minimum
cost/time?
COMP 538 Introduction / Slide 17
Course Content/Sequential Decision Making

Models:

Markov decision processes, consider only uncertainty in
actuators/environment factors

Partially observable decision processes, consider uncertainty
in sensors and actuators/environment factors.

Solution methods:




Value iteration
Policy iteration
Dealing with model complexity using dynamic Bayesian networks
Learning sequential decision models

Model-based reinforcement learning
COMP 538 Introduction / Slide 18
Course Content/Summary

Bayesian networks

Concept and semantics, inference, learning, causilty

Special models: Hidden Markov models, latent class
analysis

Influence diagrams:


Evaluation, value of information
Markov decision processes and partially observable Markov
decision processes


Solution methods: value iteration, policy iteration, dynamic
Bayesian networks
Model-based reinforcement learning