1

Une vue unifiée des algorithmes avec passage de

message:mesures de divergence

Florence Forbes INRIA Rhone-Alpes

D’après un article de Tom Minka, Divergence measures and message

passing, 2005

2

Contexte:Modélisation de problèmes réels, algorithmes trop

exigeants en temps, ressources informatiques et humaines

Nécessité de disposer d’outils d’approximation

BUT: approcher une loi p(x) complexe par une loi plus simple q(x) appartenant à une famille F

Pourquoi? La loi q peut alors etre utilisée pour remplacer p dans un processus d’inférence plus générale:

Ex: calcul de fonction de partition, segmentation d’image, sélection de modèles, etc.

3

Les méthodes variationnelles

Une famille de méthodes d’approximation où p complexe est remplacée par q dans F “plus simple” en minimisant “la perte d’information”

Souvent un problème peut-etre décomposer en sous problèmes: Stratégie de décomposition qui conduit aux algorithmes de passage de messages

Algorithmes de passage de messages: une méthode “locale”, “distribuée” pour calculer q

4

Les algorithmes de passage de messages

Des recettes différentes pour minimiser une mesure d’information

Se base sur la notion de divergence

Idée: étudier les propriétés de ces divergences devrait permettre de choisir le meilleur algorithme en fonction de l’application visée, de la tache à accomplir

Exemples d’algorithmes de passage de messages

5

Exemples d’algorithmes (Message-Passing Algorithms)

Mean-field MF [Peterson,Anderson 87]

Loopy belief propagation BP [Frey,MacKay 97]

Expectation propagation EP [Minka 01]

Tree-reweighted message passing

TRW [Wainwright,Jaakkola,Willsky 03]

Fractional belief propagation FBP [Wiegerinck,Heskes 02]

Power EP PEP [Minka 04]

6

Un algorithme de passage de messages se construit en 4 étapes

1. Choisir une famille F (ex. Lois factorisées, lois gaussiennes, mélanges de gaussiennes, etc.)

2. Choisir une mesure de divergence à minimiser pour trouver le “meilleur” q dans F (ex Kullback-Leibler)

3. Proposer une méthode pour calculer le q optimal: souvent une itération de point fixe

4. Mettre en oeuvre le calcul de manière distribuée et locale (minimisation de divergences “locales”)

Florence Forbes

Message Passing: compute marginals

• Example

• Find marginal for a particular node

– for M-state nodes, cost is – exponential in length of chain– but, we can exploit the graphical structure

(conditional independences)

Florence Forbes

Message Passing

• Joint distribution

• Exchange sums and products: ab+ ac = a(b+c)

beforexi

after xi

Florence Forbes

Message Passing

• Express as product of messages

• Recursive evaluation of messages

• Find Z by normalizing

Florence Forbes

Belief Propagation

• Extension to general tree-structured graphs• At each node:

– form product of incoming messages and local evidence– marginalize to give outgoing message– one message in each direction across every link

• Fails if there are loops

Florence Forbes

Loopy Belief Propagation

• Apply belief propagation directly to general graph– possible because message passing rules are local– need to keep iterating– might not converge

• State-of-the-art performance in error-correcting codes

Florence Forbes

Max-product Algorithm: most probable x

• Goal: find

– define

– then

• Message passing algorithm with “sum” replaced by “max”• Example:

– Viterbi algorithm for HMMs

14

Divergence de Kullback-Leibler (KL)

Mesures de divergence soient p,q des distributions non normalisées

Alpha-divergence (nombre réel quelconque)

Asymétrique, convexe

15

Exemples d’alpha-divergences

16

Minimum alpha-divergenceq est Gaussienne, minimise D(p||q)

= -1

17

Minimum alpha-divergenceq est Gaussienne, minimise D(p||q)

= 0

18

Minimum alpha-divergenceq est Gaussienne, minimise D(p||q)

= 0.5

19

Minimum alpha-divergenceq est Gaussienne, minimise D(p||q)

= 1

20

Minimum alpha-divergenceq est Gaussienne, minimise D(p||q)

= 1

21

Propriétés des alpha-divergences

