Séance 5 — L’IA qui doute

Raisonner sous incertitude : probabilités, théorème de Bayes, réseaux bayésiens

Séance 5 d’Introduction à l’intelligence artificielle : raisonner sous incertitude : probabilités, Bayes, réseaux bayésiens.

Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Navigation conceptuelle

Amont. Les environnements partiellement observables et stochastiques (Séance 1) ; la logique, qui ne connaît que le vrai et le faux, appliquée au Monde de Bouki (Séance 2) ; la recherche d’une suite d’actions dans un monde connu avec certitude (Séance 3).

Aval. Une croyance ne dit pas quoi faire : la Séance 6 passe à la décision sous incertitude (utilité, processus de décision markoviens). Le cours de Machine Learning apprendra les probabilités à partir des données (Naive Bayes, vraisemblance, modèles génératifs).

Objectifs

Construire une distribution jointe, marginaliser une variable, calculer une probabilité conditionnelle.
Appliquer le théorème de Bayes en table : prior, vraisemblance, produit, évidence, posterior.
Enchaîner les mises à jour séquentielles, et mesurer l’effet d’une preuve contradictoire.
Construire un réseau bayésien, écrire sa factorisation et compter ses paramètres.
Décider d’une indépendance conditionnelle par la d-séparation, sans calcul.
Calculer une probabilité par énumération et par élimination de variables, et comparer leurs coûts.
Relier le classifieur Naive Bayes au diagnostic, et au cours de Machine Learning.

Pourquoi un agent doit douter

Le diagnostic de Fatou

Août, en pleine saison des pluies : Fatou, 28 ans, consulte le Dr Ndoye au centre de santé de la Médina, à Dakar, pour une fièvre. Le médecin sait par expérience que trois causes dominent à cette période : le paludisme, la grippe, et un ensemble d’autres causes (insolation, infection, typhoïde). Il dispose de trois observations possibles : les frissons de Fatou, qu’il constate à l’examen clinique ; sa température, qu’il mesure ; et le résultat d’un test de diagnostic rapide du paludisme (TDR), qu’il peut demander. Toute la séance suit ce cas : comment passer de « probablement le paludisme » à une conviction assez forte pour traiter, et comment réviser ce jugement à chaque observation ?

Les outils des séances précédentes ne répondent pas à cette question. La logique de la Séance 2 voudrait une règle comme \(\text{fièvre}\land\text{frissons}\Rightarrow\text{paludisme}\). Mais les mêmes symptômes accompagnent la grippe ou la typhoïde : la même prémisse mènerait à des conclusions contradictoires, et une proposition ne peut pas être à la fois vraie et fausse. La recherche de la Séance 3 suppose un état initial connu, des actions au résultat certain et des coûts connus d’avance ; or le médecin ne voit pas la maladie, et un test peut donner un faux positif. A* est optimal sur une carte exacte ; ici, la « destination » elle-même est cachée.

Les trois sources d’incertitude

Les sources de l’incertitude d’un agent

Observabilité partielle. L’agent ne perçoit pas tout l’état du monde : le médecin voit les symptômes, pas la maladie ; le joueur de poker voit ses cartes, pas celles de l’adversaire.
Non-déterminisme. Le même état et la même action ne produisent pas toujours le même résultat : deux patients atteints de la même maladie ne présentent pas les mêmes symptômes, un test se trompe parfois.
Ignorance. Certains facteurs sont inconnus, ou trop nombreux pour être tous modélisés : le terrain génétique de Fatou, les piqûres de moustique de la nuit précédente.

Ce sont les environnements « partiellement observables » et « stochastiques » du tableau des environnements de la Séance 1, celui où le diagnostic médical avait été rangé parmi les cas les plus exigeants. L’ignorance est la source la plus irréductible : même un dossier médical complet laisse des facteurs dans l’ombre.

Du vrai et du faux au degré de croyance

L’idée centrale de la séance est de remplacer les deux valeurs de la logique, vrai et faux, par un nombre de l’intervalle \([0,1]\) : le degré de croyance. Quand le Dr Ndoye dit « je pense que c’est le paludisme », il n’énonce pas un fait déduit par modus ponens ; il exprime une croyance du type « au vu de ce que je sais maintenant, environ 70 % », que la prochaine observation pourra renforcer ou affaiblir.

	logique (Séance 2)	probabilités
valeurs	vrai, faux	\([0,1]\)
opérateurs	\(\land\), \(\lor\), \(\neg\), \(\Rightarrow\)	\(P(\cdot)\), \(P(\cdot\mid\cdot)\)
raisonnement	modus ponens, résolution	théorème de Bayes
monde supposé	certain, complet	incertain, incomplet
force	correction garantie	incertitude chiffrée
limite	trop rigide pour le réel	aucune certitude absolue

Les probabilités ne remplacent pas la logique : elles l’étendent. Quand toutes les probabilités valent 0 ou 1, on retrouve exactement la logique classique ; la logique est le cas limite d’un monde sans incertitude.

Le langage des probabilités

Variables aléatoires

Pour raisonner sur ce qu’il ne sait pas, l’agent commence par le nommer. Quand le médecin examine Fatou, il réserve mentalement une « case » pour la maladie, dont il ignore encore la valeur.

Variable aléatoire

Une variable aléatoire \(X\) prend ses valeurs dans un ensemble appelé son domaine, \(\mathrm{Dom}(X)\). Elle est booléenne (deux valeurs : les frissons), discrète (un nombre fini de valeurs : la maladie) ou continue (un intervalle réel : la température en degrés). On écrit la variable avec une majuscule et ses valeurs en minuscules : \(M=\text{palu}\).

variable	domaine	rôle	pour le Dr Ndoye
\(M\) (maladie)	{palu, grippe, autre}	cachée	la cause de la fièvre, qu’il ne voit pas
\(Fr\) (frissons)	{vrai, faux}	observée	examen clinique
\(T\) (température)	{très haute, haute}	observée	thermomètre, seuil \(39{,}5\) °C
\(TDR\) (test rapide)	{\(+\), \(-\)}	observée	test sanguin du paludisme

La distinction entre variables cachées et observées est celle de la Séance 1 : un environnement est partiellement observable quand les capteurs de l’agent ne donnent pas accès à l’état complet. Les « capteurs » du Dr Ndoye (ses yeux, le thermomètre, le TDR) lui donnent accès à \(Fr\), \(T\) et \(TDR\), mais pas à \(M\) : la maladie est l’état caché du monde, qu’il faut inférer à partir d’observations indirectes.

Distribution de probabilité et axiomes de Kolmogorov

Les variables nommées, il faut quantifier la croyance en chacune de leurs valeurs. On dispose d’un « budget de croyance » total égal à 1, que l’on répartit entre les valeurs possibles : plus une valeur en reçoit, plus on la croit probable.

Distribution de probabilité

Une distribution de probabilité sur une variable discrète \(X\) est une fonction \(P:\mathrm{Dom}(X)\to[0,1]\) telle que \[\sum_{x\in\mathrm{Dom}(X)}P(X=x)=1.\]

Les registres du centre de santé donnent cette répartition pour la fièvre en août : sur les 500 patients fiévreux vus en août l’année précédente, 200 avaient le paludisme, 175 la grippe et 125 une autre cause, soit \(P(\text{palu})=0{,}40\), \(P(\text{grippe})=0{,}35\), \(P(\text{autre})=0{,}25\), de somme 1. Cette distribution, connue avant d’examiner Fatou, est le prior, la croyance a priori : c’est le point de départ du raisonnement.

Axiomes de Kolmogorov (1933)

Soit \(\Omega\) l’ensemble des résultats possibles ; un événement est une partie de \(\Omega\), par exemple « Fatou a le paludisme ». Pour tout événement \(A\) : (1) \(P(A)\geq0\), une croyance n’est jamais négative ; (2) \(P(\Omega)=1\), quelque chose se produit forcément ; (3) si \(A\cap B=\emptyset\), \(P(A\cup B)=P(A)+P(B)\), les probabilités d’événements incompatibles s’ajoutent.

Toutes les règles de calcul découlent de ces trois axiomes. Les deux plus utiles ici sont l’encadrement \(0\leq P(A)\leq1\), qui signale une erreur dès qu’un calcul sort de l’intervalle, et la règle du complémentaire \(P(\neg A)=1-P(A)\) : la probabilité que Fatou n’ait pas le paludisme vaut \(1-0{,}40=0{,}60\).

Deux lectures d’une probabilité

Que signifie \(P(\text{palu})=0{,}40\) ? La lecture fréquentiste y voit une propriété de la population : sur un grand nombre de patients fiévreux en août à Dakar, 40 % ont le paludisme, et ce nombre se mesure par une fréquence. La lecture bayésienne y voit le degré de croyance du Dr Ndoye étant donné ses connaissances : une propriété de son état de connaissance, et non du monde, révisée quand une information nouvelle arrive.

L’intelligence artificielle adopte la lecture bayésienne pour une raison pratique : elle modélise un agent qui apprend. Chaque frisson, chaque mesure, chaque test met à jour la croyance ; c’est la mise à jour bayésienne, le cœur de la séance. Le cours de Machine Learning retrouvera la même idée dans l’apprentissage bayésien, où l’on met à jour une croyance sur les paramètres d’un modèle, les données jouant le rôle des observations.

Les données du diagnostic en Python

Chaque distribution est un dictionnaire : le prior d’août, puis, pour chaque maladie, la probabilité d’observer des frissons, une température très haute (\(>39{,}5\) °C) et un TDR positif. Ces trois dernières tables ne sont pas des distributions sur la maladie : chacune donne, pour chaque maladie, la probabilité d’un symptôme.

PRIOR = {"palu": 0.40, "grippe": 0.35, "autre": 0.25}    # fievre en aout a Dakar
FR = {"palu": 0.80, "grippe": 0.30, "autre": 0.10}       # P(Fr = vrai | M)
TE = {"palu": 0.70, "grippe": 0.20, "autre": 0.05}       # P(T = tres haute | M)
TDR = {"palu": 0.95, "grippe": 0.10, "autre": 0.10}      # P(TDR = + | M)
print(sum(PRIOR.values()))
print(1 - PRIOR["palu"])

La sortie est :

1.0
0.6

La distribution jointe

Le monde réel contient des variables qui s’influencent : la maladie de Fatou rend les frissons plus ou moins probables. Pour décrire cette influence, on considère toutes les combinaisons de valeurs à la fois.

Distribution jointe

La distribution jointe de deux variables \(X\) et \(Y\) donne une probabilité \(P(X=x,Y=y)\) à chaque couple de valeurs ; la somme de toutes les cases vaut 1 : \[\sum_x\sum_y P(X=x,Y=y)=1.\]

Pour la maladie et les frissons, la jointe est un tableau de six cases. Chaque case combine deux informations : 40 % des patients ont le paludisme, et 80 % d’entre eux ont des frissons, donc 32 % des patients ont à la fois le paludisme et des frissons : \(P(\text{palu},\text{oui})=0{,}40\times0{,}80=0{,}320\). Ce tableau contient toute l’information sur la relation entre maladie et frissons : la probabilité du paludisme, celle des frissons, et ce que l’observation des frissons change au diagnostic se lisent dans ses seules cases.

	\(Fr=\) oui	\(Fr=\) non	\(P(M)\)
palu	\(0{,}320\)	\(0{,}080\)	\(0{,}40\)
grippe	\(0{,}105\)	\(0{,}245\)	\(0{,}35\)
autre	\(0{,}025\)	\(0{,}225\)	\(0{,}25\)
total	\(0{,}450\)	\(0{,}550\)	\(1\)

Exemple pas à pas : la jointe, la marge, le zoom

Le programme suivant construit le tableau, puis en tire deux réponses : la probabilité d’avoir des frissons, et la distribution de la maladie sachant que Fatou en a.

jointe = {}
for m in PRIOR:
    jointe[m, "oui"] = PRIOR[m] * FR[m]
    jointe[m, "non"] = PRIOR[m] * (1 - FR[m])
p_fr = 0
for m in PRIOR:
    p_fr = p_fr + jointe[m, "oui"]
post = {}
for m in PRIOR:
    post[m] = jointe[m, "oui"] / p_fr
