La vitrine de diffusion des mémoires et thèses de l'ÉTS
RECHERCHER

Adaptive systems for hidden Markov model-based pattern recognition systems

Cavalin, Paulo Rodrigo (2011). Adaptive systems for hidden Markov model-based pattern recognition systems. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

[img]
Prévisualisation
PDF
Télécharger (3MB) | Prévisualisation
[img]
Prévisualisation
PDF
Télécharger (716kB) | Prévisualisation

Résumé

This thesis focuses on the design of adaptive systems (AS) for dealing with complex pattern recognition problems. Pattern recognition systems usually rely on static knowledge to define a configuration to be used during their entire lifespan. However, some systems need to adapt to knowledge that may not have been available in the design phase. For this reason, AS are designed to tailor a baseline pattern recognition system as required, and in an automated fashion, in both the learning and generalization phases. These AS are defined here, using hidden Markov model (HMM)-based classifiers as a case study.

We first evaluate incremental learning algorithms for the estimation of HMM parameters. The main goal is to find incremental learning algorithms that perform as well as the traditional batch learning techniques, but incorporate the advantages of incremental learning for designing complex pattern recognition systems. Experiments on handwritten characters have shown that a proposed variant of the Ensemble Training algorithm, which employs ensembles of HMMs, can lead to very promising results. Furthermore, the use of a validation dataset demonstrates that it is possible to achieve better performances than those of batch learning.

We then propose a new approach for the dynamic selection of ensembles of classifiers. Based on the concept called “multistage organizations”, the main objective of which is to define a multi-layer fusion function that adapts to individual recognition problems, we propose dynamic multistage organization (DMO), which defines the best multistage structure for each test sample. By extending Dos Santos et al’s approach, we propose two implementations for DMO, namely DSAm and DSAc. DSAm considers a set of dynamic selection functions to generalize a DMO structure, and DSAc uses contextual information, represented by the output profiles computed from the validation dataset. The experimental evaluation, considering both small and large datasets, demonstrates that DSAc outperforms DSAm on most problems. This shows that the use of contextual information can result in better performance than other methods. The performance of DSAc can also be enhanced in incremental learning. However, the most important observation, supported by additional experiments, is that dynamic selection is generally preferred over static approaches when the recognition problem presents a high level of uncertainty.

Finally, we propose the LoGID (Local and Global Incremental Learning for Dynamic Selection) framework, the main goal of which is to adapt hidden Markov model-based pattern recognition systems in both the learning and generalization phases. Given that the baseline system is composed of a pool of base classifiers, adaptation during generalization is conducted by dynamically selecting the best members of this pool to recognize each test sample. Dynamic selection is performed by the proposed K-nearest output profiles algorithm, while adaptation during learning consists of gradually updating the knowledge embedded in the base classifiers by processing previously unobserved data. This phase employs two types of incremental learning: local and global. Local incremental learning involves updating the pool of base classifiers by adding new members to this set. These new members are created with the Learn++ algorithm. In contrast, global incremental learning consists of updating the set of output profiles used during generalization. The proposed framework has been evaluated on a diversified set of databases. The results indicate that LoGID is promising. In most databases, the recognition rates achieved by the proposed method are higher than those achieved by other state-of-the-art approaches, such as batch learning. Furthermore, the simulated incremental learning setting demonstrates that LoGID can effectively improve the performance of systems created with small training sets as more data are observed over time.

Titre traduit

Un système adaptatif basé sur les HMM pour la reconnaissance de formes

Résumé traduit

Cette thèse porte sur l’étude des systèmes adaptatifs pour la reconnaissance de formes. Habituellement les systèmes de reconnaissance reposent sur une connaissance statique du problème à résoudre et cela pour la durée de vie du système. Cependant il y a des circonstances où la connaissance du problème est partielle lors de l’apprentissage initial à l’étape de la conception.

Pour cette raison, les systèmes de classification adaptatifs de nouvelle génération permettent au système de base de s’adapter à la fois en apprenant sur les nouvelles données et sont également capables de s’adapter à l’environnement lors de la généralisation. Cette thèse propose une nouvelle définition d’un système de reconnaissance adaptatif où les MMCs (Modèles de Markov Cachés) sont considérés comme étude de cas.

