Modèles graphiques probabilistes

Francis Bach
Centre de Morphologie Mathématique
Ecole des Mines de Paris

Mai 2006
 Modèles graphiques probabilistes

Modèle graphique probabiliste = représentation graphique d’un

ensemble de lois de probabilité multivariées

• Modularité
– Gestion de la complexité

• Modèle probabiliste
– flexibilité d’utilisation (inférence et apprentissage)

• Formalisme commun à de nombreux modèles/domaines

– Transferts : théorie/applications, théorie/théorie
 Modèles graphiques probabilistes
Plan de la présentation

• Définition

• Inférence

• Apprentissage
– Paramètres
– Structure

• Applications et perspectives
 Modèle graphique

• Variables aléatoires: X = (X1, . . . , Xn)

• Modèle graphique = structure (graphe) + collection de lois locales

• Graphe
– Sommets ∼ variables
– Absence d’arêtes ∼ indépendances conditionnelles

• Deux grandes familles:

– Graphe orienté
– Graphe non orienté
Modèle graphique non orienté (champ de Markov)

• Graphe, cliques

1 Yp
• (1) Loi factorisée: p(x) = φCj (xCj )
Z j=1
Z est une constante de normalisation
Modèle graphique non orienté (champ de Markov)

• Graphe, cliques

1 Yp
• (1) Loi factorisée: p(x) = φCj (xCj )
Z j=1
Z est une constante de normalisation

• (2) Indépendances conditionnelles: sachant ses voisins, chaque

variable est indépendante du reste du graphe (séparation)

• Propriétés équivalentes sous certaines conditions (Théorème de

Hammersley-Cliford)
 Modèle graphique orienté
(“Réseaux Bayésiens”)
X2 X4

X1
X6
X3 X5

• DAG (Directed acyclic graph): graphe orienté sans cycle

Y
n
• (1) Loi factorisée: p(x) = p(xi|xparents(i))
i=1
(pas de contrainte de normalisation)
 Modèle graphique orienté
(“Réseaux Bayésiens”)
X2 X4

X1
X6
X3 X5

• DAG (Directed acyclic graph): graphe orienté sans cycle

Y
n
• (1) Loi factorisée: p(x) = p(xi|xparents(i))
i=1
(pas de contrainte de normalisation)

• (2) Indépendance conditionnelles: chaque variable est

indépendante de ses non-descendants sachant ses parents (d-
séparation)
 Modèles à trois noeuds
• Modèles triviaux

• Non orienté:
X Y Z
X⊥Z |Y

• Orienté 1 : Chaı̂ne de Markov

X Y Z
X⊥Z |Y

• Orienté 2 : variable latente commune

X Y Z
X⊥Z |Y

• Orienté 3 : “Explaining away”

X Y Z
X⊥Z
– exemple: X, Z deux dés indépendants, Y leur somme
 Markov-équivalence

• Deux graphes G1, G2 sont Markov-équivalents ssi ils définissent la

même famille de lois de probabilité
• G1, G2 non orientés: Markov-équivalence ⇔ égalité
 Markov-équivalence

• Deux graphes G1, G2 sont Markov-équivalents ssi ils définissent la

même famille de lois de probabilité
• G1, G2 non orientés: Markov-équivalence ⇔ égalité
• G1, G2 orientés: Markov-équivalence ⇔ G1 et G2 ont les mêmes
“v-structures” et des graphes non orientés égaux

X2 X4

X1
X6
X2 X4 X3 X5 X2 X4

X1 X1
X6 X6
X3 X5 X3 X5
 Graphes décomposables

• G1 orienté, G2 non orienté: Markov-équivalence possible pour les

graphes décomposables (i.e., triangulés)
– G non orienté est décomposable/triangulé ssi il n’existe pas de
cycle d’ordre supérieur ou égal à 4 sans cordes.

Triangulé Non triangulé

Modèles classiques formulés en modèles graphiques

• Modèles de mélange

• Analyse factorielle

• Modèle de Markov caché

• Filtre de Kalman

• Modèles pour inférence Bayésienne

• Champs de Markov
 Modèles de mélange