print(round(p_fr, 3))
print({m: round(p, 3) for m, p in post.items()})

Les lignes 2 à 4 remplissent le tableau ligne par ligne, par la règle du produit : la case \((m,\text{oui})\) vaut \(P(m)\,P(Fr\mid m)\), la case \((m,\text{non})\) vaut \(P(m)\,(1-P(Fr\mid m))\). Les lignes 5 à 7 additionnent la colonne \(Fr=\) oui : c’est la marginalisation de la maladie. Les lignes 8 à 10 divisent chaque case de cette colonne par son total : c’est le conditionnement, un zoom sur les patients qui ont des frissons. La table suivante donne ce que calcule chaque étape.

Étape	Ligne	\(m\)	Ce qui est calculé
1	3–4	palu	\(P(palu,\text{oui})=0{,}40\times0{,}80=0{,}320\), \(P(palu,\text{non})=0{,}080\)
2	3–4	grippe	\(P(grippe,\text{oui})=0{,}35\times0{,}30=0{,}105\), \(P(grippe,\text{non})=0{,}245\)
3	3–4	autre	\(P(autre,\text{oui})=0{,}25\times0{,}10=0{,}025\), \(P(autre,\text{non})=0{,}225\)
4	7	palu	`p_fr` \(=0{,}320\)
5	7	grippe	`p_fr` \(=0{,}425\)
6	7	autre	`p_fr` \(=0{,}450\)
7	10	palu	\(P(palu\mid\text{oui})=0{,}320/0{,}450=0{,}711\)
8	10	grippe	\(P(grippe\mid\text{oui})=0{,}105/0{,}450=0{,}233\)
9	10	autre	\(P(autre\mid\text{oui})=0{,}025/0{,}450=0{,}056\)

Les trois premières étapes reproduisent le tableau de la jointe. La somme partielle de la ligne 7 passe par \(0{,}320\) puis \(0{,}425\) et atteint \(0{,}450\) : 45 % des patients fiévreux ont des frissons. La division de la ligne 10 redonne une distribution, de somme 1. La figure de gauche montre l’étape où la marginale est complète ; celle de droite, la fin de l’exécution.

La sortie est :

0.45
{'palu': 0.711, 'grippe': 0.233, 'autre': 0.056}

La marginalisation

Marginalisation

Pour connaître la distribution de \(X\) sans se soucier de \(Y\), on somme sur les valeurs de \(Y\) : \[P(X=x)=\sum_{y\in\mathrm{Dom}(Y)}P(X=x,Y=y).\]

On somme une ligne du tableau pour obtenir la distribution de la variable en ligne, une colonne pour celle de la variable en colonne ; le résultat s’écrit dans la marge du tableau, d’où le nom. Sommer la ligne du paludisme, \(0{,}320+0{,}080=0{,}40\), redonne le prior : qu’on regarde les frissons ou non, la proportion de paludéens ne change pas. Sommer la colonne des frissons, \(0{,}320+0{,}105+0{,}025=0{,}45\), donne la probabilité d’avoir des frissons, toutes causes confondues. Marginaliser, c’est répondre à une question qui ignore une variable ; l’inférence dans les réseaux bayésiens répétera cette opération à grande échelle.

La probabilité conditionnelle

La probabilité conditionnelle répond à la question que se pose tout agent devant une observation : qu’est-ce que cela change ?

Probabilité conditionnelle

\[P(X=x\mid Y=y)=\frac{P(X=x,Y=y)}{P(Y=y)},\qquad\text{défini si }P(Y=y)>0.\] Le symbole « \(\mid\) » se lit « sachant ».

L’image est celle d’un zoom. Sur 100 patients fiévreux, 45 ont des frissons ; observer que Fatou en a, c’est ne plus regarder que ces 45. Parmi eux, 32 ont le paludisme, 10,5 la grippe et 2,5 une autre cause, d’où \(P(\text{palu}\mid Fr)=32/45\approx0{,}711\), \(P(\text{grippe}\mid Fr)=10{,}5/45\approx0{,}233\) et \(P(\text{autre}\mid Fr)=2{,}5/45\approx0{,}056\). Ces trois nombres somment à 1 : le conditionnement redonne une distribution.

L’observation a redistribué la croyance : le paludisme passe de 0,40 à 0,711, la grippe de 0,35 à 0,233, les autres causes de 0,25 à 0,056. Elle a poussé la croyance vers l’hypothèse la plus compatible avec ce qui est observé.

La règle du produit et l’indépendance

En multipliant la définition de la probabilité conditionnelle par \(P(Y)\), on obtient la règle du produit, celle qui a rempli le tableau de la jointe.

Règle du produit

\[P(X,Y)=P(X\mid Y)\,P(Y)=P(Y\mid X)\,P(X).\] La probabilité que \(X\) et \(Y\) se produisent ensemble est la probabilité de l’un, multipliée par celle de l’autre sachant le premier. L’égalité des deux écritures donnera le théorème de Bayes.

Indépendance

\(X\) et \(Y\) sont indépendantes, \(X\perp Y\), si \(P(X,Y)=P(X)\,P(Y)\), ou de façon équivalente \(P(X\mid Y)=P(X)\) : connaître \(Y\) ne change rien à la croyance sur \(X\).

La maladie et les frissons ne sont pas indépendants : \(P(\text{palu}\mid Fr)=0{,}711\neq0{,}40\). C’est précisément parce qu’ils sont dépendants que les frissons servent au diagnostic ; un symptôme indépendant de la maladie n’apprendrait rien.

Le théorème de Bayes

De l’effet à la cause

Le zoom a donné \(P(\text{palu}\mid Fr)\) à partir de la jointe. Mais la jointe est rarement disponible ; ce que l’on connaît d’habitude, c’est la direction cause \(\to\) effet. \(P(Fr\mid\text{palu})=0{,}80\) se mesure en suivant des patients dont le paludisme est confirmé et en comptant ceux qui frissonnent. La direction effet \(\to\) cause, \(P(\text{palu}\mid Fr)\), est celle dont le médecin a besoin : remonter de l’observation à la cause cachée est un problème d’inférence. Le théorème de Bayes est exactement la formule qui passe de la première direction à la seconde.

Ne pas confondre \(P(A\mid B)\) et \(P(B\mid A)\)

« 80 % des paludéens ont des frissons » n’est pas « 80 % des patients qui ont des frissons sont paludéens » : ici, \(0{,}80\) contre \(0{,}711\). De même, « 90 % des étudiants de l’UCAD parlent wolof » n’est pas « 90 % des locuteurs du wolof sont étudiants à l’UCAD », et « 95 % des malades ont un test positif » n’est pas « 95 % des tests positifs signalent un malade ». La population de ceux qui frissonnent, parlent wolof ou sont positifs est bien plus large que celle des paludéens, des étudiants ou des malades : les deux probabilités n’ont pas le même dénominateur. Cette confusion porte un nom, l’erreur du procureur ; elle a causé de graves erreurs judiciaires.

La dérivation et les quatre termes

La preuve tient en trois lignes et ne demande que la règle du produit. Elle écrit la jointe d’une hypothèse \(H\) et d’une observation \(E\) de deux façons, \(P(H,E)=P(E\mid H)\,P(H)\) et \(P(H,E)=P(H\mid E)\,P(E)\) ; les deux membres de gauche sont égaux, donc \(P(H\mid E)\,P(E)=P(E\mid H)\,P(H)\), et il reste à diviser par \(P(E)\).

Théorème de Bayes (1763)

\[P(H\mid E)=\frac{P(E\mid H)\,P(H)}{P(E)},\qquad P(E)=\sum_h P(E\mid h)\,P(h).\]

Chaque terme a un nom et un rôle. Le prior \(P(H)\) résume tout ce que l’on sait avant l’observation : pour le Dr Ndoye, 0,40, 0,35 et 0,25 ; il encode le contexte (le lieu, la saison, la population des patients fiévreux). La vraisemblance \(P(E\mid H)\) mesure la compatibilité de l’observation avec chaque hypothèse : les frissons sont fréquents avec le paludisme (0,80), rares avec les autres causes (0,10) ; c’est la force de la preuve. L’évidence \(P(E)\) ne dépend pas de l’hypothèse : c’est un facteur de normalisation, calculé par la formule des probabilités totales, moyenne des vraisemblances pondérée par les priors. Le posterior \(P(H\mid E)\), la probabilité a posteriori, est la croyance mise à jour, celle qui guidera la suite (traiter, demander un test). En une phrase : le posterior est proportionnel à la vraisemblance multipliée par le prior.

Exemple pas à pas : Bayes en table

La fonction bayes applique le théorème à toutes les hypothèses à la fois : elle multiplie prior et vraisemblance (lignes 3–4), somme les produits (ligne 5), puis divise chaque produit par cette somme (lignes 7–8).

def bayes(prior, vrais):
    num = {}
    for h in prior:
        num[h] = prior[h] * vrais[h]
    z = sum(num.values())
    post = {}
    for h in num:
        post[h] = num[h] / z
    return post
post = bayes(PRIOR, FR)
print({h: round(p, 3) for h, p in post.items()})

La présentation en table, une ligne par hypothèse, est celle de tous les exercices de la séance : les deux premières colonnes sont les données, la troisième les produits, la dernière les posteriors ; la ligne du bas donne l’évidence.

\(h\)	prior	\(P(Fr\mid h)\)	produit	posterior
palu	\(0{,}40\)	\(0{,}80\)	\(0{,}320\)	\(\mathbf{0{,}711}\)
grippe	\(0{,}35\)	\(0{,}30\)	\(0{,}105\)	\(\mathbf{0{,}233}\)
autre	\(0{,}25\)	\(0{,}10\)	\(0{,}025\)	\(\mathbf{0{,}056}\)
somme	\(1\)		\(z=0{,}450\)	\(1\)

Les produits \(0{,}320\), \(0{,}105\) et \(0{,}025\) sont les cases de la colonne des frissons dans la jointe : le théorème de Bayes calcule la même chose que le zoom, sans écrire le tableau entier. La somme \(z=0{,}450\) est \(P(Fr)\). La figure de gauche montre le tour où l’évidence est calculée, celle de droite la fin de l’exécution.

La sortie est :

{'palu': 0.711, 'grippe': 0.233, 'autre': 0.056}

Le rapport de vraisemblance

Le paludisme gagne pour deux raisons qui se multiplient. Son prior était déjà le plus élevé (\(0{,}40>0{,}35>0{,}25\)) ; et les frissons sont bien plus fréquents avec lui qu’avec les autres causes : l’observation est discriminante. La quantité qui mesure cette discrimination entre deux hypothèses est le rapport de vraisemblance : \[\mathrm{LR}(\text{palu}/\text{grippe})=\frac{P(Fr\mid\text{palu})}{P(Fr\mid\text{grippe})}=\frac{0{,}80}{0{,}30}=\frac83\approx2{,}67.\] Les frissons sont 2,67 fois plus probables sous l’hypothèse du paludisme que sous celle de la grippe. Le rapport des posteriors vaut le rapport des priors multiplié par ce LR : \(\frac{0{,}711}{0{,}233}=\frac{0{,}40}{0{,}35}\times\frac83\).

Même preuve, autre contexte

Le Dr Dupont exerce à Paris, en janvier. Un patient se présente avec de la fièvre et des frissons. Les vraisemblances sont les mêmes qu’à Dakar : la biologie du paludisme ne change pas avec la géographie. Seul le prior diffère : le paludisme y est rare, \(P(\text{palu})=0{,}001\), contre \(0{,}700\) pour la grippe et \(0{,}299\) pour les autres causes.

PARIS = {"palu": 0.001, "grippe": 0.700, "autre": 0.299}
post = bayes(PARIS, FR)
print({h: round(p, 3) for h, p in post.items()})

La sortie est :

{'palu': 0.003, 'grippe': 0.872, 'autre': 0.124}

\(h\)	prior	\(P(Fr\mid h)\)	produit	posterior
palu	\(0{,}001\)	\(0{,}80\)	\(0{,}0008\)	\(\mathbf{0{,}003}\)
grippe	\(0{,}700\)	\(0{,}30\)	\(0{,}2100\)	\(\mathbf{0{,}872}\)
autre	\(0{,}299\)	\(0{,}10\)	\(0{,}0299\)	\(\mathbf{0{,}124}\)
somme	\(1\)		\(z=0{,}2407\)	\(1\)

