On the tractability of SHAP explanations under Markovian distributions

Overview

• The paper investigates the computational complexity of the Shapley Additive Explanations (SHAP) framework, a widely used method for explaining the predictions of machine learning models.
• SHAP is known to be computationally challenging, with its exact computation being NP-Hard in various configurations.
• The paper relaxes the assumption of feature independence, which is often simplistic in real-world scenarios, and introduces a Markovian perspective to the problem.

Plain English Explanation

The SHAP framework is a popular way to explain how machine learning models make their predictions. It assigns a "SHAP score" to each feature, showing how much that feature contributed to the final prediction. Despite its widespread use, calculating these SHAP scores can be very difficult, and has been proven to be a computationally complex problem.

Previous research has found that for certain types of machine learning models, like decision trees and random forests, the SHAP scores can be computed efficiently, as long as the features in the model are independent of each other. However, in real-world scenarios, this assumption of feature independence is often an oversimplification.

In this paper, the researchers investigate what happens when we relax this assumption of feature independence. They introduce a "Markovian" perspective, which allows for some level of dependence between the features. Surprisingly, they find that under this Markovian assumption, the SHAP scores can be computed efficiently for certain classes of machine learning models, like weighted automata, disjoint DNFs, and decision trees. This is the first positive complexity result for SHAP score computation that goes beyond the limitations of the feature independence assumption.

Technical Explanation

The paper focuses on the computational complexity of calculating the SHAP score, a widely used framework for explaining the predictions of machine learning models. The SHAP score quantifies the contribution of each feature to the final prediction of a model.

Previous work has shown that the exact computation of the SHAP score is NP-Hard in various configurations. However, recent research has unveiled positive complexity results for specific model families, such as decision trees, random forests, and some classes of boolean circuits, under the assumption of feature independence.

The key contribution of this paper is to relax the feature independence assumption, which is often overly simplistic in real-world scenarios, and introduce a Markovian perspective to the problem. The authors show that under the Markovian assumption, the SHAP score can be computed in polynomial time for the classes of weighted automata, disjoint DNFs, and decision trees. This is the first positive complexity result for SHAP score computation that transcends the limitations of the feature independence assumption.

Critical Analysis

The paper provides an important step forward in understanding the computational complexity of the SHAP framework, a widely used technique for explaining the predictions of machine learning models. By relaxing the assumption of feature independence, which is often an oversimplification in real-world scenarios, the authors have shown that efficient computation of SHAP scores is possible for certain classes of models under a Markovian assumption.

However, it is important to note that the Markovian assumption may still be restrictive in some domains, and there may be cases where even this assumption does not hold. Additionally, the paper focuses on specific model classes, and the complexity results may not generalize to more complex or diverse model families.

Further research is needed to understand the computational complexity of SHAP score computation in more general settings, potentially exploring alternative explanatory frameworks or approximation techniques that can handle a wider range of machine learning models and real-world data structures. Efforts to correct SHAP scores and develop alternative explanation methods could also be valuable in this context.

Conclusion

This paper makes an important contribution to the field of interpretable machine learning by investigating the computational complexity of the SHAP framework under more realistic assumptions. By relaxing the feature independence assumption and introducing a Markovian perspective, the authors have shown that efficient SHAP score computation is possible for certain model classes, offering a significant advancement beyond previous complexity results.

This work has implications for the practical application of SHAP and other explanation methods, as it suggests that it may be possible to explain the predictions of a broader range of machine learning models in a computationally tractable manner. As the demand for interpretable AI systems continues to grow, research like this will be crucial in developing scalable and effective explanation techniques for complex real-world problems.