Thèse

Aix-Marseille Université Laboratoire d’Informatique Fondamentale de Marseille Thèse présentée pour obtenir le grade de Docteur d’Aix-Marseille Université Délivré par l’Université de Provence Spécialité: Informatique par Guillaume Stempfel Robustesse des Séparateurs Linéaires au Bruit de Classification Thèse soutenue publiquement le 09 Octobre 2009 meM Florence d’Alché-Buc, Université d’Évry-Val d’Essonne (Examinatrice) M. François Denis, Aix-Marseille Université (Examinateur) M. Rémi Gilleron, Université Charles-de-Gaulle Lille 3 (Rapporteur) M. Yves Grandvalet, Université de Technologie de Compiègne M. Jérome Mainka, Antidot (Examinateur) M. Liva Ralaivola, Aix-Marseille Université (Directeur de Thèse)Table des matières Table des matières iii Introduction 1 I Préliminaires 11 1 Classification supervisée et bruit de classification 13 1.1 Bases de la Classification Supervisée . . . . . . . . . . . 14 1.2 Bruit de Ction . . . . . . . . . . . . . . . . . . . . 19 1.3 Bruit Cccn et Semi-supervisé . . . . . . . . . . . . . . . . . 23 1.4 Une Heuristique pour Estimer les Taux de Bruit . . . . . 24 1.5 Le Cadre PAC . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 Bornesde Généralisationet Complexitéde Classesde Concepts 31 2.1 Dimension de Vapnik-Chervonenkis . . . . . . . . . . . . . 33 2.2 Complexité de Rademacher . . . . . . . . . . . . . . . . . . 36 2.2.1 Structure Type pour l’Établissement d’une Borne de Gé- néralisation . . . . . . . . . . . . . . . . . . . . . . . . . 38 3 Noyaux de Mercer et Réduction de Dimension 41 3.1 Noyaux de Mercer et Astuce du Noyau . . . . . . . . . . . 42 3.2 Réduction de Dimension par Projections Déterministes 45 3.3 Réd de D par Pr Aléatoires . . 48 II Perceptrons et Bruit de Classification 51 4 Un Premier Algorithme : le Perceptron Linéaire 53 4.1 L’Algorithme du Perceptron . . . . . . . . . . . . . . . . . 54 4.2 Perceptron et Bruit de Classification . . . . . . . . . . . 56 5 Rp-learn, un Algorithme pour l’Apprentissage de Per- ceptrons à Noyau 63 5.1 Un Nouveau Modèle d’Altération des Données : le Bruit Mixte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2 Perceptrons et Tolérance au Bruit Mixte . . . . . . . . . 67 5.3 Peronset Projections Aléatoires,versla Dimen- sion Infinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 iiiIII Machines à Vecteurs de Support et Bruit de Classifica- tion 83 6 Machines à Vecteurs de Support et Tolérance au Bruit 85 6.1 Machines à Vecteurs de S . . . . . . . . . . . . . . . 86 6.2 Optimisation dans le Dual . . . . . . . . . . . . . . . . . . 91 6.3 Oation dans le Primal . . . . . . . . . . . . . . . . . 92 6.4 Algorithme par Plans Sécants . . . . . . . . . . . . . . . . 94 6.5 Tolérance au Bruit des Svm . . . . . . . . . . . . . . . . . . 99 7 nSvm, ou l’Apprentissage de CSvm sur des Données Bruitées 101 7.1 Les Svm ne sont pas Cn-tolérantes . . . . . . . . . . . . . 102 7.2 Un Programme d’Optimisation pour les Svm Bruitées . 111 7.3 Analyse de la Solution de nSvm . . . . . . . . . . . . . . . 114 7.4 Résoudre nSvm . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7.5 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7.5.1 Données Synthétiques . . . . . . . . . . . . . . . . . . . 122 7.5.2 Problèmes Uci . . . . . . . . . . . . . . . . . . . . . . . 123 7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 8 Un Algorithme à Plans Sécants pour la Résolution de nSvm 127 8.1 Description Haut Niveau de l’Approche . . . . . . . . . . 128 8.2 L’Algorithme Scpa . . . . . . . . . . . . . . . . . . . . . . . 129 8.3 Analyse de la Convergence de Scpa . . . . . . . . . . . . . 130 8.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 8.5 S . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 8.5.1 Simulations Semi-Supervisées Asymétriques . . . . . . . 137 8.5.2 Application Pratique au Jeu de Données Images Corel . 138 8.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 9 Conclusion 145 A Annexes 149 A.1 Preuve du Lemme 5.2 . . . . . . . . . . . . . . . . . . . . . . 149 A.2 P du L 8.1 . . . . . . . . . . . . . . . . . . . . . . 150 A.3 Borne de Chernoff . . . . . . . . . . . . . . . . . . . . . . . 151 Bibliographie 153 Résumé 165 ivIntroduction Généralement considérée comme une des disciplines de l’intelligence ar- tificielle, l’apprentissage automatique est fortement lié, entre autres, aux statistiques, à la théorie des probabilités, aux sciences cognitives et bien sûr à l’informatique théorique. Elle consiste en la conception et l’analyse de méthodes non triviales, d’algorithmes permettant à une machine, à partir d’un ensemble de données ou de mesures, d’effectuer automatique- ment des tâches complexes comme la prise intelligente de décision ou la reconnaissance de motifs. Le champ des applications de l’apprentissage automatique est très large et se situe dans des domaines aussi divers que la biologie, la chimie, la robotique, la linguistique et les technologies web. Citons quelques exemples de problèmes qu’il est possible de résoudre en utilisant des techniques relevant de l’apprentissage automatique. D’abord, considérons un site internet de vente par correspondance. Celui-ci sou- haite mettre en place un système de recommandation automatique, en conseillant à un acheteur des produits pouvant l’intéresser. Une des ap- proches possibles consiste, à partir des commandes précédemment effec- tuées et des pages visitées par chaque utilisateur, à identifier des groupes de clients au comportement proche grâce à une méthode d’apprentissage non supervisée ou de clustering. Ainsi, on pourra orienter l’internaute vers des produits commandés par des utilisateurs aux centres d’intérêt simi- laires. Second exemple, la poste américaine s’est intéressée dans les an- nées 1980 au problème de la reconnaissance de chiffres manuscrits, afin d’être capable de diriger automatiquement le courrier en fonction du code postal. On dispose au départ d’une base de données (un ensemble d’ap- prentissage) constituée de quelques milliers de chiffres, provenant de scrip- teurs différents, et identifiés, par un être humain, comme appartenant à une classe donnée, c’est-à-dire comme étant un 0, un 1, un 8... A partir de ces exemples munis d’une classe, ou étiquette, l’objectif est de calculer une fonction capable d’associer automatiquement une classe (de catégo- riser) à un chiffre manuscrit ne provenant pas de l’ensemble d’appren- tissage. C’est à ce type de problèmes de classification supervisée que nous nous intéressons dans ce manuscrit. Enfin, dernier exemple, la concep- tion d’un mini-hélicoptère capable de voler à l’envers en vol stationnaire. Une stratégie envisageable consiste à avoir recours à l’apprentissage par renforcement. L’hélicoptère va effectuer des vols successifs et sera récom- pensé (positivement ou négativement) suivant ses actions à chaque étape d’un vol. Par exemple, la récompense sera positive lorsque l’hélicoptère réussira à se retourner. Ainsi, l’hélicoptère va, au cours de cette séquence d’expériences (autrement dit de ces vols successifs), rechercher le com- portement lui permettant de maximiser les récompenses obtenues jusqu’à atteindre le maximum, lorsque le véhicule est en vol stationnaire inversé. 12 Introduction C’est à la classification supervisée que nous nous intéressons dans ce document. Cet ensemble de problèmes peut être globalement résumé de la manière suivante : on dispose initialement d’une certaine quantité d’exemples décrit par un ensemble de variables (ou attributs), constituant un échantillon d’apprentissage, chaque exemple étant associé à une éti- quette. Le but est alors de construire, grâce à cet échantillon, une fonction de classification (une fonction associant une classe à une description) pou- vant prédire correctement la classe de nouveaux exemples qui lui seront présentés, c’est-à-dire de généraliser au mieux. De nombreux types d’algorithmes ont été proposés pour résoudre ces pro- blèmes de catégorisation. Tout d’abord, la méthode des k plus proches voi- sins (Cover et Hart [1967]). Cette méthode, qualifiée de paresseuse puisque ne nécessitant pas d’apprentissage à proprement parler, consiste à choisir la classe majoritaire parmi les k exemples (de l’ensemble d’apprentissage) les plus proches de l’exemple que nous cherchons à classifier. Les k-plus- proches voisins permettent ainsi une classification extrêmement simple. Le choix de la distance utilisée est crucial, la qualité de la classification en dépendant grandement. Autre famille d’algorithmes utilisée pour la classification supervisée, les arbres de décision, qui sont encore très populaires. Ces procédures construisent des classifieurs ayant la forme d’arbre : chaque noeud repré- sente une règle de décision, et chaque feuille une classe. Pour classer un exemple, il suffit donc de parcourir l’arbre depuis la racine, en choisissant à chaque noeud, selon la règle de décision associée, la branche correspon- dant à l’exemple que l’on classe, jusqu’à arriver à une feuille et renvoyer l’étiquette correspondante. Il existe plusieurs algorithmes pour l’appren- tissage d’arbres de décision ; on peut citer parmi les plus répandus CART (Breiman et coll. [1984]) et C4.5 (Quinlan [1993]). Ces algorithmes pré- sentent l’avantage d’être assez performants en général et surtout de pro- duire des classifieurs très facilement lisibles et interprétables, y compris pour des non-initiés, et peuvent ainsi être facilement destinés à la sélec- tion d’attributs. Le classifieur naïf de Bayes est un classifieur probabiliste introduit dans Minsky [1961] et qui utilise la règle de Bayes. Le qualificatif ’naïf’ pro- vient d’une l’hypothèse très forte : chaque caractéristique descriptive des données est considérée comme indépendante de tou