La couverture de Markov
le plus petit ensemble de nœuds qui isole une variable du reste du graphe
1 · DÉFINITION
$$\mathrm{mb}(T) = \mathrm{pa}(T)\,\cup\,\mathrm{ch}(T)\,\cup\bigcup_{C\in \mathrm{ch}(T)}\mathrm{pa}(C)\setminus\{T\},
\qquad X_T \perp\!\!\!\perp X_{\text{reste}} \mid X_{\mathrm{mb}(T)}$$
PARENTSbloquent les chemins vers les non-descendants
ENFANTSbloquent les chemins vers les descendants
CO-PARENTSconditionner sur un enfant ouvre le collisionneur \(T\to C\leftarrow Q\)
2 · À TOI : TROUVE L'ENSEMBLE QUI ISOLE T
graphe orienté acyclique — clique sur les nœuds
critère : dépendance de \(T\) et de chaque autre nœud \(W\)
Nœuds grisés : conditionnés (dans Z). Une barre vide signifie une corrélation partielle nulle : W n'apporte plus rien sur T une fois Z connu.
3 · RAPPELS
- Les parents coupent les chemins qui remontent, les enfants ceux qui descendent ; mais conditionner sur un enfant ouvre le collisionneur qu'il forme avec ses autres parents, d'où les co-parents.
- Seule la couverture intervient dans la loi conditionnelle d'un nœud, ce qu'utilise l'échantillonneur de Gibbs : $$p(x_T\mid x_{\text{reste}}) \propto p(x_T\mid x_{\mathrm{pa}(T)})\prod_{C\in\mathrm{ch}(T)} p(x_C\mid x_{\mathrm{pa}(C)}).$$
- Cas gaussien : \(\mathrm{mb}(T)=\{W : \Theta_{TW}\neq 0\}\), les coefficients non nuls de la régression de \(T\) sur tous les autres nœuds, soit les voisins de \(T\) dans le graphe moralisé.
- Sous l'hypothèse de fidélité, la couverture est le seul ensemble minimal qui isole T : pour prédire T, aucune autre variable n'apporte d'information (sélection de variables).
- Les petits-enfants et les parents des parents n'en font pas partie : ils ne sont reliés à T qu'à travers la couverture.