CIS 732

Machine Learning and Pattern Recognition

Fall, 2001

Homework Assignment 1

Thursday, 13 September 2001

Due: Thursday, 20 September 2001

(before midnight Friday 21 September 2001)

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

1. (4 points) Candidate Elimination Algorithm. Mitchell, Exercise 2.2 – answer all questions

2. (6 points) Hypothesis Learning. Mitchell, Exercise 2.7

3. (6 points) VC Dimension. Mitchell, Exercise 7.5

4. (3 points) Entropy and Decision Trees. Mitchell, Exercise 3.2

5. (6 points) Delta Rule Learning. Mitchell, Exercise 4.6

Extra credit

a) (2 points) Learning with A Helpful Teacher. Mitchell, Exercise 2.4d

b) (3 points) Russell and Norvig, Problem 18.7(b)