Classification systems optimization with multi-objective evolutionary algorithms

Radtke, Paulo Vinicius Wolski (2006). Classification systems optimization with multi-objective evolutionary algorithms. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

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

Résumé

L'optimisation des systèmes de classification est une tâche complexe qui requiert l'intervention d'un spécialiste (expérimentateur). Cette tâche exige une bonne connaissance du domaine d'application afin de réaliser l'extraction de l'information pertinente pour la mise en oeuvre du système de classification ou de reconnaissance. L'extraction de caractéristiques est un processus itératif basé sur l'expérience. Normalement plusieurs évaluations de la performance en généralisation du système de reconnaissance, sur une base de données représentative du problème réel, sont requises pour trouver l'espace de représentation adéquat.

Le processus d'extraction de caractéristiques est normalement suivi par une étape de sélection des caractéristiques pertinentes (FSS). L'objectif poursuivi est de réduire la complexité du système de reconnaissance tout en maintenant la performance en généralisation du système. Enfin, si le processus d'extraction de caractéristiques permet la génération de plusieurs représentations du problème, alors il est possible d'obtenir un gain en performance en combinant plusieurs classificateurs basés sur des représentations complémentaires. L'ensemble de classificateurs (EoC) permet éventuellement une meilleure performance en généralisation pour le système de reconnaissance.

Nous proposons dans cette thèse une approche globale pour l'automatisation des tâches d'extraction, de sélection de caractéristiques et de sélection des ensembles de classificateurs basés sur l'optimisation multicritère. L'approche proposée est modulaire et celle-ci permet l'intégration de l'expertise de l'expérimentateur dans le processus d'optimisation. Deux algorithmes génétiques pour l'optimisation multicritère ont été évalués, le Fast Elitist Non-Dominated sorting Algorithm (NSGA-II) et le Multi-Objective Memetic Algorithm (MOMA). Les algorithmes d'optimisation ont été validés sur un problème difficile, soit la reconnaissance de chiffres manuscrits isolés tirés de la base NIST SD19. Ensuite, notre méthode a été utilisée une seule fois sur un problème de reconnaissance de lettres manuscrites, un problème de reconnaissance provenant du même domaine, pour lequel nous n'avons pas développé une grande expertise. Les résultats expérimentaux sont concluants et ceux-ci ont permis de démontrer que la performance obtenue dépasse celle de l'expérimentateur.

Finalement, une contribution très importante de cette thèse réside dans la mise au point d'une méthode qui permet de visualiser et de contrôler le sur-apprentissage relié aux algorithmes génétiques utilisés pour l'optimisation des systèmes de reconnaissance. Les résultats expérimentaux révèlent que tous les problèmes d'optimisation étudiés (extraction et sélection de caractéristiques de même que la sélection de classificateurs) souffrent éventuellement du problème de sur-apprentissage. À ce jour, cet aspect n'a pas été traité de façon satisfaisante dans la littérature et nous avons proposé une solution efficace pour contribuer à la solution de ce problème d'apprentissage.

Titre traduit

Optimisation des systèmes et classification avec algorithmes évolutifs multicritère

Résumé traduit

The optimization of classification systems is a non-trivial task, which is most of the time performed by a human expert. The task usually requires the application of domain knowledge to extract meaningful information for the classification stage. Feature extraction is traditionally a trial and error process, where the expert chooses a set of candidate solutions to investigate their accuracy, and decide if they should be further refined or if a solution is suitable for the classification stage. Once a representation is chosen, its complexity may be reduced through feature subset selection (FSS) to reduce classification time. A recent trend is to combine several classifiers into ensemble of classifiers (EoC), in order to improve accuracy.

This thesis proposes a feature extraction based approach to optimize classification systems using a multi-objective genetic algorithm (MOGA). The approach first optimizes feature sets (representations) using the Intelligent Feature Extractor (IFE) methodology, selecting from the resulting set the best representation for a single classifier based system. After this stage, the selected single classifier can have its complexity reduced through FSS. Another approach is to use the entire IFE result set to
optimize an EoC for higher classification accuracy.

Classification systems optimization is challenged by the solution over-fit to the data-set used through the optimization process. This thesis also details a global validation strategy to control over-fit, based on the validation procedure used during classifier training. The global validation strategy is compared to traditional methods with the proposed approach to optimize classification system. Finally, a stopping criterion based on the approximation set improvement is also proposed and tested in the global validation context. The goal is to monitor algorithm improvement and stop the optimization process when it cannot further improve solutions.

An experiment set is performed on isolated handwritten digits with two MOGAs, the Fast Elitist Non-Dominated Sorting Algorithm (NSGA-11) and the Multi-Objective Memetic Algorithm (MOMA). Both algorithms are compared to verify which is the most appropriate for each optimization stage. Experimental results demonstrate that the approach to optimize classification systems is able to outperform the traditional approach in this problem. Results also confirm both the global validation strategy and the stop criterion. The next experiment set uses the best configuration found with digits to optimize isolated uppercase handwritten letters, demonstrating the approach effectiveness on an unknown problem.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"A thesis presented to the École de technologie supérieure in fullfilment of the thesis requirement for the degree of philosophiae doctor in engineering". Bibliogr.: f. [163]-173. Ch. 1. State of the art -- Ch. 2. Classification systems optimization -- Ch. 3. Multi-objective optimization memetic algorithm -- Ch. 4. Validation strategies to control solution -- Ch. 5. Stopping criterion -- Ch. 6. Validation experiments on isolated handwritten digits -- Ch. 7. Experiments on isolated handwritten uppercase letters -- Appendix 1. Fast elitist non-dominated sorting genetic algorithm - NSGA II -- Appendix 2. Statistical analysis -- Appendix 3. Rejection strategies.
Mots-clés libres:	Algorithme, Approche, Automatisation, caracteristique, classificateur, Classification, Ensemble, Evolutif, Extraction, Genetique, Modulaire, Multicritere, Optimisation, Reconnaissance, Selection; Systeme
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Sabourin, Robert
Codirecteur:	Codirecteur Wong, Tony
Programme:	Doctorat en génie > Génie
Date de dépôt:	23 mars 2011 14:14
Dernière modification:	04 nov. 2016 20:23
URI:	https://espace.etsmtl.ca/id/eprint/497

Gestion Actions (Identification requise)

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