Introduction to Artificial Inteligence

Assignment 6

Written assignment: planning, probabilistic inference, and learning

Justify all answers!

1) We are given the following independence statements about random variables
   A, B, C, D:

      not I({B},{C}|{D})

a) Construct a Bayes network that is consistent with the 
   above set of independence statements.

b) Is the answer above unique? If not, what is the set of possible BNs 
   that is consistent with the statements?

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

     variable         parents
        A               none
        B               none
        C               none
        D               A C
        E               A F
        F               B
        G               D B
        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}, {E} | {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.2, P(B=true)= 0.1, P(E=true|A=F=True) = 0.5,
       P(E=true|A=false,F=true) = 0.1, P(E=true|A=true,F=false) = 0.5, 
       P(E=true|A=F=false) = 0.5
       P(H=true|E=true) = 0.1, P(H=true|E=false) = 0.4, 
       P(F=true|B=true) = 0, P(F=true|B=false) = 0.5 

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

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

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

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

   b) Suppose that is not known whether On(A,B) or On(B,A) 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 the value unit "Million 
    Unspecified-Middle-Eastern-Country Monetary Unit" (MUMECMU for short).
    Assume also that moral considerations are not part of your utility function.

    Forest fires are a disaster that occur with intervals approximately according to an
    exponential distribution. The damage caused by a fire can also be modeled by
    an appropriate distribution. For simplicity, we will use an annual time granularity,
    and assume that the probability of forest fire count per year is as follows:
      a) no forest fire: 0.1
      b) 1 forest fire:  0.6
      c) 2 forest fires: 0.3
    The distribution of forest fire sizes is:
      a) Large: 0.9
      b) Huge: 0.1
    Assume that fire size distributions are independent, and so are fire occurences
    in different years.

    The damage caused by a forest fires are as follows (depending on whether you have
    fire-extinguishing air-craft):
      a) Large: 10 MUMECMU if you have no aircraft, 2 MUMECMU if you have at least 1 aircraft
      b) Huge:  300 MUMECMU if you have no aircraft, 50 if you have at least one aircraft,
                but only 10 MUMECMU if you have 2 or more aircraft.

    You need to decide whether to purchase fire-extinguishing aircraft, and if so,
    how many. Each aircraft costs 60 MUMECMU, and maintainance costs of each
    aircraft is 1 MUMECMU per year. 

    A) Which is the best policy (resp. worst) from the candidates below,
       assuming that the lifetime of each aircarft is 5 years, and assuming simple 
       5-year cumulative rewards, for the following cases:
     a) Do not purchase any aircraft (since they are expensive and huge fires
        have not happened yet).
     b) Do not purchase any aircraft, only do so after the first huge fire.
     c) Immediately purchase 1 aircraft.
     d) Immediately purchase 2 aircraft.

    B) Repeat for discounted rewards, with a discounting factor of 0.2.

    C) In a year that is considered a "global heat wave", the distribution
       of forest fire sizes changes so that a huge fire now has a probability
       of 0.3, and a large fire 0.7. Repeat A assuming
       that the probability of a "global heat wave" year occurence is independent
       and with a probability of 0.1

    D) Giru Heller can predict "global heat wave" years with absolute accuracy,
       but charges 1 MUMECMU for each year predicted. Should we pay him, and if yes,
       for which years out of the next 5 years?

6) Consider the following Canadian traveller problem instance.

   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.
     (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
   The cost factor K for crossing an icy edge is 10.
   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.

   b3)In addition, from node I only, and before it starts moving,
      the agent can perform a SENSE action
      for a cost of 1, which results in the agent knowing the state of
      the edge (V2, G). Re-compute the optimal policy for this case.

7)  A principal researcher in the Canadian-traveler problem research project
    would like to construct a decision procedure based on results from hiring
    employees in the IMG4 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),  C programming ability (B) Self motivation (C), grade in AI (D).
    The target attribute is the "decision", whether to hire or not.

  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      L      70             N
   1      F      M      95             Y
   1      T      L      70             N
   2      F      H      95             Y
   2      T      M      95             N
   2      T      M      80             N
   2      T      H      95             Y
   2      T      H      80             Y

  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 5, 2011, 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.