• 0 cherche le mode de plus grande masse (pas le plus grand mode)– zero-forcing: p(x)=0 force q(x)=0– Sous-estime le support de p– Modélise queues plutot que la partie centrale

• ¸ 1 s’étire pour tout englober– inclusive: p(x)>0 force q(x)>0– Sur-estime le support de p

[Frey,Patrascu,Jaakkola,Moran 00]

22

Structure de l’espace en alpha

0 1

zeroforcing

inclusive (zeroavoiding)

MFBP,EP

FBP,PEP

TRW

23

• Si q est un minimum exact d’1 alpha-divergence:• Constante de normalisation:

• Si =1: Gaussienne q a moyenne,variance de p – q factorisée a les marginales de p

Autres propriétés

24

Exemple à deux variables

• q factorisée, minimise -divergence avec p• q a les correctes marginales seulement pour = 1 (BP)

x y

25

Exemple à deux variables

= 1 (BP)

DistributionBimodale

Bon Mauvais

•Marges•Masse

•Zeros•hauteurs modes

•Zeros•un mode

•Marges•Masse

= 0 (MF) 0.5

26

Exemple à deux variables

= 1

Distributionbimodale

Bon Mauvais

•Hauteurs modes

•Zeros•Marges

27

Leçons

• Pas de méthode meilleure – dépend de ce à quoi on s’intéresse

• une approx factorisée ne préserve pas les marginales (seulement pour =1)

• Ajouter y au problème peut changer la marginale estimée pour x (alors que la vraie marginale est inchangée)

28

Minimisation d’une alpha-divergence

®6= 0

q point stationaire deD®(pjjq) , q point stationaire de K L(p®q1¡ ®jjq)

Itération de point fixe

, q point stationaire de D¯ (p®=̄ q1¡ ®=̄ jjq)

q= Proj[p® q1¡ ®]Pour q qui minimise,…

Heuristique: à l’itération t, on a un qt ~q= P roj [p®q1¡ ®

t ]

qt+1 = q²y ~q1¡ ²

Moralité: une méthode simple pour minimiser une alpha-divergence est de minimiser successivement différentes KL-divergences

29

Minimisation de la KL-divergence

Cas où F est une famille exponentielle

Dans le schéma heuristique, on peut donc remplacer la première étape par un calcul d’espérances des gj pour la loi

Ex: si F est la famille des lois gaussiennes, pour mettre à jour q, on

calcule la constante de normalisation, moyenne, variance de On prend pour la gaussienne déterminée par ces valeurs de

moyenne, variance mais avec le facteur d’échelle adéquat

®= 1

q(x) = exp(P

j gj (x)ºj )

ºj sont les paramµetres, gj (x) = 1;x;x2;etc

q= P roj [p] , 8jR

xgj (x) q(x) dx =

Rx

gj (x) p(x) dx

p®q1¡ ®

p®q1¡ ®~q

~q

30

Cas où F est une famille de lois factorisées

Dans le schéma heuristique

si F famille exponentielle factorisée

q(x) = sQ

i qi (x) avec qi normalisees

q= P roj [p] , 8iR

x=x iq(x) dx =

Rx=xi

p(x) dx

, 8i qi (x) = 1s

Rx=x i

p(x) dx

, 8i qi (x) = 1s P roj [

Rx=xi

p(x) dx]

~qi (xi ) = s1¡ ®

~s qi (xi )1¡ ®R

x=x ip(x)®

Qj 6=i qj (xj )1¡ ® dx

31

Le champ moyen

Itération de point fixe hors du schéma précédent

A comparer avec

quand

®= 0

®! 0

~qi (xi ) / exp(R

x=xilogp(x)

Qj 6=i qj (xj ) dx)

~qi (xi ) = s1¡ ®

~sqi (xi )1¡ ®

Rx=x i

p(x)®Q

j 6=i qj (xj )1¡ ® dx

32

En pratique ….

Déterminer un schéma d’itération ne résout pas nécessairement le problème: ex. Calcul

d’esperance difficile…

33

Divergence globale et divergence locale

• Divergence globale:

• Divergence locale:

34

• Ecrire p comme un produit de facteurs:

• Approcher les facteurs un par un:

• Les multiplier pour avoir l’approximation:

Minimisation Distribuée

35

F famille exponentielle factorisée

Schéma d’itération

~ta(x) =Q

i ma! i (xi )

mi ! a(xi ) =Q

b6=a mb! i (xi )

~s =R

xta(x)®

Qj ma! j (xj )1¡ ®mj ! a(xj )dx

~ma! i = 1~smi ! a (xi ) P roj [ma! i (xi )1¡ ® mi ! a(xi )

...R

x=x ita(x)®

Qj 6=i ma! j (xj )1¡ ® mj ! a(xj )dx]

qi (xi ) = ma! i (xi ) mi ! a(xi ) 8a (cf HMM)

Cas particulier: ta(x) ne depend pas de xi ) ma! i (xi ) = 1

ie les messages ne sont propagés que d’un facteur “a” aux variables “xi” qu’il utilise (cas des MRFs, messages seulement entre voisins)

36

F factorisée sans contrainte de famille exponentielle est

équivalent à F exponentielle avec

– Cas du champ moyen (alpha = 0)

– Loopy Belief Propagation (alpha = 1)

Expectation Propagation (alpha= 1 + F factorisée exponentielle)

Ajoute un terme de Projection, réduit la complexité des messages…

Fractional BP et Power EP (alpha quelconque, F factorisée, sans ou avec hypothèse exponentielle)

~ma! i (xi ) / exp(R

x=x ilogta(x)

Qj 6=i ma! j (xj ) mj ! a(xj ) dx)

~ma! i (xi ) /R

x=xita(x)

Qj 6=i mj ! a(xj ) dx)

gi j (xi ) = ±(xi ¡ j )

~ma! i (xi ) / 1mi ! a (x i )

P roj [mi ! a(xi )R

x=xita(x)

Qj 6=i mj ! a(xj ) dx)

37

Passages de messages

• Messages: passés entre facteurs

• Messages: approxim. des facteurs

• Facteur a reçoit – Minimise divergence locale pour avoir – L’envoie aux autres facteurs– Répète à convergence

• Produit les 6 algos

38

Divergence globale vs. locale

En général, local global

• mais résultats similaires

• BP ne minimise pas KL globale, mais est proche

0

MF

local = globalPas de pertes

avec le passage de messages

local global

39

Une Hiérarchie d’algorithmes

BP• fully factorized• KL(p||q)

EP• exp family• KL(p||q)

FBP• fully factorized• D(p||q)

Power EP• exp family• D(p||q)

MF• fully factorized• KL(q||p)

TRW• fully factorized• D(p||q),>1

Structured MF• exp family• KL(q||p)

40

Matrice d’algorithmes

BP• fully factorized• KL(p||q)

EP• exp family• KL(p||q)

FBP• fully factorized• D(p||q)

Power EP• exp family• D(p||q)

Mesures dedivergence

Autres familles?(melanges)

MF• fully factorized• KL(q||p)

TRW• fully factorized• D(p||q),>1

Famille approximante

Structured MF• exp family• KL(q||p)

Autres divergences?

41

Qu’a-t-on apris sur la qualité des approximations?

Rien!? Mais accés à quelques propriétés de ces approximations

Guide le choix d’une mesure de divergence à minimiser et donc d’un algorithme. 3 critères:

• Complexité: quelle est la divergence la plus facile à minimiser (calculs dépendent du problème par ex)

• Famille approximante:Si proche de la vraie distribution (alpha équivalents), loin

(alpha=0 ou négatif), moyen (dépend de la tache)

• Nature de la tache:Marginales, constante de normalisation (BP)

42

Cas de l’apprentissage bayesien,modèles à données manquantes, etc.

Vraisemblance observée, sélection de modèles, distribution prédictive

• Distribution d’intéret:

• Critère à considérer:

• MAP dans HMRF: alpha-Divergences OK• Sélection de modèles dans HMRF: lien avec l’approximation

de Laplace?

Rx

p(yjx) p(x) dx

D®(R

xp(xjy) p(x) dxjj

Rx

p(xjy) q(x) dx)