Justify all answers!
1) Use situation calculus (i.e. the result function, and fluents) to
write down the axioms for the money-and-banana example. The monkey
needs to get the banana, which can be done by climbing a box after
moving it into position below the bananas, which are too high to
reach otherwise. In the initial state, the box is in the room, but
not under-bananas, the monkey does not have the bananas. Actions
are:
a) grab - gets the bananas if the monkey is on the box and the box is
under the bananas
b) climb - puts the monkey on the box if the monkey is near the box
c) move(item, position) - moves item into position if the item is
a box and the monkey is not on it.
Fluents (time-dependent predicates) are:
box_at(location) (location can be under-bananas or elsewhere)
on-box (monkey is on box)
has-bananas (monkey has the bananas)
Now, you need to prove that, for the initial situation S where the monkey
is not on the box and does not have tha bananas, the action sequence
(move, climb, grab) works, i.e. that:
holds(has-bananas,
result(grab, result(climb,
result(move(box, under-bananas), S))))
Can you do it with your original formulation (show the proof!).
If not, add the requisite axioms and complete the proof.
2) Write down the axioms and facts for example below in FOPC:
The taxonomic hierarchy for animals, contains dogs, which
which in turn contains German shepherds and chihuahuas (which are
disjoint). All dogs are carnivorous.
German shepherds are large. All large dogs can be guard dogs,
unless they are old. Fido is an old German shepherd.
a) Convert the knowledge base into normal form
b) Show how this knowledge-base should be indexed - using
a table.
c) Prove or disprove by using resolution (or argue that neither
can be done):
1) Fido is an animal.
2) Fido is large.
3) Fido can be a guard dog.
4) If Fido is a chihuahua, then Fido is young.
5) Fido is carnivorous.
SHOW ALL STEPS, including the relevant unifiers, etc.
d) Would using INPUT RESOLUTION only change the answers to c?
e) Can you prove all the above using only either forward or
backward chaining?
3) Consider the following variables and their immediate causes (parents):
variable parents
-------------------------------
A none
E none
B A
C A E
D A
F B C
a) Is this network a poly-tree?
b) Determine the truth of the following independence
statements (using d-separation):
1) I({A}, {E} | {})
2) I({A}, {E} | {B})
3) I({A}, {E} | {C})
4) I({A}, {E} | {F})
5) I({A}, {C, F} | {B})
6) I({A}, {F} | {B, C})
c) Determine at least 2 different ways to convert the network into
a poly-tree using cutset conditioning.
d) Suppose that P(A) = 0.9, P(E) = 0.3, P(B|A) = 0.1, P(B|~A) = 0.8.
Find P(A|E)
5) You need to construct a 3-input neural network that has value 1 in the
output just when exactly 1 of its inputs is 1, and 0 otherwise
(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!)
6) a) Using the perceptron learning rule (the "delta" rule), show the steps
of learning 3-input function AND with a single perceptron
and a step activation function with threshold 1. Initially all
weights are 1, and the learning rate is 0.4.
b) Is it possible to combine back-propagation with genetic algorithms, and
if so, how?
7) a) Construct by hand a decision tree for the following table, a set of
examples for sorting client loan risk.
where the first decision is based on bad credit (A),
then if necessary pending number of loan requests - B),
granted loan by this bank in past (C), and monthly income (in tens of
thousands of dollars a year) (D).
input variables decision
A B C D
--------------------------------------------
F 1 F 5 small
F 1 F 4 small
F 1 F 3 small
F 1 T 3 small
F 2 F 3 medium
F 2 F 4 medium
T 1 F 8 small
T 1 T 4 large
T 1 T 5 large
b) Which node will be pruned first, based on least information gain?
c) Is a more compact decision tree possible (possibly using a different
ordering of the variables)? Which tree?
Deadline: Monday, January 28, 2002.
Note: submission (as well as WORK) on this exercise is SOLO (that is, NOT in pairs or other groups of size > 1)