Inapproximability of sufficient reasons for decision trees
In this note, we establish the hardness of approximation of the problem of computing the minimal size of a $\delta$-sufficient reason for decision trees.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Probabilistic Explanations for Linear Models
Formal XAI is an emerging field that focuses on providing explanations with mathematical guarantees for the decisions made by machine learning models. A significant amount of work in this area is centered on the computat…
On the Explanatory Power of Decision Trees
Decision trees have long been recognized as models of choice in sensitive applications where interpretability is of paramount importance. In this paper, we examine the computational ability of Boolean decision trees in d…
On Computing Probabilistic Explanations for Decision Trees
Formal XAI (explainable AI) is a growing area that focuses on computing explanations with mathematical guarantees for the decisions made by ML models. Inside formal XAI, one of the most studied cases is that of explainin…
Explainable Artificial Intelligence (XAI)Superconstant Inapproximability of Decision Tree Learning
We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothesis tree $T$ is required to be optimally …
LEMMAPAC learningTrading Complexity for Sparsity in Random Forest Explanations
Random forests have long been considered as powerful model ensembles in machine learning. By training multiple decision trees, whose diversity is fostered through data and feature subsampling, the resulting random forest…