Artificial Intelligence: Problem Set 7

Assigned: Apr. 16
Due: Apr. 23

Note: I will be grading this, rather than the grader, so if you submit this by email, send it to davise@cs.nyu.edu.

Problem 1

The algorithm for Datalog described in lecture is called backward chaining; it starts with a query, matches the query to a fact or a head of a rule, and generates subqueries from the tail of the rule. An alternative mode of inference is called forward chaining .

The forward chaining algorithm involves the repeated application of the two inference subroutines, "fc-infer-fact", and "fc-infer-rule", defined below, which it runs until no new conclusions can be drawn.

fc-infer-fact(in F : fact; R : rule with one literal in the conditions;
              out G : fact)
  Let R have the form "A => C"
  If R uses some of the same variables names as F, then rename the variables;
  if F matches A under variable binding B 
     then G  := the application of B to C
end fc-infer1

fc-infer-rule(in F : fact; 
                 R : rule with more than one literal in the conditions;
              out Q : rule)
  Let R have the form "A1 & A2 ...  & Ak => C"
  If R uses some of the same variables names as F, then rename the variables;
  If F matches A1 under variable binding B
    then Q := the application of B to "A2 & ...  & Ak => C"
end

For instance if you start with

Fact F1: man(socrates)  
Rule R2: man(X) => mortal(X)
fc-infer-fact will match the tail of R2 to F1 under the variable binding X -> socrates, and infer the new fact "mortal(socrates)".

If you start with

Fact F3: parent(elizabeth,charles) 
Fact F4: female(elizabeth)
Rule R5: female(X) & parent(X,Y) => mother(X,Y)
first, fc-infer-rule applies to F4 and R5 under X -> elizabeth to infer the new rule
Rule R6: parent(elizabeth,Y) => mother(elizabeth,Y)
Second, fc-infer-fact applies to rule F3 and R6 under the binding Y -> charles to infer the new fact
Fact F7: mother(elizabeth,charles).

The entire forward chaining algorithm can be described as follows:

forward-chain(in out FF : set of facts; RR : set of rules)
   NEW := FF union RR;
   loop until NEW is empty
      { pop Z from NEW;
        if Z is a fact then
           loop for R in RR
              if R has form "A => C" and Z matches A then
                 { fc-infer-fact(Z,R,G);
                   if G is not in FF then 
                     { add G to FF;
                       add G to NEW} endif  }
              else if R has form "A1, A2 ... Ak => C" and Z matches A1 then
                 { fc-infer-rule(Z,R,Q);
                   if Q is not in RR then 
                     { add Q to RR;
                       add Q to NEW} endif  } endif endloop
        elseif Z is a rule of the form "A => C" then
           loop for F in FF 
               if F matches A then
                { fc-infer-fact(F,Z,G);
                  if G is not in FF then 
                    { add G to FF;
                      add G to NEW} endif  } endif endloop 
        elseif Z is a rule of the form "A1 ... Ak => C" then
           loop for F in FF 
               if F matches A1 then
                { fc-infer-rule(F,Z,Q);
                  if Q is not in FF then 
                    { add Q to RR;
                      add Q to NEW} endif  } endif endloop endif } endloop
end forward-chain

A. Trace what happens when the forward chaining algorithm is applied to the following knowledge base:

Facts:
F1: parent(elizabeth,charles).
F2: parent(philip,charles).
F3: parent(elizabeth,anne).
F4: parent(philip,anne).
F5: parent(charles,william).
F6: parent(charles,harry).
F7: female(elizabeth).
F8: male(philip).
F9: male(charles).
F10: female(anne).
F11: anc(X,X).

Rules:
R1: parent(X,Y) => child(Y,X).
R2: child(X,Y) => parent(Y,X)
R3: child(X,Y) & female(X) => daughter(X,Y).
R4: parent(X,Y) & anc(Y,Z) => anc(X,Z).
Your trace should show every call to "fc-infer-fact" and "fc-infer-rule" that generates a new fact or rule.

B. It is possible to prove that, for a Datalog knowledge base, the algorithm "forward-chain" is complete with respect to the inference of facts. That is, if F is a fact that is a logical consequence of FF and RR, then F will be returned in the set of facts returned by forward-chain(FF,RR). Give an example to show that "forward-chain" is not complete with respect to the inference of rules; that is, an example of a set of facts FF, a set of rules RR and a conclusion Q such that Q is a logical consequence of FF and RR, but Q is not in the set of rules returned by forward-chain(FF,RR).

Problem 2

Find (do not invent) a short (4 or 5 sentences) narrative text. A paragraph or two from a narrative article in a magazine or newspaper would be fine.

A. As far as is possible, write down the contents of the text in a set of formulas of the form "holds(S,F)" where S is a situation and F is a fluent (in an English language description); "occurs(S1,S2,E)" where S1 and S2 are situations and E is an event (in an English language description); and purely temporal relations between situations (e.g. "S5 occured before S4"; "S6 was less than an hour after S7" etc.)

B. Give three examples of queries that could be answered from your representation.

C. Is there any significant temporal information in this narrative that you have not been able to express in this notation?