Transcript Document

Outline for 4/11
•Bayesian Networks
•Planning
Sources of Uncertainty
• Medical knowledge in logic?
– Toothache <=> Cavity
• Problems
– Too many exceptions to any logical rule
• Tiring to write them all down
• Hard to use enormous rules
– Doctors have no complete theory for the domain
– Don’t know the state of a given patient state
• Agent has degree of belief, not certain knowledge
– Initial States
– Actions effects
– Exogenous effects
2
Probability As “Softened Logic”
• “Statements of fact”
– Prob(TB) = .06
• Soft rules
– TB  cough
– Prob(cough | TB) = 0.9
• (Causative versus diagnostic rules)
– Prob(cough | TB) = 0.9
– Prob(TB | cough) = 0.05
• Inference: ask questions about some facts given
others
Probabilistic Knowledge Representation
and Updating
• Prior probabilities:
– Prob(TB) (probability that population as a whole, or population
under observation, has the disease)
• Conditional probabilities:
– Prob(TB | cough)
• updated belief in TB given a symptom
– Prob(TB | test=neg)
• updated belief based on possibly imperfect sensor
– Prob(“TB tomorrow” | “treatment today”)
• reasoning about a treatment (action)
• The basic update:
– Prob(H)  Prob(H|E1)  Prob(H|E1, E2)  ...
Basics
• Random variable takes values
– Cavity: yes or no
• Joint Probability Distribution
• Unconditional probability
(“prior probability”)
– P(A)
– P(Cavity) = 0.1
• Conditional Probability
Ache
Cavity
0.04
No Cavity 0.01
No Ache
0.06
0.89
– P(A|B)
– P(Cavity | Toothache) = 0.8
• Bayes Rule
– P(B|A) = P(A|B)P(B) / P(A)
6
Conditional Independence
• “A and P are independent given C”
• P(A | P,C) = P(A | C)
Ache
Cavity
Probe
Catches
C
F
F
F
F
T
T
T
T
A
F
F
T
T
F
F
T
T
P
F
T
F
T
F
T
F
T
Prob
0.534
0.356
0.006
0.004
0.048
0.012
0.032
0.008
7
Conditional Independence
• “A and P are independent given C”
• P(A | P,C) = P(A | C) and also P(P | A,C) = P(P | C)
Suppose C=True
P(A|P,C) = 0.032/(0.032+0.048)
= 0.032/0.080
= 0.4
P(A|C) = 0.032+0.008
0.048+0.012+0.032+0.008
= 0.04 / 0.1 = 0.4
C
F
F
F
F
T
T
T
T
A
F
F
T
T
F
F
T
T
P
F
T
F
T
F
T
F
T
Prob
0.534
0.356
0.006
0.004
0.012
0.048
0.008
0.032
8
Conditional Independence
• Can encode joint probability distribution in
compact form
Ache
C
T
F
P(A)
0.4
0.02
C
T
F
P(P)
0.8
0.4
Cavity
P(C)
.01
Probe
Catches
C
F
F
F
F
T
T
T
T
A
F
F
T
T
F
F
T
T
P
F
T
F
T
F
T
F
T
Prob
0.534
0.356
0.006
0.004
0.012
0.048
0.008
0.032
9
Causality
• Probability theory represents correlation
– Absolutely no notion of causality
– Smoking and cancer are correlated
• Bayes nets use directed arcs to represent causality
–
–
–
–
Write only (significant) direct causal effects
Can lead to much smaller encoding than full JPD
Many Bayes nets correspond to the same JPD
Some may be simpler than others
11
Creating a Network
• 1: Bayes net = representation of a JPD
• 2: Bayes net = set of cond. independence statements
• If create correct structure
• Ie one representing causlity
– Then get a good network
• I.e. one that’s small = easy to compute with
• One that is easy to fill in numbers
13
Example
My house alarm system just sounded (A).
Both an earthquake (E) and a burglary (B) could set it off.
John will probably hear the alarm; if so he’ll call (J).
But sometimes John calls even when the alarm is silent
Mary might hear the alarm and call too (M), but not as reliably
We could be assured a complete and consistent model by fully
specifying the joint distribution:
Prob(A, E, B, J, M)
Prob(A, E, B, J, ~M)
etc.
Structural Models
Instead of starting with numbers, we will start with structural
relationships among the variables
 direct causal relationship from Earthquak to Alarm
 direct causal relationship from Burglar to Alarm
 direct causal relationship from Alarm to JohnCall
