SCMI-TREE: SYNERGY-AWARE DECISION TREES VIA CONDITIONAL MUTUAL INFORMATION WITH ADAPTIVE LOOKAHEAD
Article Sidebar
-
Decision Trees, Feature Synergy, Interaction Information, Interpretable Machine Learning, Lookahead, Mutual Information
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
Full text article
References
Akash, P. S., Kadir, M. E., Ali, A. A., & Shoyaib, M. (2019). Inter-node Hellinger distance based decision tree. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI-19) (pp. 1967–1973). DOI: 10.24963/ijcai.2019/272
Anastassiou, D. (2007). Computational analysis of the synergy among multiple interacting genes. Molecular Systems Biology, 3(1), 83. DOI: 10.1038/msb4100124
Belghazi, M. I., Baratin, A., Rajeshwar, S., Ozair, S., Bengio, Y., Courville, A., & Hjelm, R. D. (2018). Mutual information neural estimation. In Proceedings of the 35th International Conference on Machine Learning (Vol. 80, pp. 531–540). DOI: 10.48550/arXiv.1801.04062
Beraha, M., Metelli, A. M., Papini, M., Tirinzoni, A., & Restelli, M. (2019). Feature selection via mutual information: New theoretical insights. In Proceedings of the International Joint Conference on Neural Networks (IJCNN) (pp. 1–9). DOI: 10.1109/IJCNN.2019.8852410
Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. DOI: 10.1023/A:1010933404324
Breiman, L., Friedman, J., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Brooks/Cole, Wadsworth, Monterey, CA, 358 pp. DOI: 10.1201/9781315139470
Brown, G., Pocock, A., Zhao, M.-J., & Luján, M. (2012). Conditional likelihood maximisation: A unifying framework for information theoretic feature selection. Journal of Machine Learning Research, 13(1), 27–66.
Chen, T., & Guestrin, C. (2016). XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 785–794). DOI: 10.1145/2939672.2939785
Cieslak, D. A., Hoens, T. R., Chawla, N. V., & Kegelmeyer, W. P. (2012). Hellinger distance decision trees are robust and skew-insensitive. Data Mining and Knowledge Discovery, 24(1), 136–158. DOI: 10.1007/s10618-011-0222-1
Elomaa, T., & Malinen, T. (2003). On lookahead heuristics in decision tree learning. In Foundations of Intelligent Systems (ISMIS 2003), Lecture Notes in Computer Science (Vol. 2871, pp. 445–453). Springer, Berlin. DOI: 10.1007/978-3-540-39592-8_63
Esmeir, S., & Markovitch, S. (2007). Anytime learning of decision trees. Journal of Machine Learning Research, 8(5), 891–933.
Grinsztajn, L., Oyallon, E., & Varoquaux, G. (2022). Why do tree-based models still outperform deep learning on typical tabular data? In Advances in Neural Information Processing Systems (Vol. 35, pp. 507–520). DOI: 10.48550/arXiv.2207.08815
Karthikeyan, A., Jain, N., Natarajan, N., & Jain, P. (2022). Learning accurate decision trees with bandit feedback via quantized gradient descent. Transactions on Machine Learning Research, 2022(6), 1–28. DOI: 10.48550/arXiv.2102.07567
Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., & Liu, T.-Y. (2017). LightGBM: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems (Vol. 30, pp. 3146–3154).
Kraskov, A., Stögbauer, H., & Grassberger, P. (2004). Estimating mutual information. Physical Review E, 69(6), 066138. DOI: 10.1103/PhysRevE.69.066138
Lyon, R. J., Brooke, J. M., Knowles, J. D., & Stappers, B. W. (2014). Hellinger distance trees for imbalanced streams. In Proceedings of the 22nd International Conference on Pattern Recognition (ICPR) (pp. 1969–1974). DOI: 10.1109/ICPR.2014.344
McGill, W. J. (1954). Multivariate information transmission. Psychometrika, 19(2), 97–116. DOI: 10.1007/BF02289159
Murthy, S. K., Kasif, S., & Salzberg, S. (1994). A system for induction of oblique decision trees. Journal of Artificial Intelligence Research, 2(1), 1–32. DOI: 10.1613/jair.63
Norouzi, M., Collins, M., Johnson, M. A., Fleet, D. J., & Kohli, P. (2015). Efficient non-greedy optimization of decision trees. In Advances in Neural Information Processing Systems (Vol. 28, pp. 1729–1737).
Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106. DOI: 10.1007/BF00116251
Quinlan, J. R. (1993). C4.5: Programs for machine learning. Morgan Kaufmann, San Francisco, CA, 302 pp. DOI: 10.1016/C2009-0-27846-9
Raileanu, L. E., & Stoffel, K. (2004). Theoretical comparison between the Gini index and information gain criteria. Annals of Mathematics and Artificial Intelligence, 41(1), 77–93. DOI: 10.1023/B:AMAI.0000018580.96245.c6
Rudin, C. (2019). Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5), 206–215. DOI: 10.1038/s42256-019-0048-x
Tan, H., Wang, G., Wang, W., & Zhang, Z. (2022). Feature selection based on distance correlation: A filter algorithm. Journal of Applied Statistics, 49(2), 411–426. DOI: 10.1080/02664763.2020.1815672
Tax, T. M. S., Mediano, P. A. M., & Shanahan, M. (2017). The partial information decomposition of generative neural network models. Entropy, 19(9), 474. DOI: 10.3390/e19090474
Vergara, J. R., & Estévez, P. A. (2014). A review of feature selection methods based on mutual information. Neural Computing and Applications, 24(1), 175–186. DOI: 10.1007/s00521-013-1368-0
Wickramarachchi, D. C., Robertson, B. L., Reale, M., Price, C. J., & Brown, J. (2016). HHCART: An oblique decision tree. Computational Statistics and Data Analysis, 96(1), 12–23. DOI: 10.1016/j.csda.2015.11.006
Williams, P. L., & Beer, R. D. (2010). Nonnegative decomposition of multivariate information. arXiv Preprint, arXiv:1004.2515, 1–14. DOI: 10.48550/arXiv.1004.2515
Authors
Copyright (c) 2026 Taha A. Ababakar , Hakar J. M. Salih , Dilheen H. Sabri, and Omar M. Ahmed
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License [CC BY-NC-SA 4.0] that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work, with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online.