Unsupervised Learning of Pictures by Genetic Hybridization of Hidden Markov Chain. Apprentissage Non-Supervisé D'images par Hybridation Génétique d'une Chaîne de Markov Cachée

Unsupervised Learning of Pictures by Genetic Hybridization of Hidden Markov Chain

Apprentissage Non-Supervisé D'images par Hybridation Génétique d'une Chaîne de Markov Cachée

Mohamed Slimane Thierry Brouard  Gilles VenturinI  Jean-Pierre Asselin De Beauville 

Laboratoire d'Informatique- EA2 101 , Ecole d'Ingénieurs en Informatique pour l'Industrie, Université de Tours, 64, Avenue Jean Portalis, 37200 Tours FRANCE

Page: 
461-475
|
Received: 
26 January 1998
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

This paper presents a learning algorithm using hidden Markov models (HMMs) and genetic algorithms (GAs) . Two standard problems to be solved with HMMs are how to determine the probabilities and the number of hidden states of the learned models. Generally, this number of states is determined either by the trial-error method that needs experimentation, or by the background knowledge available. The presented algorithm uses a GA in order to determine at the same time both the number of states and the probabilities of learned HMMs. This hybrid algorithm uses the Baum-Welch algorithm to optimise precisely the probabilities of HMMs. Several algorithms, either hybrid or not, are compared in a face recognition task . The obtained results highlight the strength of our approach for the concerned problem . 

Résumé 

Cet article présente un algorithme d'apprentissage non supervisé par chaînes de Markov cachées (CMC) et algorithmes génétiques(AG). Deux des problèmes rencontrés lors de l'utilisation des CMCsont de déterminer les probabilités de la CMCet le nombre d'états de cette chaîne. Bien souvent, ce nombre d'états est déterminé soit par expériences successives, soit à l'aide de connaissances a prioridu domaine. L'algorithme présenté ici emploie un algorithme génétique afin de déterminer le nombre d'états cachés de la CMCainsi que les différentes probabilités qui la constituent. Cet algorithme est couplé à l'algorithme de Baum-Welch qui permet une réestimation efficace des probabilités de la CMC. Différents algorithmes, hybrides ou non, sont comparés entre eux sur une application d'apprentissage et de reconnaissance d'images représentant des visages . Les résultats montrent la supériorité de l'approche génétique pour ce type de problème. 

Keywords: 

Hidden Markov chains, genetic algorithms, hybridization, unsupervised learning, picture recognition.

Mots clés 

Chaînes de Markov cachées, algorithmes génétiques, hybridation, apprentissage non supervisé, reconnaissance d'images.

Introduction
1. Les Chaînes de Markov Cachées (CMC)
2. Problèmes Fondamentaux
3. Algorithme Génétique pour la Manipulation d'une CMC
4. Algorithme GHOSP
5. Système D'apprentissage D'images
6. Système de Reconnaissance D'images par CMC
7. Tests et Résultats
8. Conclusion
9. Remerciements
  References

[1] L.R. Rabiner, A tutorial on hidden Markov models and selected applications , in speech recognition, Proc. of IEEE, vol. 77-2, pp. 257-286, 1989. 

[2] M. Slimane, J.P. Asselin de Beauville, Les modèles de Markov cachés du premier ordre (lère partie), Rapport de recherches 171 - Laboratoire d'informatique, univ. de Tours, 36p, 1994. 

[3] A. Kriouille, La reconnaissance automatique de la parole et les modèles Markoviens cachés, Thèsede doctorat,Univ. de Nancy I, 149p, 1990. 

[4] I. Guyon, F. Pereira, Design of a linguistic postprocessor using variable memory length Markov models, International Conference on Document Analysis and Recognition (Montréal, Canada), IEEE Computer Society Press, pp. 454-457, 1995. 

[5] X. Huang, Y. Akiri, M. Jack, Hidden Markov models for Speech Recognition, Edimburgh Unversity Press, 1990. 

[6] J.C. Anigbogu, Reconnaissance de textes imprimés multifontes à l'aide de modèles stochastiques et métriques, Thèse de doctorat, Univ. de Nancy I, 157p, 1992. 

[7] S-S. Kuo, O. Agazzi, Keyword spotting in poorly printed documents using pseudo-2D hidden Markov models, IEEE transactions on Pattern Analysis and Machine Intellegence, vol. 16-8, pp. 842-848, 1994. 

[8] A. Kundu, L. Bahl, Recognition of handwritten Script :a hidden Markov model based approach,Proc. of International Conference on Acoustics, Speech and Signal Processing, pp. 928-931, 1988. 

[9] M. Saerens, Hidden Markov models assuming a continuous time dynamic emission of acoustic vectors, Proc. ofEurospeech, 1993. 

