What makes an Ensemble (Un) Interpretable?
This provides a foundational insight for the ML community by rigorously analyzing interpretability bottlenecks, though it is incremental in applying existing complexity theory to a known issue.
The paper tackles the problem of understanding why ensemble models are often considered uninterpretable by applying computational complexity theory to analyze how factors like the number, size, and type of base models affect interpretability, finding that small ensembles of decision trees are efficiently interpretable while interpreting ensembles with constant linear models remains intractable under standard assumptions.
Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of trees (e.g., boosted trees) are often treated as black-boxes. Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what particularly makes an ensemble (un)-interpretable, including how fundamental factors like the (1) *number*, (2) *size*, and (3) *type* of base models influence its interpretability. In this work, we seek to bridge this gap by applying concepts from computational complexity theory to study the challenges of generating explanations for various ensemble configurations. Our analysis uncovers nuanced complexity patterns influenced by various factors. For example, we demonstrate that under standard complexity assumptions like P$\neq$NP, interpreting ensembles remains intractable even when base models are of constant size. Surprisingly, the complexity changes drastically with the number of base models: small ensembles of decision trees are efficiently interpretable, whereas interpreting ensembles with even a constant number of linear models remains intractable. We believe that our findings provide a more robust foundation for understanding the interpretability of ensembles, emphasizing the benefits of examining it through a computational complexity lens.