Fast Sparse Decision Tree Optimization via Reference Ensembles.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Interpretable Machine Learning

Background:

• Sparse decision tree optimization is a fundamental AI problem, crucial for interpretable machine learning.
• Existing methods for finding optimal sparse decision trees are computationally intensive, especially for datasets with continuous features.

Purpose of the Study:

• To develop practical strategies for optimizing sparse decision trees that compete with black box models in accuracy.
• To reduce the computational time and memory requirements for constructing accurate sparse decision trees.

Main Methods:

• Introduced "smart guessing" strategies applicable to branch-and-bound algorithms for decision tree optimization.
• Leveraged knowledge from black box machine learning models to inform guesses for feature binning, tree size, and error bounds.
• Developed methods to bound the deviation in accuracy and expressive power from black box models.

Main Results:

• Achieved significant reductions in computation time, often by multiple orders of magnitude.
• Demonstrated the ability to rapidly construct sparse decision trees matching black box model accuracy in many cases.
• Provided bounds on the accuracy and expressive power deviation from black box models.

Conclusions:

• Smart guessing strategies offer a practical approach to overcoming computational challenges in sparse decision tree optimization.
• This method enables the efficient creation of interpretable sparse decision trees with competitive accuracy.
• The findings suggest that informed guessing is a viable strategy when optimizing complex decision tree structures.