Les modèles de Markov


Introduction
Les chaînes de Markov
Les modèles de décision Markoviens
Les modèles de Markov cachés
Les modèles de décision Markoviens partiellement observables
Diagramme des modèles Markoviens
Chaînes de Markov Processus de décision Markoviens Modèles de Markov cachés Modèles de décision Markoviens partiellement observables

Introduction

Les modèles de Markov sont des automates probabilistes à états finis. Je vais m'intéresser plus spécifiquement aux modèles discrets. Tous ces modèles se basent sur l'hypothèse de Markov, qui peut se résumer à « Le futur ne dépend que de l'état présent. »

Cette hypothèse implique que l'état du modèle doit contenir suffisamment d'informations pour permettre une prédiction parfaite du comportement du système. Dans la majorité des situations réelles, cette hypothèse n'est pas verifiée, car il faudrait pour cela prendre en compte un trop grand nombre de paramètres. Cependant, si l'on se restreint à un sous-ensemble de propriétés, on peut souvent construire un modèle pour lequel la propriété Markovienne est presque respectée.

Ainsi, par exemple, si l'on s'intéresse au modèle d'une voiture roulant sur une route, le nombre de paramètres est gigantesque. Cependant, si l'on restreint ce modèle à sa simple position sur la chaussée, il est possible de réduire fortement ce nombre. Ainsi, on peut considérer que la trajectoire de la voiture ne dépend que de la position du volant, et de son accelération. A ce moment, un modèle constitué par la position de la voiture, sa vitesse, son volant et son accelération serait Markovien... Sauf s'il existe des portions verglacées de route.


Les chaînes de Markov

Le modèle Markovien de base correspond à un simple graphe d'états, doté d'une fonction de transition probabiliste. A chaque pas de temps, le modèle subit une transition qui va potentiellement modifier son état. Cette transition permet donc au système modélisé d'évoluer, selon une loi connue par avance. Néanmoins, cette loi de transition est probabiliste. En effet, l'évolution du système peut être incertaine, ou simplement mal connue. Cette fonction probabiliste permet donc d'exprimer simplement la loi d'évolution du modèle, sous la forme d'une matrice de probabilités. Cela ouvre donc la porte à un très grand nombre d'utilisations où l'évolution d'un système n'est connue qu'à travers des statistiques.

Notations :

Finalité du modèle :
 Prédire les caractèristiques du système étudié : si on le laisse évoluer librement à partir d'une situation donnée, aura-t'on :


Les modèles de décision Markoviens

Les modèles de décision Markoviens (MDP) sont une extension des chaînes de Markov. La grande différence entre ces deux modèles tient à la notion de récompense. En effet, même si la notion d'action ne fait pas partie intégrante des chaînes de Markov, elle peut y être ajoutée sans peine. La notion de récompense, par contre, modifie radicalement la finalité du modèle en introduisant la notion de but.

Les MDP contiennent donc, en plus de l'ensemble d'états, un ensemble fini d'actions qui permettent d'influencer l'évolution du modèle. Or, dans les chaînes de Markov, l'évolution du modèle est régie par la fonction de transition A . L'évolution des MDP sera donc naturellement décrite par une fonction A* qui indiquera la probabilité d'atteindre un état du modèle, en partant d'un état donné, en connaissant l'action en cours. Cette fonction est habituellement représentée par un ensemble de matrices, chacune décrivant l'évolution du modèle pour une action donnée.

La fonction de récompense, quant à elle, permet d'indiquer au modèle quel objectif il doit atteindre. Cette fonction peut donc prendre plusieurs formes.

Types de récompenses possibles :

  1. Si le système se trouve dans un état donné.
  2. Si le système choisit une action précise dans un état donné.
  3. Si le système arrive dans un état donné avec une action précise.
  4. Si le système passe d'un état donné à un autre avec une action précise.

La dernière forme de récompense est évidement la plus expressive, et permet d'exprimer exactement les trois précédentes. Cependant, elle requiert un grand nombre de paramètres, puisqu'elle doit donner une valeur à chaque action pour chaque couple d'états. C'est pourquoi, en général, la forme retenue est la seconde. Elle offre en effet une bonne expressivité, tout en ne nécessitant qu'un faible nombre de paramètres.

Notations :