Z X

X X
• p(x) = p(z = k)p(x|z = k) = πk pk (x)
k k

• NB: moyen simple pour modéliser des variables aléatoires non

Gaussiennes/non standard:
 Analyse factorielle
Z1 Z2

X1 X2 X3 X4 X5

P
• zi ∼ N (0, 1), xj |z ∼ N ( j wjizi, σj2)

• NB: si σj2 = σ 2, ∀j, équivalent à l’analyse en composantes

principales (Tipping & Bishop, 1999)
 Modèles de Markov cachés
Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Zi discrets

• NB: équivalent à
Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5
 Filtre de Kalman
Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Densités Gaussiennes
 Modèles factoriels
Y1 Y2 Y3 Y4 Y5

Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Modèles de Markov cachés factoriels (Ghahramani & Jordan, 1997)

• Variables latentes discrètes et continues (switching Kalman filter)

 Modèle pour inférence Bayésienne
µ σ2

X1 X 2 Xn

• Paramètres considérés comme variables aléatoires

• Exemple: xi|µ, σ 2 ∼ N (µ, σ 2), σ 2 ∼ Γ(α, β), µ ∼ N (µ0, t2)

µ σ2
• Notation “plate”:
Xi
n
 Champs de Markov

• Images/Pixels

• Physique statistique
 Modèles graphiques probabilistes
Plan de la présentation

• Définition

• Inférence

• Apprentissage
– Paramètres
– Structure

• Applications et perspectives
 Inférence dans les modèles graphiques

• {1, . . . , n} = O ∪ C, observations et variables cachées

• Calculer p(xC |xO ) ou arg maxxC p(xC |xO )

• Inférence naı̈ve: p(xC |xO ) = p(xC , xO )/p(xO )

P
et p(xO ) = xC p(xC , xO )
 Inférence dans les modèles graphiques

• {1, . . . , n} = O ∪ C, observations et variables cachées

• Calculer p(xC |xO ) ou arg maxxC p(xC |xO )

• Inférence naı̈ve: p(xC |xO ) = p(xC , xO )/p(xO )

P
et p(xO ) = xC p(xC , xO )

• Inférence exacte non naı̈ve

– utilise la factorisation des lois
– cadre non orienté plus adapté
P Qp
– Tâche générique: calculer Z = φCj (xCj ) ou
Qp x1 ,...,x n j=1
arg maxx1,...,xn j=1 φCj (xCj )

• Inférence approchée
 Inférence exacte dans les arbres

Xj Xi

• Arbre (non orienté): graphe sans cycle

– Potentiels: ψi(xi), ψij (xi, xj )
1
Q Q
– p(x) = Z i ψi(xi) i,j ψij (xi, xj )
P Q Q
– But: calculer Z = x1,...,xn i ψi(xi) i,j ψij (xi, xj )
 Inférence exacte dans les arbres
Xj Xi

m ij

P Q Q
• But: calculer Z = x1,...,xn i ψi(xi) i,j ψij (xi, xj )

• Propagation de 2n messages le long des arêtes

X Y
mij (xj ) = ψi(xi)ψij (xi, xj ) mki(xi)
xi k∈N (i)\{j}

• Complexité linéaire
P
• NB: configuration la plus probable: remplacer par max
 Inférence exacte
(Lauritzen & Spiegelhalter,1988)

• Transformation des graphes en arbres non orientés

1. Moralisation des modèles graphiques orientés
X2 X4 X2 X4

X1 ⇒ X1
X6 X6
X3 X5 X3 X5
 Inférence exacte
(Lauritzen & Spiegelhalter,1988)

• Transformation des graphes en arbres non orientés

1. Moralisation des modèles graphiques orientés
X2 X4 X2 X4

X1 ⇒ X1
X6 X6
X3 X5 X3 X5
2. Triangulation du graphe non orienté
X2 X4 X2 X4

X1 ⇒ X1
X6 X6
X3 X5 X3 X5
 Inférence exacte
(Lauritzen & Spiegelhalter,1988)

• Transformation des graphes en arbres non orientés

1. Moralisation des modèles graphiques orientés
X2 X4 X2 X4

