Searching for actual causes: Approximate algorithms with adjustable precision

Causality has enhanced the interpretability of machine learning models. However, traditional causality often falls short of producing relevant explanations, those grounded in actual causes. Identifying actual causes remains computationally intractable (NP-complete). We propose two polynomial-time algorithms: a beam-search-based method and an optimized variant (ISI) leveraging causal structure. Experiments on a causal model with varying size show our algorithms (1) identify multiple causes and (2) offer tunable precision-exhaustiveness-runtime tradeoffs, paving the way to using causality for relevant explanation in explainable AI.