What variables should be used to get explanations (of AI systems) that are easily interpretable? The challenge to find the right degree of abstraction in explanations, also called the {\textquoteleft}variables problem{\textquoteright}, has been actively discussed in the philosophy of science. The challenge is striking the right balance between specificity and generality. Concepts such as proportionality and exhaustivity are investigated and discussed. We propose a new and formal definition based on Kolmogorov complexity and argue that this corresponds to our intuitions about the right level of abstraction. First, we require that variables are uniform, so that they cannot be decomposed into less abstract variables without increasing the Kolmogorov complexity. Next, uniform variables are optimal for an explanation if they can compose the explanation without increasing its Kolmogorov complexity. For this, the concepts K-decomposability and K-composability of sets are defined. Explanations of a certain instance should encompass a maximal set of instances without being K-decomposable. Although Kolmogorov complexity is uncomputable and depends on the choice of programming language, we show that it can be used effectively to evaluate and reason about explanations, such as in the evaluation of XAI methods.
Lemeire, J & Buijsman, S 2024, Defining and Evaluating the Degrees of Abstraction in Explanations with Kolmogorov Complexity. in FA Oliehoek, M Kok & S Verwer (eds), Artificial Intelligence And Machine Learning, Bnaic/benelearn 2023. vol. 2187, Communications in Computer and Information Science, vol. 2187 CCIS, pp. 40-53. https://doi.org/10.1007/978-3-031-74650-5_3
Lemeire, J., & Buijsman, S. (2024). Defining and Evaluating the Degrees of Abstraction in Explanations with Kolmogorov Complexity. In F. A. Oliehoek, M. Kok, & S. Verwer (Eds.), Artificial Intelligence And Machine Learning, Bnaic/benelearn 2023 (Vol. 2187, pp. 40-53). (Communications in Computer and Information Science; Vol. 2187 CCIS). https://doi.org/10.1007/978-3-031-74650-5_3
@inproceedings{85ff0e2f3068418988ad7c1def678b24,
title = "Defining and Evaluating the Degrees of Abstraction in Explanations with Kolmogorov Complexity",
abstract = "What variables should be used to get explanations (of AI systems) that are easily interpretable? The challenge to find the right degree of abstraction in explanations, also called the {\textquoteleft}variables problem{\textquoteright}, has been actively discussed in the philosophy of science. The challenge is striking the right balance between specificity and generality. Concepts such as proportionality and exhaustivity are investigated and discussed. We propose a new and formal definition based on Kolmogorov complexity and argue that this corresponds to our intuitions about the right level of abstraction. First, we require that variables are uniform, so that they cannot be decomposed into less abstract variables without increasing the Kolmogorov complexity. Next, uniform variables are optimal for an explanation if they can compose the explanation without increasing its Kolmogorov complexity. For this, the concepts K-decomposability and K-composability of sets are defined. Explanations of a certain instance should encompass a maximal set of instances without being K-decomposable. Although Kolmogorov complexity is uncomputable and depends on the choice of programming language, we show that it can be used effectively to evaluate and reason about explanations, such as in the evaluation of XAI methods.",
keywords = "Explainability, Explainable AI, Kolmogorov complexity, Abstraction",
author = "Jan Lemeire and Stefan Buijsman",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.",
year = "2024",
month = nov,
day = "2",
doi = "10.1007/978-3-031-74650-5\_3",
language = "English",
isbn = "978-3-031-74649-9",
volume = "2187",
series = "Communications in Computer and Information Science",
pages = "40--53",
editor = "Oliehoek, \{Frans A.\} and Manon Kok and Sicco Verwer",
booktitle = "Artificial Intelligence And Machine Learning, Bnaic/benelearn 2023",
}