Polynomial time learning in logic programming and constraint logic programming
Résumé
Induction in first-order logic languages suffers from an additional factor of complexity compared to induction in attribute-value languages: the number of possible matchings between a candidate hypothesis and a training example. This paper investigates the use of a stochastic bias to control this factor of complexity: the exhaustive exploration of the matching space is replaced by considering a fixed number of matchings, obtained by random sampling. One thereby constructs from positive and negative examples a theory which is only approximately consistent. Both the degree of approximation and the computational cost of induction are controlled from the number of samples allowed. This approach is illustrated and validated on the mutagenesis problem. An ad hoc sampling mechanism has been purposely designed and experimental results fully demonstrates the power of stochastic approximate induction in terms of both predictive accuracy and computational cost. Furthermore, this approach applies for learning both logic programs as it is usually the case in ILP, and constrained logic programs, ie extended logic programs that can naturally handle numerical information. The gain of learning constrained logic programs for the mutagenesis problem is evaluated by comparing the predictive accuracy of the theories induced in both languages.
Origine : Fichiers produits par l'(les) auteur(s)
