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, E, F, G, H:

      I({A,B,C},{D,E}|{})
      I({A,B,C},{F,G,H}|{})
      I({D,E},{F,G,H}|{})
      I({A},{C}|{B})
      I({F},{H}|{})
      
      not I({A},{C}|{})
      not I({D},{E}|{})
      not I({F},{H}|{G})

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 all the statements?

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

     variable         parents
-------------------------------
        A               none
        B               none
        C               A B
        D               A
        E               B
        F               D
        G               D 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}, {F} | {C})
       5)  I({B}, {F} | {D})
       6)  I({B}, {F} | {A, G})
    d) Assume that the nodes are binary-valued.
       Suppose that P(A=true) = 0.2, P(B=true)= 0.3
       P(C=true|A=true,B=true) = 0.9, P(C=true|A=false,B=true) = 0.2
       P(C=true|A=true,B=false) = 0.5, P(C=true|A=false,B=false) = 0.1
       P(E=true|B=true) = 0.8, P(E=true|B=false) = 0.1
       P(G=true|D=true, E=true) = 0

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

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

3)  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:

       E
       D
       A
    C  B
------------

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

4)  Consider the following business opportunities scenario, occuring in a certain country.*
    We will assume that you are a risk-neutral, i.e. that
    your utility function is linear in the amount of money that your assets are worth.
    Assume also that moral considerations are not part of your utility function.

    You have just purchased a new tobacco products company, and wish to do business in said country.
    A preliminary market survey suggests that you expect to make 1000 MMU (Million monetary units) 
    every year. However, you wish to improve your gains, by vigorous advertizing, for a cost of 100 MMU per
    year. The result of advertizing will gain you nothing if the advertizing campaign fails, but with a
    probability of 0.5 it will succeed and add 500 MMU per year to your profits. Unfortunately, under directives from
    the health ministry it is currently illegal to advertise such products (and it is openly illegal, so
    you cannot take that chance). Nevertheless, if you meet Mr. Lim, the
    minister of health, then Lim surely will be convinced to legalize such advertisements for a share of 300 MMU
    for the first year, and 100 MMU for every following year, delivered in unmarked envelopes.
    Since convincing Lim of your position by greasing his palm is also illegal, 
    assume a probability of 0.001 of getting caught
    and losing ALL your gains, plus landing in jail, which is an additional loss of per 10000 MMU per year to you.
    If this happens, you will also have to do the time in a cell shared with Lim, which you consider equivalent to
    an additional loss of 10000 MMU per year. But in both cases, jail time will only start next year.
    In this case, you will not participate in any business in the next years, so not have to pay advertising beyond
    the first year.

    Clarification: the decisions are to be made initially before the beginning of the current year,
    and the decisions are valid for the next years as well (unless aborted by your landing in jail), you do not
    make a new decision each year.

    a) What is your optimal policy, in order to maximize your sum of gains for the first 3 years
       (i.e. this year, next year, and the year after the next year)?

    b) You can now also purchase an additional market survey, that will give you perfect information on
       whether the advertizing campain will work, for 50 MMU. Does your optimal policy differ?

    c) Repeat a and b above for sum of gains for 3 years under a discounted reward factor of 0.1, that is,
       next year is only worth 10% of what this year is worth, etc.

5) Consider the following Harassed Citizen problem instance.

   The (undirected) graph has 7 vertices, as follows:
     (S, I1, I2, V1, V2, V3, G)
   The edges are as follows:
     (S, V1), weight 10.
     (V1, V2), weight 1.
     (V2, V3), weight 1.
     (V3, G), weight 1.
     (S, G), weight 100.
     (S, I1), weight 1.
     (S, I2), weight 2.
     (I1, V2), weight 1000.
     (I2, V3), weight 1000.

   S is the start vertex, V2 may contain a key with a probability of 0.5, 
   V3 may contain a lock of the same type with probablity 0.8, and G is a goal vertex.
   No other locks or keys are possible in this graph.
 
     
   b1) Formalize the above problem as a (belief-state) MDP, i.e. 
       what are the states, the transition probability
       function, and the reward function? (He the cost of traversing an edge is equal to it weight).

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

6)  A principal researcher (PR) in the Paypal project must hire a new programmer for
    the GA optimization, since the last employee has quit suddenly.
    The PR would like to construct a decision procedure based on results from hiring
    employees in the DARPA Robotics Challenge project.
    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), number of
    papers published in AI workshops (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 decision tree as close to consistent as possible for the following table:

     input variables               decision
   A      B      C      D
--------------------------------------------
   2      F      L      0             N
   2      F      H      1             Y
   2      T      L      0             N
   3      F      H      0             Y
   3      T      H      2             Y
   3      T      H      2             Y
   3      T      H      2             N
   3      T      L      0             Y
   3      T      H      1             Y

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

7) You need to construct a 7-input neural network that has 1 output: the output should be 1 if
   the number of input units that are 1 is odd, and 0 otherwise.
   a) Can this be done without hidden units?
   b) Show a network using threshold elements that performs
      the required computation (specify the weights, too!)

Deadline (strict): Wednesday, January 25, 2017, 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.