Méthode de résolution au méta-niveau et Hyperparamètres

Télécharger le fichier pdf d’un mémoire de fin d’études

Proposition d’un critère de performance

Afin de pouvoir proposer et illustrer un critère de performance de méta-analyse sur un exemple, on introduit un cas d’étude de méta-apprentissage : la sélection d’algorithmes de classification. La classification étant l’un des champs les plus actifs de l’apprentissage, il est en effet notablement plus facile d’en collecter des expériences documentées. On disposera donc d’un ensemble d’algorithmes de classification, ou classifieurs, parmi lesquels choisir, et d’un ensemble de jeux de données sur lesquels réaliser les expériences de classification.
Pour un jeu de données particulier, l’objectif d’une expérience de sélection d’algorithmes est de choisir un classifieur maximisant un critère donné. Dans cet exemple, nous utiliserons le critère traditionnel de précision (proportion d’instances bien classées), qui, bien que simpliste (Provost et al. 1998), reste très intuitif.
Pour réaliser cette sélection, nous envisageons d’employer une technique de métaapprentissage, ce qui nécessite de collecter un ensemble de données décrivant les performances de nos algorithmes. Afin de construire ce jeu de données du méta-niveau, ou metadataset, il faut alors collecter deux éléments fondamentaux. La précision de nos algorithmes de classification doit tout d’abord être mesurée sur un ensemble de jeux de données (voir Table 3.1). Ces jeux de données doivent ensuite être caractérisés par un ensemble fixe de descripteurs qui seront les attributs du metadataset, donc méta-attributs (voir Table 3.2, et section 2.4 de l’état de l’art). Ces éléments sont ici extraits de la base d’OpenML (Vanschoren et al. 2013), dont la base d’expériences d’apprentissage répertorie les résultats d’exécutions de nombreux classifieurs sur des milliers de jeux de données de divers domaines.

Dimensions des expériences au méta-niveau

Nous recensons ici les différentes dimensions pouvant varier d’une expérience à une autre, dont celles considérées dans l’exemple (Figure 3.1) ainsi que d’autre dimensions envisageables. L’objectif de cette représentation est de pouvoir isoler l’impact de ces dimensions sur les performances.
Par exemple, si l’on restreint nos résultats à la dimension de la Méthode de résolution au méta-niveau (dans l’exemple précédent, il s’agit de l’algorithme de méta-apprentissage utilisé) en en faisant la moyenne selon toutes les autres dimensions, on obtient une estimation de la performance des diverses Méthodes de résolution au méta-niveau utilisées.
Ce procédé permet de mitiger l’impact des autres dimensions sur notre résultat. De plus, comme nous le verrons en section 3.5, ce format permet l’emploi de tests d’hypothèse statistique pour qualifier la significativité des résultats produits.

Caractérisation de jeux de données

