CIS 732
Due: Friday 12
September 2003
(before midnight
Saturday 13 September 2003)
Show your work.
For problems from the textbook, be sure to answer all the
questions. For example, for Exercise
2.2, explain briefly why the final version space is invariant with respect to
the ordering of examples.
You must type your solutions.
Note: Some of these problems have several parts, so
please start early!
Problems (50 points total)
1.
(15
points) Candidate Elimination Algorithm.
Mitchell, Exercise 2.2 – answer all questions
2.
(15 points) Learning Algorithm Analysis Mitchell,
Exercise 2.9 - write down your analysis
of the running time
3.
(10
points) Hypothesis Learning. Mitchell,
Exercise 7.5
4.
(10
points) Perceptrons. Mitchell, Exercise 4.3
Extra credit (10 points total)
a)
(5
points) Linear Hidden Units in Feedforward ANNs. Duda and Hart, p. 335:
Show that if the activation function of the hidden units is linear, a three-layer
network is equivalent to a two-layer one.
Use your result to explain why a three-layer network with linear hidden
units cannot solve a nonlinearly separable problem such as XOR or d-bit parity.
b)
(5
points) Gradient Descent. Mitchell, Exercise 4.5