L’évidence vaut \(P(Fr)=0{,}2407\), et le posterior du paludisme \(0{,}0008/0{,}2407\approx0{,}003\). La même observation et les mêmes vraisemblances, avec un prior différent, mènent à une conclusion opposée : 0,711 à Dakar en août, 0,003 à Paris en janvier.

Le prior est le contexte

Le théorème formalise ce qu’un médecin expérimenté sait d’instinct : un symptôme n’a pas le même sens selon le lieu et la saison. Dans le vocabulaire de la Séance 1, le prior encode la connaissance que l’agent a de son environnement. En apprentissage supervisé, ce contexte sera appris sur les données d’entraînement.

Bayes sous forme de cotes

La cote d’une hypothèse est le rapport de sa probabilité à celle de son contraire : \(O(H)=P(H)/P(\neg H)\). Pour le paludisme, \(O=0{,}40/0{,}60=2/3\), « 2 contre 3 ». En écrivant le théorème pour \(H\) et pour \(\neg H\) et en divisant, l’évidence disparaît : \[\underbrace{\frac{P(H\mid E)}{P(\neg H\mid E)}}_{\text{cote après}}=\underbrace{\frac{P(E\mid H)}{P(E\mid\neg H)}}_{\text{rapport de vraisemblance}}\times\underbrace{\frac{P(H)}{P(\neg H)}}_{\text{cote avant}}.\] Ici \(P(Fr\mid\neg\text{palu})=(0{,}105+0{,}025)/0{,}60=13/60\), d’où \(\mathrm{LR}=0{,}80/(13/60)=48/13\approx3{,}69\) et une cote après observation de \(\frac23\times\frac{48}{13}=\frac{32}{13}\approx2{,}46\), soit \(P(\text{palu}\mid Fr)=32/45\). Un LR supérieur à 1 renforce l’hypothèse, inférieur à 1 l’affaiblit, égal à 1 laisse la croyance inchangée ; cette forme est très employée en médecine, parce qu’elle sépare la force du test (le LR) du contexte (la cote avant).

Quand le théorème de Bayes échoue

Le calcul est exact dès que le prior et les vraisemblances sont justes, mais il n’est que cela. Un prior faux fausse tout : une hypothèse jugée impossible (\(P=0\)) le reste après n’importe quelle preuve. Des vraisemblances estimées sur une autre population faussent aussi le posterior. Et avec de nombreuses observations liées entre elles, la jointe devient impossible à écrire : c’est le problème que les réseaux bayésiens résolvent.

Accumuler les preuves

La mise à jour séquentielle

Un agent reçoit rarement une seule observation : le Dr Ndoye mesure ensuite la température, puis demande un TDR. Le cadre bayésien s’applique alors de façon itérative : le posterior obtenu après la première observation devient le prior de la seconde.

Mise à jour séquentielle

Partir du prior \(P(H)\). (2) Observer \(E_1\) ; Bayes donne \(P(H\mid E_1)\). (3) Prendre \(P(H\mid E_1)\) comme nouveau prior. (4) Observer \(E_2\) ; Bayes donne \(P(H\mid E_1,E_2)\). (5) Recommencer pour chaque observation.

Condition : l’indépendance conditionnelle des preuves

Mettre à jour par \(P(E_2\mid H)\) seul suppose \(P(E_1,E_2\mid H)=P(E_1\mid H)\,P(E_2\mid H)\) : une fois la maladie connue, savoir que Fatou frissonne ne change pas la probabilité d’une forte fièvre. L’hypothèse est forte, souvent approchée, mais elle allège considérablement le calcul ; c’est celle du classifieur Naive Bayes de la section 8.

Les vraisemblances des trois observations sont les suivantes : pour une température très haute, \(0{,}70\) avec le paludisme, qui donne souvent de fortes fièvres, \(0{,}20\) avec la grippe, qui dépasse rarement 39,5 °C, et \(0{,}05\) pour les autres causes ; pour le TDR, une sensibilité \(P(TDR^+\mid\text{palu})=0{,}95\) et un taux de faux positifs de \(0{,}10\) en l’absence de paludisme.

Exemple pas à pas : la mise à jour séquentielle

OBS = [("frissons", FR), ("temperature", TE),
       ("TDR+", TDR)]
p = PRIOR
for nom, vrais in OBS:
    p = bayes(p, vrais)
    print(nom, [round(p[h], 3) for h in p])

La boucle applique bayes une fois par observation, en remplaçant à chaque tour la croyance par le posterior. Le tableau donne, pour chaque tour, les produits, l’évidence et le posterior du paludisme, puis l’évolution des trois croyances.

Tour	observation	produits (palu, grippe, autre)	évidence \(z\)	\(P(\text{palu})\)
1	frissons	\(0{,}3200\), \(0{,}1050\), \(0{,}0250\)	\(0{,}4500\)	\(0{,}711\)
2	température	\(0{,}4978\), \(0{,}0467\), \(0{,}0028\)	\(0{,}5472\)	\(0{,}910\)
3	TDR\(^+\)	\(0{,}8642\), \(0{,}0085\), \(0{,}0005\)	\(0{,}8732\)	\(0{,}990\)

\(h\)	prior	\(+Fr\)	\(+T\)	\(+TDR^+\)
palu	\(0{,}400\)	\(0{,}711\)	\(0{,}910\)	\(0{,}990\)
grippe	\(0{,}350\)	\(0{,}233\)	\(0{,}085\)	\(0{,}010\)
autre	\(0{,}250\)	\(0{,}056\)	\(0{,}005\)	\(0{,}001\)

Les frissons portent le paludisme à 0,711 ; la température très haute, 3,5 fois plus probable qu’avec la grippe (\(0{,}70\) contre \(0{,}20\)), à 0,910 ; le TDR positif à 0,990. Chaque preuve concordante renforce le paludisme et affaiblit les autres causes : la grippe passe de 0,35 à 0,010. La figure montre la fin de l’exécution : la table complète et les trois courbes de croyance.

La sortie est :

frissons [0.711, 0.233, 0.056]
temperature [0.91, 0.085, 0.005]
TDR+ [0.99, 0.01, 0.001]

La preuve contradictoire

Le raisonnement bayésien est symétrique : une preuve peut renforcer une hypothèse, elle peut aussi l’affaiblir. Après les frissons et la température, \(P(\text{palu})=0{,}910\) ; le TDR revient négatif. Les vraisemblances sont les compléments : \(P(TDR^-\mid\text{palu})=0{,}05\), le taux de faux négatifs, et \(P(TDR^-\mid\neg\text{palu})=0{,}90\).

NEG = {h: 1 - p for h, p in TDR.items()}   # P(TDR = - | M)
avant = bayes(bayes(PRIOR, FR), TE)
apres = bayes(avant, NEG)
print(round(avant["palu"], 3), round(apres["palu"], 3))
autre_ordre = bayes(bayes(bayes(PRIOR, TDR), TE), FR)
print(round(autre_ordre["palu"], 3))

La sortie est :

0.91 0.359
0.99

\(h\)	prior	\(P(TDR^-\mid h)\)	produit	posterior
palu	\(0{,}910\)	\(0{,}05\)	\(0{,}0455\)	\(\mathbf{0{,}359}\)
grippe	\(0{,}085\)	\(0{,}90\)	\(0{,}0768\)	\(\mathbf{0{,}605}\)
autre	\(0{,}005\)	\(0{,}90\)	\(0{,}0046\)	\(\mathbf{0{,}036}\)
somme	\(1\)		\(z=0{,}1268\)	\(1\)

Le paludisme tombe de 0,910 à 0,359 : une preuve contraire a un effet puissant. Mais il ne tombe pas à zéro, puisque le test manque 5 % des vrais cas ; deux preuves concordantes résistent en partie à une preuve contradictoire. La dernière ligne du programme applique les trois preuves positives dans l’ordre inverse : on retrouve 0,990. Sous l’indépendance conditionnelle, le posterior final est le prior multiplié par le produit des vraisemblances, normalisé ; l’ordre des facteurs d’un produit ne compte pas.

Retour au Monde de Bouki

En Séance 2, Ousmane explorait la grotte de Kédougou, une grille \(4\times4\), avec la logique propositionnelle. Bouki, la hyène des contes, occupe une case ; une odeur signale qu’il est dans une case voisine (nord, sud, est, ouest). Après une odeur en \((2,1)\), la logique concluait \(B_{2,2}\lor B_{3,1}\) : Bouki est en \((2,2)\) ou en \((3,1)\). Avec un seul Bouki et un odorat infaillible, l’odeur en \((1,2)\) désignerait \((2,2)\), seule case voisine des deux cases visitées. Mais un capteur qui se trompe parfois ne permet plus aucune déduction certaine : la logique n’a pas de place pour un capteur qui ment.

Le modèle probabiliste remplace la règle par des probabilités. Le prior est uniforme sur les 15 cases autres que le départ (Bouki n’est jamais au départ). Le capteur est bruité : \(P(\text{odeur}\mid\text{Bouki voisin})=0{,}9\), et une fausse alerte se produit avec \(P(\text{odeur}\mid\text{non voisin})=0{,}05\). Enfin, Ousmane vivant dans une case est une observation : la vraisemblance que Bouki y soit vaut 0.

CASES = [(i, j) for i in range(1, 5) for j in range(1, 5)]
def adjacentes(c):
    i, j = c
    return {(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)}
P = {c: 1 / 15 for c in CASES if c != (1, 1)}   # Bouki n'est pas au depart
print(len(P), round(P[(2, 2)], 3))
print(sorted(adjacentes((2, 1)) & set(P)))

La sortie est :

15 0.067
[(2, 2), (3, 1)]

Exemple pas à pas : le Monde de Bouki probabiliste

def observer(P, ici, odeur):
    for c in P:
        if c == ici:
            v = 0  # Ousmane y est vivant
        elif c in adjacentes(ici):
            v = 0.9 if odeur else 0.1
        else:
            v = 0.05 if odeur else 0.95
        P[c] = P[c] * v
    z = sum(P.values())
    for c in P:
        P[c] = P[c] / z
OBS = [((1, 1), False), ((2, 1), True),
       ((1, 2), True)]
VUES = [(2, 2), (3, 1)]
for ici, odeur in OBS:
    observer(P, ici, odeur)
    print(ici, [round(P[c], 3) for c in VUES])

Chaque appel de observer est une application du théorème de Bayes à 15 hypothèses, « Bouki est en \(c\) » : les lignes 2 à 9 multiplient la croyance de chaque case par la vraisemblance de l’observation, les lignes 10 à 12 normalisent. Le tableau suit six cases au fil des trois observations.

après	\((1,2)\)	\((2,1)\)	\((2,2)\)	\((3,1)\)	\((1,3)\)	\((4,4)\)	\(z\)
prior	\(0{,}067\)	\(0{,}067\)	\(0{,}067\)	\(0{,}067\)	\(0{,}067\)	\(0{,}067\)	–
(1, 1), rien	\(0{,}008\)	\(0{,}008\)	\(0{,}076\)	\(0{,}076\)	\(0{,}076\)	\(0{,}076\)	\(0{,}8367\)
(2, 1), odeur	\(0{,}002\)	\(0{,}000\)	\(0{,}382\)	\(0{,}382\)	\(0{,}021\)	\(0{,}021\)	\(0{,}1783\)
(1, 2), odeur	\(0{,}000\)	\(0{,}000\)	\(0{,}876\)	\(0{,}049\)	\(0{,}049\)	\(0{,}003\)	\(0{,}3927\)

En \((1,1)\), l’absence d’odeur divise par dix environ la croyance des deux voisines, \((1,2)\) et \((2,1)\), qui tombent à 0,008 sans être éliminées : le capteur peut se tromper. En \((2,1)\), Ousmane est vivant (cette case passe à 0) et sent une odeur : \((2,2)\) et \((3,1)\), ses deux voisines encore possibles, montent ensemble à 0,382. La symétrie entre elles n’est brisée qu’en \((1,2)\) : \((2,2)\) en est voisine, \((3,1)\) ne l’est pas. Les figures montrent la grille avant et après la dernière normalisation.

