Apprentissage actif en-ligne d’un classifieur évolutif

Reconnaissance de commandes gestuelles

Avec la démocratisation des écrans tactiles, les interactions Homme-Machine évoluent. De nouvelles méthodes d’interaction ont été inventées pour tirer parti du nouveau potentiel d’interaction offert par ces nouvelles interfaces. Parmi elles, un nouveau concept est apparu récemment : associer des commandes à des gestes/symboles. Ces commandes gestuelles  permettent à l’utilisateur d’exécute de nombreuses actions simplement en traçant les symboles associés. Pour mémoriser facilement une douzaine de commandes, il est essentiel de laisser l’utilisateur choisir lui-même ses propres gestes. L’utilisation de commandes gestuelles requiert un système de reconnaissance de symboles manuscrits. De plus, pour que les commandes gestuelles soient personnalisables, ce classifieur doit être capable d’apprendre à partir de peu de données et d’évoluer pendant son utilisation.
L’utilisation de commandes gestuelles est un problème de classification, où il faut reconnaître des symboles inconnus. Si la reconnaissance de symboles manuscrits est un domaine largement étudié, le contexte des commandes gestuelles implique certaines contraintes particulières, que nous allons détailler.

Apprentissage pendant l’utilisation du système

Puisque le système ne dispose que de quelques exemples pour inférer son modèle initialement, celui-ci est forcément limité. Il est donc nécessaire que le système continue d’apprendre pendant son utilisation pour améliorer ses performances.
Qui plus est, il est également souhaitable que le système s’adapte de manière fine à l’utilisateur. En effet, l’utilisateur novice va sans doute tracer ses symboles avec lenteuret précision, mais va progressivement accélérer. Au bout d’un certain temps, l’utilisateur confirmé va ainsi tracer ses symboles de plus en plus rapidement et, à la manière d’une signature, les tracés seront de plus en plus déformés. Il faut alors que le système soit capable de s’adapter, de suivre l’évolution de l’utilisateur, et non pas que l’utilisateur se restreigne pour s’adapter à un système statique.
Il faut donc un système dynamique avec un algorithme d’apprentissage incrémental, pour pouvoir mettre à jour le modèle de connaissance du classifieur. De plus, cette mise à jour doit être faite entre deux utilisations du système. L’algorithme d’apprentissage doit donc être incrémental en temps réel, c’est-à-dire être « en-ligne ».

Typologie des problèmes d’apprentissage

Cette section présente les principaux types de problèmes d’apprentissage automatique  aussi appelé apprentissage artificiel qui existent : les problèmes de classification ; les problèmes de régression ;  les problèmes de regroupement (clustering) ; les problèmes de détection d’erreurs (outliers) ; les problèmes d’inférence de règles.
La reconnaissance de commandes gestuelles est un problème de classification, de catégorisation de données inconnues. Cependant, nous verrons que certaines approches et techniques utilisées pour d’autres types de problèmes peuvent être intéressantes et utiles dans notre cas.

Taxonomie de modèles de connaissance des classifieurs

Cette section définie une taxonomie des modèles de connaissance des systèmes de classification, suivant le caractère dynamique de leur modèle de connaissance.
Nous distinguons ainsi : les systèmes avec modèle statique ; les systèmes avec modèle adaptatif ; les systèmes avec modèle évolutif.
Classifieur à modèle statique : Un classifieur est un système permettant de reconnaître des données inconnues, à partir d’un modèle de connaissances. Ce modèle est créé par un algorithme d’apprentissage à partir des données d’entrainement. Le classifieur utilise ensuite ce modèle pour reconnaître les données inconnues pendant l’utilisation du système.
Le plus souvent, le modèle du classifieur est statique, c’est-à-dire que ce modèle n’est pas modifiable pendant l’utilisation du système. Si de nouvelles données deviennent disponibles, il est nécessaire de ré-apprendre un nouveau modèle depuis zéro pour pouvoir en tirer profit. De même, si certaines données utilisées lors de l’apprentissage du modèle deviennent obsolètes, il n’est pas possible de les oublier, il est nécessaire de ré-apprendre un nouveau modèle. Plus de flexibilité requiert un classifieur avec un modèle dynamique, c’est-à-dire un classifieur adaptatif ou évolutif. Classifieur à modèle adaptatif : Un classifieur adaptatif est un système dont le modèle peut être modifié a posteriori, après son apprentissage. Le modèle doit quand même être créé initialement par un algorithme d’apprentissage sur une base de données d’entrainement, mais ses paramètres peuvent ensuite être adaptés .
Les différents paramètres du modèle peuvent être modifiés pour prendre en compte de nouvelles données. Un classifieur adaptatif peut notamment être appris incrémentalement, en construisant son modèle au fur et à mesure du traitement des exemples d’apprentissage. Si les paramètres du modèle peuvent évoluer, sa structure reste fixe, et en particulier le nombre de classes ne peut pas changer. Un système dont les paramètres et la structure peuvent évoluer est appelé un système évolutif.

Apprentissage hors-ligne

