Abstract

Explainable AI (XAI) refers to the development of AI systems andmachine learning models in a way that humans can understand, interpret and trustthe predictions, decisions and outputs of these models. A common approach toexplainability is feature importance, that is, determining which input features of themodel have the most significant impact on the model prediction. Two major techniquesfor computing feature importance are LIME (Local Interpretable Model-agnosticExplanations) and SHAP (SHapley Additive exPlanations). While very generic,these methods are computationally expensive even when the data is not encrypted.Applying them in the privacy-preserving setting when part or all of the input datais private is therefore a major computational challenge. In this paper, we presentXorSHAP - the first practical data-oblivious algorithm for computing SHAP valuesfor decision tree ensemble models. The algorithm is applicable in various privacypreserving settings such as SMPC, FHE and differential privacy. Our algorithm hascomplexity O(TMDe 2D), where T is the number of decision trees in the ensemble, Dis the depth of the decision trees and Me is the maximum of the number of features Mand 2D (the number of leaf nodes of a tree), and scales to real-world datasets. Weimplement the algorithm in the semi-honest Secure Multiparty Computation (SMPC)setting with full threshold using Inpher’s Manticore framework. Our implementationsimultaneously computes the SHAP values for 100 samples for an ensemble of T = 60trees of depth D = 4 and M = 100 features in just 7.5 minutes, meaning thatthe SHAP values for a single prediction are computed in just 4.5 seconds for thesame decision tree ensemble model. Additionally, it is parallelization-friendly, thus,enabling future work on massive hardware acceleration with GPUs.

Keywords

Explainable AI · model explainability · gradient boosting decision trees· SHAP values · secure multiparty computation