SCMI-TREE: SYNERGY-AWARE DECISION TREES VIA CONDITIONAL MUTUAL INFORMATION WITH ADAPTIVE LOOKAHEAD

Abstract

Decision trees built with greedy axis-aligned splits perform well when individual features carry a meaningful signal about the target. They fail, often badly, in the setting where the useful information resides in the joint behaviour of two or more features rather than in any single one. The exclusive-or problem is the textbook example, since no single feature predicts the label but the pair does. This study presents SCMI-Tree, a tree induction algorithm whose splitting score augments mutual information with two additional terms, namely a synergy bonus for features that interact constructively with the ancestor splits along the path, and a redundancy penalty for features that overlap with them. A dataset-level synergy score is computed once at fit time from a random sample of feature pairs, which allows the algorithm to decide whether to engage a lookahead mechanism that addresses the root exclusive-or problem, and to skip that overhead when it would not help. SCMI-Tree was evaluated on eight classification datasets comprising four real benchmarks and four synthetic tasks of varying difficulty. The lookahead variant achieved the best average rank of 1.88 across the eight datasets, outperforming both Gini-based CART at 4.12 and entropy-based ID3 at 2.75. On a noisy exclusive-or task with eight irrelevant features the difference was substantial, reaching 89.3% accuracy for SCMI-Tree against 53.2% for CART. Ablation experiments show that two failure modes of conventional greedy induction, namely sensitivity to noise features and dependence on tree depth, are largely avoided by the proposed method