Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules

Xi He, Max A. Little · 2025

Read Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules by Xi He, Max A. Little (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01455.txt.

Description

Decision trees sort data by a chain of yes or no splits, and finding the best tree for a job is a classic hard problem. Xi He and Max Little build a rule based frame in 2025 for judging which tree problems have clean structure. They name the well behaved family proper decision trees and show it covers many known structures, from space dividing trees to learning models.

Only the proper family, they prove, can be summed up in a compact form, while other trees carry far greater complexity. From that form they derive a step by step method that solves such problems exactly for any splitting rule. They also show that storing partial results is generally too costly, correcting a claim in the field. The frame extends to some improper cases with tweaks.

Catalog record

CREATORXi He, Max A. Little
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE175 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01455

Browse the full library · About the Tower of Babel