Abstract FR:

Dans cette thèse, nous nous préoccupons d'apprentissage à partir d'exemples. Un bon algorithme d'apprentissage doit pouvoir trouver des formules présentant un bon compromis entre taille et adéquation aux données. Nous avons étudié la faisabilité de ce compromis pour une grande partie des formules booléennes. Nous avons montré qu'il est impossible pour la plupart d'entre elles. Nous avons également étudié une nouvelle classe de formules booléennes, les comités de décision, et montre qu'elle contient une sous-classe parmi les plus vastes étant apprenables dans le modèle PAC. Nous avons étudié les rapports qu'elle entretient avec d'autres classes de formules booléennes, ce qui nous a permi de mettre en évidence le pouvoir expressif des listes de décision. Nous avons étudié d'un point de vue théorique les capacités d'apprentissage d'un algorithme pour l'aide à la supervision de réseaux. Nous avons également étudié les capacités d'approximation des systèmes d'apprentissage utilisant la programmation logique inductive. Nous donnons ensuite deux algorithmes permettant d'apprendre en utilisant respectivement les comités de décision et les listes de décision. Nos résultats sur un grand nombre de problèmes tests montrent la validité de notre approche, en particulier vis-à-vis des algorithmes construisant des arbres de décision.