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}|{B})
I({D},{E}|{})
not I({A},{B}|{})
not I({B},{C}|{})
not I({E},{F}|{})
not I({D},{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
I A B H
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} | {I})
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, corresponding to
the binary value of the sum of the inputs (e.g. if all 3 inputs are on, then bothe outputs are on,
because 3 in binary is "11".)
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:
E
D
A
C B
------------
and the goal state containing: On(A,B) and On(B,D)
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.
You are to vote for determining the government for the next 4 years.
There are 3 candidates for whom you could vote: Yahoo, Future, and BozoAndWhite.
Yahoo hates the poor, but always wishes to appease the "party of the eternally poor" (POEP)
which will cost you 100 MEMU (mid-eastern monetary units) this year in subsidies paid to
PEOP, and the amount would double every following year due to success of POEP, which will generate more
poor people receiving your money.
Future, as its name implies, is future-oriented. It will give nothing to POEP, but will invest
200 MEMU of your money this year to educate the supporters of PEOP, after which they
will require no further subides.
BozoAndWhite are more of an uncertain proposition: they claim that, like Future, they will
educate the supporters of PEOP, and that they can do it for only 180 MEMU. However, based on
past record, there is a probability of 0.5 that after winning the elections they will choose
to appease PEOP anyway, with the same results as if Yahoo won.
Assume that all are equally likely to win, but that your vote will swing the election if you vote.
You have the following options:
1) Vote for Yahoo
2) Vote for Future
3) Vote for BozoAndWhite
4) Not vote at all, since you can save 1 MEMU by staying at home on election day.
Draw the decision diagram for each case below, and solve it.
a) What is your rational choice in voting, for the following utility combination functions:
1) Undiscounted rewards.
2) Discounted rewards with a discounting factor of 0.1 (i.e you really do not
care very much about next year).
b) As above, but you have the choice to pay 10 MEMU to Guri Heller
who can use his powers to divine what BozoAndWhite will actually do
if elected. Should you pay for Guri Heller's opinion, and what should
you vote after hearing his response?
6) Consider the following Yazidi refugee problem instance.
The (undirected) graph has 4 vertices, as follows:
(I, V1, V2, G)
The edges are as follows:
(I, V1), weight 10.
(I, G), weight 60.
(V1, V2), weight 10.
(V2, G), weight 10.
I is the start vertex, V2 may contain terrorists with a probability of 0.5, 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 Yazidi 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 whether V2 contains
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 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?
Deadline: Tuesday, January 20, 2015, 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 (yeah, sure it ain't).