Solving Explainability Queries with Quantification: The Case of Feature Relevancy
Xuanxiang Huang, Yacine Izza, Joao Marques-Silva
Abstract
Trustable explanations of machine learning (ML) models are vital in high-risk uses of artificial intelligence (AI). Apart from the computation of trustable explanations, a number of explainability queries have been identified and studied in recent work. Some of these queries involve solving quantification problems, either in propositional or in more expressive logics. This paper investigates one of these quantification problems, namely the feature relevancy problem (FRP), i.e.\ to decide whether a (possibly sensitive) feature can occur in some explanation of a prediction. In contrast with earlier work, that studied FRP for specific classifiers, this paper proposes a novel algorithm for the \fprob quantification problem which is applicable to any ML classifier that meets minor requirements. Furthermore, the paper shows that the novel algorithm is efficient in practice. The experimental results, obtained using random forests (RFs) induced from well-known publicly available datasets, demonstrate that the proposed solution outperforms existing state-of-the-art solvers for Quantified Boolean Formulas (QBF) by orders of magnitude. Finally, the paper also identifies a novel family of formulas that are challenging for currently state-of-the-art QBF solvers.
BibTeX
@article{Huang_Izza_Marques-Silva_2023, title={Solving Explainability Queries with Quantification: The Case of Feature Relevancy}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25514}, DOI={10.1609/aaai.v37i4.25514}, abstractNote={Trustable explanations of machine learning (ML) models are vital in
high-risk uses of artificial intelligence (AI). Apart from the
computation of trustable explanations, a number of explainability
queries have been identified and studied in recent work. Some of these
queries involve solving quantification problems, either in
propositional or in more expressive logics. This paper investigates
one of these quantification problems, namely the feature relevancy
problem (FRP), i.e.\ to decide whether a (possibly sensitive) feature
can occur in some explanation of a prediction. In contrast with
earlier work, that studied FRP for specific classifiers, this paper
proposes a novel algorithm for the \fprob quantification problem which
is applicable to any ML classifier that meets minor requirements.
Furthermore, the paper shows that the novel algorithm is efficient
in practice. The experimental results, obtained using random forests
(RFs) induced from well-known publicly available datasets,
demonstrate that the proposed solution outperforms existing
state-of-the-art solvers for Quantified Boolean Formulas (QBF) by
orders of magnitude. Finally, the paper also identifies a novel family
of formulas that are challenging for currently state-of-the-art QBF
solvers.}, number={4}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Huang, Xuanxiang and Izza, Yacine and Marques-Silva, Joao}, year={2023}, month={Jun.}, pages={3996-4006} }