Experiments with optimal model trees.

Area of Science:

• Machine Learning
• Data Mining
• Artificial Intelligence

Background:

• Model trees offer interpretable machine learning for classification and regression.
• Unlike classic decision trees, model trees use linear combinations in leaf nodes for improved accuracy and smaller tree size.
• Greedy algorithms for model trees are fast but yield locally optimal splits, potentially leading to less accurate and more complex trees.

Purpose of the Study:

• To empirically investigate the impact of constructing globally optimal model trees.
• To compare globally optimal model trees against those from greedy and dynamic programming algorithms.
• To evaluate the trade-offs between interpretability and accuracy when using multivariate splits.

Main Methods:

• Model trees with linear support vector machines in leaf nodes were learned using mixed-integer linear programming (MILP) formulations.
• Benchmark datasets were used for empirical comparison.
• Performance was evaluated based on tree size and predictive accuracy.

Main Results:

• MILP-based optimal model trees demonstrated competitive predictive accuracy.
• These globally optimal trees were significantly smaller than those produced by greedy algorithms.
• Replacing axis-parallel splits with multivariate ones was explored for potential accuracy gains, albeit with a loss of interpretability.

Conclusions:

• Globally optimal model trees, learned via MILP, offer a promising approach for achieving high accuracy with reduced complexity.
• The study highlights the benefits of global optimization over greedy methods in model tree construction.
• Further research can explore the balance between interpretability and accuracy through different splitting strategies.