Abstract FR:

Dans le cadre de l'apprentissage inductif, les données sont souvent mal décrites et bruitées. Dans ce cas, la génération de procédures de classification présentant une parfaite adéquation aux données, produit des résultats de taille (ou complexité) importante. Les performances sont excellentes sur les données ayant servi à apprendre, mais mauvaises sur un ensemble test. On cherche alors des procédures présentant un bon compromis complexité adéquation aux données et la tache se rapproche de l'optimisation. Plusieurs approches gloutonnes ont été proposées. L'objet de cette thèse est de proposer une approche plus puissante. L'apport principal est un algorithme d'apprentissage base sur la recherche stochastique d'une liste de décision de faible complexité. Cet algorithme procède en deux phases distinctes: la diversification et l'intensification de la recherche, exécutées respectivement par le recuit simule et par la méthode tabou