La sortie est :

(1, 1) [0.076, 0.076]
(2, 1) [0.382, 0.382]
(1, 2) [0.876, 0.049]

L’apport des probabilités

Le moment clé est la brisure de symétrie. Avant la dernière observation, \((2,2)\) et \((3,1)\) ont la même croyance. L’odeur en \((1,2)\) est \(0{,}9/0{,}05=18\) fois plus probable si Bouki est en \((2,2)\) que s’il est en \((3,1)\) : ce rapport de vraisemblance porte \((2,2)\) à 0,876 et ramène \((3,1)\) à 0,049.

	logique (Séance 2)	probabilités
conclusion	« \((2,2)\) » si l’odorat est infaillible ; aucune déduction s’il se trompe	« \((2,2)\) avec 0,876 »
capteur bruité	hors du langage	modélisé par la vraisemblance
case visitée	\(\neg B_{i,j}\)	vraisemblance 0 : la même élimination
décision	explorer \((1,3)\) ou \((3,1)\), sûres	éviter \((2,2)\), risque chiffré

La logique est le cas limite des vraisemblances 0 et 1 : une case visitée est éliminée par une vraisemblance nulle comme par \(\neg B_{i,j}\). Les probabilités, elles, gardent une conclusion graduée et exploitable : Ousmane peut éviter \((2,2)\) en connaissant le risque qu’il court ailleurs. Choisir la prochaine case à partir de ces croyances est un problème de décision, celui de la Séance 6.

Les réseaux bayésiens

L’explosion combinatoire de la jointe

Jusqu’ici, le diagnostic tenait en deux ou trois variables. Un diagnostic réel en compte des dizaines. Or la jointe de \(n\) variables booléennes demande \(2^n-1\) nombres (la dernière case se déduit des autres) :

\(n\) variables booléennes	paramètres \(2^n-1\)	ordre de grandeur
5	31	à la main
10	1 023	laborieux
20	1 048 575	un million
30	1 073 741 823	un milliard
100	\(\approx1{,}27\times10^{30}\)	hors de portée

C’est le mur rencontré en Séance 3 : un arbre de recherche de facteur \(b\) a \(b^d\) nœuds au niveau \(d\), la jointe de \(n\) variables a \(2^n\) cases. Là-bas, l’heuristique évitait d’explorer tout l’arbre ; ici, ce sont les indépendances conditionnelles qui évitent d’écrire toute la jointe. À 30 variables, un milliard de nombres à fournir est hors de portée d’un expert, et même des données disponibles.

L’indépendance conditionnelle

Dans le monde réel, la plupart des variables ne s’influencent pas directement. Les frissons de Fatou dépendent de sa maladie ; le résultat du TDR aussi ; mais les frissons ne dépendent pas directement du TDR. Ils sont liés à travers la maladie : si l’on connaissait la maladie avec certitude, apprendre le résultat du test n’apprendrait rien de plus sur les frissons.

Indépendance conditionnelle

\(X\) et \(Y\) sont conditionnellement indépendants sachant \(Z\), \(X\perp Y\mid Z\), si \[P(X,Y\mid Z)=P(X\mid Z)\,P(Y\mid Z).\] Une fois \(Z\) connu, apprendre \(X\) n’apporte rien sur \(Y\) : toute la dépendance entre \(X\) et \(Y\) passe par \(Z\).

Sans connaître la maladie, frissons et TDR sont dépendants : un TDR positif rend les frissons plus probables, puisque les deux pointent vers le paludisme. Sachant que Fatou a le paludisme, ils deviennent indépendants : la maladie « crée » la dépendance apparente entre les symptômes, et chaque symptôme n’est qu’une conséquence de la maladie.

Définition d’un réseau bayésien

Réseau bayésien

Un réseau bayésien est un couple \((\mathcal G,\Theta)\). \(\mathcal G\) est un graphe orienté acyclique : un nœud par variable aléatoire, un arc \(X\to Y\) quand \(X\) influence directement \(Y\) (\(X\) est un parent de \(Y\)). \(\Theta\) donne, pour chaque nœud \(X_i\), sa table de probabilités conditionnelles \(P(X_i\mid\mathrm{Parents}(X_i))\), une distribution de \(X_i\) pour chaque combinaison des valeurs de ses parents.

Factorisation de la jointe

\[P(X_1,\dots,X_n)=\prod_{i=1}^n P\big(X_i\mid\mathrm{Parents}(X_i)\big).\]

Cette factorisation n’est pas la règle du produit générale, qui conditionnerait chaque variable par toutes les précédentes : chaque variable n’y dépend que de ses parents. Elle est exacte quand le graphe décrit correctement les indépendances du domaine. Pour construire un réseau, on choisit les variables, on les ordonne des causes vers les effets, puis on donne à chacune pour parents le plus petit ensemble de variables déjà placées qui la rend indépendante des autres, et sa table. L’ordre causal produit en général un réseau plus compact et plus lisible.

Le réseau de Fatou

Le réseau de la séance complète le diagnostic par deux causes de la maladie : la saison \(S\) (pluies ou sèche) et la moustiquaire imprégnée \(Mq\) (Fatou dort dessous ou non). La maladie \(M\) a ces deux parents ; elle est le parent unique des trois observations.

La saison et la moustiquaire sont supposées indépendantes, chacune de probabilité 0,5. La table \(P(M\mid S,Mq)\) a une ligne par combinaison des parents ; c’est une table illustrative, construite pour le cours et non mesurée. En saison des pluies sans moustiquaire, 64 % des fièvres sont des paludismes ; en saison sèche avec moustiquaire, 2 %. La moustiquaire divise la part du paludisme par 4 en saison des pluies (\(0{,}64\) contre \(0{,}16\)), par 9 en saison sèche (\(0{,}18\) contre \(0{,}02\)) ; dans chaque saison, la grippe et les autres causes gardent le même rapport, qu’il y ait moustiquaire ou non. Les tables des observations sont celles du diagnostic. En saison des pluies, la moyenne des deux lignes de la saison redonne le prior d’août, \(0{,}40\), \(0{,}35\), \(0{,}25\) : le réseau contient le modèle des sections précédentes. En saison sèche, la même moyenne donne \(0{,}10\), \(0{,}45\), \(0{,}45\).

P_S = {"pluies": 0.5, "seche": 0.5}
P_MQ = {"oui": 0.5, "non": 0.5}                  # dort sous moustiquaire
P_M = {("pluies", "oui"): {"palu": 0.16, "grippe": 0.49, "autre": 0.35},
       ("pluies", "non"): {"palu": 0.64, "grippe": 0.21, "autre": 0.15},
       ("seche", "oui"): {"palu": 0.02, "grippe": 0.49, "autre": 0.49},
       ("seche", "non"): {"palu": 0.18, "grippe": 0.41, "autre": 0.41}}
DOM = {"S": ["pluies", "seche"], "Mq": ["oui", "non"],
       "M": ["palu", "grippe", "autre"], "Fr": [True, False],
       "T": [True, False], "TDR": [True, False]}
print({m: (P_M["pluies", "oui"][m] + P_M["pluies", "non"][m]) / 2
       for m in PRIOR})

La sortie est :

{'palu': 0.4, 'grippe': 0.35, 'autre': 0.25}

La jointe factorisée est un produit de six facteurs, un par nœud. Sa somme sur les 96 configurations vaut 1, et une configuration se calcule en un produit : \(P(\text{pluies},\text{sans moustiquaire},\text{palu},Fr,T,TDR^+)=0{,}5\times0{,}5\times0{,}64\times0{,}80\times0{,}70\times0{,}95=0{,}08512\).

def p_oui(table, m, x):                          # P(X = x | M = m), X booleen
    return table[m] if x else 1 - table[m]
def jointe_reseau(s, q, m, fr, te, tdr):
    return (P_S[s] * P_MQ[q] * P_M[s, q][m]
            * p_oui(FR, m, fr) * p_oui(TE, m, te) * p_oui(TDR, m, tdr))
total = 0
for x in itertools.product(*DOM.values()):
    total = total + jointe_reseau(*x)
print(round(total, 12))
print(round(jointe_reseau("pluies", "non", "palu", True, True, True), 5))

La sortie est :

1.0
0.08512

Compter les paramètres

Pour chaque combinaison de ses parents, les probabilités d’un nœud somment à 1 : une valeur se déduit des autres. Un nœud à \(k\) valeurs et \(q\) combinaisons de parents a donc \(q(k-1)\) paramètres libres.

nœud	parents	valeurs \(k\)	combinaisons \(q\)	\(q(k-1)\)
\(S\)	–	2	1	1
\(Mq\)	–	2	1	1
\(M\)	\(S\), \(Mq\)	3	4	8
\(Fr\)	\(M\)	2	3	3
\(T\)	\(M\)	2	3	3
\(TDR\)	\(M\)	2	3	3
total				19

Le réseau demande 19 paramètres, la jointe brute 95. Le gain grandit avec le domaine : une maladie à 3 valeurs et 30 symptômes booléens demandent \(3\times2^{30}-1\approx3{,}2\times10^9\) paramètres pour la jointe, et \(2+30\times3=92\) pour le réseau où chaque symptôme ne dépend que de la maladie.

Structures canoniques et d-séparation

La structure du graphe dit comment l’information circule entre les variables : apprendre la valeur d’un nœud modifie-t-il la croyance sur un autre ? Trois motifs élémentaires répondent à toutes les situations. Pour les vérifier par le calcul, on interroge le réseau en sommant la jointe factorisée, exactement comme on sommait les cases du tableau des frissons :

def prob(requete, obs):
    num = 0
    den = 0
    for x in itertools.product(*DOM.values()):
        a = dict(zip(DOM, x))
        if all(a[v] == obs[v] for v in obs):
            p = jointe_reseau(*x)
            den = den + p
            if all(a[v] == requete[v] for v in requete):
                num = num + p
    return num / den
print(round(prob({"Fr": True}, {"S": "pluies"}), 3))
print(round(prob({"Fr": True}, {"S": "seche"}), 3))

La sortie est :

0.45
0.26

La chaîne

Dans la chaîne \(S\to M\to Fr\), la saison agit sur la maladie, qui agit sur les frissons. Sans rien savoir de la maladie, la saison renseigne sur les frissons : \(P(Fr\mid\text{pluies})=0{,}45\), \(P(Fr\mid\text{sèche})=0{,}26\), puisque la saison des pluies apporte plus de paludisme, qui donne plus de frissons. Sachant \(M=\) palu, en revanche, \(P(Fr)=0{,}8\) quelle que soit la saison : \(S\perp Fr\mid M\). La maladie absorbe toute l’information utile ; le nœud du milieu, observé, bloque le passage.

La cause commune

Dans \(Fr\leftarrow M\to TDR\), la maladie est la cause commune de deux effets. Sans la connaître, les deux effets sont liés : \(P(TDR^+)=0{,}3125\) monte à \(0{,}5789\) quand on sait que Fatou a des frissons. Sachant \(M=\) palu, \(P(TDR^+)=0{,}95\), frissons ou non : \(Fr\perp TDR\mid M\). Comme dans la chaîne, observer le nœud central bloque.

print(round(prob({"Fr": True}, {"S": "seche", "M": "palu"}), 3))
print(round(prob({"TDR": True}, {}), 4))
print(round(prob({"TDR": True}, {"Fr": True}), 4))
print(round(prob({"TDR": True}, {"Fr": True, "M": "palu"}), 3))

La sortie est :

La v-structure et l’explication concurrente

Dans \(S\to M\leftarrow Mq\), deux causes indépendantes agissent sur un même effet. Sans rien observer, elles sont indépendantes : \(P(Mq=\text{oui})=0{,}5\), en saison sèche comme en général. Mais sachant que Fatou a le paludisme, \(P(Mq=\text{oui})\) vaut 0,18, et apprendre en plus que c’est la saison sèche le fait tomber à 0,1 : en saison sèche, le paludisme a besoin d’une autre explication, l’absence de moustiquaire. Connaître l’effet a ouvert une dépendance entre ses causes : c’est l’explication concurrente (explaining away), l’une des formes de raisonnement les plus fines que capturent les réseaux bayésiens.

