Abstract: 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 ensembles of linear models remain intractable, even with a constant number of models. 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.

Lay Summary:

Ensemble models - where multiple smaller base-models are combined to make predictions - are commonly used in ML and are known for being hard to interpret. For example, a single decision tree is fairly easy to understand, but when many trees are combined (like in boosted trees), the model is usually treated as a "black box." While this idea is widely accepted, we still lack a clear mathematical understanding of why these models are difficult to interpret.In this work, we take a step toward answering that question. Using tools from computational complexity theory, we study how hard it is to explain the predictions of different types of ensemble models. We look at how factors like the number, size, and type of the individual models within the ensemble affect how difficult it is to generate explanations.Our findings show a high versatility of results. For instance, even if each base-model in the ensemble is very small, explaining the whole ensemble can still be highly difficult. Interestingly, the type of base-model within the ensemble matters a lot - for example, ensembles with just a few decision trees can be interpreted efficiently, but an ensemble with even a significantly small number of linear models is hard to explain.By analyzing these challenges through the lens of computational complexity, our work helps lay a more solid foundation for understanding when and why ensemble models are (un) interpretable.