Moteur de reconnaissance GA/HMM

Les modèles de Markov cachés (HMM) sont des outils statistiques permettant de modéliser des phénomènes stochastiques. Ces modèles sont utilisés dans de nombreux domaines (Cappé 2001) tels que la reconnaissance et la synthèse de la parole, la biologie, l’ordonnancement, l’indexation de documents, la reconnaissance d’images, la prédiction de séries temporelles, … Pour pouvoir utiliser ces modèles efficacement, il est nécessaire d’en connaitre les principes. L’amélioration de l’apprentissage des HMM à l’aide de métaheuristique à base de population est l’objet de ce chapitre. Ce chapitre a donc pour objectif d’établir les principes, les notations utiles et les principaux algorithmes qui constituent la théorie des HMM. A cet effet, nous commençons ce chapitre en définissant de que sont les HMM leur principes, et nous présentons les algorithmes classiques des HMM : Forward, Backkward et de Viterbi.

Modèles de Markov Cachés

Définition

Un modèle HMM est défini comme un ensemble d’états, chacun d’entre eux associé à une distribution de probabilité (en général multidimensionnelle). Les transitions entre les états sont régies par un ensemble de probabilités appelées probabilités de transition Dans un état particulier, un résultat ou observation peut être généré conformément à la distribution de probabilité associée. Par opposition à un modèle de Markov classique ou l’état est directement observable par un observateur externe, dans un modèle HMM, l’état n’est pas directement observable et seulement des variables influencées par l’état le sont. Les états sont donc cachés, d’ou le nom de modèle de Markov caché. Un HMM (représenté dans la figure 4.1) est défini par : Figure 4.1 – HMM à 5 états dont 3 émetteurs.  N : le nombre d’états du modèle. Les états seront notés xi pour 1 ≤ i ≤ N  M : le nombre de symboles d’observation. Dans le cas ou les observations sont continues, M est infini. Dans notre notation, les symboles d’observation de l’alphabet sont notés Y = {yj} pour 1 ≤ j ≤ M. – π : le vecteur de probabilités initiales des états. Concernant cet élément, un autre type de HMM utilise des états start et end et non une distribution d’états initiaux. Ce type d’HMM est notamment employé en bioinformatique. – A : la matrice de transition ou sont définies les probabilités de transition entre les états. Ces probabilités A = {aij} sont définies comme : 𝑎𝑖𝑗 = 𝑝 𝑥𝑡 = 𝑖|𝑥𝑡−1 = 𝑗 , 1 ≤ 𝑖,𝑗 ≤ 𝑁 (4.1) avec xt désigne l’état courant à l’instant t. Les probabilités de transition aij doivent satisfaire les contraintes stochastiques : 𝑎𝑖𝑗 ≥ 0 𝑒𝑡 𝑎𝑖𝑗 , 1 ≤ 𝑖,𝑗 ≤ 𝑁 𝑁 𝑗=1 (4.2)  B : la matrice de confusion (ou matrice d’observation) contenant les probabilités d’observation (ou probabilités d’émission) B = {bj(k)} associées aux états. Ces probabilités sont définies comme : 𝑏𝑗 𝑘 = 𝑝 𝑦𝑡 = 𝑣𝑘 𝑥𝑡 = 𝑗 , 1 ≤ 𝑗 ≤ 𝑁, 1 ≤ 𝑘 ≤ 𝑀 (4.3) avec vk dénote le k eme symbole d’observation dans l’alphabet, et yt le vecteur de paramètres actuel (ou simplement observation actuelle) à l’instant t. Les probabilités d’observation satisfont aussi les contraintes stochastiques. Dans le cas d’observations continues, des densités de probabilités continues sont à utiliser. Pour dénoter un modèle HMM le triplet λ = (π, A, B) est généralement utilisé. Il est important de noter que chaque probabilité dans la matrice de transition (de confusion) est  indépendante du temps. En d’autres termes, les matrices ne changent pas dans le temps quand le système évolue. En pratique, ceci est l’une des suppositions les plus discutables des modèles de Markov à propos des processus réels. Dans la théorie des HMMs, des hypothèses sont faites pour une docibilité mathématique et informatique :  Hypothèse markovienne : concernant la définition des éléments de la matrice de transition A, la probabilité de transition vers un état ne dépend que de l’état actuel et non des états rencontrés précédemment. Ainsi, la séquence des états constitue une chaîne de Markov simple.  Hypothèse de stationnarité : comme nous l’avons déjà évoqué, la matrice des probabilités de transition est indépendante de l’actuel temps, dans lequel les transitions prennent place. Mathématiquement : 𝑝 𝑥𝑡1+1 = 𝑗 𝑥𝑡1 = 𝑖 = 𝑝 𝑥𝑡2+1 = 𝑗 𝑥𝑡2 = 𝑖 𝑝𝑜𝑢𝑟 𝑡𝑜𝑢𝑡 𝑡1 𝑒𝑡 𝑡2 , (4.4) – Hypothèse d’indépendance des sorties (observations) : l’observation courante est statiquement indépendante des observations précédentes. Mathématiquement, cette hypothèse peut être formulée pour un HMM λ par : 𝑝 𝑌 𝑥1 , 𝑥2 , … , 𝑥𝑡 , 𝜆 = 𝑝 𝑦𝑡 𝑥𝑡 , 𝜆 . 𝑇 𝑡=1 (4.5) 