[10] G. Celeux, J. Clairambault, Estimation de chaînes de Markov cachées : méthodes &problèmes, GDR 134, Traitementdu signal et images, journées thématiques «ApprochesMarkoviennes en signal et images», pp .5-19, 1992. 

[11] V. Krishnamurthy, S.B. Moore, S-H. Chung, Hidden Markov model signal processing in presence of unknown deterministic interferences, IEEE transactions on Automatic Control, vol.38-1, 1993. 

[12] W.D. Mao, S.Y. Kung, An object recognition system using stochastic knowledge source and VLSI parallel architecture, Proc. of International Conference on Pattern Recognition, pp. 382-386, 1990. 

[13] F. Salzenstein, Modèles Markoviens flous et segmentation statistique non supervisée d'image,Thèse dedoctorat, Univ. deRennesI, 142 p, 1996. 

[14] M. Slimane, J.P. Asselin de Beauville, T. Brouard, G. Venturini, J.M. Sealelli, Reconnaissance d'image par chaîne de Markov cachée optimisée génétiquement, 28èmesJournéesdeStatistiques, (Québec, Canada), pp683687,1996. 

[15] F. S. Samaria, F. Fallside, Face identification and features extract using hidden Markov models, Image processing :theory and applications,Elsevier Science Publisher, pp. 295-298, 1993. 

[16] P. Baldi, Y.Chauvin, T. Hunkapiller, M. McClure, Hidden Markov models of biological primary Sequence information, Proc. Natural Academic Sciences, vol. 91-3, pp. 1059-1063, 1995. 

[17] L.E. Baum, J.A. Eagon, An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology,Bull. American Society,vol. 73, pp. 360-363, 1967.

[18] B. Benmiloud, W. Pieczynski, Estimationdes paramètres dans les chaînes de Markov cachées et segmentation d'images, Traitementdu Signal, vol. 12-5, pp. 433-454, 1995. 

[19] G. Celeux, J. Diebolt, The SEMalgorithm : a probabilistic teacher algorithm derived from the EM algorithm for the mixture problem, Computational statistics quarterly, vol. 2, pp. 73-82, 1985. 

[20] M. Askar, B. Derin, A recursive algorithm for the Bayes solution of the smoothing problem, IEEE transactions on Automatic Control, vol. 26-2, pp. 558-561, 1981. 

[21] M. Slimane, G. Venturini, J.P. Asselin deBeauville, T. Brouard, A.Brandeau, Optimizing HMM with a genetic algorithm, Artificial Evolution, Lecture Notes in Computer Science, Springer Verlag, vol. 1063, pp. 384-396, 1996. 

[22] C. Dours, Contribution à l'étude du décodageaccoustico-phonétique pour la reconnaissance automatique de la parole, Thèse de doctorat, Univ. de Toulouse, 1989. 

[23] K.M. Pouting, A statistical approach to the determination of hidden Markov models structure,Proc. ofthe 7thFASESymposium, Edimburgh, 1988. 

[24] T. Brouard, M. Slimane, G. Venturini, J.P. Asselin de Beauville, Apprentissage du nombre d'états d'une chaîne de Markov cachée pour la reconnaissanced'images, ColloqueGRETSIsur le Traitementdu Signal etdesImages, Grenoble(France), pp. 845-848, 1997.

[25] A. J. Viterbi, Error bounds for convolutional codes and asymptotically optimum decoding algorithm,IEEE transactions on Information Theory, vol. 13, pp. 260-269, 1967. 

[26] J. H. Holland, Adaptation in natural and artificial systems, Ann Arbor University of Michigan Press, 1975. 

[27] T. Brouard, M. Slimane, G. Venturini, J.P. Asselin de Beauville, Segmentation non-supervisée d'images parchaînes de Markovcachées,Sème rencontrede laSociété Francophone de Classification, Lyon (France), pp. 177-180, 1997. 

[28] M. Slimane, G. Venturini, J.P. Asselin de Beauville, T. Brouard, Hybrid Genetic Learning of Hidden Markov Models for Time Series Prediction, In Biomimetic approaches in management science», pp. 179-196, KLUWER Academics Eds, 1998. 

[29] T. Brouard, M. Slimane, J.P. Asselin deBeauville, G.Venturini,Apprentissage d'une chaînede Markov cachée : problèmes numériques liés àl'application àl'image,Revue deStatistique Appliquée, vol.XLVI (2), pp. 83-108, 1998. 

[30] F.S. Samaria, A. Harter, Paramatrisation of a stochastic model for human face identification, 2nd IEEE Workshop on. application of computer vision, Sarasota (Florida), 1994.