Problem

1. What is regularization, and what kind of problems with machine learning does it solve?

2. Give decision trees to represent the following Boolean functions:

(a) A and B¯.

(b) A or (B and C).

(c) (A and B) or (C and D).

3. Suppose we are given an n × d labeled classification data matrix, where each item has an associated label class A or class B. Give a proof or a counterexample to each of the statements below:

(a) Does there always exist a decision tree classifier which perfectly separates A from B?

(b) Does there always exist a decision tree classifier which perfectly separates A from B if the n feature vectors are all distinct?

(c) Does there always exist a logistic regression classifier which perfectly separates A from B?

(d) Does there always exist a logistic regression classifier which perfectly separates A from B if the n feature vectors are all distinct?