Justify all answers!
1) We are given the following independence statements about random variables
A, B, C, D, E, F, G, H:
I({A,B},{C,D}|{})
I({A,B},{C,D,G,H}|{})
I({E,F},{C,D,G,H}|{})
I({G},{C}|{D})
not I({A},{B}|{})
not I({C},{G}|{})
not I({E},{F}|{})
not I({C},{G}|{D,H})
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 D E
D A
E B
F D
G A B
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, C})
4) I({B}, {F} | {G})
5) I({B}, {F} | {D})
6) I({B}, {F} | {A, C})
d) Assume that the nodes are binary-valued.
Suppose that P(A=true) = 0.2, P(B=true)= 0.3
P(G=true|A=true,B=true) = 0.9, P(G=true|A=false,B=true) = 0.2
P(G=true|A=true,B=false) = 0.5, P(G=true|A=false,B=false) = 0.1
P(E=true|B=true) = 0.8, P(E=true|B=false) = 0.1
P(C=true|D=true, E=true) = 0
Find P(E=true, A=True | B=true)
Hint: you may want to preprocess to get rid of nodes before doing any computation.
3) 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(E,D) and On(D,C)
4) Your car has been stolen. You have just received the insurance money, and are about to
buy a new car. Suppose you are down to 2 options: Hybrid (H), and regular gasoline engine (G).
The Hybrid costs 40KMU (Kilo Monetary Units), and consumes 4 liters of gasoline per 100KM.
The regular costs 25KMU, and consumes 8 liters of gasoline per 100KM. You figure
that you will be driving 50000KM per year in the next 3 years, after which you will
sell the car for half of the purchase price. Gasoline costs 1.5 MU per liter.
However, Premier Pico (PP)* has announced new "environmental" taxation, which
will double the cost of gasoline. You have heard that people are about to riot against
this tax, and figure that with probablity 0.5 the riots will cause Pico's wife to recommend to
Pico to cancel the new tax. Pico always does what his wife tells him (after all, she
was also his teacher).
A) Assuming a utility linear in (simple) sum of MU gained or lost in the next 3 years:
a) The deal on the car is only possible today, and additionally you
have no car, which is a bummer you cannot tolerate, so you must decide today, what is your optimal
decision?
b) You figure out that you can join the riots (action R), which will increase the probability
that the tax will be canceled to 0.6, but you may be captured by the police and made to
pay a fine or go to jail, which you evaluate at a cost of 50KMU to you,
(with probability 0.01, independent of whether or not the riots succeed).
Suppose you still need to make the purchasing decision before
you know the result of the rioting, what is your optimal policy now?
c) You know of Picard, who attended graduate school with Pico's wife. For
some palm grease, Picard can obtain perfect information (action I) from Pico's wife on what
she will recommend to Pico to do due to the riots.
What is the maximum amount you should be willing to pay Picard for this
information? (Assume that this information is obtained immediately, and that the option
of your joining the rioting is not possible in this case).
B) Repeat items a, b, c, assuming a discounting factor of 0.1 per year.
5) Consider the following uncertain Hurricane Evacuation decision
problem instance, with a deadline of T=10.
The (undirected) graph has 6 vertices, as follows:
(S, V1, V2, P1, P2, G)
The edges are as follows:
(S, V1), weight 1.
(V1, P2), weight 1, blocked with probability 0.5
(V1, G), weight 2.
(S, V2), weight 2.
(V2, P2), weight 1, blocked with probability 0.01
(P1, G), weight 3.
(P1, P2), weight 3.
(P2, G), weight 5.
S is the start vertex. G contains a shelter.
Vertex P1 contains one person, and P2 contains 2.
No edges are blocked in this graph, except possibly the ones indicated above.
b1) Formalize the above problem as a (belief-state) MDP, i.e.
what are the states, the transition probability
function, and the reward function? (The time to traversing an edge is equal to it weight).
b2) Find the optimal policy. You may assume that the agent starts
at vertex S in order to save some computation.
6) A principal researcher (PR) in the AI for Cybersecurity project needs to hire a programmer to
develop and test algorithms for computing the most likely path in a Markov chain.
The PR would like to construct a decision procedure based on results from hiring
employees in the ISG consortium 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), Java 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 decision tree as close to consistent as possible for the following table:
input variables decision
A B C D
--------------------------------------------
2 F L 0 N
2 F H 0 N
2 F L 1 N
3 F L 0 Y
3 F H 0 N
3 F H 2 Y
3 F L 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?
7) You need to construct a binary 6-input neural network that has 1 output: the output should be 1 if
the number of inputs that have a value of 1 is divisible by 3, and 0 otherwise.
a) Can this be done without hidden units?
b) Show a network using threshold elements that performs
the required computation (specify the weights, too!)
Deadline (strict): Tuesday, January 8, 2019, at 4 PM.
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.