How to cite this WIREs title:
WIREs Data Mining Knowl Discov

Impact Factor: 7.250

Learning decision trees through Monte Carlo tree search: An empirical evaluation

Focus Article

Cecília Nunes, Mathieu De Craene, Hélène Langet, Oscar Camara, Anders Jonsson

Published Online: Feb 24 2020

DOI: 10.1002/widm.1348

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Abstract Decision trees (DTs) are a widely used prediction tool, owing to their interpretability. Standard learning methods follow a locally optimal approach that trades off prediction performance for computational efficiency. Such methods can however be far from optimal, and it may pay off to spend more computational resources to increase performance. Monte Carlo tree search (MCTS) is an approach to approximate optimal choices in exponentially large search spaces. We propose a DT learning approach based on the Upper Confidence Bound applied to tree (UCT) algorithm, including procedures to expand and explore the space of DTs. To mitigate the computational cost of our method, we employ search pruning strategies that discard some branches of the search tree. The experiments show that proposed approach outperformed the C4.5 algorithm in 20 out of 31 datasets, with statistically significant improvements in the trade‐off between prediction performance and DT complexity. The approach improved locally optimal search for datasets with more than 1,000 instances, or for smaller datasets likely arising from complex distributions. This article is categorized under: Algorithmic Development > Hierarchies and Trees Application Areas > Data Mining Software Tools Fundamental Concepts of Data and Knowledge > Data Concepts

Two nodes of the search tree, n and n′, with their states, s(n) and s(n′). Executing the action a(n′) on s(n) adds a split to leaf ℓ, resulting in two new leaves ℓ_L and ℓ_R. The depth of a search node corresponds to the number of upstream actions that led to it, and is equal to the number of splits of its decision tree (DT). For example, node n′ has search depth equal to 3, and s(n′) has three internal nodes (in black) and four leaves (in gray)

[ Normal View | Magnified View ]

Effect of bootstrapping on the C4.5b policy as a function of dataset size. The plots display the difference in average F1 score between (a) the C4.5b and validation‐set (VS) performance policies, and (b) the C4.5b and C4.5 policies. Each dot does represents a dataset. Bootstrapping the induction and validation sets during simulation helped improve the performance for datasets with less than 730 examples

[ Normal View | Magnified View ]

Difference between the F1 obtained with Upper Confidence Bound applied to tree (UCT)–decision tree (DT) algorithm using the validation‐set performance policy and the C4.5 algorithm. Pruning methods are (a) none, (b) value‐based, (c) decision tree‐based, and (d) both. Each point represents a dataset

[ Normal View | Magnified View ]

Maximum search depth of Upper Confidence Bound applied to tree (UCT)–decision tree (DT) algorithm using the validation‐set performance policy (a) without search pruning, (b) with value‐based pruning, (c) with decision tree‐based pruning, and (d) with both methods. Each dot represents a dataset

[ Normal View | Magnified View ]

Illustration of one iteration of the UCT‐DT approach

[ Normal View | Magnified View ]

References