q = {"Mq": "oui"}
print(round(prob(q, {}), 3), round(prob(q, {"S": "seche"}), 3))
print(round(prob(q, {"M": "palu"}), 3))
print(round(prob(q, {"M": "palu", "S": "seche"}), 3))

La sortie est :

0.5 0.5
0.18
0.1

Dans l’autre sens, sachant le paludisme, la saison des pluies a pour probabilité 0,8 ; apprendre que Fatou dort sous moustiquaire la porte à \(8/9\approx0{,}889\), apprendre qu’elle n’en a pas la ramène à \(32/41\approx0{,}780\). Le paludisme a deux causes, la saison des pluies et l’absence de moustiquaire : quand l’une manque, l’autre devient plus probable ; quand l’une est présente, l’autre est moins nécessaire.

Les trois motifs

motif	sans observer le nœud central	en l’observant
chaîne \(A\to B\to C\)	\(A\), \(C\) dépendants	\(A\perp C\mid B\) : bloque
cause commune \(A\leftarrow B\to C\)	\(A\), \(C\) dépendants	\(A\perp C\mid B\) : bloque
v-structure \(A\to B\leftarrow C\)	\(A\perp C\)	\(A\), \(C\) dépendants : ouvre

La chaîne et la cause commune se comportent de la même façon : observer le nœud central bloque le flux d’information. La v-structure est le cas inverse : observer le nœud central l’ouvre.

Le descendant d’une v-structure

Observer un descendant du nœud central ouvre aussi la v-structure. Observer les frissons renseigne sur la maladie, donc la saison et la moustiquaire deviennent dépendantes sachant \(Fr\).

Le critère de d-séparation

d-séparation (Pearl)

\(X\) et \(Y\) sont d-séparés par un ensemble d’observations \(Z\) si tout chemin non orienté entre \(X\) et \(Y\) est bloqué. Un chemin est bloqué dès qu’il contient une chaîne ou une cause commune dont le nœud central est dans \(Z\), ou une v-structure dont ni le nœud central ni aucun de ses descendants n’est dans \(Z\).

Théorème

Si \(X\) et \(Y\) sont d-séparés par \(Z\), alors \(X\perp Y\mid Z\) pour toutes les tables compatibles avec le graphe. Si un chemin reste actif, \(X\) et \(Y\) sont en général dépendants sachant \(Z\).

La procédure examine chaque chemin entre \(X\) et \(Y\), puis chaque triplet consécutif \((a,b,c)\) de ce chemin : le triplet bloque si \(b\) est un nœud de chaîne ou de cause commune observé, ou un nœud de v-structure non observé sans descendant observé. Un seul triplet bloquant bloque le chemin ; un seul chemin actif maintient la dépendance. Le critère lit les indépendances dans le graphe, sans un seul calcul ; sur le réseau de Fatou, les 240 requêtes possibles (15 paires de variables, 16 ensembles d’observations pour chacune) donnent le même verdict que le calcul par la jointe.

PARENTS = {"S": [], "Mq": [], "M": ["S", "Mq"], "Fr": ["M"], "T": ["M"], "TDR": ["M"]}
VOISINS = {v: set(PARENTS[v]) for v in PARENTS}
for v in PARENTS:
    for p in PARENTS[v]:
        VOISINS[p].add(v)
def descendants(v):
    d = set()
    for w in PARENTS:
        if v in PARENTS[w]:
            d = d | {w} | descendants(w)
    return d
def chemins(x, y, vus):
    if x == y:
        return [[y]]
    res = []
    for v in sorted(VOISINS[x] - set(vus)):
        for c in chemins(v, y, vus + [v]):
            res.append([x] + c)
    return res

Exemple pas à pas : la d-séparation

def bloque(a, b, c, Z):
    if a in PARENTS[b] and c in PARENTS[b]:
        ouvert = b in Z or descendants(b) & Z
        return not ouvert
    return b in Z
def d_separe(x, y, Z):
    for ch in chemins(x, y, [x]):
        actif = True
        for a, b, c in zip(ch, ch[1:], ch[2:]):
            if bloque(a, b, c, Z):
                actif = False
        if actif:
            return False
    return True
REQ = [("S", "Fr", set()), ("S", "Fr", {"M"}),
       ("Fr", "TDR", {"M"}), ("S", "Mq", set()),
       ("S", "Mq", {"M"}), ("S", "Mq", {"Fr"})]
for x, y, Z in REQ:
    print(x, y, sorted(Z), d_separe(x, y, Z))

La fonction bloque applique la règle à un triplet : pour une v-structure, le passage est ouvert si le nœud central ou l’un de ses descendants est observé ; sinon, il est bloqué par l’observation du nœud central. d_separe rend False dès qu’un chemin n’a aucun triplet bloquant. Sur le réseau de Fatou, chaque requête n’a qu’un chemin :

requête	chemin	triplet, motif, état	d-séparés ?
\(S\), \(Fr\), \(Z=\emptyset\)	S–M–Fr	\(M\) (chaîne), laisse passer	non
\(S\), \(Fr\), \(Z=\{M\}\)	S–M–Fr	\(M\) (chaîne), bloque	oui
\(Fr\), \(TDR\), \(Z=\{M\}\)	Fr–M–TDR	\(M\) (cause commune), bloque	oui
\(S\), \(Mq\), \(Z=\emptyset\)	S–M–Mq	\(M\) (v-structure), bloque	oui
\(S\), \(Mq\), \(Z=\{M\}\)	S–M–Mq	\(M\) (v-structure), laisse passer	non
\(S\), \(Mq\), \(Z=\{Fr\}\)	S–M–Mq	\(M\) (v-structure), laisse passer	non

Les deux premières requêtes sont la chaîne, la troisième la cause commune, les trois dernières la v-structure, ouverte par l’observation de \(M\) comme par celle de son descendant \(Fr\). Les figures montrent la v-structure bloquée (rien d’observé) puis ouverte par le descendant.

La sortie est :

S Fr [] False
S Fr ['M'] True
Fr TDR ['M'] True
S Mq [] True
S Mq ['M'] False
S Mq ['Fr'] False

La d-séparation à deux chemins

Sur le réseau de Fatou, chaque requête n’a qu’un chemin ; le critère prend tout son sens quand deux chemins relient les mêmes variables. Le réseau agricole suivant décrit un ménage de paysans : une bonne pluie fait la récolte, avec la qualité du sol, et fait baisser le prix du marché ; la récolte et le prix font le revenu, qui fait la santé du ménage. Entre la récolte et le prix, deux chemins existent : l’un par la pluie (une cause commune), l’autre par le revenu (une v-structure).

Plusieurs chemins

Deux variables sont d-séparées si tous les chemins entre elles sont bloqués ; un seul chemin actif les rend dépendantes.

requête	chemin	triplets	état	d-séparés
Récolte, Prix, sans observation	Récolte–Pluie–Prix	Pluie (cause commune), laisse passer	actif	non
	Récolte–Revenu–Prix	Revenu (v-structure), bloque	bloqué
Récolte, Prix, sachant Pluie	Récolte–Pluie–Prix	Pluie (cause commune), bloque	bloqué	oui
	Récolte–Revenu–Prix	Revenu (v-structure), bloque	bloqué
Récolte, Prix, sachant Pluie et Santé	Récolte–Pluie–Prix	Pluie (cause commune), bloque	bloqué	non
	Récolte–Revenu–Prix	Revenu (v-structure), laisse passer	actif
Pluie, Santé, sachant Revenu	Pluie–Prix–Revenu–Santé	Prix (chaîne), laisse passer ; Revenu (chaîne), bloque	bloqué	oui
	Pluie–Récolte–Revenu–Santé	Récolte (chaîne), laisse passer ; Revenu (chaîne), bloque	bloqué

Sans observation, la récolte et le prix sont dépendants : une récolte abondante signale une bonne pluie, donc un prix bas, même si le chemin par le revenu est bloqué par sa v-structure. Sachant la pluie, les deux chemins sont bloqués : la récolte et le prix sont d-séparés. Observer en plus la santé du ménage, descendant du revenu, rouvre la v-structure : le second chemin redevient actif, et les deux variables redeviennent dépendantes. Enfin, la pluie et la santé sont reliées par deux chaînes qui passent toutes deux par le revenu : l’observer bloque les deux à la fois.

La couverture de Markov

Couverture de Markov

La couverture de Markov d’un nœud est l’ensemble de ses parents, de ses enfants et des autres parents de ses enfants. Sachant sa couverture, un nœud est indépendant de tous les autres nœuds du réseau.

La couverture de \(M\) contient toutes les autres variables : la maladie est au centre du réseau. Celle de \(S\) contient \(M\), son enfant, et \(Mq\), l’autre parent de \(M\) : c’est la v-structure qui y fait entrer la moustiquaire. Sachant \(\{M,Mq\}\), la saison n’apprend plus rien des frissons, de la température ni du test. En Machine Learning, la couverture de Markov de la variable à prédire est l’ensemble minimal des attributs utiles : ajouter des variables hors de la couverture n’améliore pas la prédiction.

Quand la d-séparation échoue

Le critère ne voit que le graphe. Deux variables non d-séparées peuvent être indépendantes par un hasard des nombres ; un graphe faux, un arc oublié, donne des indépendances fausses. Enfin, le nombre de chemins entre deux nœuds peut croître de façon exponentielle avec la taille du graphe : c’est l’énumération des chemins qui coûte, pas la d-séparation elle-même, qu’un parcours du graphe de type Bayes-Ball décide en temps linéaire.

L’inférence dans un réseau bayésien

Le problème d’inférence

Le réseau construit, il reste à l’interroger : sachant certaines observations, que croire des variables cachées ? Une requête comporte une variable \(X\), des observations \(\mathbf e\) et des variables cachées \(\mathbf h\), toutes les autres. Exemple : \(P(M\mid Fr=\text{vrai},TDR=+)\), où \(S\), \(Mq\) et \(T\) sont cachées.

Inférence par énumération

\[P(X\mid\mathbf e)=\alpha\sum_{\mathbf h}\prod_i P\big(X_i\mid\mathrm{Parents}(X_i)\big).\] Pour chaque valeur de \(X\) : fixer les observations, sommer le produit des tables sur toutes les combinaisons de valeurs des variables cachées ; puis normaliser, \(\alpha\) étant l’inverse de la somme.

L’énumération

def enumeration(var, obs):
    caches = [v for v in DOM if v != var and v not in obs]
    scores = {}
    termes = 0
    for val in DOM[var]:
        scores[val] = 0
        for h in itertools.product(*(DOM[v] for v in caches)):
            a = dict(zip(caches, h))
            a.update(obs)
            a[var] = val
            scores[val] = scores[val] + jointe_reseau(*(a[v] for v in DOM))
            termes = termes + 1
    z = sum(scores.values())
    return {v: round(p / z, 3) for v, p in scores.items()}, termes
print(enumeration("M", {"Fr": True, "TDR": True}))
print(enumeration("M", {"Fr": True, "TDR": True, "S": "pluies"}))

La sortie est :

({'palu': 0.925, 'grippe': 0.058, 'autre': 0.017}, 24)
({'palu': 0.959, 'grippe': 0.033, 'autre': 0.008}, 12)

Sans connaître la saison, l’énumération calcule 24 termes : 3 valeurs de \(M\), pour chacune 8 combinaisons de \(S\), \(Mq\) et \(T\). Elle donne \(P(\text{palu}\mid Fr,TDR^+)\approx0{,}925\). Quand la saison des pluies est connue, \(S\) devient une observation et il ne reste que 12 termes :

\(M\)	\(Mq\)	\(T\)	terme
palu	oui	oui	\(0{,}021280\)
palu	oui	non	\(0{,}009120\)
palu	non	oui	\(0{,}085120\)
palu	non	non	\(0{,}036480\)
grippe	oui	oui	\(0{,}000735\)
grippe	oui	non	\(0{,}002940\)

\(M\)	\(Mq\)	\(T\)	terme
grippe	non	oui	\(0{,}000315\)
grippe	non	non	\(0{,}001260\)
autre	oui	oui	\(0{,}000044\)
autre	oui	non	\(0{,}000831\)
autre	non	oui	\(0{,}000019\)
autre	non	non	\(0{,}000356\)

