TDSM 11.5

(a) Does there always exist a decision tree classifier which perfectly separates A from B?
No, a perfect decision tree classifier does not exist if there are one or more sets of feature vectors which are exactly the same and correspond to different labels.

(b) Does there always exist a decision tree classifier which perfectly separates A from B if the n feature vectors are all distinct?
Yes, there always exists a perfect decision tree classifier if all the feature vectors are distinct, because a tree can always be constructed such that there exists a unique path from the root to a leaf corresponding to each vector.

(c) Does there always exist a logistic regression classifier which perfectly separates A from B?
No. The logistic regression classifier is based on separating the n-dimensional space into two parts using a line / plane / hyperplane. There can always exist a point with the other label beyond the line in one part of the space.

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