# Learning Small Decision Trees with Few Outliers: A Parameterized Perspective

arXiv: https://arxiv.org/abs/2505.15648 · HTML: https://mlsanity.com/paper/2505.15648/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 21 May 2025.

## Builds on (most cited first, 7 of 7)

- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Parameterized Algorithms for the Matrix Completion Problem](https://mlsanity.com/paper/1804.03423/) (2018)
- [Witty: An Efficient Solver for Computing Minimum-Size Decision Trees](https://mlsanity.com/paper/2412.11954/) (2024)
- [Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty](https://mlsanity.com/paper/1509.02424/) (2015)
- [On Computing Optimal Tree Ensembles](https://mlsanity.com/paper/2306.04423/) (2023)
- [Backdoors into Heterogeneous Classes of SAT and CSP](https://mlsanity.com/paper/1509.05725/) (2015)

## Built on by (most cited first, 1 of 1)

- [Improving Decision Trees through the Lens of Parameterized Local Search](https://mlsanity.com/paper/2510.12726/) (2025)

## Abstract (arXiv)

Decision trees are a fundamental tool in machine learning for representing, classifying, and generalizing data. It is desirable to construct ``small'' decision trees, by minimizing either the textitsize (s) or the textitdepth (d) of the textitdecision tree (textscDT). Recently, the parameterized complexity of textscDecision Tree Learning has attracted a lot of attention. We consider a generalization of textscDecision Tree Learning where given a textitclassification instance E and an integer t, the task is to find a ``small'' textscDT that disagrees with E in at most t examples. We consider two problems: textscDTSO and textscDTDO, where the goal is to construct a textscDT minimizing s and d, respectively. We first establish that both textscDTSO and textscDTDO are W[1]-hard when parameterized by s+δmax and d+δmax, respectively, where δmax is the maximum number of features in which two differently labeled examples can differ. We complement this result by showing that these problems become textscFPT if we include the parameter t. We also consider the kernelization complexity of these problems and establish several positive and negative results for both textscDTSO and textscDTDO.