Suppose you have the following training set with four boolean attributes $x_1$, $x_2$, $x_3$ and $x_4$ and a boolean output $y$.

What is the tree learned by CART (without any pruning mechanism) from this training set?

You should be able to construct it from your general understanding of this algorithm without going into all the details of computing explicitly every step of this algorithm.

Is there another binary decision tree which would perfectly classify the same training examples and would not be as deep as the one proposed by CART?

Suppose you have a training set with 20 positive and 20 negative examples.

Compute the drop of impurity for the two following splits, performed at the root of the tree:

• $[4+, 14-]$ (left) $\ [16+, 6-]$ (right)
• $[8+, 18-]$ (left) $\ [12+, 2-]$ (right)

Give your answer in the following format: drop_first, drop_second

When rounding, give at least 3 decimals. For example, 0.452.

Based on your answer in the previous question, which split will be chosen by CART?

Beware: you will only receive credit for this question if you answered the previous one correctly.

Suppose now that the mistakes on the positive examples are about 5 times as costly as mistakes to the negative. One way of dealing with such a cost imbalance is to replicate the positive examples 5 times each. The splits become:

• $[20+, 14-]$ (left) $\ [80+, 6-]$ (right)
• $[40+, 18-]$ (left) $\ [60+, 2-]$ (right)

What is their drop of impurity?

Give your answer in the following format: drop_first, drop_second

When rounding, give at least 3 decimals. For example, 0.452.

Consequently, which split will be performed by CART?

Beware: you will only receive credit for this question if you answered the previous one correctly.

Consider a classification problem based only on 2 continuous attributes (the instance space is the plane $\mathbb{R}^2$). CART incorporates these attributes by defining threshold based boolean attributes. In the induced tree, each node corresponds to a particular decision boundary splitting the examples into two regions. What is the shape (in the instance space) of the decision boundaries learned by CART? Into how many regions is the instance space divided before pruning? Does it depend on the attribute values of the training examples? Does it depend on the number of classes?

Select all valid sentences