L’apprentissage hors-ligne d’un système d’apprentissage automatique est la manière la plus courante de procéder . Cela consiste à séparer les phases d’apprentissage et d’utilisation du système .
Dans un premier temps, le système est entrainé sur une base d’apprentissage. L’apprentissage se poursuit aussi longtemps que nécessaire pour optimiser le modèle du classifieur à partir de cette base d’apprentissage.
Dans un second temps, une fois l’apprentissage du modèle terminé, celui-ci peut être utilisé par l’algorithme de reconnaissance. Le modèle obtenu à l’issu de la phase d’apprentissage est un modèle statique, qui ne changera pas pendant la phase d’utilisation.
Cette manière de procéder comporte plusieurs inconvénients. Tout d’abord, il faut que la base d’apprentissage soit la plus grande possible, pour garantir de bonnes performances. Ensuite, il faut que les données d’apprentissage soient représentatives des données d’utilisation, car le modèle étant statique, il ne s’adapte pas en cas de changement dans la distribution des données. Enfin, les classes sont prédéfinies lors de l’apprentissage et il n’est pas possible d’en ajouter lors de l’utilisation.
L’apprentissage hors-ligne s’oppose à l’apprentissage en-ligne, où cette fois le système apprend pendant son utilisation. L’apprentissage hors-ligne d’un système est le plus souvent réalisé de manière « batch », mais il peut également être réalisé de manière incrémentale.

Table des matières

