Justify all answers!
1) We are given the following independence statements about random variables
A, B, C, D, E, F:
I({A,B,C,D},{E,F}|{})
I({A},{C,D}|{B})
I({D},{A,B}|{C})
not I({A},{B}|{})
not I({B},{C}|{})
not I({C},{D}|{})
not I({E}, {F}|{})
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
D A
E C B
G D B
H 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})
5) I({B}, {C} | {})
6) I({B}, {C} | {G})
d) Assume that the nodes are binary-valued.
Suppose that P(A=true) = 0.2, P(B=true)= 0.1, P(E=true|C=false) = 0.5,
P(E=true|C=true) = 0.5,
P(H=true|E=true) = 0.2, P(H=true|E=false) = 0.4,
P(C=true|A=true) = 0.9, P(C=true|A=false) = 0.2
P(D=true|A=true) = 0.8, P(D=true|A=false) = 0.1
Find P(C=true | D=true, G=true)
Hint: you may want to preprocess to get rid of nodes before doing any computation.
3) You need to construct a 3-input neural network that has 2 outputs: the first
has value 1 in the output just when the number of its inputs that are "on" is even,
and the other has a value of 1 in the ouput just when the number of its inputs that are "on" is greater than
or equal to 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:
D
A
C B
------------
and the goal state containing: On(A,B) and On(B,D)
b) Suppose that is not known whether the above is the initial state,
and the initial state can either the above initial state, or the
following state, and these are the only possibilities.
D
B
A C
------------
and that there is an operator "Check(clear(x)))" which results in knowing whether
this is true or not. Show how a conditional plan is constructed for the above
case.
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 mojo(**), is
threatening to destroy it immediately (a damage of 1 mort),
and will only return it to you if release their band member the great Humongous(***).
Surrendering Humongous is not of immediate
material damage, but may cause you a loss in the future, as Humongous is a notorious criminal.
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) Release Humongous, and possibly encur the respective future losses.
c) Request the police to try a raid to recover your mojo in location A.
d) Request the police to try a raid to recover your mojo in location B.
Since you do not know where your mojo is hidden, the results of a raid are:
With probability 0.4 they will succeed at location A, and with probability
0.9 in location B, assuming your mojo is at that location. The probability
of the mojo being at A is 0.6, and it is certain that your Mojo is either at A or at B.
A failed raid causes immediate and permanent loss of you mojo.
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.5 (per fortnight).
5.2) Would the answer be different, if in releasing Humongous, there is
in addition a probability of 0.5 that the band of criminals will steal
your mojo 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 tell with certainty whether your mojo is at A or B, how much
should you be willing to pay for such information (in both cases a and b)?
6) Consider the following Syrian traveller problem instance.
The (undirected) graph has 3 vertices, as follows:
(I, V1, G)
The edges are as follows:
(I, V1), weight 10, no terrorists.
(V1, G), weight 20, probability of terrorists 0.2
(I, G), weight 100, no terrorists
Vertex I contains chems and an army, and G is a goal vertex.
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 SENSING action
for a cost of 10, which results in the agent knowing the state of
the edge (V1, G), i.e. whether it contains terrorists. Re-compute the optimal policy for this case.
7) A principal researcher in the Israeli Smart Grid (ISG) consortium
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), C 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 consistent decision tree for the following table:
input variables decision
A B C D
--------------------------------------------
2 F L 0 N
2 F M 1 Y
2 T L 0 N
3 F H 0 Y
3 T M 2 Y
3 T M 0 N
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?
Deadline: Wednesday, January 15, 2014, 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.
*** The Great Humongous: copyright some other film studio we do not recall.