Final Exam Review CPS721: Artificial Intelligence
December 1, 2020
Final Exam Review December 1, 2020 1 / 12
Query answering from a B.N.
In general we compute a conditional probability for a Query random variable, i.e., P(Query|Evidence) given a j.p.d. P(Query,Evidence,Other). By definition of cond.
P(Query,Evidence)
probability, P(Query|Evidence) = . Therefore, using marginalization P(Evidence)
P(Query|Evidence) = Other P(Query, Evidence, Other) . Query,Other P(Query,Evidence,Other)
In our example, a bored guard who does not listen to radio observes that both Martin and Norman are late, and would like to compute probability of a train strike:
O P(O,T=t,M=t,N=t) P(T=t|M=t,N=t)= P(O,T,M=t,N=t) .
O,T
P(O,T,M,N)= P(O) · P(T) · P(M |O,T) · P(N |T).
P(O=true)=0.4 and P(T=true)=0.1
O P(O,T=t,M=t,N=t)=P(O=t,T=t,M=t,N=t)+P(O=f,T=t,M=t,N=t)= 0.4* 0.1* 0.8* 0.8 + 0.6* 0.1* 0.6* 0.8 = 0.0256 + 0.0288 = 0.0544.
O T P(M|O,T) P(N,T) t t 0.8 0.8
t f 0.5 0.1
f t 0.6 0.8
f f 0.5 0.1
O,T P(O,T,M=t,N=t)= /* The sum of 4 terms with O={t,f} and T={t,f} */ 0.0544 + P(O=t,T=f,M=t,N=t) + P(O=f,T=f,M=t,N=t) =
0.0544 + 0.4* 0.9* 0.5* 0.1 + 0.6* 0.9* 0.5* 0.1 = 0.0544 + 0.018 + 0.027 = 0.0994 Thus,P(T=t |M=t,N=t)=0.0544/0.0994=0.547
Final Exam Review December 1, 2020 3 / 12
O T P(M|O,T) tt 0.8
tf 0.5
ft 0.6 ff 0.5
T t f
P(N | T) 0.8 0.1
Bayesian Network: ’s example
Martin oversleeps
P(O) =0.4
M Martin late
Train strike
P(T) =0.1
Random variables (r.v.) O=”martin Over- sleeps”, T=”Train strike”, M=”Martin late”, N=”Norman late” take values: t (true), f (false). Note that conditional probability for M means P(M=t |O,T), and P(M=f |O,T)=1– P(M=t|O,T). Similarly, cond. prob. table for N defines P(N=true|T), and P(N=false |T)=1–P(N=true|T). Prior probabilities P(T=t)=0.1, i.e., P(T=f)=0.9, and P(O=t)=0.4, i.e., P(O=f)=0.6 Since all r.v. O,T,M,N are binary, without BN we need 24 numbers to define j.p.d. P(O,T,M,N). But with BN,we need only 1+1+4+2=8 numbers for j.p.d.
N Norman late
Using the bottom-up algorithm from class, we get an expression for j.p.d. P(O,T,M,N)= P(M |N,O,T) · P(N,O,T)= /*simplify using B.N., then expand P(N,O,T)*/ P(M |O,T)· P(N |O,T) * P(O,T)= /*simplify P(N|O,T), then expand P(O,T)*/ P(M |O,T) · P(N |T) · P(O) · P(T).
Acknowledgement: this example is taken from Professor online tutorial posted at http: //www.eecs.qmul.ac.uk/∼norman/BBNs/BBN_Tutorial__About_this_section.htm
Final Exam Review December 1, 2020 2 / 12
Query answering: explaining away
NoteP(T=t |M=t,N=t)=0.547ismuchhigherthanpriorprobability0.1foratrain strike. So, the guard can conclude that since both Martin and Norman are late, it is more likely than not this happened due to a train strike.
Similarly, one can compute that P(O=t | M=t,N=t)=0.44, but this is lower than the above probability 0.547
Therefore, the security guard can conclude that lateness of Martin can be explained away by a train strike rather than by the fact that he overslept.
Acknowledgement: this example is taken from http://www.eecs.qmul.ac.uk/∼norman/BBNs/The_notion_of__explaining_away__evidence.htm
Final Exam Review December 1, 2020 4 / 12
Grammar for parsing
A grammar for parsing given noun phrases and simple sentences. It will be given to you. But practice with examples to make sure you know this grammar well. Note that if you parse a noun phrase, then the rules (1)-(4) are irrelevant.
1 S->NPVP
2 VP -> copula_verb Mods
3 VP -> transitive verb NP Mods
4 VP -> intransitive verb Mods
5 NP -> proper_noun
6 NP -> article NP2
7 NP2 -> adjective NP2
8 NP2 -> common_noun Mods
9 Mods->[]
10 Mods -> PP Mods
11 PP -> preposition NP
Final Exam Review
December 1, 2020
5 / 12
Parsing an ambiguous sentence: funny case
In a funny reading of this sentence, it is a cow who uses an ax. This meaning is rendered by a short NP=[a,farmer] and by applying the rule (10) to Mods produced from the rule (3): Mods -> PP Mods. Subsequently, the rule 11 is applied to PP=[with,an,ax] that starts with a preposition “with”, but the latter Mods is empty, i.e., the rule 9 is applied.
Final Exam Review December 1, 2020 7 / 12
Parsing an ambiguous sentence: an example
S=[an,enraged,cow,injured,a,farmer,with,an,ax]
(1) S consists of NP followed by VP. Then, the rule (3) VP -> transitive verb NP Mods
applies, since the verb “injure” is a transitive verb that requires an object NP and Mods that can possibly modify how the action was performed.
There are two different parsing trees for this sentence. The rule (3) expands VP into a transitive verb “injured”, NP and Mods. Then, the rule (6) applies, and NP expands into an article “a” and NP2. For NP2, since “farmer” is a common noun, the rule (8) applies and produces the second Mods node.
Therefore, we get a partial parsing tree with 2 different Mods nodes. For one of them, we can apply the rule (9), bot to another node we can apply the rule (10). Since there are 2 Mods nodes, we can produce 2 different parsing trees.
Final Exam Review December 1, 2020
Parsing an ambiguous sentence: intended meaning
In an intended meaning of this sentence, the farmer has an ax, but not the cow. This meaning is rendered by applying the rule (9) to Mods originating from rule (3), parsing NP arising from (3) as article followed by NP2 (see rule 6), and then applying the rule (8) to NP2 -> common_noun Mods, where common_noun is “farmer”, and Mods=[with,an,ax] characterizes the farmer as PP that consists of a preposition “with” followed by a NP=[an,ax].
6 / 12
Final Exam Review December 1, 2020
8 / 12
Situations and fluents: Example 1, preconditions
The robot can go from a location L1 to L2: action go(L1, L2). The robot can do 2 other actions: grab(X), if it does not hold anything, and drop(X), if it is holding X. The robot can hold at most one item in S: fluent holding((X,S). Write correct precondiiton rules followed by SSA rules.
Let’s consider also a fluent at(X,L,S) that is true, when X (the robot, or the object) is at a location L in situation S. Represent topology with a predicate adjacent(L1, L2) that is true if the agent can navigate from L1 to L2. When it is possible for the robot to go from L1 to L2 ?
poss(go(L1,L2),S):- at(robot,L1,S),adjacent(L1,L2), not L1=L2.
When it is possible for the robot to grab an object Obj ? poss(grab(Obj), S) :- at(robot,L,S), at(Obj,L,S),
not holding(Anything,S).
When it is possible for the robot to drop an object Obj ? poss(drop(Obj), S) :- holding(Obj,S).
How to write SSAs rules specifying changes in fluents after executing actions?
Final Exam Review December 1, 2020 9 / 12
Example 2 from Lab 9: elevator, preconditions
Actions (terms): board(F,P) – a person P boards the elevator at floor F depart(F,P) – a person P exits fromm the elevator at floor F
up(F1,F2) – elevator moves up from floor F1 to floor F2
down(F 1, F 2) – elevator moves down from floor F 1 to floor F 2
Fluents (predicates): boarded(P,S) – a person P has boarded the elevator served(P,S) – a person P was served, i.e., P arrived at a destination liftAt(F,S) – the elevator is at a floor F in situation S
Non-fluent (static) predicates: floor (F ) – a positive integer F is a floor passenger(P) – P is a person to be served once only
origin(P,F) – a person P waits for the elevator at floor F
destin(P,F) – a person P wants to arrive at floor F
poss(board(F,P),S) : −passenger(P),origin(P,F),not boarded(P,S), not served(P,S),liftAt(F,S).
poss(depart(F,P),S) : −passenger(P),destin(P,F),boarded(P,S), not served(P,S),liftAt(F,S).
poss(up(F1,F2),S) : −floor(F1),floor(F2),F2 > F1,liftAt(F1,S). poss(down(F1,F2),S) : −floor(F1),floor(F2),F1 > F2,liftAt(F1,S).
How to write SSAs for fluents boarded(P,S), served(P,S), liftAt(F,S) ? Which actions makes them true? Which actions make them false ?
Final Exam Review December 1, 2020 11 / 12
Example 1: SSAs
Obviously, only the action go(L1, L2) can have any effect on robot’s location. In other words, if the robot did not go recently to another location, it is located where it was in the previous situation. How to write SSAs for fluent at(robot, Loc, S) ?
at(robot, Lnext, [go(L,Lnext) | S]).
at(robot, L, [A | S] ) :- not A=go(L,Anywhere), at(robot,L,S).
Exercise: for the object that is carried by the robot, write rules how location of this object will change.
How does the fluent holding(Obj, S) change after doing actions ?
holding(X, [grab(X) | S]).
The robot holding an object X if it did the action grab(X).
Suppose the robot is already holding something. When it continues to hold its object ?
holding(X, [A | S]) :- holding(X,S), not A = drop(X).
If the robot is holding the object X in previous situation S, it will hold X in the next situation after executing an action A, unless the most recent action was drop(X). Note the RHS can start with a recursive call, or with a negation “not A=drop(X)”. This is OK, because in queries the variable X will always be instantiated in precondition rules.
Note that action go(L1, L2) has no effect on whether the robot is holding any object. For this reason, it is not mentioned anywhere in the SSAs for the fluent holding(X,S).
Final Exam Review December 1, 2020
Example 2: elevator from Lab 9, SSAs
Fluent boarded(P,S) becomes true, when a person enters the elevator. It becomes false when a person exits from the elevator.
boarded(P, [board(F,P) | S]).
boarded(P, [A | S] ) :- not A=depart(F,P), boarded(P,S).
Fluent served(P,S) becomes true when a passenger exits. It cannot become false since for simplicity we assume all passengers are served once only.
served(P, [depart(F,P) | S]).
served(P, [A | S]):- served(P,S). /* There is no action to make it false.*/
Fluent liftAt(F,S) becomes true when the elevator arrives at a floor F either after moving up, or moving down. This fluent remains true, unless the elevator moves.
liftAt(F2, [up(F1,F2) | S]).
liftAt(F2, [down(F1,F2) | S]).
liftAt(F,[A|S]):- not A=up(F,FU), not A=down(F,FD), liftAt(F,S).
Exercise: develop reasonable declarative heuristics for this application.
liftAt(0,[ ]). /* Initial state */ goal_state(S) :- served(p0,S), served(p1,S), served(p2,S), served(p3,S). passenger(p0). passenger(p1). passenger(p2). passenger(p3).
origin(p0,15). origin(p1,2). origin(p2,2). origin(p3,7).
destin(p2,18). destin(p3,5). destin(p0,11). destin(p1,0). floor(0). floor(2). floor(5). floor(7). floor(11). floor(15). floor(18).
10 / 12
Final Exam Review December 1, 2020
12 / 12