Machine Learning (W4771)

Homework 1

Due Date: Tuesday, February 1.

Reading: Chapters 1 and 2 ("Machine Learning" by Mitchell)

Homework problems. Answers to problems 1 and 3 are fairly open-ended -- their purpose is to stimulate thinking about machine learning. However, the other questions have correct and incorrect answers.

  1. Exercise 1.2 from the text. Please restrict yourself to 1 page max.
  2. Why use machine learning methods, when are they necessary? To answer this questions, give an example hypothesis space H1 for which an exhaustive search would suffice to find a good hypothesis, and a contrasting one H2 for which exhaustive search is not possible.
  3. Consider the application of machine learning to the game Tritris (a variation of Tetris) as described in class on day 1.
  4. Consider a learning problem where each instance is described by a conjunction of n boolean features, and each hypothesis is a DISJUNCTION of literals over these features. Propose an algorithm that produces a consistent hypothesis if one exists. Your algorithm should run in time that is polynomial in n and in the number of training examples.
  5. Exercise 2.4 (parts a, b and c only) from the text.

email: evs at cs dot columbia dot edu