Recently, the Shapley value has been widely applied in machine learning for feature importance analysis and model explainability. The multilinear extension of games proposed by Owen (1972) expresses the Shapley value as the integral of partial derivatives along the main diagonal of the cube. Direct evaluation of this integral requires exponential-time computation of the partial derivatives. To improve computational efficiency, we propose a sampling-based estimation strategy within Owen's multilinear extension framework, combining stratified sampling with coalition leverage scores. Experimental results demonstrate that the proposed method significantly reduces computational costs while maintaining explanation accuracy.
Figures & tables
Figure 1: Feature-dropping curves for the UCS dataset (15 features, regression task). The x -axis represents the number of top features dropped, while the y -axis reports the corresponding R2 . Each legend entry reports the weighted slope score S .
Figure 2: Feature-dropping curves for the Adult Income dataset (11 features, binary classification task). The x -axis represents the number of top features dropped, while the y -axis reports the corresponding Accuracy. Each legend entry reports the weighted slope score S .
Figure 3: Feature-dropping curves for the Crime dataset (121 features, regression task). The x -axis represents the number of top features dropped, while the y -axis reports the corresponding R2 . Each legend entry reports the weighted slope score S .
Table 3: Weighted slope score S across all XAI methods (the best score in each column is given in bold)
Table 4: Running time across all XAI methods
Figure 4: Pareto frontier of two-criteria evaluation (running time on x -axis and 1/S on y -axis) for the UCS dataset (15 features, regression task). For the LightGBM model the Pareto frontier consists of TreeSHAP, Improved ShapG, Original ShapG, Sampling Owen, and Exact Owen; for the TabM model it consists of ES, SamplingSHAP and Original ShapG.
Figure 5: Pareto frontier of two-criteria evaluation (running time on x -axis and 1/S on y -axis) for the Adult Income dataset (11 features, binary classification task). For the LightGBM model the Pareto frontier consists of TreeSHAP, ES, FESP, Improved ShapG, and Sampling Owen; for the TabM model it consists of ES, FESP and Improved ShapG.
Figure 6: Pareto frontier of two-criteria method evaluation (running time on x -axis and 1/S on y -axis) for the Crime dataset (121 features, regression task). For the LightGBM model the Pareto frontier consists of TreeSHAP, ES, FESP, Improved ShapG, LeverageSHAP, Sampling Owen and Original ShapG; for the TabM model it consists of ES and Sampling Owen.
Department of Statistics, LMU Munich, Munich, Germany · Munich Center for Machine Learning, Munich, Germany · Institute for Informatics, LMU Munich, Munich, Germany +2