Provable Guarantees for Decision Tree Induction (via Zoom)

Abstract: 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.

Bio: I'm a first year PhD student at Stanford broadly interested in CS theory. As an undergrad, also at Stanford, I worked with Li-Yang Tan and Greg Valiant, and am currently rotating with Moses Charikar. I'm still figuring out which areas of theory most interest me, but so far have dabbled in learning theory, complexity theory, and online algorithms.