Hidden Markov Model - Les trois questions

Maintenant que nous savons à quoi ressemble un HMM, nous sommes en droit de nous demander ce que nous pouvons en faire.
Il y a trois questions majeures que nous pouvons poser à un HMM, étant donnée une séquence d'observations :
    - Quelle est la probabilité d'apparition de cette séquence ?
    - Quelle est la séquence d'états la plus probable qui a généré cette séquence ?
    - Comment modifier le HMM pour que la probabilité d'apparition de cette séquence soit maximale ?

Probabilité d'une séquence d'observations

Nous avons un HMM dont nous connaissons tous les paramètres (nombre d'états, nombre d'observations, probabilités de départ, probabilités de transition et probabilités d'émission) ainsi qu'une séquence d'observations de longeur T. Nous nous demandons alors quelle est la probabilité d'apparition de cette séquence. Dans le cas d'un HMM "entraîné" à reconnaître "quelque chose" (la langue d'un texte, par exemple), c'est cette question que nous nous posons pour déterminer si "autre chose" est du même type ou non.

Cette question a une réponse unique. En effet, la probabilité de voir apparaître la séquence d'observations se trouve en additionnant les probabilités de la voir apparaître pour chacune des séquences d'états possibles.

De façon naïve, nous pourrions écrire un algorithme qui parcourt toutes les séquences d'états possibles en calculant la probabilité d'apparition de la séquence d'observations, puis additionnerait tous les résultats pour trouver la réponse à la question. Le problème de cet algorithme est qu'il y a NT séquences d'états candidates (N états, T longeur de la séquence d'observations), ce qui donnerait une complexité en O(NT). Autant dire incalculable car T est souvent très grand.

Heureusement, le forward-algorithm permet de trouver la solution avec une bien meilleure complexité : O(N2T). On en verra un exemple commenté dans la partie exemples d'utilisation.

Séquence d'états la plus probable

Nous avons un HMM dont nous connaissons tous les paramètres (nombre d'états, nombre d'observations, probabilités de départ, probabilités de transition et probabilités d'émission) ainsi qu'une séquence d'observations de longeur T. Nous nous demandons alors quelle était la séquence d'états génératrice. C'est la question à laquelle nous souhaitons répondre dans le cadre de la reconnaissance vocale.

Cette question n'a pas qu'une seule réponse. Si le HMM étudié ne présente aucune probabilité d'émission nulle, n'importe quelle séquence d'états de longeur T peut générer n'importe quelle séquence d'observations de longeur T. Même avec certaines probabilités d'émission nulles, il reste plusieurs réponses à cette question.

Puisqu'il y a plusieurs séquences d'états possibles pour une séquence d'observations donnée, nous ne pouvons pas dire avec certitude laquelle a généré nos observations. En revanche, puisque nous connaissons les paramètres du HMM, nous pouvons dire quelle est la plus probable.

De façon naïve, nous pourrions encore écrire un algorithme qui parcourt toutes les séquences d'états possibles en calculant la probabilité d'appartion de la séquence d'observations, trouvant ainsi la séquence d'états qui a le plus probablement généré notre séquence d'observations. Le problème est à nouveau la complexité : il y a NT séquences d'états candidates (N états, T longeur de la séquence d'observations) et donc une complexité en O(NT).

L'algorithme de Viterbi permet de trouver la solution avec une bien meilleure complexité : O(N2T). On en verra un exemple commenté dans la partie exemples d'utilisation.

Maximiser la probabilité d'une séquence d'observations

Nous avons un HMM, dont nous connaissons le nombre d'états N et le nombre d'observations M, et une séquence d'observations de longeur T. Nous nous demandons alors quelles sont les matrices S, A et B (respectivement probabilités de départs, de transitions et d'émissions) qui maximisent la probabilité d'apparition de notre séquence d'observations. C'est à cette question qu'il nous faut répondre lorsque nous souhaitons entraîner un HMM à reconnaître "quelque chose".

Cette question a une réponse unique. Il existe bien 3 matrices S, A et B pour lesquelles la probabilité d'apparition de notre séquence d'observations est maximale. Malheureusement, si la résolution mathématique de ce problème est déjà difficile, il n'existe aucun algorithme permettant de le résoudre (à ce jour du moins). Il existe, par contre, un algorithme permettant d'approcher la solution.

Cet algorithme, appelé algorithme de Baum-Welch, présente cependant le défaut de ne pas toujours converger vers la même solution, voire même de ne pas converger du tout sous certaines conditions. Ces problèmes surviennent surtout losque nous n'avons aucune idée des probabilités du HMM que nous recherchons (pas même approximative) et que nous commençons donc avec un HMM quasiment équiprobable (ce qui signifie que les probabilités de départ et de transition sont toutes égales à ~1/N et les probabilités d'émission à ~1/M). "Quasiment" équiprobable justement pour minimiser le risque d'échec de l'algorithme, qui ne converge presque jamais en cas d'équiprobabilité parfaite.

L'idée de l'algorithme est la suivante :
    1) Nous initialisons le HMM avec des probabilités presque équivalantes ou des approximations de ce à quoi nous nous attendons ;
    2) Nous réévaluons le HMM par rapport à la séquence d'observations sur laquelle nous voulons l'entraîner ;
    3) Nous calculons la probabilité d'apparition de la séquence d'observations avec le "nouveau" HMM ;
    4) Si la probabilité d'apparition augmente, nous recommencons en 2.
L'algorithme tourne donc jusqu'à ce que la réévaluation fasse baisser la probabilité d'apparition.

La complexité de cet algorithme est O(N2T), mais attention, il est beaucoup plus long à exécuter que les deux premiers. En effet, il y a d'une part la présence de la boucle (entre 100 et 500 itérations en général lors de mes tests sur une séquence de 50 000 observations) et d'autre part, à l'intérieur même de la boucle on a déjà une constante multiplicative de 4. En résumé, il y a un facteur de l'ordre de 1 000 qui est masqué dans cette complexité.

Nous verrons un exemple commenté de cet algorithme dans la partie exemples d'utilisation.

Aller à la Modélisation