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:
A
B
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
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 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.