L'objectif du système est donc de choisir une action, connaissant l'état actuel, de façon à maximiser la récompense attendue. Pour y parvenir, il faut donc calculer une politique, c'est à dire une fonction qui associe à chaque état l'action optimale. Ce calcul peut être mené en particulier par deux grands algorithmes : Value Iteration et Policy Iteration.

Les modèles de Markov cachés

Les modèles de Markov cachés (HMM) sont une autre évolution possible des chaînes de Markov. Ces nouveaux modèles se basent cette fois sur deux processus stochastiques dépendants l'un de l'autre. En effet, l'état du système n'est plus directement observable; il est caché par un processus d'observation.

Notations :

Par exemple, prenons une personne qui a à sa disposition deux dés à six faces non pipés. A chaque instant, il peut lancer un dé (avec un résultat de 1 à 6) ou deux dés (avec un résultat de 2 à 12). Nous avons donc deux processus aléatoires : le choix du lancer, et le lancer lui-même. On peut donc modéliser le premier processus comme une chaîne de Markov à 2 états. Dans le premier, un dé est lancé, alors que dans le second, les deux dés sont utilisés.

Sachant le lancer choisi, il est donc facile de prédire le résultat attendu. Si, maintenant, le lanceur se trouve derrière un rideau, et annonce simplement le résultat, comment peut-on déterminer s'il a lancé 1 ou 2 dés ? Il s'agit très exactement de la finalité des modèles partiellement observables: A partir d'une séquence d'observations, quelle est la séquence d'états correspondante ?

Ce problème peut être résolu grâce à la loi de Bayes :

P(A.B)=P(A|B).P(B)=P(B|A).P(A)

On peut donc exprimer la probabilité de chaque état, connaissant l'observation courante et l'état précédant :


Calcul de P(S|O)

Revenons au problème du lanceur de dés, et ajoutons qu'après chaque lancer, il change le nombre de dés lancés avec 25% de probabilité. Nous avons donc un système à deux états : dans le premier, le joueur lance un dé; dans le second, il en lance 2. Depuis chaque état, la transition mène à l'autre état dans 25% des cas, et reste sur place le restant du temps. De plus, la matrice d'observation sera la suivante :

Valeur 1 2 3 4 5 6 7 8 9 10 11 12
1 Dé 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0 0 0
2 Dés 0 1/36 2/36 3/36 4/36 5/36 6/36 5/36 4/36 3/36 2/36 1/36

L'application de l'algorithme Forward à cet exemple donne donc simplement la probabilité que le système soit dans chacun des deux états aprè chaque observation. Il faut néanmoins ajouter l'hypothèse d'initialisation : au premier coup, on ignore s'il va lancer 1 ou 2 dés. On peut donc être dans chacun des deux états avec 50% de probabilité. Voici une simulation du modèle :

Votre navigateur ne supporte pas Java 1.4! Accès au code source

Les modèles de décision Markoviens partiellement observables

Les processus de décision Markoviens sont issus de la fusion des MDP et des HMM. Ils incluent donc simultanément la notion d'observation et la notion d'action. L'objectif de ces modèles est donc de choisir un plan d'action permettant d'atteindre un but donné à partir d'un état de croyance quelconque portant sur l'espace d'états.

La planification proprement dite est la phase la plus intéressante, puisqu'elle n'est pas couverte par les modèles précédents. Cependant, sa complexité est trè importante, ce qui limite son application à des modèles très simples. Néanmoins, il existe des algorithmes de planification approchée qui permettent d'obtenir des plans sous-optimaux, mais avec une complexité admissible.

L'algorithme de planification exact le plus utilisé est Witness , lui-même dérivé de l'algorithme Value Iteration. Il construit un ensemble de politiques à valeur linéaire par morceaux. Chaque politique est un arbre où chaque branchement correspond à une observation possible, et où chaque noeud correspond à une action.

L'algorithme de planification approchée le plus simple est le QMDP. Il consiste à prendre une simple planification de MDP, et à pondérer la valeur de chaque action par la probabilité d'appartenance à chaque état du modèle. L'action ayant la valeur la plus importante est donc celle qui a la valeur espérée la plus grande.


Page Créée par Laurent JEANPIERRE.
Dernière modification le jeudi 9 juin 2005