X1 ⇒ X1
X6 X6
X3 X5 X3 X5
2. Triangulation du graphe non orienté
X2 X4 X2 X4

X1 ⇒ X1
X6 X6
X3 X5 X3 X5
3. Construction d’un arbre de cliques
 Construction d’un arbre de cliques
• Arbre de cliques

X2 X4 X2 X4
24

X1 ⇒ X1
123 256
X6 235 X6
X3 X5 X3 X5

• Si le graphe est triangulé, arbre de clique = arbre de jonctions

(propriété d’intersection courante)

• Sinon...
X2 X4 X2 X4
24

X1 ⇒ X1 12
256
X6 13 X6
35
X3 X5 X3 X5
 Propagation des messages
• Arbre de jonctions

X2 X4 24
24

X1
123 256
⇒ 123
235
256

235 X6
X3 X5

• Propagation de 2m messages (m = nombre de cliques), “MAX”

ou “SUM”

• Cohérence locale ⇒ cohérence globale !

• Complexité: exponentielle dans le cardinal de la plus grande clique

• Largeur arborescente (treewidth)

= Cardinal de la plus grande clique d’un graphe triangulé optimal
 Inférence
Modèle de Markov cachés
Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Zi discrets

• Max-propagation = algorithme de Viterbi

 Filtre de Kalman
Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Densités Gaussiennes

• Propagation de vecteurs moyennes et de matrice de covariances

 Modèles factoriels
Y1 Y2 Y3 Y4 Y5

Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Modèles de Markov cachés factoriels

• Si m chaı̂nes de Markov latentes, complexité O(2m+1) au lieu de

O(22m) (cas binaire)

• Données hétérogènes ?
 Champs de Markov

• Largeur arborescente non bornée

 Problèmes de l’inférence exacte

• (1) Grande largeur arborescente

• (2) Données hétérogènes

• Inférence approchée
– Méthodes stochastiques (MCMC)
– Méthodes variationnelles
 Markov chain Monte Carlo (MCMC)

• Echantillonner p(xH C|xO ) à l’aide d’une

chaı̂ne de Markov dont la loi stationnaire
est exactement p(xC |xO )
 Markov chain Monte Carlo (MCMC)

• Echantillonner p(xH C|xO ) à l’aide d’une

chaı̂ne de Markov dont la loi stationnaire
est exactement p(xC |xO )
• Construction simple de la loi de transition: échantillonage de Gibbs
(Geman & Geman, 1984)

– Itération: pour i de 1 à n,
échantilloner p(xi|xvoisins(i))
– “burn-in”
 Markov chain Monte Carlo (MCMC)

• Avantages
– converge vers l’inférence exacte
– peut toujours être utilisé

• Inconvénients
– Non triviale à mettre en oeuvre correctement
– Lenteur
 Méthodes variationnelles d’inférence
(Jordan & al., 1997)
• Approcher p(x) par une loi q(x, λ) plus simple
– Optimization (efficace) du paramètre variationnel λ
 Méthodes variationnelles d’inférence
(Jordan & al., 1997)

• Approcher p(x) par une loi q(x, λ) plus simple

– Optimization (efficace) du paramètre variationnel λ

• Modèles graphiques: q(x, λ) obtenue en enlevant des arêtes

Méthode du champ moyen (physique statistique)

 Méthodes variationnelles d’inférence
(Jordan & al., 1997)
• Approcher p(x) par une loi q(x, λ) plus simple
– Optimization (efficace) du paramètre variationnel λ

• Modèles graphiques: q(x, λ) obtenue en enlevant des arêtes

Méthode structurée : utilisation de sous-structures simples

Méthodes variationnelles d’inférence
Modèle factoriel
Y1 Y2 Y3 Y4 Y5

Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

Y1 Y2 Y3 Y4 Y5

Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5
 Méthodes variationnelles d’inférence

• Avantages
– Déterministe
– Simple à mettre en oeuvre

• Inconvénients
– ne converge pas vers l’inférence exacte
 Modèles graphiques probabilistes
Plan de la présentation

• Définition

• Inférence

• Apprentissage
– Paramètres
– Structure

• Applications et perspectives
 Apprentissage des paramètres

• Nécessaire en pratique

• Hypothèse: structure fixe (graphe + paramétrisation des lois

locales)

• Cadre fréquentiste: estimateur de maximum de vraisemblance bien

adapté aux modèles graphiques

• Cadre Bayésien
 Apprentissage des paramètres

• Cadre Bayésien: paramètres considérés comme variables aléatoires

– Probabilités a priori p(θ), a posteriori p(θ|x)
– Formule de Bayes: p(θ|x) = p(x|θ)p(θ)
p(x)
– Apprentissage “=” inférence
– “Vrais Bayésiens” : jamais d’estimateurs ponctuels
– “Faux Bayésiens” : maximum a posteriori (MAP)

µ σ2

Xi
n

• Deux cadres asymptotiquement équivalents

“Réseaux Bayésiens Bayésiens” et “réseaux
Bayésiens non Bayésiens” ?
 Données complètes
Maximum de vraisemblance

Y
n
• Modèles orientés: p(x|θ) = p(xi|xparents(i), θi)
i=1

– Découplage du maximum de vraisemblance (∀ treewidth ! )

– Estimations locales
– Exemples: modèles discrets / Gaussiens
 Données complètes
Maximum de vraisemblance

Y
n
• Modèles orientés: p(x|θ) = p(xi|xparents(i), θi)
i=1

– Découplage du maximum de vraisemblance (∀ treewidth ! )

– Estimations locales
– Exemples: modèles discrets / Gaussiens

1 Y
p
• Modèles non orientés: p(x|θ) = φCj (xCj , θj )
Z(θ1, . . . , θp) j=1

– Pas de découplage du maximum de vraisemblance

– Algorithmes itératifs (IPF, IS). Cf. Della Pietra et. al (1997),
Jirousek, 1995.
 Données incomplètes
Algorithme Expectation-Maximisation (EM)

• Modèle p(x, z|θ)

z non observée (données manquantes ou modèles de mélange)
P
• log vraisemblance: log p(x|θ) = log z p(x, z|θ)

• Algorithme itératif
– E-step: calculer J(θ) = Ep(z|x,θ) log p(x, z|θ)
– M-step: maximiser J(θ) par rapport à θ

• Propriétés de convergence
– Croissance de la vraisemblance à chaque itération
– Minimas locaux
 Apprentissage de la structure

• Deux visions des modèles graphiques → deux types de méthodes

– Apprentissage de la structure par tests d’indépendances
conditionnelles (IC/PC: Pearl, 2000, Spirtes & al, 1993)
∗ Problème de complexité
∗ Problème de cohérence/fiabilité
 Apprentissage de la structure

• Deux visions des modèles graphiques → deux types de méthodes

– Apprentissage de la structure par tests d’indépendances
conditionnelles (IC/PC: Pearl, 2000, Spirtes & al, 1993)
∗ Problème de complexité
∗ Problème de cohérence/fiabilité
– Apprentissage de la structure par des méthodes statistiques de
sélection de modèles
∗ Utilisation de la loi factorisée
∗ Calcul d’un score pour chaque structure
∗ Fouille dans l’espace des graphes orientés
 Apprentissage de la structure
Scores pour données complètes - Modèle orienté

• Cadre Bayésien
– Calcul de la probabilité marginale du modèle
– Formule analytique dans certains cas (e.g., BDe pour
discrets/Gaussiens, Heckerman & al, 1995)

• Cadre fréquentiste
 Apprentissage de la structure
Scores pour données complètes - Modèle orienté

• Cadre fréquentiste
– Le maximum de vraisemblance ne permet pas de faire de la
sélection de modèles
 Apprentissage de la structure
Scores pour données complètes - Modèle orienté

• Cadre fréquentiste
– Le maximum de vraisemblance ne permet pas de faire de la
sélection de modèles
– Pénaliser les modèles plus complexes: AIC - BIC/MDL

X
n X
n
J(G) = I(xi, xπi(G)) + cste × #(i, πi(G))
i=1 i=1

I information mutuelle calculée à l’aide des distributions

