Introduction to Artificial Inteligence

Assignment 6


Written assignment: inference and learning

Justify all answers!

1) A) Use situation calculus (i.e. the result function, and fluents) to
   write down the axioms for the following modified wumpus world example.
   The robot needs to get the gold and climb back out.
   Stairs are at (1, 1) always.
   Actions are: 
   a) Move(dx, dy): the robot moves by dx in the x direction, and by dy
      in the y direction (this robot can move omnidirectionally).
   b) Grab: if the gold is in the same room as the robot, the predicate
      HasGold becomes true as a result.
   c) Climb: if the robot is at the room with the stairs, the result is
      that the robot and all it has gets out (success).

    Fluents (situation-dependent predicates) are: 
        GoldAt(x, y, s)  
        HasGold(s)           (Robot has the gold)
        RobotAt(x, y, s)     (Robot at x, y in situation s)
        Success(s)           (In situation s, robot and gold ouside maze)

    B) Now, you need to prove that, for the initial situation S where the
       robot is at (1,1), and the gold at (1,2), the action sequence:
            Move(0, 1), Grab, Move(0, -1), Climb
       results in success, that is, prove that:
         Success(result(Climb, 
                        result(Move(0, -1),
                               result(Grab,
                                      result(Move(0, 1), S))))

    Can you do it with your original formulation (show the proof!).
    If not, add the requisite axioms and complete the proof.

2) Write down the axioms and facts for example below in FOPC:
   The taxonomic hierarchy for animals, contains dogs, and cats,
   which are disjoint but not exhaustive. Dogs
   in turn contains German shepherds and chihuahuas (which are
   disjoint). All dogs are carnivorous.
   German shepherds are large. All large dogs can be guard dogs,
   unless they are deaf. Fido is a deaf German shepherd.

   a) Convert the knowledge base into IMPLICATION normal form
   b) Show how this knowledge-base should be indexed - using
      a table.
   c) Prove or disprove by using resolution  (or argue that neither 
      can be done):
      1) Fido is an animal.
      2) Fido is large.
      3) Fido can be a guard dog.
      4) If Fido is a chihuahua, then Fido is young.
      5) Fido is carnivorous.
      6) If Poopoo is a cat, then it is not a German Shepherd
      SHOW ALL STEPS, including the relevant unifiers, etc.
   d) Would using INPUT RESOLUTION only change the answers to c?
   e) Can you prove all the above using only either forward or
      backward chaining?

3) Consider the following variables and their immediate causes (parents):

     variable         parents
-------------------------------
        A               none
        E               none
        B               A
        C               A E
        D               A
        F               B C A

    a) Is this network a poly-tree?
    b) Determine the truth of the following independence
       statements (using d-separation):
       1)  I({A}, {E} | {})
       2)  I({A}, {E} | {B})
       3)  I({A}, {E} | {C})
       4)  I({A}, {E} | {F})
       5)  I({A}, {C, F} | {B})
       6)  I({A}, {F} | {B, C})
    c) Determine at least 2 different ways to convert the network into
       a poly-tree using cutset conditioning.
    d) Suppose that P(A) = 0.9, P(E) = 0.3, P(B|A) = 0.1, P(B|~A)  = 0.8.
       Find P(A|E)

4) You need to construct a 4-input neural network that has value 1 in the 
   output just when exactly 2 of its inputs are 1, and 0 otherwise
   (assume inputs are in {0, 1}).
   a) Can this be done without hidden units?
   b) Show a network using threshold elements that performs
      the required computation (specify the weights, too!)

5) a) Using the perceptron learning rule (the "delta" rule), show the steps
      of learning 3-input function OR with a single perceptron
      and a step activation function with threshold 1. Initially all
      weights are 0.7, and the learning rate is 0.4.

   b) Is it possible to combine back-propagation with simulated annealing, and
      if so, how?

6) a) Construct by hand a decision tree for the following table, a set of
      examples for classifying oranges, where the attributes are:
      color (A), shape (B), surface (C), and smell (D).
      Use the greedy algorithm studied in class, with information gain
      as the heuristic for deciding the attribute ate each sub-tree.

     input variables               quality
   A      B      C      D
--------------------------------------------
light  sphere  rough   sharp          1
light  sphere  rough   mild           1
light  sphere  hairy   sharp          0
light  oval    rough   sharp          1
light  oval    rough   mild           0
light  oval    smooth  sharp          1
dark   sphere  hairy   sharp          0
dark   sphere  rough   mild           1
dark   sphere  smooth  mild           1
dark   oval    hairy   sharp          0
dark   oval    hairy   mild           0
dark   oval    smooth  mild           0


   b) Is a decision tree with fewer internal nodes possible? Which?
   c) Which node will be pruned first, based on least information gain?



Deadline: Sunday, June 8, 2003, at 11AM.

Note: submission (as well as WORK) on this exercise is SOLO (that is, NOT in pairs or other groups of size > 1)