Local learning for dynamic ensemble selection

De Araujo Souza, Mariana (2023). Local learning for dynamic ensemble selection. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (4MB) | Prévisualisation

Résumé

Dynamic selection techniques are based on the idea that the classifiers from an ensemble are experts in different areas of the feature space. As such, they attempt to single out only the most competent one(s) to label a given query sample generally based on the locality assumption, i.e., assuming that similar instances share a similar set of classifiers able to correctly label them. Therefore, the success of the dynamic selection task is strongly linked to the local data distribution, as it establishes the quality of the defined region for the dynamic selection task and may affect how the classifiers’ local expertise is perceived. As such, characteristics such as local class overlap and data sparsity may lead to a poorly defined local region presenting a weak locality assumption, thus hindering the search for a local expert.

Thus, in this thesis, several techniques that integrate the local context into the multiple classifier system are proposed to improve the dynamic selection of classifiers over challenging scenarios. To that end, the definition of an adequate local region is addressed by characterizing the local data and defining the regions using different methods to tackle complex distributions and with multiple scales to provide ample context to the system. The presence of local experts is also addressed by producing the pool over the local border to yield more specialized classifiers, and by learning the dynamic selection task in an end-to-end manner from the classifiers’ interactions and the local data relations to boost the search for local experts. Thus, by leveraging the information from the local data distribution, the dynamic selection techniques’ ability to find local experts may be enhanced, improving its robustness and performance over complex problems.

In Chapter 2, the Online Local Pool (OLP) technique is proposed to tackle the difficulty the dynamic selection techniques present in searching for local experts in overlap areas. To that end, the OLP technique generates several linear models in the vicinity of the query instance with different locality degrees to produce classifiers able to recognize the local border. To identify the class overlap areas, an instance hardness measure is computed in memorization for all the available samples, and the classifiers are so that they fully “cover” the target region. Experimental results demonstrate that using the generated local pool provided an improvement to the evaluated dynamic classifier selection techniques compared to a globally generated pool, suggesting an advantage in having locally specialized classifiers in the pool for the dynamic selection task. The proposed approach also performs similarly to several state-of-the-art learning methods.

In Chapter 3, a local ensemble method based on the OLP was proposed, the OLP++, to address the limitations the former presented over high dimensional data due to its local region definition being susceptible to the effects of the curse of dimensionality. To that end, the OLP++ approach leverages the data partitions obtained from tree-based algorithms for the locality definition, and then produces the local experts over the different impure nodes from the decision path that a given query instance traverses in the tree(s), therefore introducing an increasingly wider local context to the local ensemble. Experimental results show that the OLP++’s recursive partition-based region definition successfully identified borderline instances more often than the OLP’s nearest neighbors-based region definition, suggesting an improvement in the data distribution used to learn the local linear rules. The OLP++’s region definition also leads to a more diverse local ensemble and a statistically superior performance compared to the OLP over the high dimensional data. The OLP++ also outperforms the random forest baseline and several local-based dynamic selection techniques, further suggesting the advantages of the proposed approach for dealing with high dimensional data in the context of dynamic selection.

Lastly, in Chapter 4, a novel dynamic multiple classifier system is proposed to deal with sparse and overlapped data as the OLP++ presents a shortcoming due to its reliance on pre-defined partitions that were not optimized for the dynamic selection task. The proposed Graph Neural Network Dynamic Ensemble Selection (GNN-DES) technique addresses this issue by learning the dynamic selection task in an end-to-end manner using a multi-label Graph Neural Network (GNN), that is responsible for the selection of the local experts. By learning from the samples’ local relationships, represented in a graph, and the classifiers’ inter-dependencies, modeled in the meta-labels, the GNN may implicitly learn an embedded space where the locality assumption is stronger without requiring an explicit local region definition. Experimental results demonstrate that the classical dynamic selection techniques generally struggle over sparse and overlapped data, and that the GNN-DES outperforms the static selection baseline and several techniques based on similarities in the feature space. Further analysis also shows the GNN-DES better deals with performed better than the contending techniques over the problems where the locality assumption is weaker in the presence of class overlap, suggesting that leveraging the local data distribution and the classifiers’ interactions can aid the dynamic selection task in challenging scenarios.

Titre traduit

Apprentissage local pour la sélection dynamique d’ensembles

Résumé traduit

Les techniques de sélection dynamique reposent sur l’idée que les classificateurs d’un ensemble sont experts dans différents domaines de l’espace des caractéristiques. En tant que telles, elles tentent d’identifier uniquement le(s) classificateur(s) le(s) plus compétent(s) pour étiqueter un échantillon de requête donné, généralement sur la base de l’hypothèse de localité, c’est-à-dire en supposant que des instances similaires partagent un ensemble similaire de classificateurs capables de les étiqueter correctement. Par conséquent, la réussite de la tâche de sélection dynamique est étroitement liée à la distribution locale des données, car elle établit la qualité de la région définie pour la tâche de sélection dynamique et peut affecter la manière dont l’expertise locale des classificateurs est perçue. Ainsi, des caractéristiques telles que le chevauchement des classes locales et la rareté des données peuvent conduire à une région locale mal définie présentant une hypothèse de localité faible, entravant ainsi la recherche d’un expert local.

