Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost

Résumé

Recently, several exact methods to compute decision trees have been introduced. On the one hand, these approaches can find optimal trees for various objective functions including total size, depth or accuracy on the training set and therefore. On the other hand, these methods are not yet widely used in practice and classic heuristics are often still the methods of choice. In this paper we show how the SAT model proposed by [Narodytska et al., 2018] can be lifted to a MaxSAT approach, making it much more practically relevant. In particular , it scales to much larger data sets; the objective function can easily be adapted to take into account combinations of size, depth and accuracy on the training set; and the fine-grained control of the objective function it offers makes it particularly well suited for boosting. Our experiments show promising results. In particular, we show that the prediction quality of our approach often exceeds state of-the-art heuristic methods. We also show that the MaxSAT formulation is well adapted for boosting using the well-known AdaBoost Algorithm.
Fichier principal
Vignette du fichier
MaxSAT_DT_IJCAI_CRC.pdf (287.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02740415 , version 1 (02-06-2020)

Identifiants

  • HAL Id : hal-02740415 , version 1

Citer

Hao Hu, Mohamed Siala, Emmanuel Hébrard, Marie-José Huguet. Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost. IJCAI-PRICAI 2020, 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, Jul 2020, Yokohama, Japan. ⟨hal-02740415⟩
57 Consultations
44 Téléchargements

Partager

Gmail Facebook X LinkedIn More