zbMATH — the first resource for mathematics

Embedding decision trees and random forests in constraint programming. (English) Zbl 06605749
Michel, Laurent (ed.), Integration of AI and OR techniques in constraint programming. 12th international conference, CPAIOR 2015, Barcelona, Spain, May 18–22, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-18007-6/pbk; 978-3-319-18008-3/ebook). Lecture Notes in Computer Science 9075, 74-90 (2015).
Summary: In past papers, we have introduced empirical model learning (EML) as a method to enable combinatorial optimization on real world systems that are impervious to classical modeling approaches. The core idea in EML consists in embedding a machine learning model in a traditional combinatorial model. So far, the method has been demonstrated by using neural networks and constraint programming (CP). In this paper we add one more technique to the EML arsenal, by devising methods to embed decision trees (DTs) in CP. In particular, we propose three approaches: 1) a simple encoding based on meta-constraints; 2) a method using attribute discretization and a global table constraint; 3) an approach based on converting a DT into a multi-valued decision diagram, which is then fed to an mdd constraint. We finally show how to embed in CP a Random Forest, a powerful type of ensemble classifier based on DTs. The proposed methods are compared in an experimental evaluation, highlighting their strengths and their weaknesses.
For the entire collection see [Zbl 1337.68015].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI