Thèse
169 pages
Français

Thèse

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
169 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

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 . . . . . . . . . . . . . . . . . . . . ...

Sujets

Informations

Publié par
Nombre de lectures 204
Langue Français
Poids de l'ouvrage 2 Mo

Exrait

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 toutes les autres étant donné la classe. L’apprentissage se fait ensuite en maximisant la vraisem- blance. Malgré l’hypothèse naïve, le comportement de l’algorithme s’avère souvent satisfaisant, y compris sur des données complexes, et même en présence d’un échantillon d’apprentissage de taille réduite. Introduit dans Rosenblatt [1958] ; Block [1962], le perceptron linéaire est un algorithme destiné à la classification linéaire binaire (à deux classes), c’est-à-dire au calcul d’hyperplans de séparation. Le fonctionnement de l’algorithme est simple : il repose sur une mise à jour itérative du classi- fieur à l’aide d’un exemple mal classé. Si les données d’apprentissage sont séparables linéairement, alors l’algorithme est prouvé convergent avec une une borne polynomiale sur le nombre maximal d’itérations (Minsky et Pa- pert [1969]). Par contre, dans le cas contraire, l’algorithme échoue à pro- duire un hyperplan séparateur. Introduction 3 Par palier ce défaut, il est possible de combiner des perceptrons sous la forme de perceptrons multi-couches (ces classifieurs font partie de la fa- mille des réseaux de neurones artificiels, Hopfield [1988]). Inspiré sché- matiquement par le fonctionnement de neurones biologiques, le percep- tron multi-couches est composé d’une succession de couches de neurones (de perceptrons linéaires), chaque neurone étant relié aux neurones de la couche précédente par des synapses et calculant une somme pondérée des sorties des neurones de la couche précédente. La phase d’apprentissage consiste à rechercher pour chaque neurone la pondération optimale pour l’ensemble d’apprentissage considéré. Les perceptrons multi-couches per- mettent d’aborder des problèmes non linéaires plus complexes mais ils présentent deux inconvénients principaux. Tout d’abord, l’apprentissage est difficile à mettre en oeuvre puisqu’il demande la minimisation d’une fonction de coût non-convexe. Ensuite, interpréter le classifieur obtenu est une tâche très ardue. Basés également sur la combinaison de classifieurs simples (par exemple, des arbres de décision constitués d’une unique règle de décision), les algorithmes de boosting se sont fortement développé dans les années 1990 (Adaboost, Freund et Schapire [1997]). Ces procédures consistent à construire itérativement un classifieur complexe à partir de classifieurs faibles (c’est-à-dire ayant un taux d’erreur éventuellement proche de 50% sur l’ensemble d’apprentissage). A chaque itération, le poids de chaque exemple de l’échantillon d’apprentissage est modifié en fonction de la décision du classifieur fort (fonction qui combine les classifieurs faibles calculés lors des itérations précédentes). Enfin, dernier algorithme d’apprentissage que nous abordons, les ma- chines à vecteurs de support (ou Svm, Vapnik [1998]). Ce programme d’optimisation produit un séparateur linéaire qui tente de classifier correc- tement les exemples de l’échantillon d’apprentissage, tout en maximisant la marge (c’est-à-dire la distance entre le classifieur et les exemples d’ap- prentissage). Maximiser la marge permet, en effet, de bénéficier de bonnes propriétés théoriques de généralisation. Ces bonnes propriétés théoriques proviennent également des caractéristiques parcimonieuses des Svm (Vap- nik [1995]), c’est-à-dire de la possibilité d’exprimer le classifieur calculé en fonction d’un nombre réduit d’instances d’apprentissage. Nous diffé- rencions deux types de Svm : si les Svm à marge dure sont uniquement destinées à la classification de problèmes linéaires, les CSvm (ou Svm à marge douce), par l’ajout de variables d’écart au programme d’optimi- sation, permettent quelques erreurs sur l’échantillon d’apprentissage afin de maximiser la marge, et donc d’aborder des problèmes qui ne sont pas totalement linéairement séparables. Le travail présenté ici s’intéresse à l’apprentissage de séparateurs linéaires et donc se concentre particulièrement aux algorithmes du perceptron li- néaire et des machines à vecteurs de support à marge douce. Les argu- ments nous permettant de nous limiter à l’apprentissage d’hyperplans sont multiples : tout d’abord, ces algorithmes d’appr sont simples à mettre en oeuvre et relativement répandus. Ensuite, de cette manière, nous limitons la complexité de la classe de fonctions considérée. Contrôler cette complexité est un enjeu important, puisqu’elle influe directement sur 4 Introduction les capacités théoriques de généralisation d’un classifieur. Toutefois, ces deux algorithmes paraissent présenter des limitations assez nettes : l’algo- rithme du perceptron linéaire ne converge pas si l’échantillon d’apprentis- sage n’est pas séparable. Et, même si le classifieur calculé par Csvm peut faire quelques erreurs sur l’ensemble d’apprentissage, elles ne peuvent, a priori, apprendre des fonctions de classification complexes. Le monde n’est malheureusement pas linéairement séparable. Nous avons alors recours à l’astuce du noyau. Ce ’truc’ permet, sous condition du choix d’un noyau de Mercer adéquat, de plonger les données dans un espace virtuel de très grande dimension (potentiellement infinie) où ces données sont linéairement séparables. Ainsi, il devient possible d’utiliser un algorithme de classification linéaire classique dans l’espace de plonge- ment, et de calculer ainsi une fonction qui classe correctement l’ensemble d’apprentissage même si celui-ci n’est pas linéairement séparable. Cette stratégie est très intéressante, puisque des méthodes simples comme le perceptron linéaire peuvent ainsi s’appliquer sur des problèmes plus com- plexes, et donc nous évite le recours à l’apprentissage d’un perceptron multi-couches, par exemple, beaucoup plus lourd à mettre en oeuvre. En conclusion, nous parlons donc dans ce manuscrit essentiellement de clas- sification linéaire, tout en gardant toujours à l’esprit que l’astuce du noyau rend possible son extension à des problèmes non linéairement séparables. Nous nous intéressons à l’apprentissage de séparateurs linéaires dans un cadre particulier, celui du bruit. Il n’est pas rare, en pratique, que les données dont nous disposons pour l’apprentissage soient altérées, par un ensemble de processus que nous regrouperons sous la dénomination de bruit. Par exemple, supposons que nos données soient obtenues par un en- semble de capteurs. L’un de ces capteurs est malheureusement défectueux, sans que l’on soit capable de le détecter. Les informations enregistrées, qui constituent l’ensemble d’apprentissage, s’avèrent donc être en partie erro- nées. Autre exemple, un problème de bioinformatique où l’on souhaite apprendre la fonction de protéines. L’ensemble d’apprentissage est consti- tué par un spécialiste humain, en décrivant du mieux possible un certain nombre de protéines. Malheureusement, cette description est difficile à effectuer, certains attributs peuvent être impossibles à évaluer, d’autres er- ronés. Ainsi, les descriptions de certains exemples s’avèrent être fausses ou incomplètes. Dans ces deux exemples, l’altération des données d’ap- prentissage risque d’induire nos algorithmes en erreur, et donc de faire échouer l’apprentissage. Pourtant, à condition d’être capable de gérer ce bruit, il est probablement encore possible d’extraire des caractéristiques intéressantes de ces données. La gestion du bruit est donc un enjeu très important en apprentissage. Parmi les travaux s’étant attaqués à l’apprentissage dans le cadre de bruit, on peut tout d’abord citer ceux s’intéressant à une altération de la des- cription des données par un bruit blanc gaussien (pour illustrer, l’ap- prentissage de réseaux de neurones dans Saad et Solla [1996]). De son coté, Dempster et coll. [1977] s’intéresse à l’apprentissage de bayésiens par l’algorithme Em dans le cadre de données incomplètes. D’autres ar- ticles se sont intéressés à la détection d’outliers, c’est-à-dire d’exemples aberrants (Hawkins [1980] ; Aggarwal et Yu [2001]). On peut également Introduction 5 citer les travaux ayant pour sujet le bruit malicieux (Kearns et Li [1988]). Sous cette hypothèse de bruit, une certaine proportion des exemples est décrite de manière aléatoire. Ainsi, dans ce cadre, Servedio [2003] s’inté- resse au boosting alors que Auer et Cesa-Bianchi [1998] se concentre sur l’apprentissage en ligne de perceptrons. Notre intérêt se porte particulièrement sur le bruit de classification, c’est- à-dire sur un processus de bruit modifiant la classe de certains exemples de l’ensemble d’apprentissage. Le problème est alors rendu plus diffi- cile puisque la procédure d’apprentissage est induite en erreur par ces exemples mal classés et que l’objectif reste, en ayant accès uniquement à ces données bruitées, de produire un classifieur capable de prédire correc- tement la classe (et donc de faire très peu d’erreurs) de nouvelles données qui seront fournies. Nous nous limitons par la suite à des problèmes bi- naires (i.e, à deux classes). Parmi les bruits de classification que l’on peut relever dans la littérature, on peut citer le bruit monotone, altérant plus fortement les données proches de la surface de décision (Bylander [1998]). Autre exemple, le bruit de classification constant par morceaux (ou Cpcn, Decatur [1997]). Dans ce cadre, l’espace de description est partitionné, à chaque partition étant associé une probabilité de voir un exemple être bruité. Nous nous concentrons particulièrement sur deux types de bruits de classification : d’abord, le bruit de classification uniforme (ou Cn, An- gluin et Laird [1988]), où tous les exemples ont la même probabilité de voir leur classe inversée. Ensuite, le bruit de classification constant par classe (ou Cccn, Decatur [1997]), où cette probabilité dépend de la classe (positive ou négative) de l’exemple considéré. Au-delà des arguments classiques (être capable de notamment pallier les erreurs d’étiquetage), savoir gérer le bruit Cccn permet d’aborder diffé- rents problèmes d’apprentissage. Tout d’abord, le cadre semi-supervisé asymmétrique (Denis [1998]) où l’on dispose uniquement d’exemples d’une classe (disons positifs) et non étiquetés, peut se ramener à un pro- blème Cccn. Ce type de problèmes est courant dans les domaines (par exemple, biologie) où l’étiquetage d’une donnée s’avère particulièrement fastidieux. Il suffit alors d’étiqueter en tant que négatifs la totalité des exemples sans étiquette. Nous sommes alors en présence d’un cas de clas- sification Cccn particulier avec un bruit nul sur les négatifs, et strictement supérieur à0 sur les positifs. Ainsi, les théorèmes que l’on obtiendra dans le cadre Cccn seront immédiatement extensibles à ce type de problèmes semi-supervisés. Deuxième type de problèmes que l’on peut aborder via des algorithmes tolérant, est l’apprentissage multi-instances, de sacs de données (Zhou [2004]). Les données se présentent comme étant un en- semble de descriptions. Une donnée est étiqueté positive si au moins une des données qui la compose est positive. En illustration, pre- nons un site web, où chaque page comporte plusieurs photos. Nous cher- chons les photos où apparaissent des chats. Pour constituer l’ensemble d’apprentissage, au lieu d’effectuer l’étiquetage photo par photo, il est possible d’étiqueter page par page, dans le but d’économiser du temps hu- main. Une page est considérée comme positive si au moins une des photos qui la compose représente effectivement un chat. Pour aborder ce type de problèmes, il suffit d’étiqueter comme positives l’ensemble des descrip- 6 Introduction tions composant une donnée positif, et comme négatives celles composant une donnée négative. On se retrouve ainsi dans un cadre Cccn avec un bruit non nul sur les négatifs (Lawrence et Schölkopf [2001]). Parmi les contributions ayant attrait sur la tolérance au bruit de classifica- tion, on peut citer les travaux sur les requêtes statistiques (Kearns [1998]), l’apprentissage d’arbres de décision (Sakakibara [1993]), sur le boosting (Lugosi et Vayatis [2003] ; Kalai et Servedio [2005]), sur le classifieur naïf de Bayes (Denis et coll. [2006]) où au discriminant linéaire de Fisher (Law- rence et Schölkopf [2001]). Deux problèmes nous intéressent particulièrement. D’abord l’apprentis- sage de perceptrons linéaires sur des problèmes altérés par un bruit de classification uniforme. De nombreux articles dans les années 90, se sont intéressés à ce problème, par exemple Bylander [1994] ; Blum et coll. [1996] ; Cohen [1997]. Ces algorithmes sont basés sur l’utilisation de la régularité du bruit de classification pour calculer un vecteur de mise à jour à chaque itération du perceptron. Ils sont accompagnés d’analyses théoriques démontrant que leur complexité en temps et en échantillon- nage sont polynomiales, notamment en fonction de la dimension de l’es- pace. Or, dans le cadre de l’utilisation de méthodes à noyau, l’espace uti- lisé pour l’apprentissage est l’espace de plongement, de très grande di- mension, potentiellement infinie. Dans ce dernier cas, la convergence de ces algorithmes n’est théoriquement plus assurée. Nous nous efforçons donc de proposer un algorithme d’apprentissage basé sur un perceptron linéaire tolérant au bruit Cn et dont les complexités en échantillonnage et en temps sont indépendantes de la dimension de l’espace. Ensuite, l’apprentissage de séparateurs à large marge dans le cadre du bruit de classification constant par classe. Intuitivement, les CSvm semblent, grâce à la marge douce, capables de gérer un bruit de classi- fication sur les données. En effet, sous certaines conditions, CSvm tolère un bruit de classification uniforme. Les articles de Steinwart [2002] et Bart- lett et coll. [2005] exposent ces conditions, Malheureusement, celles-ci ne nous satisfont pas. Elles consistent notamment en une condition d’univer- salité du noyau. Même si certains noyaux usuels sont universels (comme le noyau gaussien), ce n’est pas le cas pour, par exemple, le noyau li- néaire. Lorsqu’on aborde des problèmes spécifiques, et que l’on veut créer un noyau ad-hoc, il paraît très contraignant de s’assurer de l’universalité du noyau conçu. De plus, l’algorithme CSvm n’est pas adapté à des pro- blèmes Cccn, puisque la minimisation du risque empirique n’est pas une stratégie valide dans ce cadre. Nous recherchons donc une approche per- mettant d’obtenir des classifieurs à large marge, via l’usage de machines à vecteurs de support, sur des données altérées par un bruit Cccn. L’objectif du travail présenté ici est donc d’étudier l’apprentissage de sépa- rateurs linéaires (autrement dit d’hyperplans qui permettent d’envisager l’usage de noyaux) sur des données altérées par différents processus de bruit de classification. Nous proposons des algorithmes d’apprentissage efficaces, dérivés de techniques existantes, mais rendus (et prouvés) tolé- rants à certains types de bruit donné. Par efficace, nous entendons capable d’apprendre à partir des données bruitées, une fonction de classification performante sur des données non altérées, en temps raisonnable et donc
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents