CODEWITHSUNDEEP
machine-learningdata-sciencedecision-treetheory
Matthew Davidson
Matthew Davidson

Reputation: 13

Would infinitely deep decision tree guarantee 100% accuracy for binary classification task?

Would then infinitely deep decision tree on a binary classification task guarantee to achieve 100% accuracy on a training set with N examples such that there is no examples with the same feature values, but a different class label?

Upvotes: 1

Views: 523

Answers (1)

Nick ODell
Nick ODell

Reputation: 25409

Yes, it's possible to create a decision tree like this. It wouldn't need to be infinitely deep, either - just ceil(log(2, N)) levels deep, where N is the number of examples. Assuming that each training example had a unique set of feature values, then the model could get 100% accuracy.

However, a decision tree like this would probably generalize pretty poorly. The model is essentially memorizing each training example. The accuracy on examples that were not part of the original training set would likely be pretty bad. That's one reason why decision tree models typically either set a minimum split size (e.g. don't split any leaves with less than 10 examples) or use a random forest, which train many different trees and average their predictions.

Upvotes: 1

Related Questions