Earthquake and Burglar tend to occur independently
etc.
Possible Bayes Network
Earthquake
Burglary
Alarm
JohnCalls
MaryCalls
16
Complete Bayes Network
Burglary
Earthquake
P(B)
.001
Alarm
JohnCalls
A
T
F
P(J)
.90
.05
B
T
T
F
F
E
T
F
T
F
P(E)
.002
P(A)
.95
.94
.29
.01
MaryCalls
A P(M)
T .70
F .01
18
Cond. Independence in Bayes Nets
• If a set E d-separates X and Y
– Then X and Y are cond. independent given E
• Set E d-separates X and Y if every undirected path
between X and Y has a node Z such that, either
Z
X
Z
E
Y
Z
Z
Why important???
P(A | B,C) =  P(A) P(B|A) P(C|A)
23
Two Remaining Questions
• How do we add evidence to the network
– I know for sure there was an Earthquake Report
– I think I heard the Alarm, but I might have been mistaken
– My neighbor reported a burglary ... for the third time this week.
• How do we compute probabilities of events that are
combinations of various node values
– Prob(R, P | E)
– Prob(B | N, ~P)
– Prob(R, ~N | E, ~P)
(predictive)
(diagnostic)
(other)
Inference=Query Answering
• Given exact values for evidence variables
• Compute posterior probability of query variable
P(B)
Burglary .001
Alarm
JonCalls
A P(J)
T .90
F .05
Earthq
B
T
T
F
F
P(E)
.002
E P(A)
T .95
F .94
T .29
F .01
A P(M)
MaryCall T .70
F .01
• Diagnostic
– effects to causes
• Causal
– causes to effects
• Intercausal
– between causes of
common effect
– explaining away
• Mixed
27
Algorithm
• In general: NP Complete
• Easy for polytrees
– I.e. only one undirected path between nodes
• Express P(X|E) by
– 1. Recursively passing support from ancestor down
• “Causal support”
– 2. Recursively calc contribution from descendants up
• “Evidential support”
• Speed: linear in the number of nodes (in polytree)
28
Simplest Causal Case
Burglary P(B)
.001
• Suppose know Burglary
• Want to know probability of alarm
– P(A|B) = 0.95
Alarm
B P(A)
.95
T
.01
F
Burglary P(B)
.001
Alarm
B P(A)
.95
T
.01
F
Simplest Diagnostic Case
• Suppose know Alarm ringing
& want to know: Burglary?
• I.e. want P(B|A)
P(B|A) =P(A|B) P(B) / P(A)
But we don’t know P(A)
1 =P(B|A)+P(~B|A)
1 =P(A|B)P(B)/P(A) + P(A|~B)P(~B)/P(A)
1 =[P(A|B)P(B) + P(A|~B)P(~B)] / P(A)
P(A) =P(A|B)P(B) + P(A|~B)P(~B)
P(B | A) =P(A|B) P(B) / [P(A|B)P(B) + P(A|~B)P(~B)]
= .95*.001 / [.95*.001 + .01*.999] = 0.087
Normalization
P(X|Y) P(Y)
1 P(X|Y) P(Y)
P(Y | X) =
=
P(X)
P(X|Y)P(Y) + P(X|~Y)P(~Y)
=  P(X|Y) P(Y)
P(B)
Burglary .001
P(B | A) =  P(A|B) P(B)
Alarm
B P(A)
T .95
F .01
P(A | J) =  P(J|A) P(A)
JonCalls
A P(J)
T .90
F .05
P(B | J) =  P(B|A) P(A|J) P(B)
Inferences
P(A | B, J) =  P(J|A) P(A|B)
P(B)
Burglary .001
Alarm
JonCalls
B P(A)
T .95
F .01
A P(J)
T .90
F .05
why?
What about P(A|J)?
General Case
U1
• Express P(X | E)
in terms of
contributions of
Ex+ and Ex-
Um
...
+
Ex
X
Z1j
Ex-
Znj
Y1
...
Yn
• Compute contrib
of Ex+ by
computing effect
of parents of X
(recursion!)
• Compute contrib
of Ex- by ...
Multiply connected nets
Quake
Burglary
Alarm+Radio
Radio
Alarm
Jon
Call
Burglary
Mary
Call
Quake
Jon
Call
Mary
Call
• Cluster into polytree
34
Decision Networks (Influence Diagrams)
Choice of
Airport Site
Air Traffic
Deaths
Litigation
Noise
Construction
Cost
U
35
Evaluation
• Iterate over values to decision nodes
– Yields a Bayes net
• Decision nodes act exactly like chance nodes with known
probability
– Calculate the probability of all chance nodes connected
to U node
– Calculate utility
• Choose decision with highest utility
36
Planning
• Input
– Description of initial state of world (in some KR)
– Description of goal (in some KR)
– Description of available actions (in some KR)
• Output
– Sequence of actions
37
Input Representation
• Description of initial state of world
– Set of propositions:
– ((block a) (block b) (block c) (on-table a) (on-table
b) (clear a) (clear b) (clear c) (arm-empty))
• Description of goal (i.e. set of desired worlds)
– Logical conjunction
– Any world that satisfies the conjunction is a goal
– (:and (on a b) (on b c)))
• Description of available actions
How Represent Actions?
• Simplifying assumptions
–
–
–
–
Atomic time
Agent is omniscient (no sensing necessary).
Agent is sole cause of change
Actions have deterministic effects
• STRIPS representation
– World = set of true propositions
– Actions:
• Precondition: (conjunction of literals)
• Effects (conjunction of literals)
north11
a
W0
a
W1
north12
a
W2
STRIPS Actions
• Action = a function from world-state to world-state
• Precondition says when function defined
• Effects say how to change set of propositions
north11
a
W0
north11
precond: (:and (agent-at 1 1)
(agent-facing north))
a
W1
effect: (:and (agent-at 1 2)
(:not (agent-at401 1)))
Action Schemata
• Instead of defining: pickup-A and pickup-B and …
• Define a schema:
(:operator pick-up
:parameters ((block ?ob1))
:precondition (:and (clear ?ob1) (on-table ?ob1) (arm-empty))
:effect (:and (:not (on-table ?ob1))
(:not (clear ?ob1))
(:not (arm-empty))
(holding ?ob1)))
Planning as Search
• Nodes
World states
• Arcs
Actions
• Initial State
The state satisfying the complete description of the initial conds
• Goal State
Any state satisfying the goal propositions
Forward-Chaining World-Space Search
Initial
State
C
A B
Goal
State
A
B
C
Backward-Chaining World-Space Search
• Problem: Many possible goal states
are equally acceptable.
• From which one does one search?
A
B
C D E
A D
B
C
E
Initial State is
completely defined
C
D
A B E
***
A
B
C
D
E
Planning as Search 2
• Nodes
Partially specified plans
• Arcs
Adding + deleting actions or constraints (e.g. <) to plan
• Initial State
The empty plan
• Goal State
A plan which when simulated achieves the goal
Plan-Space Search
pick-from-table(C)
put-on(C,B)
pick-from-table(C)
pick-from-table(B)
• How represent plans?
• How test if plan is a solution?
Planning as Search 3
• Phase 1 - Graph Expansion
– Necessary (insufficient) conditions for plan existence
– Local consistency of plan-as-CSP
• Phase 2 - Solution Extraction
– Variables
• action execution at a time point
– Constraints
• goals, subgoals achieved
• no side-effects between actions
Planning Graph
Proposition
Init State
Action
Time 1
Proposition
Time 1
Action
Time 2
48
Constructing the planning graph…
• Initial proposition layer
– Just the initial conditions
• Action layer i
– If all of an action’s preconds are in i-1
– Then add action to layer I
• Proposition layer i+1
– For each action at layer i
– Add all its effects at layer i+1
Mutual Exclusion
• Actions A,B exclusive (at a level) if
– A deletes B’s precond, or
– B deletes A’s precond, or
– A & B have inconsistent preconds
• Propositions P,Q inconsistent (at a level) if
– all ways to achive P exclude all ways to achieve Q
50
Graphplan
• Create level 0 in planning graph
• Loop
– If goal  contents of highest level (nonmutex)
– Then search graph for solution
• If find a solution then return and terminate
– Else Extend graph one more level
51
Searching for a Solution
• For each goal G at time t
– For each action A making G true @t
• If A isn’t mutex with a previously chosen action, select it
• If no actions work, backup to last G (breadth first search)
• Recurse on preconditions of actions selected, t-1
Proposition
Init State
Action
Time 1
Proposition
Time 1
Action
Time 2
52
Dinner Date
Initial Conditions: (:and (cleanHands) (quiet))
Goal:
(:and (noGarbage) (dinner) (present))
Actions:
(:operator carry :precondition
:effect (:and (noGarbage) (:not (cleanHands)))
(:operator dolly :precondition
:effect (:and (noGarbage) (:not (quiet)))
(:operator cook :precondition (cleanHands)
:effect (dinner))
(:operator wrap :precondition (quiet)
:effect (present))
Planning Graph
noGarb
carry
cleanH
cleanH
dolly
quiet
quiet
cook
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop
Are there any exclusions?
noGarb
carry
cleanH
cleanH
dolly
quiet
quiet
cook
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop
Do we have a solution?
noGarb
carry
cleanH
cleanH
dolly
quiet
quiet
cook
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop
Extend the Planning Graph
noGarb
carry
cleanH
noGarb
carry
cleanH
dolly
quiet
cleanH
dolly
quiet
cook
quiet
cook
dinner
wrap
dinner
wrap
present
0 Prop
1 Action
2 Prop
present
3 Action
4 Prop
One (of 4) possibilities
noGarb
carry
cleanH
noGarb
carry
cleanH
dolly
quiet
cleanH
dolly
quiet
cook
quiet
cook
dinner
wrap
dinner
wrap
present
0 Prop
1 Action
2 Prop
present
3 Action
4 Prop
Summary Planning
• Reactive systems vs. planning
• Planners can handle medium to large-sized problems
• Relaxing assumptions
–
–
–
–
Atomic time
Agent is omniscient (no sensing necessary).
Agent is sole cause of change
Actions have deterministic effects
• Generating contingent plans
– Large time-scale Spacecraft control