Provable Guarantees for Decision Tree Induction

Top-down decision tree learning algorithms, such as CART, ID3, and C4.5, have been machine learning workhorses for decades. However, there hasn't been much theoretical work proving that those algorithms can effectively learn decision trees. In part 1 of this talk, we prove that a large class of top-down algorithms learn a decision tree with accuracy close to that of the best small decision tree as long as the dataset is monotone. In part 2, we develop a new splitting criterion with similar guarantees even if the dataset is not monotone.

This talk is based on joint work with Neha Gupta, Jane Lange, and Li-Yang Tan.