Comme vu en section 2.4 de l’état de l’art, le problème de caractérisation de jeux de données a été adressé selon deux axes principaux :
• Le premier consiste en l’emploi de mesures statistiques et information-théorétiques pour décrire le jeu de données. Cette approche, notamment mise en avant par le projet STATLOG (Michie et al. 1994), et employée dans une majorité d’études postérieures (Kalousis et al. 2004 ; Leite et al. 2012 ; Leyva et al. 2015 ; Sun et Pfahringer 2013 ; Vilalta et Drissi 2002), présente nombre de mesures très expressives, mais sa performance repose intégralement sur l’adéquation entre le biais de l’apprentissage effectué au méta-niveau et l’ensemble de mesures choisies. On note parfois l’emploi de techniques de sélection d’attributs à ce méta-niveau (Kalousis et Hilario 2001b), mais les résultats expérimentaux ne permettent pas de conclure à la supériorité de quelconque mesure indépendamment du méta-apprentissage employé (Todorovski et al. 2000).
• Le second axe d’approche considère quant à lui non pas des propriétés intrinsèques du jeu de données étudié, mais plutôt la performance d’algorithmes d’apprentissage simples exécutés dessus. Introduit comme « landmarking » par (Pfahringer et al. 2000), cette approche emploie initialement le taux d’erreur d’un ensemble d’algorithmes basiques comme méta-données. Comme précédemment, les résultats suggèrent une forte dépendance de l’efficacité de cette approche avec le choix des algorithmes de base et du méta-niveau, ne révélant aucune combinaison uniformément supérieure. Des développements postérieurs ont introduit des mesures plus complexes, tel (Y. Peng et al. 2002) proposant comme méta-attributs des proprié- tés structurelles d’un arbre de décision construit sur la donnée. Les expériences conduites par (Fürnkranz et Petrak 2002) sur ces différentes approches tendent à conclure que toutes peuvent réaliser de bonnes performances dans diverses parties de l’ensemble des jeux de données, sans qu’aucune ne domine globalement.
La base d’OpenML fournit plus d’une centaine de tels descripteurs, couvrant les différentes approches au problème de caractérisation de jeux de données. Plusieurs expériences comparatives (Kalousis et Hilario 2001b ; Todorovski et al. 2000) ont cependant montré que l’efficacité d’une caractérisation particulière dépend principalement de son adéquation avec le méta-problème et la solution employée au méta-niveau. Prenant exemple sur le succès d’approches consistant à adapter cette caractérisation à des ensembles de problèmes plus restreints (Leyva et al. 2015), une expérience intéressante serait d’adapter directement notre caractérisation au metadataset employé. Dans l’exemple, ceci est réalisé par l’application de l’algorithme de sélection d’attributs ReliefF (Robnik-Šikonja et Kononenko 2003), qui sélectionne l’ensemble des méta-attributs à utiliser pour construire le modèle prédictif au méta-niveau. ReliefF utilise alors des critères qui lui sont propres (voir section 2.5 de l’état de l’art) pour juger quels méta-attributs sont les plus informatifs dans le metadataset utilisé. On a ainsi adapté la caractérisation à notre metadataset particulier.
Cette adaptation pourrait cependant être réalisée par d’autres méthodes. L’emploi d’un algorithme de sélection d’attributs différent aurait probablement choisi un autre ensemble de méta-attributs. De même, utiliser un autre ensemble initial de méta-attributs engendrerait une caractérisation différente.
Explorer cette dimension de la caractérisation des instances au méta-niveau (donc ici de jeux de données) implique donc de varier les ensembles de méta-attributs retenus, que ce soit par l’emploi d’ensembles initiaux différents ou par l’utilisation de diverses techniques de sélection d’attributs au méta-niveau.

Méthode de résolution au méta-niveau et Hyperparamètres

Dans l’exemple, afin de prédire quel classifieur associer à chaque jeu de données, on a utilisé le modèle construit par une implémentation particulière de l’algorithme C4.5. Utiliser un autre algorithme, voire une implémentation différente de C4.5, produit en général un modèle différent, et donc des prédictions et une performance au méta-niveau différentes.
De plus, les méthodes de résolution au méta-niveau présentent en général un ensemble d’hyperparamètres permettant d’en ajuster le fonctionnement. Dans l’exemple, ce sont les valeurs par défaut de ces paramètres qui ont été utilisées, mais pour de nombreuses méthodes, le juste réglage des hyperparamètres permet une amélioration significative des performances.
On peut ainsi considérer dans cette dimension l’ensemble des méthodes de résolution envisageables, chacune augmentée de toutes ses paramétrisations possibles. L’exploration en profondeur d’une dimension aussi vaste se révélant rapidement beaucoup trop coûteuse, des restrictions seront nécessaires. Une première possibilité serait de n’utiliser que les hyperparamètres par défaut, ce qui limite la dimension aux seules méthodes de résolution.
Il s’agit en revanche d’un biais potentiellement important, car les diverses méthodes n’ont pas la même sensibilité aux hyperparamètres : certaines auront toujours besoin d’un réglage pour se montrer compétitives, tandis que d’autres peuvent apparaitre très convenables avec leur paramétrisation par défaut et bénéficieront peu d’un réglage plus attentif.

Complexité et exécution des expériences au méta-niveau

On reprend ici le méta-problème de l’exemple (sélection de classifieur par classification au méta-niveau) pour illustrer l’application de l’analyse dimensionnelle proposée.
Comme stipulé précédemment, le jeu de données de méta-classification est construit en utilisant des données d’OpenML, qui répertorie nombre de jeux de données et algorithmes de classification. La construction du jeu de données de méta-classification requérant de nombreux algorithmes évalués sur un ensemble de jeux de données, nous avons employé une technique de recherche de bi-clique maximale (Uno et al. 2004) pour trouver les plus grands ensembles de jeux de données et de classifieurs tels que chaque élément des deux ensembles a été évalué en conjonction avec tous les éléments de l’autre ensemble. Ceci nous a permis de nous restreindre aux 93 algorithmes de classification et 434 jeux de données vu précédemment (listes en annexe, Tables A.1 et A.2). Nous avons ensuite extrait les valeurs d’évaluation de 11 critères de performance (voir Table 3.4) sur chacune des 40.000 exécutions que cela représente. Enfin nous avons extrait les valeurs des 105 métaattributs OpenML (Table A.3) pour chaque jeu de données, et construit le metadataset correspondant.

Fonction de dissimilarité

Propriétés désirables

Avant de proposer une fonction candidate, il convient d’étudier les propriétés qu’elle devrait présenter. Soit Ω l’ensemble des jeux de données, et x, x′ ∈ Ω des instances de jeu de données. Traditionnellement, les propriétés usuelles des distances ne sont pas jugées nécessaires (Wang et al. 2009), ne conservant que la positivité (d(x, x′) ≥ 0). Parmi l’ensemble des propriétés d’une distance traditionnelle, nous préférerions cependant conserver uniquement celles présentant une interprétation naturelle dans le contexte de la caractérisation de jeu de données.
√ Positivité (d(x, x′) ≥ 0) : une dissimilarité doit quantifier la différence absolue entre éléments, donc naturellement positive.
√ Indiscernabilité des identiques (x = x′ → d(x, x′) = 0) : des jeux de données rigoureusement identiques doivent être considérés aussi similaires que possible. × Identité des indiscernables (d(x, x′) = 0 → x = x′) : des jeux de données physiquement différents doivent pouvoir être considérés parfaitement similaires (considérer par exemple l’ordre de présentation des attributs).
√ Symétrie (d(x, x′) = d(x′, x)) : l’ordre de présentation des jeux de données est indifférent, il parait donc naturel de l’ignorer. × Inégalité triangulaire (d(x, x′′) ≤ d(x, x′) + d(x′, x′′)) : perd tout sens en l’absence d’identité des indiscernables. On peut avoir d(x, x′) = d(x′, x′′) = 0 et néanmoins x 6= x′′ et d(x, x′′) ≥ 0…

Méta-attributs des jeux de données

Soit un ensemble G de méta-attributs de jeux de données. Les valeurs g(ω) de l’un de ces méta-attributs g sur nos jeux de données constitueront le cas typique d’ensembles atomiques à partir desquels calculer la dissimilarité. On doit donc définir pour chaque méta-attribut g une dissimilarité bornée dg : g(ω)2 7→ ❘+ (par exemple la différence absolue), qui selon la définition 2.1 sera donc normalisée. Ceci permet d’introduire la dissimilarité normalisée par la borne supérieure (cf. Eq. 4.1) sur G(ω) selon {dg|g ∈ G} : ∀x, y ∈ ω, dubr G(ω)(x, y) = X g∈G dg(x, y) max (x′,y′)∈ω2 (dg(x′, y′)) (4.2)
En pratique, cela coïncidera généralement avec une distance de Manhattan normalisée.
Cela pose en revanche les fondations nécessaires au prochain type de mesures : les métaattributs caractérisant les attributs individuels des jeux de données.

Évaluation Théorique

Dans (Wang et al. 2009), Wang & al. proposent une définition intuitive de la qualité d’une fonction de dissimilarité dans le contexte de l’apprentissage. Selon leur définition, une fonction de dissimilarité est strongly (ǫ, γ)-good pour un problème donné de classification binaire, si une proportion au moins 1 − ǫ des exemples z = (x, y) satisfait : P(d(x, x′) < d(x, x′′) | y′ = y, y′′ = −y) ≥ 1 2 + γ 2.
En d’autres termes, plus la probabilité que la dissimilarité juge deux exemples aléatoires de même classe plus proches que deux exemples aléatoires de classes différentes est grande, mieux elle permettra de séparer les classes. Cette interprétation nous amène à définir un problème de classification binaire entrant dans les attributions de la dissimilarité proposée.
Considérons un ensemble X de jeux de données de classification, et un ensemble A de classifieurs. On exécute chaque classifieur de A sur chaque jeu de données de X et mesure un critère de performance c du modèle résultant. Ensuite, pour chaque jeu de données x ∈ X, on définit l’ensemble Ax des algorithmes appropriés sur ce jeu de données selon le critère de performance c, comme ceux étant à au plus un écart type en dessous du meilleur : Ax = {a ∈ A tels que | max a′∈A (c(a′, x)) − c(a, x)| ≤ σx}.
On peut donc considérer, pour tout algorithme a ∈ A, le problème de classification binaire où les instances sont les jeux de données x ∈ X, et dont la classe spécifie si a est approprié sur x. Ces problèmes caractérisent donc l’adéquation entre les différents classifieurs et jeux de données, ce qui est un objectif intuitif de la dissimilarité proposée.
Pour évaluer la dissimilarité, on peut alors calculer pour chaque classifieur a ∈ A et chaque jeu de données x ∈ X, la probabilité que la dissimilarité juge deux exemples aléatoiresde même classe plus proches que deux exemples aléatoires de classes différentes, ce qui nous donnera la (ǫ, γ)-goodness de dubr ω : P(dubr ω (x, x′) < dubr ω (x, x′′) | a ∈ Ax, a ∈ Ax′ , a /∈ Ax′′).

