Discussion :

[Abstrus]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[davcha]

Dans ton autre message, tu dis :

tout HMM a pour hypothèse que les paramètres sont connus (ce qui n'est pas mon cas, je dois donc les estimer

Il faudrait que tu précises un peu ce que tu entends par là.

Je peux comprendre que tu ne peux pas faire de HMM, parce que tu fais de l'apprentissage online, or les HMM c'est offline. D'où mes précédents liens à propos du Q-learning et variants.

Ou bien... Tu ne fais pas d'apprentissage online, mais tu ne sais pas sur quelles données baser ton HMM. Dans ce cas, ce qu'il te faut, c'est une liste de mots que tu souhaite interdire dont la fréquence d'apparition correspond à la fréquence d'apparition réelle du spam. Tu te sers de cette liste pour construire ton HMM.
Si ce second discours correspond davantage à ce que tu cherches, tu peux jeter un oeil du côté de l'algorithme de Viterbi également.

Enfin, petite note supplémentaire... L'introduction de ton papier avec la façon dont le spam est habituellement détecté... Je n'ai fait que survoler, mais ça semble assez loin de ce qui se fait. Ils ne parlent pas d'apprentissage dans les graphes, ça m'étonne.

[Abstrus]

Merci davcha !

Les paramêtres connus, c'est A (matrice stochastique des transitions), B (matrice stochastique des émissions) et pi, vecteur initial. On dit \lambda = (A,B,\pi), lambda est l'hypothèse à avoir. L'algorithme Baum-Welch sert à l'estimer.

Pour l'heure, je manque trop de temps. Je vais par contre terminer ce filtre à partir de la semaine prochaine.

Dans ce cas, ce qu'il te faut, c'est une liste de mots que tu souhaite interdire dont la fréquence d'apparition correspond à la fréquence d'apparition réelle du spam. Tu te sers de cette liste pour construire ton HMM.

Cette liste, je l'ai. Ce modèle de Markov sert en fait à diminuer la DB d'un filtre bayésien naïf en associant plusieurs «orthographes» à un mot «parfait» ou plutôt «théorique» et «abstrait»

Si ce second discours correspond davantage à ce que tu cherches, tu peux jeter un oeil du côté de l'algorithme de Viterbi également.

Viterbi fait en effet parti des algo que j'ai regardé, mais comme je dis, je dois remettre ce travail. Je préfère remettre un filtre bayésien naïf super propre et complet qu'un filtre non naïf mais partiel. Par contre, dépassé les contraintes de mes cours, je veux utiliser ce logiciel. J'ai plusieurs bonnes idées pour l'améliorer et je compte bien me rendre au bout (si bout il y a ).

Enfin, petite note supplémentaire... L'introduction de ton papier avec la façon dont le spam est habituellement détecté... Je n'ai fait que survoler, mais ça semble assez loin de ce qui se fait. Ils ne parlent pas d'apprentissage dans les graphes, ça m'étonne.

Ce papier est... pourri. Bon j'exagère, mais entre vous et moi, il sous entend des calculs (passés en douce d'ailleurs) en temps factoriels, sans parler de certaines coquilles de langue .

En somme, je vais lire ces papier que tu m'as envoyé et voir ce que je peux en tirer. Si ce n'est pas un HMM que j'ai besoin, alors ce sera autre chose ! Si tu veux, on garde contact à ce sujet. Je veux vraiment arriver à pousser le filtre plus loin, et j'ai beaucoup plus de temps l'été

Je te remercie encore, et on s'en reparle.

[davcha]

Autre chose, si tu souhaites "juste" reconnaître des mots bruités figurant dans une liste de mots, tu peux peut-être regarder du côté des automates de mots.