Les quatre termes de chaque maladie somment à \(0{,}152\), \(0{,}00525\) et \(0{,}00125\) ; leur total vaut \(0{,}1585\), et \(0{,}152/0{,}1585\approx0{,}959\). Le facteur \(P(S=\text{pluies})=0{,}5\), commun à tous les termes, disparaît à la normalisation : on retrouve le calcul \(0{,}304/0{,}317\) du diagnostic d’août.

Le coût de l’énumération

L’énumération calcule chaque terme en entier : 24 termes de 6 facteurs, soit 120 multiplications, et \(d^{\,n}\) termes en général pour \(n\) variables cachées de \(d\) valeurs. Surtout, elle refait les mêmes sous-produits : la somme sur \(T\) de \(P(T\mid M)\) vaut 1 pour chaque maladie, et la somme sur \(S\) et \(Mq\) ne dépend pas des observations. Sans la saison, cette somme donne la répartition des maladies sur l’année, \(\tau(\text{palu})=0{,}25\), \(\tau(\text{grippe})=0{,}40\), \(\tau(\text{autre})=0{,}35\), plus « tiède » que le prior d’août ; le diagnostic s’en ressent : 0,925 au lieu de 0,959. Préciser le contexte donne un diagnostic plus net.

L’élimination de variables

L’élimination de variables évite ces répétitions en factorisant avant de développer, comme \(ab+ac=a(b+c)\) : on sort de chaque somme les facteurs qui ne dépendent pas de la variable sommée. \[\sum_{s,q,t}P(s)P(q)P(m\mid s,q)P(t\mid m)=\Big(\sum_s P(s)\sum_q P(q)P(m\mid s,q)\Big)\Big(\sum_t P(t\mid m)\Big).\]

Facteurs et élimination

Un facteur est une table sur quelques variables. Le produit de deux facteurs porte sur l’union de leurs variables ; la somme d’un facteur sur une variable la fait disparaître (marginalisation). Éliminer une variable cachée \(Z\) : multiplier les facteurs qui contiennent \(Z\), sommer le résultat sur \(Z\), remettre le nouveau facteur dans la liste. Quand toutes les variables cachées sont éliminées, multiplier les facteurs restants et normaliser.

def facteur(vs, f):                              # table de f sur ses variables
    return vs, {x: f(*x) for x in itertools.product(*(DOM[v] for v in vs))}
def produit(f, g):
    (vf, tf), (vg, tg) = f, g
    vs = vf + tuple(v for v in vg if v not in vf)
    t = {}
    for x in itertools.product(*(DOM[v] for v in vs)):
        a = dict(zip(vs, x))
        t[x] = tf[tuple(a[v] for v in vf)] * tg[tuple(a[v] for v in vg)]
    return vs, t
def sommer(f, var):                              # marginaliser var
    vs, t = f
    i = vs.index(var)
    s = {}
    for x, p in t.items():
        s[x[:i] + x[i + 1:]] = s.get(x[:i] + x[i + 1:], 0) + p
    return vs[:i] + vs[i + 1:], s
print(sommer(facteur(("T", "M"), lambda t, m: p_oui(TE, m, t)), "T"))

La sortie est :

(('M',), {('palu',): 1.0, ('grippe',): 1.0, ('autre',): 1.0})

Sommer \(P(T\mid M)\) sur \(T\) donne 1 pour chaque maladie : une variable cachée sans descendant observé disparaît sans calcul utile. Les observations sont fixées avant l’élimination : \(P(Fr\mid M)\) est restreint à la valeur \(Fr=\) vrai, \(P(TDR\mid M)\) à \(TDR=+\).

F = [facteur(("S",), lambda s: P_S[s]),
     facteur(("Mq",), lambda q: P_MQ[q]),
     facteur(("M", "S", "Mq"), lambda m, s, q: P_M[s, q][m]),
     facteur(("M",), lambda m: FR[m]),           # Fr = vrai, observe
     facteur(("T", "M"), lambda t, m: p_oui(TE, m, t)),
     facteur(("M",), lambda m: TDR[m])]          # TDR = +, observe
print([vs for vs, t in F], sum(len(t) for vs, t in F))

La sortie est :

[('S',), ('Mq',), ('M', 'S', 'Mq'), ('M',), ('T', 'M'), ('M',)] 28

Exemple pas à pas : l’élimination de variables

def elimination(fs, ordre):
    for var in ordre:
        avec = [f for f in fs if var in f[0]]
        sans = [f for f in fs if var not in f[0]]
        g = avec[0]
        for f in avec[1:]:
            g = produit(g, f)
        fs = sans + [sommer(g, var)]
    g = fs[0]
    for f in fs[1:]:
        g = produit(g, f)
    vs, t = g
    z = sum(t.values())
    return {x[0]: round(t[x] / z, 3) for x in t}
print(elimination(F, ["T", "Mq", "S"]))

La boucle des lignes 2 à 8 élimine \(T\), puis \(Mq\), puis \(S\) ; les lignes 9 à 11 multiplient les facteurs restants, les lignes 12 à 14 normalisent. Le tableau donne, pour chaque tour, les facteurs multipliés, le facteur créé et le nombre de multiplications.

Tour	élimine	facteurs multipliés	facteur créé	valeurs (palu, grippe, autre)	mult.
1	\(T\)	\(P(T\mid M)\)	\(\tau_1(M)\)	\(1{,}000\), \(1{,}000\), \(1{,}000\)	0
2	\(Mq\)	\(P(Mq)\), \(P(M\mid S,Mq)\)	\(\tau_2(M,S)\)	pluies : \(0{,}40\), \(0{,}35\), \(0{,}25\) ; sèche : \(0{,}10\), \(0{,}45\), \(0{,}45\)	12
3	\(S\)	\(P(S)\), \(\tau_2(M,S)\)	\(\tau_3(M)\)	\(0{,}250\), \(0{,}400\), \(0{,}350\)	6
final	–	les 4 facteurs sur \(M\)	\(g(M)\)	\(0{,}1900\), \(0{,}0120\), \(0{,}0035\)	9

Le premier tour ne multiplie rien : \(P(T\mid M)\) est seul à contenir \(T\), et sa somme vaut 1. Le deuxième combine \(P(Mq)\) et \(P(M\mid S,Mq)\) en un facteur de 12 cases, puis somme sur \(Mq\) : le résultat \(\tau_2(M,S)\) est \(P(M\mid S)\), le prior de chaque saison. Le troisième pondère les deux saisons par \(P(S)\) et donne la répartition annuelle \(\tau_3(M)\). Il reste quatre facteurs sur \(M\), dont le produit vaut \(0{,}19\), \(0{,}012\) et \(0{,}0035\) ; normalisé par \(z=0{,}2055\), il donne \(P(\text{palu}\mid Fr,TDR^+)\approx0{,}925\), comme l’énumération, en 27 multiplications au lieu de 120.

La sortie est :

{'palu': 0.925, 'grippe': 0.058, 'autre': 0.017}

Énumération contre élimination

	énumération	élimination de variables
principe	développer chaque terme	factoriser, puis développer
multiplications (requête de Fatou)	120	27
coût en général	\(O(d^{\,n})\)	\(O(n\,d^{\,w+1})\), \(w\) largeur d’arbre
réseau en arbre	exponentiel	linéaire
résultat	exact	exact

Le coût de l’élimination dépend de la taille du plus grand facteur créé, donc de l’ordre d’élimination et de la structure du graphe. La largeur d’arbre \(w\) d’un réseau est la taille du plus grand facteur créé, moins un, pour le meilleur ordre ; elle mesure sa densité structurelle. Sur un réseau en arbre, l’élimination est linéaire ; sur un réseau dense, elle reste exponentielle. Il n’existe d’ailleurs pas d’algorithme exact efficace pour tous les réseaux : Cooper (1990) a montré que l’inférence exacte dans un réseau bayésien quelconque est NP-difficile. C’est le même gain qu’A* face à BFS en Séance 3 : exploiter la structure du problème plutôt que la force brute.

L’inférence approchée par échantillonnage

Pour les très grands réseaux, on renonce au calcul exact : on simule le réseau un grand nombre de fois et l’on estime la probabilité par une fréquence. L’échantillonnage par rejet tire chaque variable dans l’ordre du graphe (la saison et la moustiquaire, puis la maladie sachant ses parents, puis les observations sachant la maladie), ne garde que les patients simulés compatibles avec les observations, et compte parmi eux les paludéens. La température, cachée et sans descendant observé, n’a pas besoin d’être tirée.

def tirer(rng, dist):
    return rng.choices(list(dist), weights=list(dist.values()))[0]
def rejet(n, rng):
    gardes = 0
    palu = 0
    for _ in range(n):
        s = tirer(rng, P_S)
        q = tirer(rng, P_MQ)
        m = tirer(rng, P_M[s, q])
        fr = rng.random() < FR[m]
        tdr = rng.random() < TDR[m]
        if fr and tdr:
            gardes = gardes + 1
            palu = palu + (m == "palu")
    return gardes, round(palu / gardes, 3)
for n in (100, 1000000):
    print(n, rejet(n, random.Random(221)))

La sortie est :

100 (25, 0.96)
1000000 (206483, 0.926)

Sur 100 tirages, 25 seulement sont gardés et l’estimation vaut 0,96 ; sur un million, 206 483 sont gardés et l’estimation vaut 0,926, pour 0,925 exactement. Par la loi des grands nombres, la fréquence converge vers la probabilité ; l’erreur décroît comme \(1/\sqrt N\) pour \(N\) tirages gardés. Seuls 21 % des tirages servent, la probabilité des observations : le rejet gaspille d’autant plus que les observations sont rares. Des variantes plus économes existent (pondération par la vraisemblance, échantillonnage de Gibbs).

Quand l’élimination de variables échoue

Un mauvais ordre crée des facteurs énormes, et trouver le meilleur ordre est lui-même un problème difficile. Sur un réseau dense, la largeur d’arbre reste grande quel que soit l’ordre : il faut alors l’échantillonnage, en acceptant une estimation et son erreur.

Naive Bayes et le pont vers le Machine Learning

Le classifieur Naive Bayes

Le diagnostic de Fatou était déjà un classifieur. Le classifieur Naive Bayes prédit une classe \(c\) à partir d’attributs \(x_1,\dots,x_k\) en supposant ceux-ci indépendants sachant la classe : \[P(c\mid x_1,\dots,x_k)\propto P(c)\prod_{i=1}^k P(x_i\mid c).\] C’est un réseau bayésien en étoile, où la classe est l’unique parent de chaque attribut ; on prédit la classe de plus grand posterior. Avec la classe \(M\) et les attributs \(Fr\), \(T\) et \(TDR\), le produit \(0{,}40\times0{,}80\times0{,}70\times0{,}95\), normalisé, redonne 0,990 : exactement le résultat des trois mises à jour successives. « Naïf » désigne l’hypothèse d’indépendance conditionnelle, rarement exacte ; le classifieur n’en reste pas moins l’un des plus utilisés pour le texte.

Le filtrage du spam

Un courriel contient les mots « gratuit », « offre » et « cliquez ». Les vraisemblances de chaque mot dans les spams et dans les courriels légitimes, et la proportion de spams, \(0{,}30\), sont connues.

P_SPAM = {"spam": 0.30, "legitime": 0.70}
MOTS = {"gratuit": {"spam": 0.80, "legitime": 0.05},
        "offre": {"spam": 0.60, "legitime": 0.10},
        "cliquez": {"spam": 0.70, "legitime": 0.08}}
def naive_bayes(mots):
    score = dict(P_SPAM)
    for w in mots:
        for c in score:
            score[c] = score[c] * MOTS[w][c]
    z = sum(score.values())
    return {c: round(s / z, 4) for c, s in score.items()}
print(naive_bayes(["gratuit", "offre", "cliquez"]))
print(naive_bayes(["offre"]))

La sortie est :

{'spam': 0.9972, 'legitime': 0.0028}
{'spam': 0.72, 'legitime': 0.28}