Expériences comparatives

Au vu des résultats encourageants de la preuve de concept, on peut étudier plus en détail l’impact en terme de performances des différents composants de la dissimilarité. Nous avons donc implémenté des variantes de ces différents composants, et développé un protocole approprié à leur évaluation, suivant le cadre d’évaluation du chapitre 3. Ce chapitre présentera tout d’abord le méta-problème sur lequel seront évaluées les dissimilarités, puis présentera les variations de dissimilarité étudiées. Nous détaillerons ensuite les expériences menées et leurs résultats.

Forme du méta-problème

Les résultats de la preuve de concept semblent suggérer que les dissimilarités prenant en compte les méta-attributs des attributs seraient particulièrement appropriées pour caractériser la performance d’algorithmes d’apprentissage particuliers sur des jeux de données. On s’attachera donc ici à construire un méta-problème exploitant cette caractéristique.
Dans la preuve de concept, nous avons évalué la dissimilarité sur un problème de méta classification, où la « classe » d’un jeu de données était l’algorithme qui y obtenait les meilleures performances. Il s’agit de l’une des premières approches de méta-apprentissage, ayant l’avantage d’être très simple, mais de nombreuses méthodes plus performantes ont depuis été développées (Giraud-Carrier et al. 2004). Par exemple, dans (P. Brazdil et al. 1994), le méta-problème est divisé en autant de sous-problèmes que de classifieurs, et l’on apprend alors pour chacun un modèle d’applicabilité. Dans (Kalousis et Hilario 2001a), on apprend plutôt un modèle pour chaque paire de classifieurs, prédisant sur quels jeux de données chacun dominera. Cette décomposition du méta-problème par paire de classifieurs est reprise dans (Sun et Pfahringer 2013), où des ensembles de règles sont appris pour comparer les performances des classifieurs dans chaque paire. D’autres travaux brisent le cadre traditionnel du problème de méta-apprentissage, tel (Leite et al. 2012), qui au lieu d’utiliser des ensembles de méta-données décrivant la performance de divers algorithmes sur des jeux de données, propose une stratégie de recherche d’algorithmes performants minimisant le nombre de tests à réaliser. De même, (Sun et al. 2012) considère l’optimisation des hyperparamètres en plus de la sélection d’algorithmes, et utilise des techniques d’optimisation pour chercher des solutions performantes.

Méta-attributs généraux des jeux de données

On présente ici les différents méta-attributs généraux des jeux de données. Ces derniers consistent en des propriétés simples des jeux de données (Table 4.6), un descriptif global des attributs numériques (Table 4.7), un descriptif global des attributs nominaux (Table 4.8), et en la performance de landmarkers évalués selon plusieurs critères (Tables 4.9, 4.10 et 4.11). Les landmarkers sont des algorithmes d’apprentissage simples, dont l’usage a été introduit dans (Pfahringer et al. 2000), que l’on applique au jeu de données considéré, afin d’y évaluer leur performance. Ceux utilisés ici proviennent de l’API Weka (Hall et al. 2009) et rassemblent différentes techniques classiques d’apprentissage. Les critères de performance retenus sont l’aire sous la courbe ROC (Table 4.9), le taux d’erreur (Table 4.10) et le coefficient Kappa de Cohen (Cohen 1968) (Table 4.11), qui capturent des aspects de la performance conceptuellement assez différents pour être considérés séparément.

Fonctions de dissimilarité

On définira ici les différentes dissimilarités à comparer. Les éléments nécessaires à ladéfinition d’une dissimilarité particulière sont, d’une part des ensembles de méta-attributs généraux et méta-attributs des attributs, tels que présentés dans la section précédente, et d’autre part des fonctions de dissimilarité sur ces méta-attributs généraux et métaattributs des attributs. On présentera donc les fonctions qui seront considérées, avant de lister les dissimilarités ainsi formées pour comparaison.

