Apprentissage actif en-ligne d’un classifieur é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 [Cornuéjols and Miclet, 2010]. Cela consiste à séparer les phases d’apprentissage et d’utilisation du système comme représenté sur la figure 1.10a. 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.

Apprentissage « permanent » (anytime learning)

   L’apprentissage permanent (anytime learning) est une forme d’apprentissage en-ligne avancé, où l’apprentissage est continu tout en restant interruptible à tout moment [Seidl et al., 2009]. Un algorithme d’apprentissage permanent tire ainsi profit du temps entre deux reconnaissances pour continuer à améliorer le modèle du classifieur. Plus le temps entre deux reconnaissances est long, plus le système peut s’améliorer et être performant lorsque la prochaine reconnaissance devra être faite. L’apprentissage permanent est également appelé apprentissage interruptible, car le processus d’apprentissage peut être interrompu à tout moment, lorsqu’une reconnaissance doit être effectuée. L’apprentissage est alors stoppé, pendant l’utilisation du système, et reprend ensuite. Lorsque l’apprentissage du système est potentiellement trop long, ou l’utilisation du système est potentiellement trop fréquente, le processus d’apprentissage et celui de reconnaissance peuvent être décorrélés pour avoir le temps d’apprendre le système entre deux reconnaissances. Ce mode de fonctionnement n’est cependant pas de l’apprentissage permanent, mais juste une désynchronisation des processus. L’apprentissage est alors réalisé en tâche de fond, en parallèle des reconnaissances. L’apprentissage permanent consiste à tirer profit du temps entre deux reconnaissances pour améliorer le système au maximum. La synthèse de données artificielles [Mouchère et al., 2007a] [Almaksour et al., 2011] à partir des derniers tracés de l’utilisateur permet par exemple de créer davantage de données d’apprentissage. L’utilisation de ces données artificielles permet de continuer à entraîner le système, en attendant la prochaine donnée réelle produite par l’utilisateur.

Scénario d’échantillonnage de bases de données

   Les scénarios d’échantillonnage de bases de données sont ceux où le système doit choisir les données à étiqueter parmi une base de données existante. Le système peut alors parcourir et étudier toute la base de données pour effectuer son échantillonnage. Lorsque l’apprentissage actif est combiné à l’apprentissage semi-supervisé, les données non choisies, et qui ne seront donc pas étiquetées, sont également utilisées conjointement à celles qui ont été étiquetées. Ce type de problème, d’échantillonnage de base de données, correspond aux tâches d’apprentissage hors-ligne, mais ne s’applique pas aux tâches d’apprentissage en-ligne.

Méthode de minimisation de l’erreur (expected error reduction)

   Cette approche consiste à évaluer non pas combien le modèle va changer, mais combien son erreur de généralisation est susceptible de diminuer. Pour cela, l’erreur future est estimée sur le reste des données parmi lesquelles l’échantillonnage est à réaliser. Les données qui sont étiquetées sont alors celles qui permettent d’obtenir l’estimation de l’erreur future la plus basse. Cette méthode a été utilisée avec succès pour de nombreux systèmes comme les systèmes Bayésiens naïfs [Roy and McCallum, 2001], des champs aléatoires gaussiens [Zhu et al., 2003], des régressions logistiques [Guo and Greiner, 2007], des machines à vecteurs supports [Moskovitch et al., 2007] [Nissim et al., 2012] [Nissim et al., 2014]. Le principal inconvénient de cette approche est son importante complexité, car non seulement l’erreur doit être ré-estimée pour chaque exemple d’apprentissage potentiel, mais pour cela le modèle doit être mis à jour à chaque fois. Enfin, cette méthode ne s’applique qu’aux problèmes d’échantillonnage de bases de données, alors que notre contexte applicatif implique une méthode d’échantillonnage de flux de données.

Classifieurs bayésiens naïfs

   Le classifieur bayésien naïf [Langley et al., 1992] est un système de classification basé sur le théorème de Bayes qui suppose une indépendance des variables explicatives, c’està-dire des caractéristiques des données. C’est un système génératif qui modélise les probabilités des différentes classes ainsi que les probabilités conditionnelles des caractéristiques en fonction des différentes classes. C’est un classifieur simple, mais qui donne de bonnes performances [Hand and Yu, 2001]. L’apprentissage d’un classifieur bayésien naïf consiste à estimer les probabilités conditionnelles des caractéristiques en fonction des différentes classes. Ces probabilités condition- nelles sont faciles à estimer lorsque les caractéristiques des données sont discrètes, mais plus complexes pour des caractéristiques numériques continues. Une première méthode pour les caractéristiques continues consiste à les discrétiser afin de pouvoir facilement estimer les probabilités conditionnelles [Yang and Webb, 2002]. Une autre méthode est de supposer que les caractéristiques numériques continues suivent une distribution gaussienne, ou parfois une distribution de Cauchy [Sebe et al., 2002]. Des méthodes plus complexes existent également, par exemple celle des noyaux multiples [John and Langley, 1995] qui estime ces distributions de manière non-paramétrique. L’apprentissage peut facilement être réalisé de manière incrémentale en mettant à jour les statistiques utilisées pour estimer les probabilités conditionnelles. Pour les caractéristiques discrètes, ou discrétisées, il suffit d’incrémenter les compteurs correspondants à l’arrivée de chaque nouvelle donnée d’apprentissage. Le principal avantage du classifieur bayésien naïf est sa capacité de généralisation et ses bonnes performances prédictives. Un autre avantage, très intéressant dans notre contexte, est sa capacité d’apprentissage à partir de très peu de données. Le classifieur bayésien naïf donne de meilleures performances que de nombreuses méthodes plus complexes quand très peu de données d’apprentissage sont disponibles [Domingos and Pazzani, 1997]. Une version incrémentale sur flux de données, qui utilise des résumés des quantiles pour suivre les évolutions de la distribution statistique des données [Salperwyck et al., 2015], a été conçue pour travailler sur des flux de grandes tailles. Cette méthode utilise également une pondération des caractéristiques, qui est calculée de manière stochastique. Dans le cas de caractéristiques discrétisées, la principale difficulté pour le rendre enligne, c’est-à-dire incrémental sur flux de données, est de rendre le processus de discrétisation en-ligne. IFFD (Incremental Flexible Frequency Discretization) [Lu et al., 2006] est une méthode de discrétisation incrémentale permettant de ne pas recalculer toutes les probabilités conditionnelles à l’arrivée de chaque donnée. Le nombre et la taille des intervalles sont flexibles et adaptés incrémentalement. De nouveaux intervalles peuvent également être insérés, et ceux existants peuvent être éclatés au besoin.

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
Publications de l’auteur
Références de l’état de l’art
Table des matières
Liste des figures
Liste des tableaux

Télécharger le rapport complet