Transcript CIS730-Lecture-24

Lecture 28 of 41
Uncertainty and Probabilistic Reasoning:
Graphical Models Preliminaries
Friday, 22 October 2004
William H. Hsu
Department of Computing and Information Sciences, KSU
http://www.kddresearch.org
http://www.cis.ksu.edu/~bhsu
Reading:
Today: Chapter 13, Russell and Norvig 2e
Friday and Next Week: Chapter 14
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Graphical Models of Probability
•
•
Conditional Independence
–
X is conditionally independent (CI) from Y given Z iff P(X | Y, Z) = P(X | Z) for all values of X, Y, and Z
–
Example: P(Thunder | Rain, Lightning) = P(Thunder | Lightning)  T  R | L
Bayesian (Belief) Network
–
Acyclic directed graph model B = (V, E, ) representing CI assertions over 
–
Vertices (nodes) V: denote events (each a random variable)
–
Edges (arcs, links) E: denote conditional dependencies
•
Markov Condition for BBNs (Chain Rule):
•
Example BBN
n
P X 1 , X 2 , , X n    P X i | parentsX i 
i 1
Exposure-To-Toxins
Age X1
X3
Cancer
Serum Calcium
X6
X5
Gender X2
X4
Smoking

 



X7
Tumor
Lung


Descendant s
Non Descendant s
Parents
P(20s, Female, Low, Non-Smoker, No-Cancer, Negative, Negative)
= P(T) · P(F) · P(L | T) · P(N | T, F) · P(N | L, N) · P(N | N) · P(N | N)
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Automated Reasoning using Probabilistic Models:
Inference Tasks
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Semantics of Bayesian Networks
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Markov Blanket
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Constructing Bayesian Networks:
The Chain Rule of Inference
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Example:
Evidential Reasoning for Car Diagnosis
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
BNJ Core [1]
Design
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
BNJ Core [2]
Graph Architecture
© 2004 KSU BNJ Development Team
CIS 730: Introduction to Artificial Intelligence
CPCS-54 Network
Kansas State University
Department of Computing and Information Sciences
BNJ Graphical User Interface:
Network
ALARM
Network
© 2004 KSU BNJ Development Team
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
BNJ Visualization [1]
Framework
© 2004 KSU BNJ Development Team
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
BNJ Visualization [2]
Pseudo-Code Annotation (Code Page)
ALARM
Network
© 2004 KSU BNJ Development Team
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
BNJ Visualization [3]
Network
Poker
Network
© 2004 KSU BNJ Development Team
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Current Work:
Features in Progress
• Scalability
– Large networks (50+ vertices, 10+ parents)
– Very large data sets (106+)
• Other Visualizations
– K2 for structure learning
– Conditioning
• BNJ v1-2 ports
– Guo’s dissertation algorithms
– Importance sampling (CABeN)
• Lazy Evaluation
Barley
Network
CIS 730: Introduction to Artificial Intelligence
© 2004 KSU BNJ Development Team
Kansas State University
Department of Computing and Information Sciences
Terminology
•
Introduction to Reasoning under Uncertainty
– Probability foundations
– Definitions: subjectivist, frequentist, logicist
– (3) Kolmogorov axioms
•
Bayes’s Theorem
– Prior probability of an event
– Joint probability of an event
– Conditional (posterior) probability of an event
•
Maximum A Posteriori (MAP) and Maximum Likelihood (ML) Hypotheses
– MAP hypothesis: highest conditional probability given observations (data)
– ML: highest likelihood of generating the observed data
– ML estimation (MLE): estimating parameters to find ML hypothesis
•
Bayesian Inference: Computing Conditional Probabilities (CPs) in A Model
•
Bayesian Learning: Searching Model (Hypothesis) Space using CPs
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Summary Points
•
Introduction to Probabilistic Reasoning
– Framework: using probabilistic criteria to search H
– Probability foundations
• Definitions: subjectivist, objectivist; Bayesian, frequentist, logicist
• Kolmogorov axioms
•
Bayes’s Theorem
– Definition of conditional (posterior) probability
– Product rule
•
Maximum A Posteriori (MAP) and Maximum Likelihood (ML) Hypotheses
– Bayes’s Rule and MAP
– Uniform priors: allow use of MLE to generate MAP hypotheses
– Relation to version spaces, candidate elimination
•
Next Week: Chapter 14, Russell and Norvig
– Later: Bayesian learning: MDL, BOC, Gibbs, Simple (Naïve) Bayes
– Categorizing text and documents, other applications
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences