Justify all answers!
1) We are given the following independence statements about random variables
A, B, C, D, E, F:
I({A,E,F},{B,C,D}|{})
I({B},{C}|{})
I({A},{E}|{F})
not I({B},{C}|{D})
not I({A},{E}|{})
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
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})
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=false) = 0.5,
P(E=true|A=true) = 0.5,
P(H=true|E=true) = 0.2, P(H=true|E=false) = 0.4,
Find P(A=true | B=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:
D A
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
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 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
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 40 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 aircraft is 10 years, and assuming simple
3-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 3 years?
6) Consider the following multi-car Canadian traveller problem instance.
The (undirected) graph has 4 vertices, as follows:
(I, V1, V2, G)
The edges are as follows:
(I, V1), weight 10, no flood.
(I, V2), weight 20, no flood.
(V1, V2), weight 30, probability of flood 0.5
(V1, G), weight 10, probability of flood 0.8
(V2, G), weight 20, probability of flood 0.5
There is a car C1 with speed 10 at I that can travel at speed 5 on a flooded road,
And a car C2 with speed 20 that cannot travel a flooded road ad all at V2
Switching cars cost 1
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 a car C1 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 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 Intelligent Smart Grid (ISG) consortium
would like to construct a decision procedure based on results from hiring
employees in the Canadian Traveler Problem research 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 N
3 T M 0 N
3 T H 1 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?
Deadline: Wednesday, January 25, 2012, 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.