Rhodes, Greece. September 2-8, 2023.
Copyright © 2023 International Joint Conferences on Artificial Intelligence Organization
We study multivariate decision trees (MDTs), in particular,
classes of MDTs determined by the language
of relations that can be used to split feature space.
An abductive explanation (AXp) of the classification
of a particular instance, viewed as a set of feature-value
assignments, is a minimal subset of the instance
which is sufficient to lead to the same decision.
We investigate when finding a single AXp is
tractable. We identify tractable languages for real,
integer and boolean features. Indeed, in the case
of boolean languages, we provide a P/NP-hard dichotomy.