Soutenance mémoire
Classification interactive
Les approches de classification centrées sur l’utilisateur (« user-centered ») visent à produire des résultats individuels plus adaptés aux préférences de chaque utilisateur que les approches entièrement automatiques (e.g. Amershi (2011); Amershi et al. (2015); Fails and Olsen Jr (2003); Lintott et al. (2008); Porter et al. (2013); Ware et al. (2001)). L’utilisateur devient le coach qui annote, en positif ou en négatif, un nombre limité d’exemples pour expliquer ses préférences. À partir de ces quelques exemples, un algorithme d’apprentissage tente de capturer ces préférences pour apprendre un premier modèle prédictif qui lui fournit des prédictions personnalisées. En fonction de sa satisfaction, l’utilisateur peut soit arrêter l’apprentissage si son concept cible a bien été appris ou continuer à entraîner le modèle en fournissant plus de précisions sur son concept cible. Pour affiner les prédictions, l’utilisateur peut corriger les mauvaises prédictions ou éventuellement ajouter de nouveaux exemples si son concept cible est difficile à apprendre (i.e. bouclage de pertinence (Salton and Buckley, 1997; Stumpf et al., 2007)). En fonction des actions de l’utilisateur, le modèle se met automatiquement à jour et tente de proposer des prédictions de plus en plus fines au fil du temps .
Formellement, supposons qu’un utilisateur ait pour objectif de classer un ensemble X de n exemples non-étiquetés X = {x1, x2, . . . , xn} où chaque exemple xi est défini dans un espace de m attributs numériques. Supposons qu’au début de l’interaction t0, un utilisateur crée un label désiré et l’explique en annotant un petit ensemble Tt0 = {(xi , yi)| i = 1..n0} de n0 exemples où yi est le label associé à l’exemple xi : yi = 1 (resp. 0) si l’exemple xi est annoté positivement (resp. négativement). À partir de Tt0 , un algorithme d’apprentissage apprend un modèle prédictif ht0 . Si les prédictions fournies par le modèle ne correspondent pas bien aux préférences de l’utilisateur, il peut alors améliorer sa performance prédictive en corrigeant les mauvaises prédictions de ht0 ou en ajoutant de nouveaux exemples à Tt0 . Le processus d’apprentissage peut être répété plusieurs fois jusqu’à ce que l’utilisateur soit satisfait des prédictions de son classifieur.
L’importance croissante donnée actuellement aux contenus personnalisés a conduit au développement de plusieurs systèmes de classification interactive pour diverses applications que nous présentons brièvement dans ce chapitre : classification d’images (Fogarty et al., 2008), sélection de fichiers (Ritter and Basu, 2009), classification de gestes (Fiebrink et al., 2009), classification de documents (Drucker et al., 2011), reconnaissance d’écriture manuscrite (Shilman et al., 2006), tri d’alarmes (Amershi et al., 2011) et création de groupes d’utilisateurs dans les réseaux sociaux (Amershi et al., 2012).
Exemples de systèmes de classification interactifs
cueTip (Shilman et al., 2006) est un classifieur qui permet de corriger les erreurs d’un modèle de reconnaissance d’écriture manuscrite . Le système interprète d’abord ce que l’utilisateur écrit sur une interface visuelle puis affiche la prédiction fournie par un algorithme de reconnaissance d’écriture. L’utilisateur peut ensuite corriger ce résultat si nécessaire en utilisant des gestes simples et intuitifs sur l’écran. Ces gestes sont codés par les développeurs du système. Par exemple, pour effacer une lettre, il faut la raturer et pour remplacer une lettre incorrecte, il faut réécrire au dessus. Les corrections fournies par l’utilisateur sont traduites en contraintes sur les données et transmises au modèle de reconnaissance d’écriture pour un nouvel apprentissage plus fin.
Wekinator (Fiebrink et al., 2009) est un classifieur de gestes qui permet, aux musiciens, compositeurs et nouveaux producteurs de sons, d’associer des sons à des gestes en temps réel. Le classifieur de gestes obtenu peut être utilisé par exemple pour animer des spectacles musicaux. Pour entraîner le classifieur, un utilisateur illustre chaque geste cible (i.e. classe) avec un exemple ainsi que le son qu’il doit déclencher. À partir des exemples illustrés par l’utilisateur, un algorithme d’apprentissage sélectionné de la libraire Weka (Witten and Frank, 2005) apprend un modèle prédictif qui reconnait automatiquement ses gestes et joue leurs sons associés. Pour renforcer si nécessaire le modèle appris, l’utilisateur peut fournir des exemples supplémentaires ou en modifier les précédents.
iCluster (Drucker et al., 2011) est un classifieur de documents qui permet de détecter les documents préférés d’un utilisateur . Avant la phase d’apprentissage, l’utilisateur crée ses labels cibles. Pour expliquer chaque label, l’utilisateur sélectionne quelques exemples représentatifs (i.e. positifs). Les exemples des autres labels sont considérés comme ses exemples négatifs. En se basant seulement sur quelques exemples fournis par l’utilisateur, une régression logistique apprend un modèle prédictif qui fournit, pour chaque nouveau document, ses probabilités d’appartenance aux différents labels. Un algorithme d’apprentissage de métrique est aussi utilisé pour prédire les 20 documents les plus proches de chaque label cible. De manière interactive, l’utilisateur inspecte les prédictions des modèles et ajoute au fur et à mesure de nouveaux exemples pour affiner les prédictions.
Smart selection (Ritter and Basu, 2009) est un classifieur de fichiers proche du gestionnaire de fichiers de WindowsTM. Il permet d’assister un utilisateur dans des tâches de sélection de fichiers complexes . Par exemple, un utilisateur souhaite sélectionner tous les fichiers dont le nom contient le mot « MARKF » ou « JOEP » mais pas le mot « TMP » pour les classer dans un dossier à part. Pour une tâche de sélection, l’utilisateur sélectionne uniquement quelques fichiers désirés. Les fichiers non-sélectionnés sont considérés comme exemples négatifs. À partir de quelques exemples de fichiers sélectionnés, un modèle prédictif est appris pour généraliser automatiquement la sélection aux autres fichiers. Ce modèle est construit à l’aide d’un boosting d’arbres de décision de taille 2. Pour fournir plus de précision, l’utilisateur peut continuer à fournir de nouveaux exemples et contre exemples en sélectionnant ou en désélectionnant des fichiers jusqu’à ce que tous les fichiers désirés soient sélectionnés.
ReGroup (Amershi et al., 2012) est un classifieur de profils qui permet de reconnaitre des profils désirés dans les réseaux sociaux . Pour expliquer son profil cible, l’utilisateur effectue d’abord une recherche par mots clés et sélectionne quelques profils à partir de la liste fournie par le moteur de recherche du réseau (i.e. exemples positifs). Les personnes n’ayant pas été sélectionnées sont considérées comme indésirables (i.e. exemples négatifs). En se basant sur cette première liste, un modèle prédictif est appris pour fournir de nouveaux profils susceptibles d’intéresser l’utilisateur. Ce modèle est appris par un classifieur bayésien naïf. Pour fournir davantage de précisions sur le profil cible, l’utilisateur trie les profils proposés à chaque itération par le modèle et ainsi de suite jusqu’à obtenir une liste satisfaisante.
cueT (Amershi et al., 2011) est un classifieur d’alarmes qui permet d’assister les opérateurs dans le tri alarmes . Un opérateur définit d’abord un ensemble de labels cibles (e.g. alarme inconnue, alarme majeure, alarme normale, etc) et annote ensuite manuellement quelques alarmes en fonction de leur gravité. Un algorithme de k plus proches voisins (kppv) se base sur ces exemples d’alarmes et prédit les labels des nouvelles alarmes. Cet algorithme est combiné avec une métrique apprise à partir des actions des opérateurs. Si la distance estimée entre une nouvelle alarme et les exemples de l’ensemble d’apprentissage est inférieure à un seuil, cueT recommande à l’utilisateur de créer un nouveau label pour cette alarme inconnue.
Pour expliquer davantage quelques alarmes et améliorer les prédictions du modèle, l’opérateur peut étiqueter manuellement de nouveaux exemples ou corriger les mauvaises prédictions.
cueFlick (Fogarty et al., 2008) est un classifieur d’images qui permet de reconnaitre automatiquement un concept visuel désiré par l’utilisateur . Pour expliquer son concept cible (e.g. photos avec des couleurs psychédéliques lumineuses), l’utilisateur interroge d’abord le catalogue d’images avec des mots clés et sélectionne quelques exemples avec et sans les caractéristiques visuelles désirées à partir des résultats retournés. Un algorithme d’apprentissage de k plus proches voisins combiné avec une métrique reclasse ensuite les images. Cette métrique est apprise en fonction des interactions de l’utilisateur avec les prédictions du modèle. L’utilisateur peut sélectionner (i.e. exemple positif) ou déselectionner (i.e. exemple négatif) manuellement d’autres images pour aider son modèle dans l’apprentissage d’un concept complexe.
Discussion
Les retours expérimentaux décrits dans les articles présentant ces systèmes de classification interactifs semblent prometteurs. Cependant, les évaluations menées sont fondées sur des protocoles encore très limités. Dans la plupart des travaux, elles sont basées sur des avis d’un échantillon très restreint d’utilisateurs (12 individus en moyenne (Amershi et al., 2012; Fogarty et al., 2008; Ritter and Basu, 2009; Shilman et al., 2006)) pour une tâche de classification spécifique. Certains auteurs (e.g. Amershi et al. (2011); Fogarty et al. (2008)) ajoutent quelques mesures quantitatives (e.g. précision, durée de l’expérimentation, vitesse d’apprentissage). Mais, leurs comparaisons avec d’autres algorithmes sont très restreintes et les jeux de test se réduisent souvent à un seul. Et à notre connaissance, il n’existe pas encore de protocole d’évaluation standardisé qui permettrait de comparer, dans un cadre partagé, les performances des différents classifieurs utilisés dans ces systèmes. De façon générale, l’évaluation d’un système pour une tâche complexe dans un environnement qui évolue reste une question délicate discutée dans la communauté Interface Homme Machine (IHM) (e.g. Cockton (2007); Greenberg and Buxton (2008); Zhai (2003)). Dans cette thèse nous n’abordons qu’un aspect restreint – mais importantde la problématique; celui de la validation des performances d’apprentissage des algorithmes dans un contexte interactif très simplifié qui omet les composantes IHM.
Dans ce contexte, nous pouvons noter que la plupart des systèmes de classification interactive récents se limitent à une classification mono-label où un seul label peut être affecté à la fois à un exemple ; ce qui est peu expressif d’autant plus que les données sont très souvent de nature multi-label. Par exemple, pour le système cueFlik une image peut contenir plusieurs concepts visuels, pour le système iCluster un document peut évoquer plusieurs sujets et un utilisateur considéré dans le système Regroup peut faire partie de plusieurs groupes sociaux. L’étiquetage multi-label est donc nécessaire pour permettre aux utilisateurs d’exprimer davantage leurs préférences sur les données.
|
Table des matières
1 Introduction
1 Personnalisation et classification interactive multi-label
2 Contenu du manuscrit
2 Classification interactive
1 Introduction
2 Exemples de systèmes de classification interactifs
3 Discussion
3 Apprentissage multi-label
1 Introduction
2 Définition du problème d’apprentissage multi-label
3 Approches d’apprentissage multi-label
3.1 Approches d’apprentissage par transformation
3.2 Approches d’apprentissage par adaptation
3.3 Approches d’apprentissage ensemble
4 Évaluation multi-label
4.1 Critères d’évaluation de la classification
4.2 Critères d’évaluation du ranking
5 Données multi-label
5.1 Distribution des labels
6 Discussion
4 Apprentissage multi-label avec contraintes d’interactivité
1 Introduction
2 Classification multi-label
2.1 Études comparatives des classifieurs multi-label
3 Critères d’évaluation
3.1 Contrainte 1 : Apprendre à généraliser à partir de peu d’exemples
3.2 Contrainte 2 : Apprendre et prédire en temps limité
4 Cadre expérimental
4.1 Protocole expérimental
4.2 Paramètres des classifieurs et jeux de données
5 Résultats expérimentaux I : apprentissage à partir de peu d’exemples
5.1 Ranking Loss (RL)
5.2 Macro-averaged Ranking Loss (macro-RL)
5.3 Accuracy, F-mesure et BER
6 Résultats éxperimentaux II : Apprendre et prédire en temps limité
7 Discussion
5 Apprentissage multi-label à partir de données latentes
1 Introduction
2 État de l’art : réduction des dimensions
3 Factorisation de matrice rapide
4 Apprentissage multi-label à partir de données latentes
4.1 Phase 1 : Réduction des dimensions par factorisation matricielle
4.2 Phase 2 : Apprentissage et prédiction multi-label dans les espaces latents
5 Étude expérimentale
5.1 Implémentation
5.2 Données d’évaluation
5.3 Protocole expérimental
5.4 Critères d’évaluation
6 Résultats expérimentaux
6.1 Résultats expérimentaux I : Temps de la réduction des dimensions
6.2 Résultats expérimentaux II : Performance prédictive
6.3 Résultats expérimentaux III : Vitesse d’apprentissage et de prédiction
7 Conclusion
6 Conclusion et perspectives
1 Résultats
2 Application : VIPE
2.1 Classification interactive multi-label de films
2.2 Classification interactive multi-label de tweets
3 Perspectives
4 Liste des travaux
7 Annexes
