MODÉLISATION DU COMPORTEMENT DES AGENTS ET DE LA DYNAMIQUE
RÉSIDENTIELLE

Considérations théoriques relatives aux réseaux bayésiens

A la fois outil mathématique de calcul de probabilités conditionnelles et modèle de représentation graphique de connaissances, les réseaux d’inférence bayésiens ou plus simplement réseaux bayésiens doivent leurs noms aux travaux de Thomas Bayes au XVIIIème siècle sur la théorie des probabilités. Ils sont actuellement le résultat des recherches effectuées dans les années 80 par J. Pearl [Pearl, 1986a, 1986b, 1987, 1988] à UCLA (University of California, Los Angeles) et une équipe de recherche danoise de l’université d’Alborg. Encore du domaine de la recherche dans les années 90, ils connaissent maintenant de plus en plus d’applications concrètes par exemple le contrôle de véhicules autonomes ou le diagnostic médical ou encore la fouille de données, la reproduction du raisonnement et du langage, etc. Les réseaux bayésiens sont des modèles qui permettent de décrire des relations de probabilités conditionnelles entre des faits. Cette représentation repose sur un graphe orienté sans cycle (DAG : directed acyclic graph) dans lequel chaque nœud, c’est-à-dire chaque variable du monde modélisé, possède une table de probabilité conditionnelle et où chaque arc représente une dépendance directe entre les variables reliées. L’ensemble du réseau représente alors la distribution des probabilités jointes de l’ensemble des variables de manière compacte, en s’appuyant sur les relations d’indépendance conditionnelle entre nœud. A ce titre, les réseaux bayésiens conjuguent deux aspects : une partie qualitative modélisée au moyen d’un graphe et une partie quantitative exprimée par le biais de probabilités (cf. Figure 6.1). Les réseaux bayésiens s’appuient donc sur la théorie des graphes et la théorie des probabilités. Figure 6.1 : Représentation graphique d’un réseau bayésien à n variables variable 1 variable 2 variable 3 variable 5 variable 4 variable … variable n .

Les graphes orientés sans cycle

L’idée de base de la théorie des graphes est de proposer un outil de manipulation et d’étude d’un ensemble fini d’objets sur lequel est défini une relation binaire quelle que soit la sémantique de cette relation. La théorie des graphes se donne donc pour objectif d’étudier de manière abstraite un type de structure d’ensemble qui ne dépend que d’une relation binaire entre ses éléments. Les graphes peuvent être alors interprétés comme une description des relations entre paires d’éléments. Le caractère abstrait d’une telle description permet à cette théorie d’avoir des champs d’applications extrêmement vastes et variés. Par exemple, elle est souvent utilisée pour l’analyse des réseaux de villes en géographie [Mathis, 2003]. L’objectif de cette section n’est pas de présenter la théorie des graphes dans son ensemble mais simplement de décrire les diverses notions indispensables à une bonne compréhension du modèle décisionnel des agents que nous allons développer.

Notion de graphe

Un graphe est un ensemble de couples d’éléments vérifiant une relation donnée. Cet ensemble peut être fini ou non. Mais en l’occurrence nous nous intéressons uniquement aux ensembles finis car le nombre de variables que nous avons identifiées dans le chapitre précédent pour caractériser les agents résidentiels est fini. Soit V = {v1, v2, …… vn} un ensemble fini non vide. Un graphe G sur V est défini par la donnée du couple G = (V, E) où ܧ ؿ ሼሺݑ, ݒ| ݑ, ݒ  א ܸ ݁ݐ ݑ ് ݒ. V est alors nommé l’ensemble des nœuds de G. E peut être donc considéré, par extension, comme étant la description de la relation entre chaque paire de nœuds. L’écriture u ≠ v interdit l’existence d’une relation réflexive. En effet, certaines définitions acceptent (u, u) comme couple dans E ; ce qui n’est pas notre cas parce qu’aucune variable ne sera en relation avec elle-même. Les distinctions fondamentales entre les divers types de graphes dépendent de la nature exacte des éléments de E c’est-à-dire la nature des relations entre chaque paire de nœuds.

Notion d’arc

La notion d’orientation est très importante lorsqu’on utilise des modèles abstraits comme les graphes. Lorsque nous considérons par exemple l’ensemble des villes françaises reliées par autoroute, la relation entre chaque paire de villes est clairement symétrique (double sens). En revanche, dans le cas d’un automate, ce n’est pas parce que celui-ci peut passer d’un état A à un état B qu’il pourra passer de B à A (les transitions possibles entre A et B peuvent donc être à sens unique). Dans ce cas la relation est qualifiée d’arc et dans le cas inverse, elle est qualifiée d’arête. Soit un graphe G = (V, E). Pour tout élément (u, v) de E, Comme défini, un arc n’apparaît qu’une seule fois dans E pour chaque paire de nœuds (u, v) de V. Les arcs et les arêtes permettent de définir et de manipuler de façon homogène les graphes orientés, et non orientés. Les graphes orientés constituent le socle des modèles bayésiens et de ce fait, sont le type de graphe qui nous intéresse.

Les graphes orientés et quelques notions connexes

Un graphe G = (V, E) est un graphe orienté noté ܩ Ԧsi et seulement si tous les éléments . Ainsi .arcs des sont E de Pour tout arc (u→v) appartenant à E, u est l’origine de l’arc et v son extrémité. On dit que u est un parent (ou prédécesseur) de v et v, l’enfant (ou successeur) de u. Nous noterons Γv l’ensemble des parents de v et Ξu l’ensemble des enfants de u.