Decision trees: from efficient prediction to responsible AI
Open accessThe DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Abstract
This article provides a birds-eye view on the role of decision trees in machine learning and data science over roughly four decades. It sketches the evolution of decision tree research over the years, describes the broader context in which the research is situated, and summarizes strengths and weaknesses of decision trees in this context. The main goal of the article is to clarify the broad relevance to machine learning and artificial intelligence, both practical and theoretical, that decision trees still have today.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Breiman, L. (2001) · Machine Learning · doi:10.1023/a:1010933404324 · Cited by 133,538
XGBoost: A Scalable Tree Boosting System
Chen, T., & Guestrin, C. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939785 · Cited by 54,569
Greedy function approximation: A gradient boosting machine
Friedman, J. H. (2001) · The Annals of Statistics · doi:10.1214/aos/1013203451 · Cited by 30,731
Quinlan, J. R. (1986) · Machine Learning · doi:10.1007/bf00116251 · Cited by 21,439 · cited 2×
“Decision trees became prominent in machine learning and data analysis around the 1980s, when popular decision tree learners were developed more or less in parallel in the computer science community (e.g., ID3 Quinlan, 1986 and its many subsequent improvements) and in the statistics community (CART Breiman et al., 1984…”
Background"Why Should I Trust You?": Explaining the Predictions of Any Classifier
Ribeiro, M. T., Singh, S., & Guestrin, C. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939778 · Cited by 17,555
Breiman, L. (1996) · Machine Learning · doi:10.1007/bf00058655 · Cited by 16,325 · cited 1×
“Ensembles of decision trees constructed in this way significantly outperform single decision trees in terms of accuracy (Breiman, 1996).”
BackgroundFrom local explanations to global understanding with explainable AI for trees
Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., & Lee, S.-I. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-019-0138-9 · Cited by 10,551
Intriguing properties of neural networks
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., & Fergus, R. (2013) · arXiv · doi:10.48550/arxiv.1312.6199 · Cited by 8,143 · cited 2×
“Kantchelian et al. (2016) propose enriching the training data with adversarial examples, as has been done before for neural networks (Szegedy et al., 2013).”
BackgroundAdvances and Open Problems in Federated Learning
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. (2019) · arXiv · doi:10.48550/arxiv.1912.04977 · Cited by 7,857
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Towards Deep Learning Models Resistant to Adversarial Attacks
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., & Vladu, A. (2017) · arXiv · doi:10.48550/arxiv.1706.06083 · Cited by 6,602
Liu, F. T., Ting, K. M., & Zhou, Z.-H. (2008) · 2008 Eighth IEEE International Conference on Data Mining · doi:10.1109/icdm.2008.17 · Cited by 6,601 · cited 2×
“In the context of anomaly detection, a tree-based approach called Isolation Forests (Liu et al., 2008) is considered state-of-the-art for a wide range of applications.”
BackgroundSagi, O., & Rokach, L. (2018) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1249 · Cited by 3,103
Ensemble Methods: Foundations and Algorithms
Zhou, Z.-H. (2012) · doi:10.1201/b12207 · Cited by 2,534
Dong, X., Yu, Z., Cao, W., Shi, Y., & Ma, Q. (2020) · Frontiers of Computer Science · doi:10.1007/s11704-019-8208-z · Cited by 1,928
Constructing optimal binary decision trees is NP-complete
Hyafil, L., & Rivest, R. L. (1976) · Information Processing Letters · doi:10.1016/0020-0190(76)90095-8 · Cited by 959 · cited 5×
“On tree ensemble models, Cui et al. (2015) showed that the constrained optimization problem of generating counterfactual explanations is NP-hard.”
BackgroundInfluentialModel-Agnostic Interpretability of Machine Learning
Ribeiro, M. T., Singh, S., & Guestrin, C. (2016) · arXiv · doi:10.48550/arxiv.1606.05386 · Cited by 699
Top-down induction of first-order logical decision trees
Blockeel, H., & De Raedt, L. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(98)00034-4 · Cited by 685
Self-citationCriminisi, A., Shotton, J., & Konukoglu, E. (2012) · Foundations and Trends® in Computer Graphics and Vision · doi:10.1561/0600000035 · Cited by 677
Tree Induction for Probability-Based Ranking
Provost, F., & Domingos, P. (2003) · Machine Learning · doi:10.1023/a:1024099825458 · Cited by 541
Distilling a neural network into a soft decision tree
Frosst, N., & Hinton, G. (2017) · arXiv · doi:10.48550/arxiv.1711.09784 · Cited by 407 · cited 3×
“Examples of work that focuses on decision trees include the work of Frosst and Hinton (2018). Thanks to the success of learning soft decision trees with gradient descent, several extensions have been made for random forests. For example, the neural decision forest (NDF) proposed by Rota Bulo and Kontschieder (2014) is…”
BackgroundInfluentialDiscrimination Aware Decision Tree Learning
Kamiran, F., Calders, T., & Pechenizkiy, M. (2010) · 2010 IEEE International Conference on Data Mining · doi:10.1109/icdm.2010.50 · Cited by 303
Neural Prototype Trees for Interpretable Fine-grained Image Recognition
Nauta, M., van Bree, R., & Seifert, C. (2021) · 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr46437.2021.01469 · Cited by 269
Beyond Sparsity: Tree Regularization of Deep Models for Interpretability
Wu, M., Hughes, M., Parbhoo, S., Zazzi, M., Roth, V., & Doshi-Velez, F. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11501 · Cited by 213
Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making
Aghaei, S., Azizi, M. J., & Vayanos, P. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33011418 · Cited by 135 · cited 6×
“Aghaei et al. (2019) adapted the MILPsolver based approach to take into account two forms of fairness; the approach optimizes a weighted sum of accuracy and fairness. Similarly, van der Linden et al. (2022) adapted the DL8-style approach such that an upper- or lower-bound on fairness can be ensured, where the fairness…”
MethodInfluentialFAHT: An Adaptive Fairness-aware Decision Tree Classifier
Zhang, W., & Ntoutsi, E. (2019) · Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/205 · Cited by 85
Metadata
- Authors
- Blockeel, H., Devos, L., Frénay, B., Nanfack, G., & Nijssen, S.
- Venue
- Frontiers in Artificial Intelligence
- Publisher
- Frontiers Media SA
- Published
- 2023-07-26
- Volume
- 6
- Pages
- 1124553-1124553
- ISSN
- 2624-8212 (ISSN-L)
- OpenAlex
- W4385318219
- Cited by
- 230
- References
- 26
- FWCI
- 54.05
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.