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?