Tests et résultats

Pour tester l'efficacité de l'algorithme Baum-Welch, nous avons procédé à de multiples tests. Deux exemples simples vont être présentés dans cette dernière partie.

Exemple 1 :

Soit un modèle Markovien à trois états cachés 1,2 et 3, et deux symboles observables P (pile) et F (face). Ce modèle représente un lancé d'une pièce de monnaie (pile ou face), possedant 3 états cachés.
Matrice de transition des états cachés , A = [$a_{ij}$ ] :
$[\indent 0.3\indent0.5\indent 0.2\indent]$
$[\indent 0\indent 0.3\indent 0.7\indent]$
$[\indent 0\indent 0\indent \indent 1\indent ]$

Matrice de probabilités de génération des symboles B = [$b_j(k)$ ] :
$[\indent 1\indent 0\indent ]$
$[\indent 0.5\indent 0.5]$
$[\indent 0\indent 1\indent ]$

Matrice O :
$[\indent 0\indent 0\indent 1\indent 1\indent ]$

Matrice $\Pi$ = [$\Pi_i$ ] :
$[\indent 0.6\indent 0.4\indent 0\indent ]$

P(O/$\lambda$ ) = 0.223200

-----------------------------------
Calcul de l'évolution des paramètres du modèle sur 1 itération
-----------------------------------

Calcul des matrices Alpha et Beta :

A l'aide des formules suivantes, nous somme en mesure de calculer les $\alpha_t(i)$ . $\alpha_1(i) = \pi_ib_i(o_1)$
$\alpha_{t+1}(j) = \left(\sum_{i=1}^N \alpha_t(i)a_{ij}\right)b_j(o_{t+1})$
AN.
$\alpha_1(1)=\pi_1 b_1(o_1)=0.6\times1.0=0.6$
$\alpha_1(2)=\pi_2 b_2(o_1)=0.4\times0.5=0.2$
$\alpha_1(3)=\pi_3 b_3(o_1)=0.0\times0.0=0.0$
$\alpha_2(1)=\alpha_1(1)a_{11}b_1(o_2) + \alpha_1(2)a_{21}b_1(o_2) + \alpha_1(3... ... 0.6\times0.3\times1.0.0 + 0.2\times0.0\times1.0 + 0.0\times0.0\times1.0 = 0.18$
...
Nous obtenons alors les valeurs suivantes :
$\alpha_1(1)= 0.6$
$\alpha_1(2)= 0.2$
$\alpha_1(3)= 0.0$
$\alpha_2(1)= 0.18$
$\alpha_2(2)= 0.18$
$\alpha_2(3)= 0.0$
$\alpha_3(1)= 0.0$
$\alpha_3(2)= 0.072$
$\alpha_3(3)= 0.162$
$\alpha_4(1)= 0.0$
$\alpha_4(2)= 0.0108$
$\alpha_4(3)= 0.2124$

La procédure de calcul des $\beta_t(i)$ est identique, avec :
$\beta_T(i) = 1$ et $\beta_{t}(i) = \sum_{j=1}^N a_{ij}\beta_{t+1}(j)b_j(o_{t+1})$
AN.
$\beta_4(1)=1.0$
$\beta_4(2)=1.0$
$\beta_4(3)=1.0$
$\beta_3(1)= a_{11}\beta_4(1)b_1(o_4) + a_{12}\beta_4(2)b_2(o_4) + a_{13}\beta_... ... = 0.3\times1.0\times0.0 + 0.5\times1.0\times0.5 + 0.2\times1.0\times1.0 = 0.45$
...
Nous obtenons alors les valeurs suivantes :
$\beta_1(1)= 0.330625$
$\beta_1(2)= 0.124125$
$\beta_1(3)= 0.0$
$\beta_2(1)= 0.4125$
$\beta_2(2)= 0.8275$
$\beta_2(3)= 1.0$
$\beta_3(1)= 0.45$
$\beta_3(2)= 0.85$
$\beta_3(3)= 1.0$
$\beta_4(1)=1.0$
$\beta_4(2)=1.0$
$\beta_4(3)=1.0$

Ré-estimation des matrices A, B et $\Pi$ :

Ré-estimation de A :

$\bar{a}_{11} = \frac{\sum_{t=1}^{T-1 = 4-1 = 3} \xi_t(i=1,j=1)}{\sum_{t=1}^{T-... ...1})\beta_{t+1}(1)}{\sum_{j=1}^{N=3}\alpha_t(1)a_{1j}b_j(o_{t+1})\beta_{t+1}(j)}$

