Induction of Decision Multi-Trees using Levin Search

César Ferri-Ramírez, José Hernández-Orallo, M. José Ramírez-Quintana

Abstract

In this paper, we present a method for generating very expressive decision trees over a functional logic language. The generation of the tree follows a short-to-long search which is guided by the MDL principle. Once a solution is found, the construction of the tree goes on in order to obtain more solutions ordered as well by description length. The result is a multi-tree which is populated taking into consideration computational resources according to a Levin search. Some experiments show that the method pays off in practice.

Keywords: Machine Learning, Decision-tree Induction, Inductive Logic Programming (ILP), Levin search, Minimum Description Length (MDL).