Relevance-Aware Rule: Structural Deletion of Irrelevant Conditions in Decision Trees

Decision trees are widely used for their interpretability, yet they often produce over-specified rules containing irrelevant conditions (IRCs). These IRCs persist even in modern, sparse tree induction algorithms because the recursive splitting process forces every descendant leaf to inherit all upstream conditions. The authors address this by developing a structural theory of IRCs, moving beyond simple empirical pruning to understand the mechanics of why conditions become redundant.

The core insight is that binary splits create a structural dependency: if one branch increases the proportion of class-1, the other must necessarily increase the proportion of class-0. The authors label these as C1-links and C0-links. By comparing these links to the class of a target leaf, the researchers identify 'mismatched' links—conditions that structurally pull the rule toward an opposite class—as prime candidates for deletion.

The paper proposes a three-layer analytical framework to diagnose and remove IRCs:

1. Local Annotation: Tagging links as C1, C0, or neutral based on class-proportion shifts.
2. Leaf-Relative Diagnosis: Identifying links as 'matched' or 'mismatched' relative to the specific class of a leaf node.
3. Path-Level Effect: Evaluating whether deleting a condition preserves the reliability and class-consequence of the rule.

The framework implements two primary methods: a mismatch-guided procedure that uses statistical or logical certificates to prune candidates, and a sibling-certified procedure that removes conditions when a sibling leaf shares the same class, providing an exact guarantee of tree-behavior preservation.

This work bridges the gap between aggressive rule simplification and the need for faithful model interpretation. By providing a theoretical basis for IRC deletion, the authors offer a way to make decision tree rules significantly more concise without the risks associated with black-box pruning or the loss of structural integrity. This is particularly valuable for high-stakes domains where every condition in a rule must be justified by the data structure rather than just empirical performance.