La première partie de la thèse présente une évaluation des principaux algorithmes d’apprentissage incrémental utilisés pour l’estimation des paramètres des MMCs. L’objectif de cette étude est de dégager les stratégies d’apprentissage incrémental dont la performance en généralisation se rapproche de cette obtenue avec un apprentissage hors-ligne (batch). Les résultats obtenus sur le problème de la reconnaissance de chiffres et de lettres manuscrits montrent la supériorité des approches basées sur les ensembles de modèles. De plus, nous avons montré l’importance de conserver dans une mémoire à court terme des exemples utilisés en validation, ce qui permet d’obtenir un niveau de performance qui peut même dépasser celui obtenu en mode batch.

La deuxième partie de cette thèse est consacrée à la formulation d’une nouvelle approche pour la sélection dynamique des ensembles de classifieurs. Inspiré du concept de fusion appelé « organisation multi-niveau » (multistage organizations), nous avons formulé une variante de ce concept appelé DMO (dynamic multistage organization - DMO) qui permet d’adapter la fonction de fusion dynamiquement pour chaque exemple de test à classer. De plus, le concept DMO a été intégré à la méthode DSA proposée par Dos Santos et al pour la sélection dynamique d’ensembles de classifieurs. Ainsi, deux nouvelles variantes, DSAm et DSAc, ont été proposées et évaluées. Dans le premier cas (DSAm), plusieurs fonctions de sélection permettent une généralisation de la structure DMO. Pour ce qui est de la variante DSAc, nous utilisons l’information contextuelle (représentée par les profils de décisions des classifieurs de base) acquise par le système et qui est associée à la base de validation conservée dans une mémoire à court terme. L’évaluation des deux approches sur des bases de données de petite et de grande échelle ont montré que la méthode DSAc domine DSAm sur la plupart des cas étudiés.

Ce résultat montre que l’utilisation d’informations contextuelles permet une meilleure performance en généralisation comparées aux méthodes non informées. Une propriété importante de l’approche DSAc est qu’elle peut également servir pour apprendre de nouvelles données dans le temps, une propriété très importante pour la conception de systèmes de reconnaissance adaptatifs dans les environnements dynamiques caractérisés par un niveau important d’incertitude sur le problème à résoudre.

Finalement, un nouveau framework appelé LoGID (Local and Global Incremental Learning for Dynamic Selection) est proposé pour la conception d’un système de reconnaissance adaptatif basé sur les MMC, et capable de s’adapter dans le temps durant les phases d’apprentissage de généralisation. Le système est composé d’un pool de classifieurs de base et l’adaptation durant la phase de généralisation est effectuée par la sélection dynamique des membres du pool les plus compétents pour classer chaque exemple de test. Le mécanisme de sélection dynamique est basé sur l’algorithme des K plus proches vecteurs de décision, tandis que l’adaptation durant la phase d’apprentissage consiste à la mise à jour et à l’ajout de classifieurs de base dans le système. Durant la phase d’apprentissage, deux stratégies sont proposées pour apprendre incrémentalement sur des nouvelles données: l’apprentissage local et l’apprentissage global.

L’apprentissage incrémentale local implique la mise à jour du pool de classifieurs de base en ajoutant des nouveaux membres à cet ensemble. Les nouveaux membres sont générés avec l’algorithme Learn++. L’apprentissage incrémental global consiste à la mise à jour de la base de connaissances composée des vecteurs de décisions qui seront utilisés en généralisation pour la sélection dynamique des membres les plus compétents.

Le système LoGID a été validé sur plusieurs bases de données et les résultats comparés à ceux publiés dans la littérature. En général, la méthode proposée domine les autres méthodes incluant les méthodes d’apprentissage hors-ligne. Enfin, le système LoGID évalué en mode adaptatif montre qu’il est en mesure d’apprendre de nouvelles connaissances dans le temps au moment où les nouvelles données sont disponibles. Cette faculté d’adaptation est très importante également lorsque les données disponibles pour l’apprentissage sont peu nombreuses.

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 of the requirements for the degree of doctor of philosophy" Bibliogr. : f. [123]-128.
Mots-clés libres: Reconnaissance des formes (Informatique) Systèmes adaptatifs. Processus de Markov. Apprentissage, Classifieur, Dynamique, Ensemble, Incrémental, LoGID, Sélection, Modèles Markoviens
Directeur de mémoire/thèse:
Directeur de mémoire/thèse
Sabourin, Robert
Co-directeurs de mémoire/thèse:
Co-directeurs de mémoire/thèse
Suen, Ching Y.
Programme: Doctorat en génie > Génie
Date de dépôt: 15 mars 2012 15:20
Dernière modification: 16 févr. 2017 22:20
URI: http://espace.etsmtl.ca/id/eprint/976

Actions (Identification requise)

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

Statistique

Plus de statistique...