Dissimilarités sur les méta-attributs généraux

Pour fournir une dissimilarité sur les méta-attributs généraux, on comparera le candidat présenté en définition 5, la dissimilarité normalisée par la borne supérieure dubr G , à des distances classiques. On considérera un simple panel constitué des distances Euclidienne (norme 2), de Manhattan (norme 1), et de Tchebychev (norme infinie). On notera :
dissimG Dissimilarité normalisée par la borne supérieure.
distEucl Distance Euclidienne.
distMan Distance de Manhattan.
distTcheb Distance de Tchebychev.

Dissimilarités sur les attributs

Une dissimilarité sur les méta-attributs des attributs a été définie dans l’équation 4.3, se basant sur les différentes méthodes d’appariement des attributs décrites en section 4.2.2.3.
Les dissimilarités construites selon ces différentes méthodes d’appariement peuvent alors être comparées entre elles.
D’autre part, des techniques existent dans le domaine du test statistique pour comparer directement des distributions. En identifiant un attribut de jeu de données à une distribution, on pourrait utiliser de telles techniques pour construire une dissimilarité entre attributs. On considère donc le test de Kolmogorov-Smirnov (Smirnov 1948), permettant de tester la significativité des différences entre deux échantillons de données. Ce dernier à l’avantage d’être non-paramétrique (aucun pré-requis sur les distributions comparées), ce qui nous permet de l’appliquer directement à tout attribut numérique. Afin de pouvoir l’appliquer également à des attributs nominaux, on considérera une simple association d’index entiers uniques aux catégories. On peut alors définir une nouvelle fonction de dissimilarité δKS sur les attributs de jeux de données comme la statistique résultante d’un test de Kolmogorov-Smirnov pour l’hypothèse nulle selon laquelle deux attributs proviennent d’une même distribution :
Définition 8 Soient x et y deux jeux de données de ω. On note xi le ith attribut de x, et ωa l’ensemble des attributs des jeux de données de ω. On note KS(H0) la statistique résultante d’un test de Kolmogorov-Smirnov pour l’hypothèse nulle H0. On définit alors δKS : ω2 a 7→ ❘+ telle que : δKS(xi, yj) = KS(« xi et yj sont issus de la même distribution »).

Table des matières

1 Introduction 
2 État de l’art 
2.1 Apprentissage automatique
2.2 Évaluation de l’apprentissage
2.3 Méta-apprentissage
2.4 Caractérisation de jeux de données
2.5 Sélection d’attributs
2.6 Méta-analyse
2.7 Conclusion
3 Cadre d’évaluation de méta-analyses 
3.1 Introduction
3.2 Proposition d’un critère de performance
3.3 Dimensions des expériences au méta-niveau
3.3.1 Metadataset
3.3.2 Caractérisation de jeux de données
3.3.3 Critère de performance au niveau de base
3.3.4 Méthode de résolution au méta-niveau et Hyperparamètres
3.3.5 Méta-problème
3.4 Complexité et exécution des expériences au méta-niveau
3.5 Interprétation des résultats
3.6 Conclusion
4 Dissimilarité entre jeux de données 
4.1 Motivation
4.1.1 Introduction
4.1.2 Exemple
4.2 Fonction de dissimilarité
4.2.1 Propriétés désirables
4.2.2 Fonction candidate
4.3 Preuve de concept
4.3.1 Évaluation Théorique
4.3.2 Évaluation Expérimentale
4.4 Expériences comparatives
4.4.1 Forme du méta-problème
4.4.2 Ensembles de méta-attributs
4.4.3 Fonctions de dissimilarité
4.4.4 Cadre d’expérimentation
4.4.5 Analyse dimensionnelle des résultats
4.5 Discussion
4.5.1 Récapitulatif des résultats
4.5.2 Conclusion
5 Assistance à l’analyse de données 
5.1 Introduction
5.2 Méthode de Méta-analyse
5.2.1 Principe
5.2.2 Cas d’utilisation
5.2.3 Approches de construction d’expériences
5.3 Preuve de concept
5.3.1 Implémentation
5.3.2 Validation
5.4 Conclusion
6 Bilan et Perspectives 
6.1 Bilan
6.2 Perspectives
6.2.1 Méta-attributs de jeux de données
6.2.2 Assistance intelligente et innovation
6.2.3 Assistance en amont
6.2.4 Assistance en aval
6.3 Conclusion
A Listings 

Télécharger le rapport complet