$\bar{a}_{11} = (0.600000\times0.300000\times1.000000\times0.412500 + 0.180000\... ...\times1.000000 + 0.000000\times0.200000\times1.000000\times1.000000) = 0.272352$

Le procédé est alors répété pour toutes les valeurs $\bar{a}_{ij}$ . Nous obtenons les résultats suivants :
$\bar{a}_{11} = 0.272352$
$\bar{a}_{12} = 0.595598$
$\bar{a}_{13} = 0.132050$
$\bar{a}_{21} = 0.000000$
$\bar{a}_{22} = 0.249282$
$\bar{a}_{23} = 0.750718$
$\bar{a}_{31} = 0.000000$
$\bar{a}_{32} = 0.000000$
$\bar{a}_{33} = 1.000000$

Ré-estimation de $\Pi$ :

$\bar{\pi}_1=\frac{\alpha_1(1)\beta_1(1)}{P(O\vert\lambda)}=\frac{0.600000\times0.330625}{0.223200}=0.888777$

$\bar{\pi}_2=\frac{\alpha_1(2)\beta_1(2)}{P(O\vert\lambda)}=\frac{0.200000\times0.124125}{0.223200}=0.111223$

$\bar{\pi}_3=\frac{\alpha_1(3)\beta_1(3)}{P(O\vert\lambda)}=\frac{0.000000\times0.000000}{0.223200}=0.000000$


Ré-estimation de B :

$\bar{b}_1(1) = \frac{\sum_{t=1\cap o_t = v_1}^{T} \gamma_t(1)}{\sum_{t=1}^{T} ... ...1\cap o_t =v_1}^T \alpha_t(1) \beta_t(1)}{\sum_{t=1}^T \alpha_t(1) \beta_t(1)}$

$\bar{b}_1(1) = (0.600000\times0.330625 + 0.180000\times0.412500)/(0.600000\tim... ...000\times0.412500 + 0.000000\times0.450000 + 0.000000\times1.000000) = 1.000000$

Le procédé est alors répété pour toutes les valeurs $\bar{b}_i(j)$ . Nous obtenons les résultats suivants :
$\bar{b}_1(1) = 1.000000$
$\bar{b}_2(1) = 0.707049$
$\bar{b}_3(1) = 0.000000$
$\bar{b}_1(2) = 0.000000$
$\bar{b}_2(2) = 0.292951$
$\bar{b}_3(2) = 1.000000$

-----------------------------------
Résultats de l'algorithme de Baum-Welch sur 3 itérations
-----------------------------------

Itération numéro1:

MatriceA:
$[\indent 0.272352\indent 0.595598\indent 0.132050\indent ]$
$[\indent 0.000000\indent 0.249282\indent 0.750718\indent ]$
$[\indent 0.000000\indent 0.000000\indent 1.000000\indent ]$

MatriceB:
$[\indent 1.000000\indent 0.000000\indent ]$
$[\indent 0.707049\indent 0.292951\indent ]$
$[\indent 0.000000\indent 1.000000\indent ]$

MatriceO:
$[\indent 0\indent 0\indent 1\indent 1\indent ]$

Matrice$\Pi$ :
$[\indent 0.888777\indent 0.111223\indent 0.000000\indent ]$

MatriceAlpha:
$[\indent 0.600000\indent 0.200000\indent 0.000000\indent ]$
$[\indent 0.180000\indent 0.180000\indent 0.000000\indent ]$
$[\indent 0.000000\indent 0.072000\indent 0.162000\indent ]$
$[\indent 0.000000\indent 0.010800\indent 0.212400\indent ]$

MatriceBeta:
$[\indent 0.330625\indent 0.124125\indent 0.000000\indent ]$
$[\indent 0.412500\indent 0.827500\indent 1.000000\indent ]$
$[\indent 0.450000\indent 0.850000\indent 1.000000\indent ]$
$[\indent 1.000000\indent 1.000000\indent 1.000000\indent ]$

