• Financement : CRIL
  • Thèse soutenue le :
  • 4 nov. 2025

Explaining the predictions made by machine learning models has long been a significant challenge in the field of explainable artificial intelligence. Recently, formal explainability has emerged as an essential subfield focused on providing explanations with mathematical guarantees. Among the various forms of explanations proposed in this area, probabilistic explanations stand out for their ability to balance succinctness and precision. However, calculating these probabilistic explanations involves computational complexities that exceed the capabilities of current solvers.

To tackle this challenge, we present a unified theoretical framework for computing probabilistic explanations with approximation guarantees. Our framework combines elements of formal explainability with computational learning theory and constraint programming.

For classification models, we reformulate the problem of generating probabilistic explanations as the task of learning monotone monomials. The corresponding empirical risk minimization task can be addressed through constraint programming. In the case of regression models, generating probabilistic linear explanations is framed as a problem of learning sparse linear functions under a hyperplane constraint. This minimization task can be handled using mixed-integer programming, and for uniform distributions, it can be approximated in polynomial time using iterative hard thresholding.

Beyond these theoretical guarantees, our empirical results show that our formal methods outperform state-of-the-art heuristic approaches, such as Anchors, LIME, and MAPLE, in terms of fidelity and interpretability.

Thesis committee

Reviewers

  • Prof. Céline Rouveirol – LIPN, Sorbonne Paris North University
  • Prof. Frédéric Saubion – LERIA, University of Angers

Examiner

  • Prof. Arnaud Durand – Paris Diderot University

Supervisors

  • Prof. Frédéric Koriche – CRIL, Artois University
  • Prof. Jean-Marie Lagniez – CRIL, Artois University
  • Dr. Stefan Mengel – CNRS