Le score du spam vaut \(0{,}30\times0{,}80\times0{,}60\times0{,}70=0{,}1008\), celui d’un courriel légitime \(0{,}70\times0{,}05\times0{,}10\times0{,}08=0{,}00028\) ; le posterior du spam est \(0{,}1008/0{,}10108\approx0{,}9972\). Le mot « offre » seul ne donne que \(0{,}18/(0{,}18+0{,}07)=0{,}72\). En termes de cotes, chaque mot multiplie la cote du spam par son rapport de vraisemblance : 16 pour « gratuit », 6 pour « offre », 8,75 pour « cliquez ».

Du modèle donné au modèle appris

Toute la séance a supposé le modèle donné par un expert : le Dr Ndoye connaît le prior et les vraisemblances. D’où viennent-ils en général ? Le Machine Learning répond à cette question : il les apprend sur des données.

	cette séance	cours de Machine Learning
modèle	donné par l’expert	appris sur des données
prior	fixé : 40 % de paludisme en août	estimé : fréquence de la classe
vraisemblances	connues : 80 % de frissons	estimées par comptage, ou par optimisation
inférence	calculer \(P(H\mid E)\)	prédire la classe d’un nouvel exemple

Sur les 10 000 patients de DataSANTÉ-221, le jeu de données du cours de Machine Learning, 1 176 ont le paludisme : \(P(\text{palu})\approx0{,}118\) est un prior estimé par comptage. Parmi ces 1 176 patients, 894 ont consulté en saison des pluies : \(P(\text{pluies}\mid\text{palu})\approx0{,}760\) est une vraisemblance, estimée de la même façon. La régression logistique, les réseaux de neurones et les modèles génératifs reprendront la vraisemblance, le posterior et la mise à jour bayésienne ; seule changera l’origine des nombres.

L’espérance, vers la décision

Une distribution de croyance permet aussi de résumer une quantité qui dépend de la variable cachée : la durée du traitement, la gravité, le coût. La Séance 6 en fera l’outil de la décision.

Espérance

L’espérance d’une variable aléatoire numérique \(X\) est la moyenne de ses valeurs, pondérées par leurs probabilités : \[\mathbb{E}[X]=\sum_x x\,P(X=x).\] Sachant une observation \(B\), l’espérance conditionnelle est \(\mathbb{E}[X\mid B]=\sum_x x\,P(X=x\mid B)\).

Un paludisme se traite en 7 jours, une grippe en 4, une autre cause en 2. Avec le prior d’août, la durée de traitement espérée d’un patient fiévreux vaut \(\mathbb{E}[\text{durée}]=0{,}40\times7+0{,}35\times4+0{,}25\times2=2{,}8+1{,}4+0{,}5=4{,}7\) jours. Sachant que Fatou a des frissons, les poids deviennent les posteriors, \(32/45\), \(7/30\) et \(1/18\) : \(\mathbb{E}[\text{durée}\mid Fr]=\frac{32}{45}\times7+\frac7{30}\times4+\frac1{18}\times2=\frac{271}{45}\approx6{,}02\) jours. La Séance 6 pondérera de la même façon les conséquences d’une action par leurs probabilités : c’est l’utilité espérée, puis la valeur d’un état.

Le raisonnement bayésien en pratique

Le même schéma, une variable cachée, des observations bruitées, un prior, des vraisemblances et une mise à jour, se retrouve partout. En médecine, le réseau QMR-DT relie environ 600 maladies et 4 000 symptômes. Un véhicule autonome estime la position des obstacles à partir de capteurs bruités (lidar, caméras) par filtrage bayésien, en temps réel. La détection de fraude calcule la probabilité d’une fraude sachant le montant, le lieu et l’heure d’une transaction de paiement mobile. La correction orthographique et la reconnaissance de la parole choisissent le mot le plus probable sachant ce qui a été écrit ou entendu.

Exercices corrigés

Les trois exercices reprennent les raisonnements de la séance sous la forme des réponses attendues : une table de Bayes par observation, un tableau de d-séparation chemin par chemin, une table par facteur créé. Ils portent sur Cheikh, coursier à vélo du Plateau.

Exercice 1 : le vélo de Cheikh

Le vélo de Cheikh fait un bruit inhabituel. Trois causes sont possibles : une chaîne sèche, un patin de frein usé, un rayon desserré, de priors respectifs \(0{,}5\), \(0{,}3\) et \(0{,}2\). Deux observations sont faites : \(E_1\), le bruit suit le pédalage ; \(E_2\), il apparaît au freinage. Les vraisemblances sont \(P(E_1\mid h)=0{,}8\), \(0{,}1\), \(0{,}4\) et \(P(E_2\mid h)=0{,}1\), \(0{,}9\), \(0{,}3\) (chaîne, frein, rayon), et les deux observations sont supposées indépendantes sachant la cause.

Calculer les posteriors après \(E_1\), dans une table de Bayes.
Calculer les posteriors après \(E_1\) puis \(E_2\).
Refaire le calcul dans l’ordre \(E_2\), \(E_1\), et conclure.
Calculer le rapport de vraisemblance de \(E_2\), chaîne contre frein, et vérifier la forme en cotes.
Cheikh vient de graisser sa chaîne : les priors deviennent \(0{,}1\), \(0{,}6\) et \(0{,}3\). Que deviennent les posteriors après \(E_1\) et \(E_2\) ?

Correction

Méthode. Chaque observation est une application du théorème de Bayes : multiplier, ligne par ligne, le prior par la vraisemblance, sommer les produits pour obtenir l’évidence, diviser chaque produit par cette somme. Après une observation, les posteriors deviennent les priors de la suivante.

(a) Les produits valent \(0{,}5\times0{,}8=0{,}40\), \(0{,}3\times0{,}1=0{,}03\) et \(0{,}2\times0{,}4=0{,}08\) ; leur somme, l’évidence \(P(E_1)\), vaut \(0{,}51\).

\(h\)	prior	\(P(E_1\mid h)\)	produit	posterior
chaîne	\(0{,}5\)	\(0{,}80\)	\(0{,}40\)	\(\mathbf{0{,}784}\)
frein	\(0{,}3\)	\(0{,}10\)	\(0{,}03\)	\(\mathbf{0{,}059}\)
rayon	\(0{,}2\)	\(0{,}40\)	\(0{,}08\)	\(\mathbf{0{,}157}\)
somme	\(1\)		\(z=0{,}51\)	\(1\)

La chaîne passe de 0,5 à \(40/51\approx0{,}784\) : le bruit au pédalage est 8 fois plus probable avec une chaîne sèche qu’avec un frein usé.

(b) Le prior est maintenant le posterior de (a). Le bruit au freinage est rare avec la chaîne (0,1) et fréquent avec le frein (0,9) : c’est une preuve contraire.

\(h\)	prior	\(P(E_2\mid h)\)	produit	posterior
chaîne	\(0{,}784\)	\(0{,}10\)	\(0{,}0784\)	\(\mathbf{0{,}440}\)
frein	\(0{,}059\)	\(0{,}90\)	\(0{,}0529\)	\(\mathbf{0{,}297}\)
rayon	\(0{,}157\)	\(0{,}30\)	\(0{,}0471\)	\(\mathbf{0{,}264}\)
somme	\(1\)		\(z=0{,}1784\)	\(1\)

L’évidence vaut \(0{,}1784\) ; la chaîne tombe à \(40/91\approx0{,}440\), le frein monte à \(27/91\approx0{,}297\), le rayon à \(24/91\approx0{,}264\). La chaîne reste en tête, mais le diagnostic n’est plus net : une inspection est nécessaire.

(c) Dans l’ordre inverse, \(E_2\) d’abord porte le frein en tête, puis \(E_1\) le fait redescendre :

\(h\)	prior	après \(E_2\)	après \(E_2\), \(E_1\)
chaîne	\(0{,}500\)	\(0{,}132\)	\(0{,}440\)
frein	\(0{,}300\)	\(0{,}711\)	\(0{,}297\)
rayon	\(0{,}200\)	\(0{,}158\)	\(0{,}264\)

Le résultat final est identique, \(40/91\), \(27/91\), \(24/91\) : sous l’indépendance conditionnelle, le posterior final est le prior multiplié par le produit des deux vraisemblances, \(0{,}5\times0{,}8\times0{,}1=0{,}04\) pour la chaîne, \(0{,}027\) pour le frein, \(0{,}024\) pour le rayon, puis normalisé par \(0{,}091\). L’ordre des observations ne compte pas.

(d) \(\mathrm{LR}=P(E_2\mid\text{chaîne})/P(E_2\mid\text{frein})=0{,}1/0{,}9=1/9\). La cote de la chaîne contre le frein vaut au départ \(0{,}5/0{,}3=5/3\) ; \(E_1\) la multiplie par \(0{,}8/0{,}1=8\), \(E_2\) par \(1/9\) : \(\frac53\times8\times\frac19=\frac{40}{27}\), qui est bien \(\frac{40/91}{27/91}\).

(e) Avec les nouveaux priors, la même table donne :

\(h\)	prior	\(+E_1\)	\(+E_2\)	prior’	\(+E_1\)	\(+E_2\)
chaîne	\(0{,}500\)	\(0{,}784\)	\(0{,}440\)	\(0{,}100\)	\(0{,}308\)	\(0{,}082\)
frein	\(0{,}300\)	\(0{,}059\)	\(0{,}297\)	\(0{,}600\)	\(0{,}231\)	\(0{,}551\)
rayon	\(0{,}200\)	\(0{,}157\)	\(0{,}264\)	\(0{,}300\)	\(0{,}462\)	\(0{,}367\)

Les mêmes observations mènent maintenant au frein (\(54/98\approx0{,}551\) après les deux observations), devant le rayon (\(36/98\approx0{,}367\)) : le prior est le contexte. La chaîne, juste graissée, ne garde que \(8/98\approx0{,}082\).

Erreur fréquente. Lire une vraisemblance comme un posterior : « \(P(E_1\mid\text{chaîne})=0{,}8\), donc la chaîne est en cause à 80 % » confond \(P(E\mid H)\) et \(P(H\mid E)\). Autre erreur : oublier de renormaliser, et prendre les produits \(0{,}40\), \(0{,}03\), \(0{,}08\) pour des probabilités, alors qu’ils ne somment pas à 1.

Exercice 2 : le réseau du retard de Cheikh

Cheikh modélise ses retards de livraison par cinq variables booléennes : la pluie \(P\), un embouteillage \(E\), une crevaison \(C\), le retard \(R\) et la plainte du client \(Q\). La pluie favorise l’embouteillage ; embouteillage et crevaison causent le retard ; le retard provoque la plainte. Les tables sont \(P(P)=0{,}3\) ; \(P(E\mid P)=0{,}7\) et \(P(E\mid\neg P)=0{,}2\) ; \(P(C)=0{,}1\) ; \(P(R\mid E,C)=0{,}9\), \(0{,}6\), \(0{,}7\), \(0{,}1\) pour \((E,C)=(1,1),(1,0),(0,1),(0,0)\) ; \(P(Q\mid R)=0{,}5\) et \(P(Q\mid\neg R)=0{,}05\).

Écrire la factorisation de la jointe et compter les paramètres libres.
Calculer \(P(P,E,\neg C,R,Q)\).
Pour chaque requête, dire si les variables sont d-séparées, en examinant chaque triplet du chemin : \(P\) et \(C\) ; \(P\) et \(C\) sachant \(R\) ; \(P\) et \(C\) sachant \(Q\) ; \(P\) et \(R\) sachant \(E\) ; \(E\) et \(Q\) sachant \(R\) ; \(P\) et \(Q\).
Calculer \(P(C\mid R)\), puis \(P(C\mid R,E)\) et \(P(C\mid R,\neg E)\), et interpréter.

Correction

(a) Chaque nœud apporte un facteur conditionné par ses seuls parents : \[P(P,E,C,R,Q)=P(P)\,P(E\mid P)\,P(C)\,P(R\mid E,C)\,P(Q\mid R).\] Un nœud booléen a un paramètre libre par combinaison de ses parents :

nœud	parents	lignes de la table	paramètres libres
\(P\)	–	1	1
\(E\)	\(P\)	2	2
\(C\)	–	1	1
\(R\)	\(E\), \(C\)	4	4
\(Q\)	\(R\)	2	2
total			10