Matrice$\Gamma$ :
$[\indent 0.888777\indent 0.111223\indent 0.000000\indent ]$
$[\indent 0.332661\indent 0.667339\indent 0.000000\indent ]$
$[\indent 0.000000\indent 0.274194\indent 0.725806\indent ]$
$[\indent 0.000000\indent 0.048387\indent 0.951613\indent ]$

P(O/$\lambda$ )=0.381487

-----------------------------------

Itération numéro2:

MatriceA:
$[\indent 0.152756\indent 0.774101\indent 0.073144\indent ]$
$[\indent 0.000000\indent 0.103466\indent 0.896534\indent ]$
$[\indent 0.000000\indent 0.000000\indent 1.000000\indent ]$

MatriceB:
$[\indent 1.000000\indent 0.000000\indent ]$
$[\indent 0.837402\indent 0.162598\indent ]$
$[\indent 0.000000\indent 1.000000\indent ]$

MatriceO:
$[\indent 0\indent 0\indent 1\indent 1\indent ]$

Matrice$\Pi$ :
$[\indent 0.970538\indent 0.029462\indent 0.000000\indent ]$

MatriceAlpha:
$[\indent 0.888777\indent 0.078640\indent 0.000000\indent ]$
$[\indent 0.242060\indent 0.388140\indent 0.000000\indent ]$
$[\indent 0.000000\indent 0.070580\indent 0.323348\indent ]$
$[\indent 0.000000\indent 0.005154\indent 0.376333\indent ]$

MatriceBeta:
$[\indent 0.416582\indent 0.142920\indent 0.000000\indent ]$
$[\indent 0.275778\indent 0.810874\indent 1.000000\indent ]$
$[\indent 0.306531\indent 0.823745\indent 1.000000\indent ]$
$[\indent 1.000000\indent 1.000000\indent 1.000000\indent ]$

Matrice$\Gamma$ :
$[\indent 0.970538\indent 0.029462\indent 0.000000\indent ]$
$[\indent 0.174986\indent 0.825014\indent 0.000000\indent ]$
$[\indent 0.000000\indent 0.152403\indent 0.847597\indent ]$
$[\indent 0.000000\indent 0.013511\indent 0.986489\indent ]$

P(O/$\lambda$ )=0.603545

-----------------------------------

Itérationnuméro3:

MatriceA:
$[\indent 0.044302\indent 0.938471\indent 0.017227\indent ]$
$[\indent 0.000000\indent 0.020091\indent 0.979909\indent ]$
$[\indent 0.000000\indent 0.000000\indent 1.000000\indent ]$

MatriceB:
$[\indent 1.000000\indent 0.000000\indent ]$
$[\indent 0.954970\indent 0.045030\indent ]$
$[\indent 0.000000\indent 1.000000\indent ]$

MatriceO:
$[\indent 0\indent 0\indent 1\indent 1\indent ]$

Matrice$\Pi$ :
$[\indent 0.996770\indent 0.003230\indent 0.000000\indent ]$

MatriceAlpha:

$[\indent 0.970538\indent 0.024671\indent 0.000000\indent ]$
$[\indent 0.148255\indent 0.631273\indent 0.000000\indent ]$
$[\indent 0.000000\indent 0.029281\indent 0.576801\indent ]$
$[\indent 0.000000\indent 0.000493\indent 0.603052\indent ]$

MatriceBeta:
$[\indent 0.619858\indent 0.079009\indent 0.000000\indent ]$
$[\indent 0.188106\indent 0.911900\indent 1.000000\indent ]$
$[\indent 0.199011\indent 0.913358\indent 1.000000\indent ]$
$[\indent 1.000000\indent 1.000000\indent 1.000000\indent ]$

Matrice$\Gamma$ :
$[\indent 0.996770\indent 0.003230\indent 0.000000\indent ]$
$[\indent 0.046206\indent 0.953794\indent 0.000000\indent ]$
$[\indent 0.000000\indent 0.044311\indent 0.955689\indent ]$
$[\indent 0.000000\indent 0.000816\indent 0.999184\indent ]$

P(O/$\lambda$ )=0.878811