Algorithme Forward modifié
Bonjour à tous !
Je bosse sur un modèle de Markov caché. Typiquement, je dois implémenter l'algorithme Forward qui permet d'évaluer la probabilité d'avoir une certaine observation sachant un modèle.
Cet algo n'est pas particulièrement compliqué à la base. Or, je dois en utiliser une version modifiée.
Mes observations sont des chaînes de caractères. Elles sont altérées vis-à-vis mon modèle abstrait (c'est normal, sinon je ferais ne pas un HMM ;) ). Ainsi, je dois prendre pour acquis que certaines observations que ne peux pas faire existent.
J'ai trouvé un papier qui explique comment gérer cette situation. Mais... je n'y comprends pas grand chose... Je saisi bien le principe derrière l'algorithme dynamique Forward, mais cette version me perd.
Pour y jeter un coup d'oeil, un pdf disponible ici : http://www.google.fr/url?sa=t&rct=j&...iivfTg&cad=rja
Le principe est qu'on constitue le vecteur des états cachés avec environ 3 états par caractère du modèle abstrait : insertion, correspondance, effacement.
Traditionnellement, on itère sur les caractères observés et sur le nombre d'états cachés pour sommer notre résultat partiel, comme dans le code suivant :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| void Forward(HMM *phmm, int T, int *O, double **alpha, double *pprob)
{
int i, j; /* state indices */
int t; /* time index */
double sum; /* partial sum */
/* 1. Initialization */
for (i = 1; i <= phmm->N; i++)
alpha[1][i] = phmm->pi[i]* phmm->B[i][O[1]];
/* 2. Induction */
for (t = 1; t < T; t++) {
for (j = 1; j <= phmm->N; j++) {
sum = 0.0;
for (i = 1; i <= phmm->N; i++)
sum += alpha[t][i]* (phmm->A[i][j]);
alpha[t+1][j] = sum*(phmm->B[j][O[t+1]]);
}
}
/* 3. Termination */
*pprob = 0.0;
for (i = 1; i <= phmm->N; i++)
*pprob += alpha[T][i];
} |
où le modèle de Markov (phmm dans le code précédent) contient A := la matrice stochastique des transitions, B:= la matrice stochastique des émission et pi:= le vecteur de probabilité initial.
Dans la version spécialisée, je ne me figure pas bien la différence, même simplement la forme de la variable alpha...
Mon problème à proprement parler, c'est que je n'arrive pas à interpréter l'algo présenté dans le pdf (ci-dessus). J'ai de la difficulté à associer la version générale avec cette version spécialisée.
J'étais sur le point de simplement abandonner ce volet de mon projet, mais je me suis dit que peut-être un gros cerveau sur les forums de Developpez.com serait en mesure de me donner un indice ;). J'aimerais vraiment intégrer un modèle de Markov dans mon filtreur de spam, mais je commence à désespérer de l'implémenter à temps...
Je suis preneur de tout coup de main !