Utilisation et algorithmes

Une fois qu’un système est décrit comme un HMM, trois problèmes doivent être résolus. Les deux premiers sont des problèmes qu’on peut associer à la reconnaissance : détermination de la probabilité d’une séquence observée étant donné un HMM (c’est le problème de l’évaluation); et, étant donné un modèle HMM et une séquence d’observations, déterminer quelle séquence d’états cachés dans le modèle est la plus probable (c’est le problème de décodage). Le troisième problème est la génération d’un HMM étant donné une séquence d’observations (c’est le problème d’apprentissage).

Evaluation et l’algorithme de Forward

Ce problème se pose notamment quand nous avons, par exemple, plusieurs HMMs décrivant différents systèmes, et une séquence d’observations. Nous voulons ainsi connaître  quel est le HMM ayant la plus forte probabilité d’avoir généré cette séquence. En d’autres termes, pour un modèle λ = (π, A, B) et une séquence d’observations Y = y1, y2, …, yT, nous avons à calculer la probabilité P(Y|λ). Un calcul de cette probabilité implique un nombre d’opérations de l’ordre de N T . Heureusement, une autre méthode, ayant une complexité inférieure, existe. Cette méthode utilise une variable intermédiaire appelée variable ”avant” ou forward; d’ou le nom de l’algorithme Forward ( ou ”avant”). Algorithme Forward : Cet algorithme est utilisé pour calculer la probabilité d’une séquence d’observation de longueur T : 𝒀 = 𝒚𝟏, 𝒚𝟐, … , 𝒚𝑻 (4.6) avec chaque y est un élément de l’ensemble observable. La variable intermédiaire 𝛼𝑡(𝑖) est définie comme la probabilité de la séquence d’observation partielle 𝒀 𝒕 = 𝒚𝟏, 𝒚𝟐, … , 𝒚𝒕 𝒕 ≤ 𝑻, qui se termine à l’état i. Les probabilités intermédiaires (ou partielles) sont calculées de manière récursive en calculant premièrement ces probabilités pour tous les états à t = 1. 𝛼1 𝑗 = 𝜋 𝑗 . 𝑏𝑗 1 , 𝑝𝑜𝑢𝑟 1 ≤ 𝑗 ≤ 𝑁 (4.7) Ensuite, pour chaque instant, t = 2, …, T, les probabilités partielles sont calculées pour chaque état par la relation récursive suivante : 𝛼𝑡+1 𝑗 = 𝛼𝑡 𝑖 𝑎𝑖𝑗 𝑏𝑗 𝑡 , 𝑝𝑜𝑢𝑟 1 ≤ 𝑗 ≤ 𝑁, 1 ≤ 𝑡 ≤ 𝑇 − 1 𝑁 𝑖=1 (4.8) Avec cette relation, nous pouvons alors calculer la probabilité intermédiaire à l’instant T pour chaque état j, 𝛼𝑇 𝑗 . Et finalement, la somme de toutes les probabilités partielles à l’instant T fournit la probabilité requise : 𝑝 𝑌 𝜆 = 𝛼𝑇(𝑖) 𝑁 𝑖=1 (4.9) Pour récapituler, chaque probabilité partielle (à l’instant t > 2) est calculée à partir de tous les états précédents. De façon similaire, nous pouvons définir une variable « arrière » ou backward 𝛽𝑡 𝑖 comme la probabilité de la séquence d’observation partielle 𝒚𝒕+𝟏, 𝒚𝒕+𝟐, … , 𝒚𝑻, étant donné que l’état courant est i.