Welcome to the UPF Digital Repository

A Monte Carlo tree search approach to learning decision trees

Show simple item record

dc.contributor.author Nunes, Cecília
dc.contributor.author De Craene, Mathieu
dc.contributor.author Langet, Hélène
dc.contributor.author Camara, Oscar
dc.contributor.author Jonsson, Anders, 1973-
dc.date.accessioned 2019-08-01T06:27:19Z
dc.date.available 2019-08-01T06:27:19Z
dc.date.issued 2019
dc.identifier.citation Nunes C, De Craene M, Langet H, Camara O, Jonsson A. A Monte Carlo tree search approach to learning decision trees. In: Proceedings 17th IEEE International Conference on Machine Learning and Applications, ICMLA 2018; 2018 Dec 17-20; Orlando, Florida. Piscataway, NJ: Institute of Electrical and Electronics Engineers; 2018. p. 429-35. DOI: 10.1109/ICMLA.2018.00070
dc.identifier.uri http://hdl.handle.net/10230/42216
dc.description Comunicació presentada a: 17th IEEE International Conference on Machine Learning and Applications (ICMLA) celebrada del 17 al 20 de 2018 a Orlando, Estats Units.
dc.description.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. Since exploring the space of all possible DTs is computationally intractable, we propose a DT learning approach based on MCTS. To bound the branching factor of MCTS, we limit the number of decisions at each level of the search tree, and introduce mechanisms to balance exploration, DT size and the statistical significance of the predictions. To mitigate the computational cost of our method, we employ a move pruning strategy that discards some branches of the search tree, leading to improved performance. The experiments show that our approach outperformed locally optimal search in 20 out of 31 datasets, with a reduction in DT size in most of the cases.
dc.description.sponsorship This work is supported by the European Union Horizon 2020 Programme for Research and Innovation, under grant agreement No. 642676 (CardioFunXion).
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Institute of Electrical and Electronics Engineers (IEEE)
dc.relation.ispartof Proceedings 17th IEEE International Conference on Machine Learning and Applications, ICMLA 2018; 2018 Dec 17-20; Orlando, Florida. Piscataway, NJ: Institute of Electrical and Electronics Engineers; 2018.
dc.rights © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. http://dx.doi.org/10.1109/ICMLA.2018.00070
dc.title A Monte Carlo tree search approach to learning decision trees
dc.type info:eu-repo/semantics/conferenceObject
dc.identifier.doi http://dx.doi.org/10.1109/ICMLA.2018.00070
dc.subject.keyword Decision trees
dc.subject.keyword Monte Carlo tree search
dc.subject.keyword Interpretability
dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/642676
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/acceptedVersion


This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Statistics

Compliant to Partaking