Ainsi, dans cette thèse, plusieurs techniques qui intègrent le contexte local dans le système de classificateurs multiples sont proposées pour améliorer la sélection dynamique des classificateurs dans des scénarios difficiles. À cette fin, la définition d’une région locale adéquate est abordée en caractérisant les données locales et en définissant les régions à l’aide de différentes méthodes pour traiter les distributions complexes et avec des échelles multiples pour fournir un contexte ample au système. La présence d’experts locaux est également prise en compte en produisant le pool sur la frontière locale afin d’obtenir des classificateurs plus spécialisés, et en apprenant la tâche de sélection dynamique de bout en bout à partir des interactions des classificateurs et des relations entre les données locales afin de stimuler la recherche d’experts locaux. Ainsi, en exploitant les informations provenant de la distribution des données locales, la capacité des techniques de sélection dynamique à trouver des experts locaux peut être renforcée, ce qui améliore sa robustesse et ses performances sur des problèmes complexes.

Dans le chapitre 2, la technique du pool local en ligne (OLP) est proposée pour résoudre la difficulté que présentent les techniques de sélection dynamique dans la recherche d’experts locaux dans les zones de chevauchement. À cette fin, la technique OLP génère plusieurs modèles linéaires à proximité de l’instance interrogée avec différents degrés de localité pour produire des classificateurs capables de reconnaître la frontière locale. Pour identifier les zones de chevauchement des classes, une mesure de dureté de l’instance est calculée par mémorisation pour tous les échantillons disponibles, et les classificateurs sont conçus de manière à "couvrir" entièrement la région cible. Les résultats expérimentaux montrent que l’utilisation de la réserve locale générée a permis d’améliorer les techniques de sélection de classificateurs dynamiques évaluées par rapport à une réserve générée globalement, ce qui suggère l’avantage d’avoir des classificateurs localement spécialisés dans la réserve pour la tâche de sélection dynamique. L’approche proposée donne également des résultats similaires à ceux de plusieurs méthodes d’apprentissage de pointe.

Au chapitre 3, une méthode d’ensemble local basée sur l’OLP a été proposée, l’OLP++, pour remédier aux limitations que la première méthode présentait sur les données de haute dimension en raison de sa définition de la région locale sensible aux effets de la malédiction de la dimensionnalité. À cette fin, l’approche OLP++ exploite les partitions de données obtenues à partir d’algorithmes basés sur les arbres pour la définition de la localité, puis produit les experts locaux sur les différents nœuds impurs du chemin de décision qu’une instance de requête donnée traverse dans le(s) arbre(s), introduisant ainsi un contexte local de plus en plus large à l’ensemble local. Les résultats expérimentaux montrent que la définition de la région basée sur la partition récursive de l’OLP++ a permis d’identifier les instances limites plus souvent que la définition de la région basée sur les plus proches voisins de l’OLP, ce qui suggère une amélioration de la distribution des données utilisée pour apprendre les règles linéaires locales. La définition de région de l’OLP++ conduit également à un ensemble local plus diversifié et à une performance statistiquement supérieure à celle de l’OLP sur les données de haute dimension. L’OLP++ surpasse également la forêt aléatoire de référence et plusieurs techniques de sélection dynamique locale, ce qui confirme les avantages de l’approche proposée pour le traitement des données de haute dimension dans le contexte de la sélection dynamique.

Enfin, au chapitre 4, un nouveau système dynamique de classification multiple est proposé pour traiter les données éparses et superposées, car l’OLP++ présente une lacune en raison de sa dépendance à l’égard de partitions prédéfinies qui n’ont pas été optimisées pour la tâche de sélection dynamique. La technique proposée de sélection dynamique d’ensemble par réseau neuronal graphique (GNN-DES) résout ce problème en apprenant la tâche de sélection dynamique de bout en bout à l’aide d’un réseau neuronal graphique (GNN) multiétiquettes, qui est responsable de la sélection des experts locaux. En apprenant à partir des relations locales des échantillons, représentées dans un graphe, et des interdépendances des classificateurs, modélisées dans les méta-étiquettes, le GNN peut apprendre implicitement un espace intégré où l’hypothèse de localité est plus forte sans nécessiter une définition explicite de la région locale. Les résultats expérimentaux démontrent que les techniques classiques de sélection dynamique ont généralement du mal à traiter les données éparses et superposées, et que le GNN-DES est plus performant que la sélection statique de base et que plusieurs techniques basées sur les similarités dans l’espace des caractéristiques. Une analyse plus poussée montre également que le GNN-DES gère mieux les données éparses et les données qui se chevauchent. a obtenu de meilleurs résultats que les techniques concurrentes sur les problèmes où l’hypothèse de localité est plus faible en présence d’un chevauchement de classes, ce qui suggère que l’exploitation de la distribution locale des données et des interactions des classificateurs peut faciliter la tâche de sélection dynamique dans des scénarios difficiles.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment for the degree of doctor of philosophy". Comprend des références bibliographiques (pages 239-252).
Mots-clés libres:	systèmes de classification multiples, sélection dynamique, apprentissage local, chevauchement de classes, dureté des instances, rareté des données, méta-apprentissage, réseaux de neurones graphiques
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Sabourin, Robert
Codirecteur:	Codirecteur Darmiton da Cunha Cavalcanti, George Menelau Cruz, Rafael
Programme:	Doctorat en génie > Génie
Date de dépôt:	25 oct. 2023 13:10
Dernière modification:	25 oct. 2023 13:10
URI:	https://espace.etsmtl.ca/id/eprint/3297

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt