KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

On the Computational Intelligibility of Boolean Classifiers

  1. Gilles Audemard(CRIL, Université d'Artois & CNRS)
  2. Steve Bellart(CRIL, Université d'Artois & CNRS)
  3. Louenas Bounia(CRIL, Université d'Artois & CNRS)
  4. Frédéric Koriche(CRIL, Université d'Artois & CNRS)
  5. Jean-Marie Lagniez(CRIL, Université d'Artois & CNRS)
  6. Pierre Marquis(CRIL, Université d'Artois & CNRS, Institut Universitaire de France)

Keywords

  1. Explainable AI

Abstract

In this paper, we investigate the computational intelligibility of Boolean classifiers, characterized by their ability to answer XAI queries in polynomial time. The classifiers under consideration are decision trees, DNF formulae, decision lists, decision rules, tree ensembles, and Boolean neural nets. Using 9 XAI queries, including both explanation queries and verification queries, we show the existence of large intelligibility gap between the families of classifiers. On the one hand, all the 9 XAI queries are tractable for decision trees. On the other hand, none of them is tractable for DNF formulae, decision lists, random forests, boosted decision trees, Boolean multilayer perceptrons, and binarized neural networks.