Introduction
I État de l’art 
1 Contexte et définitions 
1.1 Introduction
1.2 Contexte et problématique
1.2.1 Reconnaissance de commandes gestuelles
1.2.2 Apprentissage à partir de peu de données
1.2.3 Apprentissage pendant l’utilisation du système
1.2.4 Interactions avec l’utilisateur
1.2.5 Nécessité d’oublier
1.3 Typologie de tracés manuscrits
1.3.1 Tracés hors-lignes
1.3.2 Tracés en-lignes
1.3.3 Tracés mono-strokes
1.3.4 Tracés multi-strokes
1.3.5 Tracés multi-points
1.4 Typologie des problèmes d’apprentissage
1.4.1 Problème de classification
1.4.2 Problème de régression
1.4.3 Problème de regroupement (clustering)
1.4.4 Problème de détection d’erreurs/de nouveautés
1.4.5 Problème d’inférence de règles
1.5 Taxonomie de modèles de connaissance des classifieurs
1.5.1 Classifieur à modèle statique
1.5.2 Classifieur à modèle adaptatif
1.5.3 Classifieur à modèle évolutif
1.5.3.1 Compromis plasticité/stabilité
1.6 Taxonomie des méthodes d’apprentissage
1.6.1 Apprentissage hors-ligne
1.6.1.1 Apprentissage « batch »
1.6.1.2 Apprentissage incrémental
1.6.2 Apprentissage en-ligne
1.6.2.1 Apprentissage incrémental sur flux
1.6.2.2 Notion d’oubli
1.6.2.3 Notion de changement de concepts
1.6.3 Apprentissage « permanent »
1.7 Taxonomie de supervision de l’apprentissage
1.7.1 Apprentissage non-supervisé
1.7.2 Apprentissage supervisé
1.7.3 Apprentissage semi-supervisé
1.7.4 Apprentissage actif
1.8 Conclusion
2 Supervision active en-ligne 
2.1 Introduction
2.2 Scénarios d’apprentissage actif
2.2.1 Scénario de génération d’échantillons
2.2.2 Scénario d’échantillonnage de bases de données
2.2.3 Scénario d’échantillonnage de flux de données
2.3 Méthodes d’échantillonnage
2.3.1 Méthode de l’incertitude maximale
2.3.2 Méthode du comité de sélection (query by committee)
2.3.3 Méthode de l’impact maximal (expected model change)
2.3.4 Méthode de minimisation de l’erreur (expected error reduction)
2.3.5 Méthode de réduction de la variance
2.3.6 Méthode utilisant la densité
2.4 Échantillonnage par une option de rejet des données
2.4.1 Rejet de distance
2.4.2 Rejet de confusion
2.4.3 Compromis erreur/rejet
2.4.4 Fonction de confiance
2.4.5 Architectures des options de rejet
2.4.5.1 Seuil de rejet sur un score de confiance
2.4.5.2 Classe de rejet intégrée à l’apprentissage
2.4.5.3 Classifieur de rejet séparé
2.5 Conclusion
3 Panorama des classifieurs évolutifs en-ligne 
3.1 Introduction
3.2 Systèmes linéaires
3.2.1 Classifieurs bayésiens naïfs
3.2.2 Régression binomiale
3.3 Systèmes d’appariement de modèles
3.3.1 Méthode des k-plus-proches-voisins
3.3.2 Alignement de séquences
3.4 Réseaux de neurones
3.4.1 Perceptrons
3.4.2 Réseaux à fonction de base radiale
3.4.3 Réseaux auto-organisés
3.5 Séparateurs à Vaste Marge (SVM)
3.5.1 Méthodes incrémentales paquet par paquet
3.5.2 Méthodes incrémentales donnée par donnée
3.6 Arbres de décision
3.6.1 Arbres de décision incrémentaux
3.6.2 Arbres de décision évolutifs
3.7 Ensemble de classifieurs faibles
3.7.1 Bagging et Boosting en-ligne
3.7.2 Ensemble évolutifs
3.8 Systèmes à base de règles
3.8.1 Systèmes experts évolutifs
3.8.2 Systèmes flous évolutifs
3.9 Conclusion
4 Le classifieur « Evolve » 
4.1 Introduction
4.2 Architecture des systèmes d’inférence floue
4.2.1 Structure des prémisses
4.2.2 Structure des conclusions
4.2.3 Processus d’inférence
4.3 Création de nouvelles règles
4.3.1 Regroupement basé sur la densité
4.3.2 Regroupement basé sur la distance
4.3.3 Réseaux auto-organisés
4.3.4 Algorithmes basés sur des graphes
4.3.5 Discussion
4.4 Apprentissage des prémisses
4.4.1 Adaptation statistique des prototypes
4.4.2 Autres algorithmes d’adaptation
4.5 Apprentissage des conclusions
4.5.1 Optimisation par l’algorithme des moindres carrés récursifs
4.5.2 Intégration d’oubli dans les moindres carrés récursifs
4.5.3 Autres algorithmes d’optimisation
4.6 Conclusion
II Contributions 
5 Evolve ∞ : un classifieur évolutif en-ligne 
5.1 Introduction
5.2 Architecture d’Evolve ∞
5.2.1 Structure des prémisses
5.2.2 Structure des conclusions
5.2.3 Processus d’inférence
5.3 Algorithme d’apprentissage des prémisses
5.3.1 Adaptation statistique avec oubli
5.4 Algorithme d’apprentissage des conclusions
5.4.1 Mise à jour incrémentale
5.4.2 Mise à jour décrémentale
5.4.2.1 Techniques existantes
5.4.2.2 La nouvelle technique d’oubli directionnel différé DDF
5.5 Capacité d’auto-évaluation et de rejet des données
5.5.1 Option de rejet de distance
5.5.2 Option de rejet de confusion évolutive
5.5.3 Mesure de confiance interne
5.6 Algorithme de création de règles
5.6.1 Regroupement incrémental naïf
5.6.2 Utilisation du rejet de distance
5.7 Conclusion
6 IntuiSup : un superviseur actif en-ligne 
6.1 Introduction
6.2 Stratégie de supervision active en-ligne
6.2.1 Supervision implicite : sans interaction avec l’utilisateur
6.2.2 Supervision explicite : étiquetage par l’utilisateur
6.3 Méthode d’échantillonnage évolutive ESU
6.3.1 L’algorithme AMTL (Automatic Multiple Thresholds Learning)
6.3.2 Algorithme basé sur le filtrage de Kalman
6.3.3 Algorithme d’échantillonnage évolutif ESU
6.4 Méthode de « dopage » de l’apprentissage B-ESU
6.4.1 Principe du « dopage »
6.4.2 Dopage de l’échantillonnage
6.5 Conclusion
III Validation expérimentale 
7 Évaluation du classifieur évolutif en-ligne Evolve ∞ 
7.1 Introduction
7.2 Méthodologie
7.2.1 Protocole d’évaluation
7.2.2 Bases de données
7.2.2.1 ILGDB : Intuidoc Loustic Gesture Data Base
7.2.2.2 Basse de données Ironoff
7.2.2.3 Basse de données LaViola
7.2.2.4 Basse de données NicIcon
7.2.2.5 Bases de données de référence de l’UCI
7.2.3 Jeu de caractéristiques HBF49
7.3 Performances générales
7.3.1 Vitesse d’apprentissage en-ligne
7.4 Inertie du système
7.4.1 Mise en évidence du problème
7.4.2 Insuffisance des techniques existantes
7.4.3 Validation d’Evolve ∞
7.5 Adaptation aux changements de concepts
7.5.1 Changements de concepts progressifs
7.5.2 Impact de la longueur de la fenêtre
7.5.3 Changements de concepts brusques
7.6 Option de rejet
7.6.1 Mesure de confiance interne
7.6.1.1 Protocole expérimental
7.6.1.2 Amélioration de l’apprentissage croisé
7.6.2 Option de rejet multi-seuils
7.7 Conclusion
8 Évaluation du superviseur actif en-ligne IntuiSup 
8.1 Introduction
8.2 Méthodologie
8.2.1 Protocole de test
8.2.2 Méthode d’évaluation
8.3 Stratégie de supervision active en-ligne
8.3.1 Combinaison des méthodes d’étiquetage
8.3.2 Utilisation des erreurs de mémorisation et de reconnaissance
8.4 Méthode d’échantillonnage ESU pour l’étiquetage explicite
8.4.1 Comparaison des méthodes d’évolution du seuil d’échantillonnage
8.4.2 Suivi de différents compromis erreur/sollicitation
8.5 Méthode d’échantillonnage avec dopage B-ESU
8.5.1 Amélioration du point de fonctionnement final
8.5.2 Amélioration du comportement lors des changements de concepts
8.6 Conclusion
Conclusion 
Bibliographie

Télécharger le rapport complet