Alcalá‐Fdez,, J., Sanchez, L., Garcia, S., del Jesus, M. J., Ventura, S., Garrell, J. M., … Fernández, J. C. (2009). KEEL: a software tool to assess evolutionary algorithms for data mining problems. Soft Computing, 13(3), 307–318.
Alcalá‐Fdez,, J., Fernandez,, A., Luengo,, J., Derrac,, J., García,, S., Sánchez,, L., Herrera,, F.(2011). KEEL Data‐Mining Software Tool: Data Set Repository, Integration ofAlgorithms and Experimental Analysis Framework. Journal of Multiple‐Valued Logic and Soft Computing, 17(2‐3) 255–287.
Auer,, P., Cesa‐Bianchi,, N., & Fischer,, P. (2002). Finite‐time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3), 235–256.
Barros,, R. C., Basgalupp,, M. P., De Carvalho,, A. C., & Freitas,, A. A. (2012). A survey of evolutionary algorithms for decision‐tree induction. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(3), 291–312.
Bennett,, K. (1994). Global tree optimization: A non‐greedy decision tree algorithm. In Computing science and statistics (pp. 156–160). New York, NY: Springer.
Breiman,, L. (1996). Bagging predictors. Machine Learning, 24(2), 123–140.
Breiman,, L. (2001). Random forests. Machine Learning, 45(1), 5–32.
Breiman,, L., Friedman,, J. H., Olshen,, R. A., & Stone,, C. J. (1984). Classification and regression trees. Belmont, CA: Wadsworth International Group.
Browne,, C. B., Powley,, E., Whitehouse,, D., Lucas,, S. M., Cowling,, P. I., Rohlfshagen,, P., … Colton,, S. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.
Champandard,, A. J. (2014). Monte‐Carlo tree search in TOTAL WAR: ROME II`s campaign AI. AIGameDev.com. Retrieved from aigamedev. com/open/coverage/mcts‐rome‐i
Chaslot,, G., Bakkes,, S., Szita,, I., & Spronck,, P. (2008). Monte‐Carlo tree search: A new framework for Game AI. In Artificial intelligence and interactive digital entertainment.
Demsar,, J. (2006). Statistical comparison of classifiers over multiple data sets. Journal of Machine Learning Research, 7(7), 1–30.
Dwyer,, K., & Holte,, R. (2007). Decision tree instability and active learning. In European conference on machine learning (pp. 128–139).
Elith,, J., Leathwick,, J. R., & Hastie,, T. (2008). A working guide to boosted regression trees. Journal of Animal Ecology, 77(4), 802–813.
Equal Credit Opportunity Act. (Revised 2011). 12 X C.F.R. § 1002.9(b)(2).
Esmeir,, S., & Markovitch,, S. (2007). Anytime learning of decision trees. Journal of Machine Learning Research, 8(May), 891–933.
Flach,, P. A. (2003). The geometry of ROC space: Understanding machine learning metrics through ROC isometrics. In ICML (pp. 194–201).
Freitas,, A. A. (2002). Data mining and knowledge discovery with evolutionary algorithms. New York, NY: Springer.
Friedman,, J. H. (2001). Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29, 1189–1232.
Friedman,, M. (1937). The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 32(200), 675–701.
Gan,, X., Bao,, Y., & Han,, Z. (2011). Real‐time search method in nondeterministic game‐Ms. Pac‐Man. International Computer Games Association Journal, 34(4), 209–222.
General Data Protection Regulation. (2016). Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016, repealing Directive 95/46/EC, O.J. L 119, 4.5.:1–88.
Guidotti,, R., Monreale,, A., Ruggieri,, S., Turini,, F., Giannotti,, F., & Pedreschi,, D. (2018). A survey of methods for explaining black box models. ACM Computing Surveys (CSUR), 51(5), 93.
Guyon,, I. (2003). Design of experiments for the NIPS 2003 variable selection benchmark. Retrieved from clopinet.com/isabelle/Projects/NIPS2003
Hara,, S., & Hayashi,, K. (2016). Making tree ensembles interpretable: A Bayesian Model Selection Approach. arXiv preprint: 1606.09066v3.
Hyafil,, L., & Rivest,, R. L. (1976). Constructing optimal binary decision trees is NP‐complete. Information Processing Letters, 5(1), 15–17.
Kass,, G. V. (1980). An exploratory technique for investigating large quantities of categorical data. Applied Statistics, 29, 119–127.
Kaufmann,, E., & Koolen,, W. M. (2017). Monte‐Carlo tree search by best arm identification. Advances in Neural Information Processing Systems, 4897–4906.
Kocsis,, L., & Szepesvári,, C. (2006). Bandit based Monte‐Carlo planning. ECML, 6, 282–293.
Kretowski,, M., & Grzes,, M. (2005). Global learning of decision trees by an evolutionary algorithm. Information Processing and Security Systems, 401–410.
Lee,, J., Scott,, D. J., Villarroel,, M., Clifford,, G. D., Saeed,, M., & Mark,, R. G. (2011). Open‐access MIMIC‐II database for intensive care research. In Engineering in medicine and biology society, EMBC, 2011 annual international conference of the IEEE (pp. 8315–8318).
Lichman,, M. (2013). UCI machine learning repository. Retrieved from archive.ics.uci.edu
Munos,, R. (2011). Optimistic optimization of a deterministic function without the knowledge of its smoothness. In Advances in neural information processing systems (pp. 783–791).
Murthy,, S., & Salzberg,, S. (1995). Lookahead and pathology in decision tree induction. In IJCAI (pp. 1025–1033).
Norouzi,, M., Collins,, M., Johnson,, M. A., Fleet,, D. J., & Kohli,, P. (2015). Efficient non‐greedy optimization of decision trees. Advances in neural information processing systems, 1729–1737.
Norton,, S. W. (1989). Generating better decision trees. In International Joint Conference on Artificial Intelligence (IJCAI) (Vol. 89, pp. 800–805). San Francisco, CA: Morgan Kaufmann.
O`Keeffe,, D. (2017). Diagnose specific language impairment in children. Retrieved from www.kaggle.com/dgokeeffe/specific-language-impairment
Papagelis,, A., & Kalles,, D. (2001). Breeding decision trees using evolutionary techniques. In ICML (Vol. 1, pp. 393–400).
Quinlan,, R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106.
Quinlan,, R. (1992). Ross Quinlan`s homepage: C4.5 Release 8. Retrieved from www.rulequest.com/Personal/
Quinlan,, R. (1993). C4.5: Programs for machine learning. San Mateo, CA: Morgan Kaufmann.
Rokach,, L., & Maimon,, O. (2005). Top‐down induction of decision trees classifiers—A survey. IEEE Transactions on Systems and Cybernetics, 35(4), 476–487.
Schapire,, R. E. (1999). A brief introduction to boosting. In IJCAI international joint conference on artificial intelligence (Vol. 2, pp. 1401–1406). San Francisco, CA: Morgan Kaufmann.
Sheskin,, D. J. (2003). Handbook of parametric and nonparametric statistical procedures. Boca Raton, FL: Chapman and Hall/CRC Press.
Shperberg,, S. S., Shimony,, S. E., & Felner,, A. (2017). Monte‐Carlo tree search using batch value of perfect information. In Uai.
Silver,, D., Huang,, A., Maddison,, C. J., Guez,, A., Sifre,, L., van den Driessche,, G., … Hassabis,, D. (2016). Mastering the game of go with deep neural networks and tree search. Nature, 529(7587), 484–489.
Tolpin,, D., & Shimony,, S. E. (2012). Mcts based on simple regret. In Twenty‐sixth aaai conference on artificial intelligence.
Utgoff,, P. E. (1989). Incremental induction of decision trees. Machine Learning, 4(2), 161–186.
Weng,, S. F., Reps,, J., Kai,, J., Garibaldi,, J. M., & Qureshi,, N. (2017). Can machine‐learning improve cardiovascular risk prediction using routine clinical data? PLoS One, 12(4), e0174944.
Wilcoxon,, F. (1945). Individual comparisons by ranking. Biometrics Bulletin, 1(6), 80–83.
Zhang,, Q.‐s., & Zhu,, S.‐C. (2018). Visual interpretability for deep learning: A survey. Frontiers of Information Technology %26 Electronic Engineering, 19(1), 27–39.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts