Introduction to Artificial Inteligence

Assignment 6

Written assignment: planning, probabilistic inference, and learning

Justify all answers!

1) We have the following distribution over the binary variables A, B, C, D, given as a full table:

   A     B     C     D   probability
   F     F     F     F   0.0
   F     F     F     T   0.05
   F     F     T     F   0.025
   F     F     T     T   0.05
   F     T     F     F   0.0
   F     T     F     T   0.05
   F     T     T     F   0.025
   F     T     T     T   0.05
   T     F     F     F   0.0
   T     F     F     T   0.15
   T     F     T     F   0.075
   T     F     T     T   0.15
   T     T     F     F   0.0
   T     T     F     T   0.15
   T     T     T     F   0.075
   T     T     T     T   0.15

a) Construct the Bayes network that most compactly describes the 
   distribution (i.e. one that has the smallest number of arcs). 

b) Is the answer above unique? If not, what is the set of possible BNs 
   that describe the distribution compactly?

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

     variable         parents
        A               none
        B               none
        C               none
        D               A C
        E               A B
        F               B
        G               D F
        H               C E

    a) Is this network a poly-tree?
    b) Is this network (directed-path) singly connected?
    c) Determine the truth of the following independence
       statements (using d-separation):
       1)  I({D}, {E} | {})
       2)  I({D}, {E} | {A})
       3)  I({D}, {E} | {A, G})
       4)  I({B}, {G} | {D, F})
       5)  I({B}, {C} | {})
       6)  I({B}, {C} | {H})
    d) Assume that the nodes are binary-valued.
       Suppose that P(A=true) = 0.4, P(B=true)= 0.2, P(E=true|A=B=True) = 0.5,
       P(E=true|A=false,B=true) = 0.1, P(E=true|A=true,B=false) = 0.5, P(E=true|A=B=false) = 0.5
       P(H=true|E=true) = 0.1, P(H=true|E=false) = 0.4, 

       Find P(A=true | B=true, E=true, H=true)

       Hint: you may want to preprocess to get rid of nodes before doing any computation.

3) You need to construct a 6-input neural network that has value 1 in the 
   output just when the number of its inputs that are "on" is either 1
   or 4 (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!)

4) a) For the blocks world as defined in class, show how POP constructs the plan
      (that is, show all partial plans from the initial plan until a correct
      plan is reached) for initial state:
    C  D

      and the goal state cointaining: On(A,B) and On(B,C)

   b) Suppose that is not known whether On(B,D) or On(D,B) in the initial state,
      and that there is an operator "Check(On(x,y))" which results in knowing whether
      this is true or not. Show how a conditional plan is constructed for the above

5)  Consider the following scenario, occuring in a certain middle-eastern country.*
    We will assume that you are a risk-neutral, i.e. that
    your utility function is linear in value unit discused below (morts).
    Assume also that moral considerations are not part of your utility function.
    A well-known band of criminals has stolen your FOO, is 
    threatening to destroy it immediately (a damage of 1 mort), and will only return it to you if you
    give them your mojo (C)** instead. Surrendering your mojo is not of immediate
    material damage, but may cause you a loss in the future. 
    With probability 0.5 this will cause a loss
    of 1 mort next fortnight, and additionally with 
    probability 0.4, independent of the above, it will cause a damage of 10 morts
    the one fortnight after the next. Your options are as follows:

    a) Do nothing, and then the criminals destroy your FOO.
    b) Surrender your mojo, and possibly encur the respective future losses.
    c) Request the police to try a raid to recover your FOO. Since
       you do not know where it is, the results are as follows:
       With probability 0.1 they will succeed, and recover your FOO.
       With probability 0.1, this will cause a loss of 1 mort, regardless of
       whether they succeed in recovering your FOO or not.

    5.1) What is your optimal course of action? Consider two reward accumulation functions:
       a) Simple sum of rewards.
       b) Discounted sum of rewards with a discounting factor of 0.2 (per fortnight).

    5.2) Would the answer be different, if in surrendering your mojo, there is
         in addition a probability of 0.5 that the band of criminals will steal
         your FOO again after 2 fortnights (and then leave you with the same options?)

    5.3) In 5.1, suppose that an informer can provide information that
         will increase the probability of success of a police raid to 0.5. How much
         should you be willing to pay for such information (in both cases a and b)?


6) Consider the following belief-state MDP: the Canadian traveller problem.

   The (undirected) graph has 4 vertices, as follows:
     (I, V1, V2, G)
   All vertices are directly connected by edges.
   The edges are as follows:
     (I, V1), weight 1, no ice.
     (I, V2), weight 2, no ice.
     (I, G), weight 10, no ice.
     (V1, V2), weight 3, probability of ice 0.5
     (V1, G), weight 1, probability of ice 0.8
     (V2, G), weight 2, probability of ice 0.5
   b1) Formalize the above problem as a (belief-state) MDP, i.e. 
       what are the states, the transition probability
       function, and the reward function?

   b2) Find the optimal policy. You may assume that the robot starts
       at vertex I in order to save some computation.

7)  A project leader in the IMG4 consortium would like to construct a
    decision procedure based on results from hiring employees in the KITE
    consortium. The decision procedure will be based on a decision tree, using information
    in the case database. Attributes for each employee are:
    degree level (A),  Java programming ability (B), self-motivation (C), grade in AI (D).
    The target attribute is the "decision", describing the amount of money to
    pay the employee.

  a) Construct by hand (using the greedy search using the best information
     gain heuristic) a consistent decision tree for the following table:

     input variables               decision
   A      B      C      D
   1      F      M      95             8
   1      T      L      70             4
   1      F      L      70             4
   2      T      M      95             6
   2      T      M      80             6
   2      T      H      95             8
   2      T      H      80             8
   2      F      H      95             8

  b) Is a more compact (fewer internal nodes) decision tree possible for the above table?
     If no - prove it. If yes, which tree?

Deadline: Wednesday, January 13, 2010, at 12 noon.

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

* Disclaimer: any seeming identification with existing countries, institutions, political parties, or people, is unintentional.

** Mojo: copyright some film studio we do not recall.