Uncertain KR&R
Chapter 9
Outline
Probability
Bayesian networks
Fuzzy logic
2
Probability
FOL fails for a domain due to:
Laziness: too much to list the complete set of rules, too hard to
use the enormous rules that result
Theoretical ignorance: there is no complete theory for the domain
Practical ignorance: have not or cannot run all necessary tests
3
Probability
Probability = a degree of belief
Probability comes from:
Frequentist: experiments and statistical assessment
Objectivist: real aspects of the universe
Subjectivist: a way of characterizing an agents beliefs
Decision theory = probability theory + utility theory
4
Probability
Prior probability: probability in the absence of any other
information
P(Dice = 2) = 1/6
random variable: Dice
domain = <1, 2, 3, 4, 5, 6>
probability distribution: P(Dice) = <1/6, 1/6, 1/6, 1/6, 1/6, 1/6>
5
Probability
Conditional probability: probability in the presence of
some evidence
P(Dice = 2 | Dice is even) = 1/3
P(Dice = 2 | Dice is odd) = 0
P(A | B) = P(A B)/P(B)
P(A B) = P(A | B).P(B)
6
Probability
Example:
S = stiff neck
M = meningitis
P(S | M) = 0.5
P(M) = 1/50000
P(S) = 1/20
P(M | S) = P(S | M).P(M)/P(S) = 1/5000
7
Probability
Joint probability distributions:
X: <x1, , xm> Y: <y1, , yn>
P(X = xi, Y = yj)
8
Probability
Axioms:
0 P(A) 1
P(true) = 1 and P(false) = 0
P(A B) = P(A) + P(B) - P(A B)
9
Probability
Derived properties:
P(A) = 1 - P(A)
P(U) = P(A1) + P(A2) + ... + P(An)
U = A1 A2 ... An collectively exhaustive
Ai Aj = false mutually exclusive
10
Probability
Bayes theorem:
P(Hi | E) = P(E | Hi).P(Hi)/iP(E | Hi).P(Hi)
His are collectively exhaustive & mutually exclusive
11
Probability
Problem: a full joint probability distribution P(X1, X2, ..., Xn)
is sufficient for computing any (conditional) probability on
Xi's, but the number of joint probabilities is exponential.
12
Probability
Independence:
P(A B) = P(A).P(B)
P(A) = P(A | B)
Conditional independence:
P(A B | E) = P(A | E).P(B | E)
P(A | E) = P(A | E B)
Example:
P(Toothache | Cavity Catch) = P(Toothache | Cavity)
P(Catch | Cavity Toothache) = P(Catch | Cavity)
13
Probability
"In John's and Mary's house, an alarm is installed to
sound in case of burglary or earthquake. When the alarm
sounds, John and Mary may make a call for help or
rescue."
14
Probability
"In John's and Mary's house, an alarm is installed to
sound in case of burglary or earthquake. When the alarm
sounds, John and Mary may make a call for help or
rescue."
Q1: If earthquake happens, how likely will John make a
call?
15
Probability
"In John's and Mary's house, an alarm is installed to
sound in case of burglary or earthquake. When the alarm
sounds, John and Mary may make a call for help or
rescue."
Q1: If earthquake happens, how likely will John make a
call?
Q2: If the alarm sounds, how likely is the house
burglarized?
16
Bayesian Networks
Pearl, J. (1982). Reverend Bayes on Inference Engines:A
Distributed HierarchicalApproach,
presented at the Second National Conference onArtificial Intelligence
(AAAI-82), Pittsburgh, Pennsylvania
2000AAAI Classic PaperAward
17
Bayesian Networks
P(B) P(E)
Burglary .001 Earthquake .002
B E P(A)
Alarm T T .95
T F .94
F T .29
F F .001
A P(J) A P(M)
JohnCalls T .90 MaryCalls T .70
F .05 F .01
18
Bayesian Networks
Syntax:
Aset of random variables makes up the nodes
Aset of directed links connects pairs of nodes
Each node has a conditional probability table that quantifies the
effects of its parent nodes
The graph has no directed cycles
A A
yes B B no
C C
D D
19
Bayesian Networks
Semantics:
An ordering on the nodes: Xi is a predecessor of X j i < j
P(X1, X2, , Xn)
= P(Xn | Xn-1, , X1).P(Xn-1 | Xn-2, , X1). .P(X2 | X1).P(X1)
= iP(Xi | Xi-1, , X1) = iP(Xi | Parents(Xi))
P (Xi | Xi-1, , X1) = P(Xi | Parents(Xi)) Parents(Xi) {Xi-1, , X1}
Each node is conditionally independent of its predecessors given its parents
20
Bayesian Networks
Example:
P(J M A B E)
= P(J |A).P(M |A).P(A| B E).P(B).P(E)
= 0.00062
B E
J M
21
Bayesian Networks
Why Bayesian Networks?
22
Uncertain QuestionAnswering
P(Query | Evidence) = ?
Diagnostic (from effects to causes): P(B | J)
Causal (from causes to effects): P(J | B)
Intercausal (between causes of a common effect): P(B |A, E)
Mixed: P(A| J, E), P(B | J, E)
B E
J M
23
Uncertain QuestionAnswering
The independence assumptions in a Bayesian Network
simplify computation of conditional probabilities on its
variables
24
Uncertain QuestionAnswering
Q1: If earthquake happens, how likely will John make a call?
Q2: If the alarm sounds, how likely is the house burglarized?
Q3: If the alarm sounds, how likely both John and Mary make
calls?
25
Uncertain QuestionAnswering
P(B |A)
= P(B A)/P(A)
= aP(B A)
P(B |A)
= aP(B A)
a = 1/(P(B A) + P(B A))
26
General Conditional Independence
ABayesian Network implies all conditional independence
among its variables
27
General Conditional Independence
U1 Um
Z1j Znj
Y1 Yn
Anode (X) is conditionally independent of its non-descendents (Zij's),
given its parents (U i's)
28
General Conditional Independence
U1 Um
Z1j Znj
Y1 Yn
Anode (X) is conditionally independent of all other nodes, given its
parents (U i's), children (Yi's), and children's parents (Zij's)
29
General Conditional Independence
X and Y are conditionally independent given E
X E Y
Z
30
General Conditional Independence
Example:
Battery
Radio Ignition Gas
Starts
Moves
31
General Conditional Independence
Example:
Battery
Radio Ignition Gas
Gas - (Ignition) - Radio Starts
Gas - (Battery) - Radio
Gas - (no evidence at all) - Radio
Moves
Gas Radio | Starts
Gas Radio | Moves
32
V
a gueness
The Oxford Companion to Philosophy (1995):
Words like smart, tall, and fat are vague since in most contexts of
use there is no bright line separating them from not smart, not tall,
and not fat respectively
33
V
a gueness
Imprecision vs. Uncertainty:
The bottle is about half-full.
vs.
It is likely to a degree of 0.5 that the bottle is full.
34
Fuzzy Sets
Zadeh, L.A. (1965). Fuzzy Sets
Journal of Information and Control
35
Fuzzy Sets
36
Fuzzy Sets
37
Fuzzy Set Definition
Afuzzy set is defined by a membership function that maps
elements of a given domain (a crisp set) into values in [0, 1].
mA: U [0, 1]
1
mAA
young
0.5
0
25 30 40 Age
38
Fuzzy Set Representation
Discrete domain:
high-dice score: {1:0, 2:0, 3:0.2, 4:0.5, 5:0.9, 6:1}
Continuous domain:
A(u) = 1 for u[0, 25]
A(u) = (40 - u)/15 for u[25, 40] 1
A(u) = 0 for u[40, 150]
0.5
0
25 30 40 Age
39
Fuzzy Set Representation
a-cuts:
Aa = {u |A(u) a}
Aa+ = {u |A(u) > a} strong a-cut
A0.5 = [0, 30]
0.5
0
25 30 40 Age
40
Fuzzy Set Representation
a-cuts:
Aa = {u |A(u) a}
Aa+ = {u |A(u) > a} strong a-cut
A(u) = sup {a | u Aa}
A0.5 = [0, 30]
0.5
0
25 30 40 Age
41
Fuzzy Set Representation
Support:
supp(A) = {u |A(u) > 0} = A0+
Core:
core(A) = {u |A(u) = 1} = A1
Height:
h(A) = supUA(u)
42
Fuzzy Set Representation
Normal fuzzy set: h(A) = 1
Sub-normal fuzzy set: h(A) 1
43
Membership Degrees
Subjective definition
44
Membership Degrees
Subjective definition
Voting model:
Each voter has a subset of U as his/her own crisp definition of the
concept thatArepresents.
A(u) is the proportion of voters whose crisp definitions include u.
45
Membership Degrees
Voting model:
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
1
3 x x
4 x x x x x
5 x x x x x x x x x
6 x x x x x x x x x x
46
Fuzzy Subset Relations
A B iffA(u) B(u) for every uU
Ais more specific than B
X isA entails X is B
47
Fuzzy Set Operations
Standard definitions:
Complement: A(u) = 1 -A(u)
Intersection: (AB)(u) = min[A(u), B(u)]
Union: (AB)(u) = max[A(u), B(u)]
48
Fuzzy Set Operations
Example:
not young = young
not old = old
middle-age = not youngnot old
old = young
49
Fuzzy Relations
Crisp relation:
R(U 1, ..., U n) U 1 ... U n
R(u1, ..., u n) = 1 iff (u 1, ..., u n) R or = 0 otherwise
50
Fuzzy Relations
Crisp relation:
R(U 1, ..., U n) U 1 ... U n
R(u1, ..., u n) = 1 iff (u 1, ..., u n) R or = 0 otherwise
Fuzzy relation: a fuzzy set on U1 ... Un
51
Fuzzy Relations
Fuzzy relation:
U1 = {New Y
ork, Paris}, U 2 = {Beijing, New Y
ork, London}
R = very far
NY Paris
Beijing 1 .9
NY 0 .7
London .6 .3
R = {(NY
, Beijing): 1, ...}
52
Fuzzy Numbers
Afuzzy number A is a fuzzy set on R:
A must be a normal fuzzy set
Aa must be a closed interval for every a(0, 1]
supp(A) = A0+ must be bounded
53
Basic Types of Fuzzy Numbers
1 1
0 0
1 1
0 0
54
Basic Types of Fuzzy Numbers
1 1
0 0
55
Operations of Fuzzy Numbers
Interval-based operations:
(A B)a =Aa Ba
56
Operations of Fuzzy Numbers
Arithmetic operations on intervals:
[a, b][d, e] = {fg | a f b, d g e}
57
Operations of Fuzzy Numbers
Arithmetic operations on intervals:
[a, b][d, e] = {fg | a f b, d g e}
[a, b] + [d, e] = [a + d, b + e]
[a, b] - [d, e] = [a - e, b - d]
[a, b]*[d, e] = [min(ad, ae, bd, be), max(ad, ae, bd, be)]
[a, b]/[d, e] = [a, b]*[1/e, 1/d] 0[d, e]
58
Operations of Fuzzy Numbers
about 2 about 3
1
about 2 + about 3 = ?
about 2 about 3 = ?
0
2 3 +
59
Operations of Fuzzy Numbers
Discrete domains:
A = {xi: A(xi)} B = {yi: B(yi)}
A B = ?
60
Operations of Fuzzy Numbers
Extension principle:
f: U1 U2 V
induces
~ ~ ~
g: U 1 U 2 V
[g(A, B)](v) = sup{(u1, u2) | v = f(u1, u2)}min{A(u1), B(u2)}
61
Operations of Fuzzy Numbers
Discrete domains:
A = {xi: A(xi)} B = {yi: B(yi)}
(A B)(v) = sup{(xi, yj) | v = xiyj)}min{A(xi), B(yj)}
62
Fuzzy Logic
if x isAthen y is B
x isA*
------------------------
y is B*
63
Fuzzy Logic
View a fuzzy rule as a fuzzy relation
Measure similarity of AandA*
64
Fuzzy Controller
As special expert systems
When difficult to construct mathematical models
When acquired models are expensive to use
65
Fuzzy Controller
IF the temperature is very high
AND the pressure is slightly low
THEN the heat change should be slightly negative
66
Fuzzy Controller
FUZZY
actions Defuzzification CONTROLLER
model
Controlled Fuzzy inference Fuzzy rule
process engine base
Fuzzification
conditions model
67
Fuzzification
0
x0
68
Defuzzification
Center of Area:
x = (A(z).z)/A(z)
69
Defuzzification
Center of Maxima:
M = {z | A(z) = h(A)}
x = (min M + max M)/2
70
Defuzzification
Mean of Maxima:
M = {z | A(z) = h(A)}
x = z/|M|
71
Exercises
In Klir-Yuans textbook: 1.9, 1.10, 2.11, 2.12, 4.5
72