THESE

• Sujet : Etude de l’apprentissage Probablement Approximativement Correct : application aux méthodes d'agrégation.

• Directeur de these : Djamel Zighed

• Résumé : Le cadre de ma thèse est le data-mining. Au cours des années 1990 de nouveaux principes d'induction sont apparus les méthodes d'agrégation à base de vote. Les exemples les plus connus sont certainement le Bagging initié par Breiman ainsi que Boosting initié par Freund. Ces méthodes présentent d'excellentes performances sur les problèmes réels. Leur simplicité en font de bons candidats pour résoudre les problèmes de data-mining. Ils reposent en outre sur de solides fondations théoriques inspirées de l'apprentissage Probablement Approximativement Correct (PAC) et plus précisément des travaux de Vapnik. Ma thèse comporte ainsi deux parties distinctes mais complémentaires l'une de l'autre.

  La première consiste en une étude approfondie de l'apprentissage PAC et de la théorie de Vapnik. Cette théorie permet de controler l'erreur réelle à partir de l'erreur empirique pour tout algorithme d'apprentissage sans faire aucune hypothèse sur le problème à traiter. Le théorème de Vapnik et Chervonenkis est un résultat issu de cette théorie. Il propose de majorer le nombre d'exemples requis pour que l'erreur empirique soit un bon estimateur de l'erreur réelle au vu d'un critère de précision et un de fiabilité. Des minorations sur ce nombre d'exemples existent et montrent l'optimalité à une constante multiplicative près de la borne supérieure fournie par le théorème de Vapnik et Chervonenkis. Nous proposons un résultat permettant d'améliorer cette constante. Ce type de résultat ne permet cependant pas d'expliquer le comportement des algorithmes d'agrégation à base de vote. De nouveaux résultats, utilisant une nouvelle notion, appelée parait beaucoup plus adaptée. Cette notion de marge a inspiré de nouveaux algorithmes d'agrégation à base de vote mettant en lumière l'interaction forte entre la théorie et la pratique.

  La seconde partie de ma thèse est justement l'étude des algorithmes à base de vote. Nous présentons dans un premier temps quelques exemples représentatifs dont nous comparerons ensuite les justifications. Dans un second temps nous nous proposons d'adapter ces méthodes à deux problématiques du data mining : le traitement des grandes bases de données ainsi que le traitement des valeurs manquantes.

• Mots - clés : Boosting, PAC, VC-dimension, Neural Networks, Induction trees

• Jury

  rapporteur	Michèle Sebag	Professeur
  rapporteur	Patrick Gallinari	Professeur
  Président	Gilles Venturini	Professeur
  Examinateur	Louis Wehenkel	Professeur
  Directeur	Djamel Zighed	Professeur

Version (provisoire) postcript disponible