Le réseau demande 10 paramètres, contre \(2^5-1=31\) pour la jointe.

(b) On lit chaque facteur dans sa table, en prenant le complément pour une valeur fausse : \(P(P)=0{,}3\), \(P(E\mid P)=0{,}7\), \(P(\neg C)=0{,}9\), \(P(R\mid E,\neg C)=0{,}6\), \(P(Q\mid R)=0{,}5\), d’où \(0{,}3\times0{,}7\times0{,}9\times0{,}6\times0{,}5=0{,}0567\).

(c) Le graphe n’a pas de cycle non orienté : chaque paire n’a qu’un chemin. Pour chaque triplet du chemin, on identifie le motif, puis on applique la règle : chaîne ou cause commune bloquée si le nœud central est observé ; v-structure bloquée si ni le nœud central ni un descendant n’est observé.

requête	chemin	triplet, motif, état	d-séparés ?
\(P\), \(C\), \(Z=\emptyset\)	P–E–R–C	\(E\) (chaîne), laisse passer ; \(R\) (v-structure), bloque	oui
\(P\), \(C\), \(Z=\{R\}\)	P–E–R–C	\(E\) (chaîne), laisse passer ; \(R\) (v-structure), laisse passer	non
\(P\), \(C\), \(Z=\{Q\}\)	P–E–R–C	\(E\) (chaîne), laisse passer ; \(R\) (v-structure), laisse passer	non
\(P\), \(R\), \(Z=\{E\}\)	P–E–R	\(E\) (chaîne), bloque	oui
\(E\), \(Q\), \(Z=\{R\}\)	E–R–Q	\(R\) (chaîne), bloque	oui
\(P\), \(Q\), \(Z=\emptyset\)	P–E–R–Q	\(E\) (chaîne), laisse passer ; \(R\) (chaîne), laisse passer	non

Sans observation, la v-structure \(E\to R\leftarrow C\) isole la pluie de la crevaison. Observer \(R\), ou son descendant \(Q\), l’ouvre : la pluie et la crevaison deviennent dépendantes.

(d) Par Bayes, \(P(C\mid R)=P(R\mid C)P(C)/P(R)\). En sommant sur \(E\), de probabilité \(P(E)=0{,}3\times0{,}7+0{,}7\times0{,}2=0{,}35\) : \(P(R\mid C)=0{,}35\times0{,}9+0{,}65\times0{,}7=0{,}77\) et \(P(R\mid\neg C)=0{,}35\times0{,}6+0{,}65\times0{,}1=0{,}275\), d’où \(P(R)=0{,}1\times0{,}77+0{,}9\times0{,}275=0{,}3245\) et \(P(C\mid R)=0{,}077/0{,}3245\approx0{,}2373\).

probabilité	valeur	lecture
\(P(C)\)	\(0{,}1\)	a priori
\(P(C\mid R)\)	\(0{,}2373\)	le retard rend la crevaison plus probable
\(P(C\mid R,E)\)	\(1/7\approx0{,}1429\)	l’embouteillage explique le retard
\(P(C\mid R,\neg E)\)	\(7/16=0{,}4375\)	sans embouteillage, la crevaison devient l’explication

Sachant aussi l’embouteillage, \(P(C\mid R,E)=\frac{0{,}1\times0{,}9}{0{,}1\times0{,}9+0{,}9\times0{,}6}=\frac{0{,}09}{0{,}63}=\frac17\) : l’embouteillage explique déjà le retard, la crevaison redevient presque aussi rare qu’a priori. Sans embouteillage, \(P(C\mid R,\neg E)=\frac{0{,}07}{0{,}07+0{,}09}=\frac7{16}\) : il faut une autre explication. C’est l’explication concurrente de la v-structure.

Erreur fréquente. Conclure que \(P\) et \(C\) sont d-séparés sachant \(Q\) parce que \(R\) n’est pas observé : un descendant observé d’une v-structure l’ouvre. Autre erreur : dire « \(E\) et \(C\) sont indépendants, donc apprendre \(E\) ne change pas \(P(C\mid R)\) » ; ils le sont a priori, plus sachant \(R\).

Exercice 3 : l’élimination de variables sur le réseau de Cheikh

Le client de Cheikh se plaint (\(Q=1\)). Calculer \(P(C\mid Q=1)\) par élimination de variables, en éliminant \(P\), puis \(E\), puis \(R\) ; donner chaque facteur créé et le nombre de multiplications, et comparer à l’énumération.

Correction

Méthode. Les observations sont fixées d’abord : le facteur \(P(Q\mid R)\) devient \(f_Q(R)=P(Q=1\mid R)\), soit \(0{,}5\) et \(0{,}05\). Pour chaque variable à éliminer, on multiplie les facteurs qui la contiennent et l’on somme sur ses valeurs.

Élimination de \(P\). Les facteurs qui contiennent \(P\) sont \(P(P)\) et \(P(E\mid P)\) ; leur produit compte 4 cases (4 multiplications), et la somme sur \(P\) donne

E	1	0
\(\tau_1(E)\)	\(0{,}350\)	\(0{,}650\)

\(\tau_1(E)\) est la probabilité de l’embouteillage, \(0{,}3\times0{,}7+0{,}7\times0{,}2=0{,}35\).

Élimination de \(E\). Les facteurs qui contiennent \(E\) sont \(\tau_1(E)\) et \(P(R\mid E,C)\) ; le produit porte sur \((E,R,C)\), 8 cases (8 multiplications) ; la somme sur \(E\) donne

\(\tau_2(R,C)\)	\(C=1\)	\(C=0\)
\(R=1\)	\(0{,}770\)	\(0{,}275\)
\(R=0\)	\(0{,}230\)	\(0{,}725\)

\(\tau_2(R,C)\) est \(P(R\mid C)\) : \(0{,}35\times0{,}9+0{,}65\times0{,}7=0{,}77\) avec crevaison, \(0{,}35\times0{,}6+0{,}65\times0{,}1=0{,}275\) sans.

Élimination de \(R\). Les facteurs qui contiennent \(R\) sont \(\tau_2(R,C)\) et \(f_Q(R)\) ; 4 cases, 4 multiplications :

C	1	0
\(\tau_3(C)\)	\(0{,}39650\)	\(0{,}17375\)

Avec crevaison, \(0{,}77\times0{,}5+0{,}23\times0{,}05=0{,}3965\) ; sans, \(0{,}275\times0{,}5+0{,}725\times0{,}05=0{,}17375\).

Produit final et normalisation. Il reste \(P(C)\) et \(\tau_3(C)\) : 2 multiplications.

	\(C=1\)	\(C=0\)
\(P(C)\,\tau_3(C)\)	\(0{,}03965\)	\(0{,}156375\)
\(P(C\mid Q=1)\)	\(\mathbf{0{,}2023}\)	\(0{,}7977\)

La somme \(0{,}03965+0{,}156375=0{,}196025\) est \(P(Q=1)\) ; \(P(C\mid Q=1)=0{,}03965/0{,}196025\approx0{,}2023\). La plainte double presque la probabilité d’une crevaison (0,1 a priori).

Comparaison. L’élimination a demandé \(4+8+4+2=18\) multiplications. L’énumération calcule 16 termes (2 valeurs de \(C\), 8 combinaisons de \(P\), \(E\), \(R\)) de 5 facteurs, soit 64 multiplications, pour le même résultat.

Erreur fréquente. Oublier un facteur qui contient la variable éliminée (par exemple \(f_Q(R)\) quand on élimine \(R\)), ou sommer un facteur sur une variable qui figure encore dans un autre facteur : le résultat ne somme plus correctement. Autre erreur : normaliser avant la fin, alors que seule la distribution finale doit sommer à 1.

À retenir

Une probabilité est un degré de croyance ; la jointe contient toute l’information, la marginalisation somme une variable, le conditionnement zoome sur une observation.
\(P(A\mid B)\neq P(B\mid A)\) ; le posterior est proportionnel à la vraisemblance multipliée par le prior, normalisé par l’évidence.
Le prior est le contexte : les frissons donnent 0,711 de paludisme à Dakar en août, 0,003 à Paris en janvier.
Le posterior d’hier est le prior d’aujourd’hui, sous l’indépendance conditionnelle des preuves ; l’ordre des observations ne compte pas, une preuve contraire affaiblit sans annuler (0,910, puis 0,359).
Avec des vraisemblances 0 et 1, on retrouve la logique ; avec un capteur bruité, Bouki est en \((2,2)\) avec 0,876.
Un réseau bayésien factorise la jointe par les parents : 19 paramètres au lieu de 95 pour le réseau de Fatou.
Chaîne et cause commune : observer le nœud central bloque ; v-structure : observer le nœud central, ou un descendant, ouvre. La d-séparation lit ainsi les indépendances dans le graphe.
L’énumération et l’élimination de variables donnent la même réponse exacte ; l’élimination factorise, 27 multiplications au lieu de 120. L’échantillonnage estime quand le calcul exact est hors de portée.
Naive Bayes est le diagnostic séquentiel ; le Machine Learning apprend ses probabilités sur des données.

Prochaine séance

Fatou a le paludisme avec une probabilité de 0,990 : faut-il traiter tout de suite, ou attendre un examen de plus ? La Séance 6, « L’IA qui apprend », passe de la croyance à la décision : utilité espérée, processus de décision markoviens, équation de Bellman, puis apprentissage par renforcement.

Références

Russell, Norvig — Artificial Intelligence: A Modern Approach, 4^e éd., Pearson, 2020 (chap. 12 « Quantifying Uncertainty », chap. 13 « Probabilistic Reasoning »).
Pearl — Probabilistic Reasoning in Intelligent Systems, Morgan Kaufmann, 1988.
Koller, Friedman — Probabilistic Graphical Models, MIT Press, 2009.
Poole, Mackworth — Artificial Intelligence: Foundations of Computational Agents, 3^e éd., Cambridge University Press, 2023.
Murphy — Probabilistic Machine Learning: An Introduction, MIT Press, 2022.
Bayes — « An Essay towards Solving a Problem in the Doctrine of Chances », Philosophical Transactions of the Royal Society, 1763.
Cooper — « The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks », Artificial Intelligence, 1990.

Pourquoi un agent doit douter

Le diagnostic de Fatou

Les trois sources d’incertitude

Du vrai et du faux au degré de croyance

Le langage des probabilités

Variables aléatoires

Distribution de probabilité et axiomes de Kolmogorov

Deux lectures d’une probabilité

Les données du diagnostic en Python

La distribution jointe

Exemple pas à pas : la jointe, la marge, le zoom

La marginalisation

La probabilité conditionnelle

La règle du produit et l’indépendance

Le théorème de Bayes

De l’effet à la cause

La dérivation et les quatre termes

Exemple pas à pas : Bayes en table

Le rapport de vraisemblance

Même preuve, autre contexte

Bayes sous forme de cotes

Accumuler les preuves

La mise à jour séquentielle

Exemple pas à pas : la mise à jour séquentielle

La preuve contradictoire

Retour au Monde de Bouki

Exemple pas à pas : le Monde de Bouki probabiliste

L’apport des probabilités

Les réseaux bayésiens

L’explosion combinatoire de la jointe

L’indépendance conditionnelle

Définition d’un réseau bayésien

Le réseau de Fatou

Compter les paramètres

Structures canoniques et d-séparation

La chaîne

La cause commune

La v-structure et l’explication concurrente

Les trois motifs

Le critère de d-séparation

Exemple pas à pas : la d-séparation

La d-séparation à deux chemins

La couverture de Markov

L’inférence dans un réseau bayésien

Le problème d’inférence

L’énumération

Le coût de l’énumération

L’élimination de variables

Exemple pas à pas : l’élimination de variables

Énumération contre élimination

L’inférence approchée par échantillonnage

Naive Bayes et le pont vers le Machine Learning

Le classifieur Naive Bayes

Le filtrage du spam

Du modèle donné au modèle appris

L’espérance, vers la décision

Le raisonnement bayésien en pratique

Exercices corrigés

Exercice 1 : le vélo de Cheikh

Exercice 2 : le réseau du retard de Cheikh

Exercice 3 : l’élimination de variables sur le réseau de Cheikh

À retenir

Prochaine séance

Références

Pour cette séance