Learning Small Decision Trees with Few Outliers: A Parameterized Perspective

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.