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.1
   F     F     T     F   0.05
   F     F     T     T   0.1
   F     T     F     F   0.0
   F     T     F     T   0.1
   F     T     T     F   0.05
   F     T     T     T   0.1
   T     F     F     F   0.0
   T     F     F     T   0.1
   T     F     T     F   0.05
   T     F     T     T   0.1
   T     T     F     F   0.0
   T     T     F     T   0.1
   T     T     T     F   0.05
   T     T     T     T   0.1

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

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

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

    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({A}, {C} | {B, F})
    d) Assume that the nodes are binary-valued.
       Suppose that P(A=true) = 0.4, P(B=true)= 0.1, 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(C=true) = 0.9

       Find P(A=true | B=true, E=true, C=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 2. (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:
    A  B
    C  D

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

   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 voting 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 amount of money that your assets are worth.
    Assume also that moral considerations are not part of your utility function.
    There are 4 candidates for whom you could vote: Yahoo, The Man, Lightning, and White,
    all equally likely to win, unless your vote happens to swing the election.
    Assume that there is a 1% chance that your vote will actually swing the election,
    and a 0.5% chance that "The Man" will somehow find out what your vote was.
    If that happens, and you voted for someone OTHER than The Man, your business
    will be trashed for a loss of 100,000 NIS.

    Your accountant has notified you that your taxes for FY 2008-2009 amount to 1,000,000 NIS
    on your clam-encapsulation business.
    Also, you happen to be a member of "The Man"'s party, and if this party wins
    you have a 10% chance of being in the legislature, in which case you will be able to
    pass a law that declares all clam-related businesses tax-exempt. But there is also a
    10% chance that in this case a corruption charge against you will stick and you will
    go to jail and lose your business, a total additional cost of 5,000,000 NIS.

    Additional information is as follows: Yahoo claims he will reduce your taxes by 50%,
    and you think he will actually deliver with probability 0.5
    If White is elected there will be mediocre-size bonuses which will gain you 100,000 NIS.
    Lightning getting elected will improve police forces, which will decrease your security
    costs by 150,000 NIS.

    Assume that event combinations not mentioned above have a probability of 0, e.g.
    the probability that you will be a member of the legislature given that "The Man"
    does not win is 0.

    You have the following options:
       1) Vote for Yahoo
       2) Vote for The Man
       3) Vote for Lightning
       4) Vote for White
       5) Not vote at all

     Draw the decision diagram for each case below, and solve it.

    a) What is your rational choice in voting?

    b) As above, but you have the choice to pay 10,000 NIS to "future-tech polling inc."
       for a poll which tells you with certainty which 2 of the above 4 will surely NOT win
       (leaving the other 2 equally likely). If you do make the payment, you get this
       information before you need to decide about your vote. 
       Do you pay for the poll?
       What do you vote after getting the poll information, assuming you do?

6) Consider the following belief-state MDP, where scoring is total value of rewards
   obtained in 3 steps.
   The world has 4 locations in linear sequence, as follows:  F1 I F2 P
   Actions are: R attempts to move right, and L attempts to move left,
   and S senses location F2. Location F1 contains a  flag, which has a
   value of 1. Location F2 contains a flag, with value either 10 or
   100, with probability 0.5 each, and may be icy (with a probability of 0.5).

   A robot visiting a location with a flag gets a reward equal to the
   flag value, and then the flag disappears. P is an absorbing state,
   with a reward of -100.
   Transition probabilities are based on: motion succeeds with probability 0.8, 
   but with probability
   0.2 the robot either stays in the same location, or moves in the opposite direction
  (if possible),
   with probability 0.1 each (0.2 to stay in place if at end of sequence).
   Sensing, if performed, tells the robot the actual value of the flag
   at F2. 

   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 location 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
   1      T      M      95             6
   1      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: Tuesday, February 24, 2009, 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.