Predictive Equivalence in Decision Trees
This blog post is based on joint work with Hayden McTavish and Jon Donnelly and is presented in our ICML 2025 paper , "Leveraging Predictive Equivalence in Decision Trees", advised by Dr.'s Margo Seltzer and Cynthia Rudin. A Top Down View of Decision Trees Figure 1: Two decision trees which encode precisely the same logical expression. Splits to the right correspond to the variable being True, left to False. Decision trees are generally accepted as a very interpretable model class for understanding tabular machine learning problems. Look through a classical machine learning textbook, and you'll find that algorithms for 'optimizing' decision trees are a dime a dozen -- Scikit-Learn implements CART, C4.5, C5.0, and ID3. Modern research (see GOSDT and SPLIT, STreeD, and DL8.5, among others) has taken these algorithms far beyond the old days of greedy optimization into the world of true optimality, subject to depth constraints and limits on the number of leaves in...