Efficient Computation of SHAP Values for Piecewise-Linear Decision Trees

The interpretability of machine learning models is important in many applied data analysis problems. In recent years, a universal SHAP interpretation paradigm based on Shapley values has become popular. However, to interpret the values using SHAP directly, it is necessary to calculate the model’s prediction the number of times that is exponential to the size of the feature space, which leads to the prohibitive complexity of this calculation method for complex models over complex feature spaces, for example, for neural networks or gradient boosting ensembles. It was shown that there are efficient algorithms for calculating SHAP values for decision trees and additive ensembles based on them, using structure of trees for an optimized calculation. One of interesting new classes of machine learning models is piecewise linear decision trees and gradient boosting ensembles based on them. In this paper, an efficient algorithm for computing SHAP values for piecewise linear decision trees and additive ensembles based on them was proposed.