Blossom: an Anytime Algorithm for Computing Optimal Decision Trees - LAAS-Décision et Optimisation Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

Blossom: an Anytime Algorithm for Computing Optimal Decision Trees

Emir Demirović
  • Fonction : Auteur
  • PersonId : 1129473
Louis Jean
  • Fonction : Auteur
  • PersonId : 1257396

Résumé

We propose a simple algorithm to learn optimal decision trees of bounded depth. This algorithm is essentially an anytime version of the state-ofthe-art dynamic programming approach. It has virtually no overhead compared to heuristic methods and is comparable to the best exact methods to prove optimality on most data sets. Experiments show that whereas existing exact methods hardly scale to deep trees, this algorithm learns trees comparable to standard heuristics without computational overhead, and can significantly improve their accuracy when given more computation time, even for deep trees.

Mots clés

Fichier principal
Vignette du fichier
hal.pdf (610.24 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
licence : CC BY - Paternité

Dates et versions

hal-04108022 , version 1 (26-05-2023)

Licence

Paternité

Identifiants

  • HAL Id : hal-04108022 , version 1

Citer

Emir Demirović, Emmanuel Hebrard, Louis Jean. Blossom: an Anytime Algorithm for Computing Optimal Decision Trees. International Conference on Machine Learning, Jul 2023, Honolulu, United States. ⟨hal-04108022⟩
67 Consultations
102 Téléchargements

Partager

Gmail Facebook X LinkedIn More