empiriques (multinomiales, Gaussiennes)
 Apprentissage de la structure
Scores pour données complètes - Modèle orienté

X
n X
n
J(G) = I(xi, xπi(G)) + cste × #(i, πi(G))
i=1 i=1

• Optimisation du score
– Arbres
∗ Problème d’arbre couvrant de poids maximal
∗ Algorithme de Chow-Liu (1968!)
– Cas général: optimization gloutonne
– Problèmes de Markov-équivalence
 Apprentissage de la structure
Données incomplètes

• Structural EM (Friedman, 1988)

– Alterner entre apprentissage des paramêtres et apprentissage de
la structure

• Problèmes de minimas locaux

 Modèles graphiques probabilistes
Plan de la présentation

• Définition

• Inférence

• Apprentissage
– Paramètres
– Structure

• Applications et perspectives
 Perspectives

• Applications
– Bio, image, texte, son, etc...

• Thèmes récents/intéressants
– Inférence, inférence, inférence ...
– Modèles graphiques discriminants
– Modèles causaux
– Méthodes non-paramétriques
– Filtres particulaires
 Modèles graphiques discriminants
Conditional random fields (CRF)
Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Situation courante:
– x toujours observé, but=prédire z
– Apprentissage avec données complètes: maxθ p(x, z|θ)
– Utilisation du modèle: arg maxz p(x, z|θ) = arg maxz p(z|x, θ)

• Modèles graphiques discriminants:

1. Apprentissage discriminant
2. Interactions longue portée possibles
 Modèles graphiques discriminants

• Apprentissage discriminant
– maxθ p(z|x, θ) au lieu de maxθ p(z, x|θ)
– cf. régression logistique vs. analyse linéaire discriminante
– Complexité numérique supérieure
– Modèle “correct/incorrect”
 Modèles graphiques discriminants

• Interactions longue portée

Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Biologie, traitement du texte (Lafferty & al, 2001)

 Causalité

• La corrélation n’implique pas la causalité

• En général, le sens d’une arête dans un modèle orienté ne

correspond pas à une relation de causalité
 Causalité

• La corrélation n’implique pas la causalité

• En général, le sens d’une arête dans un modèle orienté ne

correspond pas à une relation de causalité

• Sans hypothèses supplémentaires, des relations de causalité ne

peuvent pas être inférée sans interventions
 Causalité

• La corrélation n’implique pas la causalité

• En général, le sens d’une arête dans un modèle orienté ne

correspond pas à une relation de causalité

• Sans hypothèses supplémentaires, des relations de causalité ne

peuvent pas être inférée sans interventions

• Ceci dit...
– Modèles graphiques causaux (Pearl, 2000, Spirtes & al, 1993)
 Modèles causaux

• Modèles orientés

• Chaque p(xi|xπi ) représente un processus stochastique autonome

– Permet les interventions

• Inférence causale

• Apprentissage de relations de causalité

– Rappel: La corrélation n’implique pas la causalité
– Hypothèse de sufficience causale
– Apprentissage sans expérimentation
– Apprentissage avec expérimentation
 Méthodes non-paramétriques

• Hypothèses paramétriques classiques

– Données binaires: loi de Bernoulli
– Données catégoriques: loi multinomiale
– Données continues: loi Gaussienne
 Méthodes non-paramétriques

• Hypothèses paramétriques classiques

– Données binaires: loi de Bernoulli
– Données catégoriques: loi multinomiale
– Données continues: loi Gaussienne
– Familles exponentielles (Poisson, Gamma, Beta) pour p(x)
– Modèles linéaires généralisés (GLIM) pour p(y|x)
 Méthodes non-paramétriques

• Hypothèses paramétriques classiques

– Données binaires: loi de Bernoulli
– Données catégoriques: loi multinomiale
– Données continues: loi Gaussienne
– Familles exponentielles (Poisson, Gamma, Beta) pour p(x)
– Modèles linéaires généralisés (GLIM) pour p(y|x)

• Non-paramétrique: permet de s’affranchir d’hypothèses restrictives

sur les lois locales
– par obligation, ignorance, ou paresse...
– sans complexité numérique additionnelle majeure

