Soutenance mémoire
Notre société est de nos jours une société tournée vers l’information. Les systèmes d’information jouent donc un rôle prépondérant dans la production de données. Ces données sont à présent produites en masse et de nombreux besoins sont apparus pour leur traitement et leur analyse car ces masses de données atteignent des complexités telles qu’elles sont difficilement appréhendables par un être humain. La nature de ces traitements et analyses est diverse et variée : acquisition, numérisation, filtrage, compression, archivage, indexation, modélisation, prévision, diagnostic, aide à la décision, etc. Ceux-ci sont exploités intensivement dans de nombreux domaines : médecine, aéronautique, biologie, astronomie, etc. Certains de ces domaines ont la particularité de manipuler des flux de données correspondant à de grandes quantités d’images.
L’imagerie médicale est certainement l’un des domaines de la médecine qui a le plus progressé ces vingt dernières années. Dans ce domaine, l’exploitation d’images numériques est courante depuis de nombreuses années à travers des outils comme les scanners, les radiographes, échographes et microscopes numériques. Ces appareillages exploitent des outils de traitements d’images d’une haute technicité. Plus récemment, nous avons assité à une forte demande de logiciels de traitements des images afin d’aider les praticiens dans leurs diagnostics. Les progrès dans le développement de techniques d’apprentissage artificiel ont permis de répondre à cette attente. L’origine de cette demande est de plus en plus pressante et accroît l’importance de l’analyse d’images dans ce domaine. L’imagerie médicale a également des besoins importants d’archivage d’images par des techniques de compression. Celle-ci doit être réalisée en préservant une haute qualité visuelle des images pour qu’elles puissent être interprétées ultérieurement par le corps médical.
Espace d’hypothèses, biais d’apprentissage et principes inductifs
Le pouvoir de généralisation d’un algorithme d’apprentissage artificiel est dépendant du processus inductif qu’il réalise et de l’espace des hypothèses. Cet espace correspond à l’ensemble des fonctions de décision réalisables. Le principe inductif permet de sélectionner dans l’espace des hypothèses, à partir d’un ensemble de données, celles explicitant le mieux ces données. Ces deux concepts représentent le biais d’apprentissage utilisé par l’apprenant artificiel pour produire une fonction de décision avec les meilleurs capacités de généralisation. Des notations et concepts relatifs aux notions d’espace d’hypothèses, de principe inductif et de biais d’apprentissage sont introduites pour permettre de formaliser les principes et objectifs de l’apprentissage supervisé. Ces notations et concepts sont utilisés ensuite dans les chapitres suivants. Des notations relatives à la constitution de bases d’exemples utilisées dans le cadre d’un apprentissage supervisé sont également introduites.
Objets, exemples et oracle
Pour réaliser un processus d’apprentissage à partir d’un ensemble d’objets, la description et la classe de ces objets doivent être accessibles. la description des objets et les classes prédites par l’oracle. Soit O l’espace des objets, X un espace de description (ou espace des entrées) associé à ces objets et un oracle o capable de réaliser une catégorisation des objets issus de O. Dans cette étude, la description d’un objet o ∈ O est un vecteur x = (x1,… ,xn) à n dimensions. Chaque composante xi de ce vecteur est désignée par le terme d’attribut ou caractéristique. Soit fd : O → X , une fonction qui détermine, pour un objet o donné, sa description x dans l’espace des entrées. Cette fonction n’est pas forcément déterministe , traduisant le fait que le processus de description peut être plus ou moins bruité (capteurs électroniques,…). Soit fo : O → Y la fonction d’étiquetage correspondant au processus de catégorisation en nc classes distinctes de l’oracle avec Y l’espace des labels des classes Y = {ω1,… ,ωnc } et ωi la i ème classe. A partir de O, Y, fd et fo il est possible de définir l’espace des exemples Z . Un exemple z ∈ Z correspondant à un objet o ∈ O est un couple de données (x,y) tels que (x,y) = (fd(o),fo(o)). L’oracle qui réalise la labellisation d’un objet n’est pas forcément parfait et il n’a pas forcément un comportement déterministe (i.e. il existe des couples d’exemples (x1,y1) et (x2,y2) dans Z, tel que x1 = x2 et y1 6= y2). Dans ce cas, nous supposerons que pour tout exemple z= (x,y) de l’espace Z, la probabilité conditionnelle pZ(y|x) est définie relativement à l’espace Z considéré (i.e. le comportement de l’oracle est prévisible en probabilité).
Base d’exemples et tirage i.i.d
Pour réaliser un apprentissage supervisé, la constitution de bases d’exemples à partir d’un ensemble d’objets est indispensable. Il est important que chaque base d’exemples soit représentative du problème à caractériser, sinon l’inférence ne pourra pas être de qualité. Pour un problème d’apprentissage donné, la fréquence d’apparition (pO(o)) des différents types d’objets n’est pas la même. La probabilité d’observer un vecteur d’attributs x, un exemple z ou une classe y a une certaine distribution qui dépend des objets du problème, de leur caractérisation et de la nature de l’oracle. Notons que ces distributions ne correspondent pas toujours au problème naturel associé, mais peuvent avoir été intentionnellement modifiées lors de la collecte des données suivant la nature du problème d’apprentissage que l’on souhaite produire. Nous noterons Zm une base de données constituée de m exemples tirés aléatoirement suivant la distribution DZ. Le tirage des exemples est indépendant et identiquement distribué (i.i.d.) relativement à cette distribution. Om désigne les objets utilisés pour la constitution de la base Zm d’exemples. Dans la suite de ce document, la notion d’objet et d’exemple est souvent non différenciée, bien que d’un point de vue pratique cette différenciation puisse être essentielle. Xm et Ym sont les notations associées respectivement aux bases de caractéristiques et de classes, lorsque ces informations sont dissociées de la base des exemples Zm dont elles sont issues. La notation Xm représente également les caractéristiques des objets Om lorsqu’aucun oracle n’est accessible (dans le cadre d’un apprentissage non supervisé, l’apprenant a seulement accès à Xm). Lorsque la taille de la base n’est pas précisée ou que cette information n’est pas essentielle, les notations Z, O, X ou Y sont utilisées.
Théorie de l’apprentissage de Vapnik
La théorie de l’apprentissage de Vapnik permet une analyse PAC (Probably Approximately Correct) avec des espaces d’hypothèses de taille infinie grâce à la notion de dimension de Vapnik-Chervonenkis.
L’analyse PAC
L’analyse PAC consiste à considérer un principe d’induction comme exploitable (approximativement correct) si l’écart entre le risque réel de l’hypothèse sélectionnée h∗I par le principe d’induction et le risque de l’hypothèse idéale h∗ est borné en probabilité et que cette borne est faible. Ce qui correspond à rechercher dans quelles conditions cette relation est vraie:
P (|Rreel (h∗I) − Rreel (h∗)| ≥ ε) < δ (2.15)
avec δ correspondant à la borne de cette probabilité et ε l’écart sur le risque réel. Pour un principe inductif I fixé, l’évolution de ε est une fonction de la base Zm, de la richesse de l’espace d’hypothèses H et de la tolérance δ. En pratique, une analyse dans le pire des cas est réalisée, ce qui permet de s’affranchir de la distribution des exemples. Ceci peut être modélisé par :
∀DZ : P (|Rreel (h∗I) − Rreel (h∗)| ≥ ε(m,H,δ)) < δ (2.16)
avec ε(m,H,δ) signifiant que ε est dépendante du nombre d’exemples m, du choix de l’espace d’hypothèses H et de la tolérance δ. Une analyse PAC peut par exemple étudier comment évolue la taille minimum de l’échantillon m si l’on fixe les valeurs de ε et δ. Ce qui correspond à résoudre le problème:
∀DZ, |Z| > m : P (|Rreel (h∗I) − Rreel (h∗)| ≥ ε) < δ (2.17) .
|
Table des matières
1 Introduction
1.1 Plan de la thèse
1.2 Un bref historique
1.3 Systèmes d’apprentissage supervisé
2 Apprentissage supervisé
2.1 Introduction
2.2 Espace d’hypothèses, biais d’apprentissage et principes inductifs
2.2.1 Objets, exemples et oracle
2.2.2 Base d’exemples et tirage i.i.d
2.2.3 Coût relatif à une hypothèse
2.2.4 Compromis biais-variance
2.2.5 Principes inductifs
2.2.5.1 Sélection de l’hypothèse qui minimise le risque empirique
2.2.5.2 Sélection de l’hypothèse la plus probable
2.2.5.3 Sélection de l’hypothèse qui comprime au mieux l’information
2.2.5.4 Sélection de l’hypothèse la plus stable
2.2.5.5 Sélection de l’hypothèse qui minimise le risque structurel
2.2.5.6 Choix d’un principe inductif
2.3 Théorie de l’apprentissage de Vapnik
2.3.1 L’analyse PAC
2.3.2 Dimension de Vapnik-Chervonenkis
2.3.3 Analyse PAC et VC-dimension
2.4 Algorithmes d’apprentissage supervisés
2.4.1 Les k plus proches voisins
2.4.1.1 Principe général
2.4.1.2 Fondements théoriques
2.4.1.3 Amélioration des capacitées de généralisation
2.4.1.4 Principe SRM pour la règle PPV
2.4.1.5 Variantes de la règle k-ppv
2.4.2 Fenêtres de Parzen
2.4.3 Arbres de décision
2.4.4 Réseaux de neurones
2.4.5 Machines à vecteurs de support
2.4.5.1 Principe d’induction
2.4.5.2 Choix de l’espace d’hypothèses
2.4.5.3 Passage par un espace de redescription
2.4.5.4 Astuce des fonctions noyaux
2.4.5.5 Notion de marge souple
2.4.5.6 Les bornes sur l’erreur de généralisation
2.4.5.7 Avantages et désavantages des SVM
2.5 Importance de la notion de marge de confiance
2.5.1 AdaBoost et marge d’hypothèse
2.5.2 Marge d’hypothèse à partir d’un ensemble de prototypes
2.5.3 Marge géométrique et marge d’hypothèse
2.6 Estimation de l’erreur de généralisation
2.6.1 Validation croisée en k parties
2.6.2 Leave-one-out
2.6.3 Bootstrap
2.7 Conclusion
3 Optimisation avec Méta-heuristiques
3.1 Recherche avec tabous
3.1.1 Synopsis de la méthode
3.1.1.1 Représentation d’une solution
3.1.1.2 Mouvements et voisinage
3.1.1.3 Mémoire à court terme
3.1.1.4 Aspiration
3.1.2 Intensification et Diversification
3.2 Algorithmes évolutionnaires
3.2.1 Synopsis des méthodes évolutionnaires
3.2.2 La population
3.2.3 Représentation d’une solution
3.2.4 Opérateurs de base
3.2.4.1 Opérateurs de sélection
3.2.4.2 Opérateurs de croisement
3.2.4.3 Opérateur de mutation
3.2.5 Elitisme
3.2.6 Optimisation multi-objectif
3.3 Autres familles de méta-heuristiques
3.3.1 Recuit simulé
3.3.2 Colonies de fourmis
3.3.3 Méthodes hybrides et autres méta-heuristiques
3.4 Conclusion
4 Entraînement d’ensembles de SVM pour la validation croisée
4.1 Entraînement d’un SVM
4.1.1 Recherche de l’hyperplan optimal
4.1.1.1 Cas des données linéairement séparables
4.1.1.2 Cas des données non-linéairement séparables
4.1.2 Solution optimale
4.1.3 Méthodes d’entraînement
4.1.4 Optimisation Séquentielle par modification Minimale (SMO)
4.1.4.1 Utilisation d’un cache
4.1.4.2 Technique de Shrinking
4.1.5 Adaptabilité des SVM à un problème donné
4.1.5.1 Les fonctions noyaux
4.1.5.2 Cas de duplication d’exemples
4.1.5.3 Cas des bases non equilibrées
4.1.5.4 Estimation de la probabilité
4.2 Entraînement d’ensembles de SVM pour la validation croisée
4.2.1 Approches existantes
4.2.1.1 Techniques d’alpha seeding
4.2.1.2 Utilisation d’un critère d’arrêt prématuré
4.2.2 Notre approche
4.2.2.1 Nouvelle technique d’alpha seeding
4.2.2.2 Nouveau critère d’arrêt prématuré
4.2.3 Cas de l’estimation rapide de l’erreur de leave-one-out
4.2.3.1 Spécificités
4.2.3.2 Résultats expérimentaux
4.2.4 Cas de l’estimation rapide de l’erreur de la k validation croisée
4.2.4.1 Spécificités
4.2.4.2 Résultats expérimentaux
4.2.5 Cas de l’estimation rapide de l’erreur de bootstap
4.2.5.1 Spécificités
4.2.5.2 Résultats expérimentaux
4.2.6 Conclusion et discussion
5 Conclusion
