4. [Decision Trees] (6 pts) In class, we covered how to learn binary decision trees. In...

Transcribed Image Text:

4. [Decision Trees] (6 pts) In class, we covered how to learn binary decision trees. In this question, you will modify the decision tree learning algorithm to obtain ternary decision trees (i.e, each internal node has three children). Assume all features are real-valued, and the labels are categorical (i.e., classification). 2 a. (2 pts) Each internal node should split a single feature into three intervals x; ≥ t1, t₁ > x; ≥ t2, and t₂ > xj. Write down all parameters for this split. b. (2 pts) Write down the information gain for a single split. You do not have to expand the entropy (e.g., for traditional decision trees, the information gain is IG(j, t) = H (Z) - H(Z[x; ≥ t])P(x; ≥ t) - H(Z[x; <t])P(x; <t)). c. (2 pts) Does this strategy increase, decrease, or keep unchanged the model capac- ity compared to traditional decision trees? What if the depth of the decision tree is bounded by 3? 4. [Decision Trees] (6 pts) In class, we covered how to learn binary decision trees. In this question, you will modify the decision tree learning algorithm to obtain ternary decision trees (i.e, each internal node has three children). Assume all features are real-valued, and the labels are categorical (i.e., classification). 2 a. (2 pts) Each internal node should split a single feature into three intervals x; ≥ t1, t₁ > x; ≥ t2, and t₂ > xj. Write down all parameters for this split. b. (2 pts) Write down the information gain for a single split. You do not have to expand the entropy (e.g., for traditional decision trees, the information gain is IG(j, t) = H (Z) - H(Z[x; ≥ t])P(x; ≥ t) - H(Z[x; <t])P(x; <t)). c. (2 pts) Does this strategy increase, decrease, or keep unchanged the model capac- ity compared to traditional decision trees? What if the depth of the decision tree is bounded by 3?

Answer rating: 100% (QA)

a For a ternary decision tree split at an internal node for a feature xj the thre... View the full answer