• Cf. tutoriel de Michael Jordan (UC Berkeley), NIPS 2005

 Filtres particulaires
pour modèles graphiques dynamiques
Z1 Z2 Z3 Z4 Z5

X1 X2 X3 X4 X5

• Données, dynamique, et/ou observations complexes (i.e., non

Gaussiennes)

• Faible largeur arborescente, mais propagation délicate

• Méthodes particulaires: mise à jour efficace d’un ensemble de

particules qui suivent la loi p(z1, . . . , zt|x1, . . . , xt) pour t = 1, . . . .

• cf. Murphy (2002), Doucet & al. (2001)

 Conclusion

• Modèle graphique probabiliste = outil flexible de modélisation

• Echanges théorie/applications
 Références

• M. Tipping and C. Bishop. Probabilistic principal component analysis. Journal of the Royal
Statistical Society B, 61, 611-622, 1999
• Z. Ghahramani and M. I. Jordan. Factorial hidden markov models. Mach. Learn., 29(2-3):245–
273, 1997.
• S. L. Lauritzen and D. J. Spiegelhalter, Local computations with probabilities on graphical
structures and their application to expert systems, J. Royal Stat. Society, B 50 (1988), no. 2,
157–223.
• S. L. Lauritzen. Graphical Models. Clarendon Press, Oxford, 1996.
• F. V. Jensen. ”Bayesian Networks and Decision Graphs”. Springer. 2001.
• J. Pearl. ”Causality”. Cambridge. 2000.
• R. G. Cowell, A. P. Dawid, S. L. Lauritzen and D. J. Spiegelhalter. ”Probabilistic Networks
and Expert Systems”. Springer-Verlag. 1999.
• M. I. Jordan (ed). ”Learning in Graphical Models”. MIT Press. 1998.
• S. Roweis & Z. Ghahramani, 1999. A Unifying Review of Linear Gaussian Models, Neural
Computation 11(2) (1999) pp.305-345
• R. McEliece and S. M. Aji, 2000. The Generalized Distributive Law, IEEE Trans. Inform.
Theory, vol. 46, no. 2 (March 2000), pp. 325–343.
• Kschischang, B. Frey and H. Loeliger, 2001. Factor graphs and the sum product algorithm,
IEEE Transactions on Information Theory, February, 2001.
• M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul, 1997. ”An introduction to
variational methods for graphical models.”
• D. MacKay, 1998. ”An introduction to Monte Carlo methods”.
• Spirtes, P., Glymour, C. and Scheines, R. (1993) Causation, Prediction, and Search. Springer-
Verlag, NY.
• D. Heckerman, D. Geiger, D. M. Chickering, Learning Bayesian networks: The combination of
knowledge and statistical data, Machine Learning 20 (1995) 197–243,
• C. Chow and C. Liu. 1968. Approximating discrete probability distributions with dependence
trees. IEEE Transactions on Information Theory, 14(3):462–467.
• N. Friedman. The Bayesian structural EM algorithm. In Proc. UAI, 1998.
• J. Lafferty, A. McCallum, F. Pereira. Conditional Random Fields: Probabilistic Models for
Segmenting and Labeling Sequence Data. In Proc. ICML, 2001.
• Kevin Murphy. Dynamic Bayesian Networks: Representation, Inference and Learning. PhD
thesis, UC Berkeley, Computer Science Division, July 2002.
• Doucet, A., de Freitas, J.F.G. and Gordon, N.J. (2001). Sequential Monte Carlo Methods in
Practice. New York: Springer-Verlag.
• S. Geman and D. Geman. Stochastic Relaxation, Gibbs Distributions, and the Bayesian
Restoration of Images. IEEE Trans. PAMI, 6:721–741, 1984.
• S. Della Pietra, V. J. Della Pietra, and J. D. Lafferty. Inducing features of random fields. IEEE
Trans. PAMI, 19(4):380–393, 1997.
• Jirousek, R. & Preucil, S. (1995). On the effective implementation of the iterative proportional
fitting procedure, Computational Statistics & Data Analysis. 19: 177-189.