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

  • Authors
  • Nunes C, De Craene M, Langet H, Camara O, Jonsson A
  • UPF authors
  • JONSSON ., PER ANDERS; CAMARA REY, OSCAR; DE CRAENE ., MATHIEU SIMON R;
  • Type
  • Scholarly articles
  • Journal títle
  • WIREs data mining and knowledge discovery
  • Publication year
  • 2020
  • Volume
  • 10
  • Number
  • 3
  • Pages
  • 0-0
  • ISSN
  • 1942-4795
  • Publication State
  • Published
  • 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.
  • Complete citation
  • Nunes C, De Craene M, Langet H, Camara O, Jonsson A. Learning decision trees through Monte Carlo tree search: An empirical evaluation. WIREs data mining and knowledge discovery 2020; 10(3).
Bibliometric indicators
  • 0 times cited Scopus
  • 0 times cited WOS
  • Índex Scimago de 1.506(2020)