Algorithme de Baum-Welch

Calculs préliminaires

Avant de décrire le processus d'estimation, nous avons besoin de savoir cela:

• le nombre prévu de transitions d'un état ${\displaystyle i}$ en ${\displaystyle O}$ et
• le nombre prévu de transitions d'un état i à l'état j dans ${\displaystyle O}$

Définissons d'abord ${\displaystyle \xi _{t}{(i,j)}}$ la probabilité d'être dans l'état ${\displaystyle i}$ à l'instant ${\displaystyle t}$ et dans l'état ${\displaystyle j}$ à l'instant ${\displaystyle t+1}$, étant donné une observation ${\displaystyle O}$ et le modèle ${\displaystyle \mu }$.

${\displaystyle \xi _{t}{(i,j)}=P(q_{t}=i,q_{t+1}=j|O,\mu )}$

${\displaystyle \xi _{t}{(i,j)}={\frac {P(q_{t}=i,q_{t+1}=j,O|\mu )}{P(O|\mu )}}={\frac {\alpha _{t}{(i)}a_{ij}b_{j}(o_{t+1})\beta _{t+1}(j)}{P(O|\mu )}}}$

${\displaystyle \xi _{t}{(i,j)}={\frac {\alpha _{t}{(i)}a_{ij}b_{j}(o_{t+1})\beta _{t+1}(j)}{\displaystyle \sum _{k=1}^{N}\displaystyle \sum _{l=1}^{N}{\alpha _{t}(k)a_{kl}b_{l}(o_{t+1})\beta _{t+1}(l)}}}}$

avec ${\displaystyle a_{ij}}$ la probabilité de transition de l'état ${\displaystyle i}$ vers l'état ${\displaystyle j}$, et ${\displaystyle b_{j}(o)}$ la probabilité d'observer ${\displaystyle o}$ lorsque l'on est dans l'état ${\displaystyle j}$, et où les valeurs ${\displaystyle \alpha _{t}(i)}$ et ${\displaystyle \beta _{t}(i)}$ définies ci après peuvent se calculer simplement avec l'algorithme forward-backward.

${\displaystyle \alpha _{t}(i)=P(o_{1},o_{2},\ldots ,o_{t},q_{t}=i|\mu )}$

${\displaystyle \beta _{t}(i)=P(o_{t+1},o_{t+2},\ldots ,o_{T}|q_{t}=i,\mu )}$

La figure montre une vue schématique partielle des éléments nécessaires pour le calcul de ${\displaystyle \xi (i,j)}$.

Nous définissons aussi ${\displaystyle \gamma _{t}(i)}$ la probabilité d'être dans l'état ${\displaystyle i}$ à l'instant ${\displaystyle t}$,

${\displaystyle \gamma _{t}(i)=\displaystyle \sum _{j=1}^{N}{\xi _{t}(i,j)}}$

En sommant ${\displaystyle \gamma _{t}(i)}$ sur le temps, on obtient:

• le nombre prévu de transitions d'un état ${\displaystyle i}$ dans l'observation ${\displaystyle O}$

${\displaystyle \displaystyle \sum _{t=1}^{T-1}{\gamma _{t}(i)}}$

Et en faisant la même chose avec ${\displaystyle \xi _{t}(i,j)}$, nous obtenons:

• le nombre prévu de transitions d'un état ${\displaystyle i}$ à l'état ${\displaystyle j}$ dans l'observation ${\displaystyle O}$

${\displaystyle \displaystyle \sum _{t=1}^{T-1}{\xi _{t}(i,j)}}$

Réestimation

Le fonctionnement de la procédure itérative est le suivant :

1. Partir d'un modèle initial qui peut être choisi aléatoirement.
2. Réaliser le calcul des transitions et symboles émis qui sont les plus probables selon le modèle initial.
3. Construire un nouveau modèle dans lequel la probabilité des transitions et des observations déterminée à l'étape précédente augmente. Pour la séquence des observables en question, le modèle aura désormais une probabilité plus élevée que le modèle précédent.

Ce processus de formation est répétée plusieurs fois jusqu'à ce qu'il n'y ait plus d'amélioration entre le modèle recalculé et l'ancien.

Probabilité d'être dans l'état ${\displaystyle i}$ à l'instant ${\displaystyle t=1}$ :

${\displaystyle {\overline {\pi }}_{i}=\gamma _{1}(i)\qquad (1\leq i\leq N)}$

Re-estimation des probabilités de transition. Le numérateur correspond au nombre attendu de transitions de ${\displaystyle i}$ à ${\displaystyle j}$, et le dénominateur représente le nombre attendu de transitions de ${\displaystyle i}$ :

${\displaystyle {\overline {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}{\xi _{t}(i,j)}}{\displaystyle \sum _{t=1}^{T-1}{\gamma _{t}(i)}}}\qquad (1\leq i,j\leq N)}$

Re-estimation des probabilités d'émission. Le numérateur correspond au nombre de fois où l'on est passé dans l'état ${\displaystyle j}$ et que l'on a observé ${\displaystyle o_{k}}$, et le dénominateur représente le nombre de fois où l'on est passé dans l'état ${\displaystyle j}$ :

${\displaystyle {\overline {b}}_{j}(k)={\frac {\displaystyle \sum _{t=1:o_{t}=v_{k}}^{T}{\gamma _{t}(j)}}{\displaystyle \sum _{t=1}^{T}{\gamma _{t}(j)}}}\qquad (1\leq j\leq N,1\leq k\leq M)}$

Cas de plusieurs séquences d'observations

L'algorithme décrit précédemment utilise une unique séquence d'observations ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$. Cependant, dans de nombreuses situations, plusieurs séquences ${\displaystyle O^{(1)},O^{(2)},...,O^{(n)}}$ sont observées. Il faut alors prendre en compte toutes ces séquences dans la réestimation des paramètres. En notant ${\displaystyle \xi _{t}^{(k)}(i,j)}$ et ${\displaystyle \gamma _{t}^{(k)}(i)}$ les probabilités calculées pour chaque séquence ${\displaystyle O^{(k)}}$, les formules de réestimation deviennent :

${\displaystyle {\overline {\pi }}_{i}={\frac {1}{n}}\sum \limits _{k=1}^{n}\gamma _{1}^{(k)}(i)\qquad (1\leq i\leq N)}$

${\displaystyle {\overline {a}}_{ij}={\frac {\sum \limits _{k=1}^{n}\sum \limits _{t=1}^{T_{k}-1}\xi _{t}^{(k)}(i,j)}{\sum \limits _{k=1}^{n}\sum \limits _{t=1}^{T_{k}-1}\gamma _{t}^{(k)}(i)}}\qquad (1\leq i,j\leq N)}$

${\displaystyle {\overline {b}}_{j}(l)={\frac {\sum \limits _{k=1}^{n}\sum \limits _{t=1:o_{t}=v_{l}}^{T_{k}}\gamma _{t}^{(k)}(i)}{\sum \limits _{k=1}^{n}\sum \limits _{t=1}^{T_{k}}\gamma _{t}^{(k)}(i)}}\qquad (1\leq j\leq N,1\leq l\leq M)}$