L'inférence Dans Les Réseaux Bayésiens Dynamiques

L’institut Supérieur de Gestion, Tunis
L’inférence dans les Réseaux

Bayésiens Dynamiques
Rouahi Aouatef
rouahi.aouatef@hotmail.fr
2010 - 2011 1
RBD-INFÉRENCE
2
RBD-INFÉRENCE-OBJECTIF
3
RBD-INFÉRENCE-FILTRAGE
 Filtrer le bruit des observations;
 Garder une trace de l’état actuel pour une prise de décisions

rationnelles.
4
RBD-INFÉRENCE-PRÉDICTION
 Evaluer l’effet de certaines actions possibles sur l’état futur.
5
RBD-INFÉRENCE-LISSAGE
 Obtenir la meilleur estimation d’un état passé.
6
RBD-INFÉRENCE-EXPLICATION
7
RBD-INFÉRENCE
Inférence
ONLINE
EXACTE OFFLINE
APPROCHEE
8
RBD-INFÉRENCE EXACTE
L’algorithme Forwards-Backwards
(Baum et al. 1970)
 Lissage hors ligne pour un HMM;
9
RBD-INFÉRENCE-FB(1)
 Passage Avant:
Algorithme Forwards_Pass ()
Input: HMM, Séquence d’observations
Output: Probabilités Forwards αt (i)
Début
For i=1 to N do // Cas de base
Calculer α1 (i) = P (X1=i|y1)
End
For t’=2 to t do
For i=1 to N do
Calculer αt’ (i) = P (Xt’=i|y1:t’)
End
End
Return all αt (i)
End
10
 Passage Arrière:
Algorithme Backwards_Pass ()
Input: HMM, Séquence d’observations
Output: Probabilités Backwards βt (i)
Début
For i=1 to N do // Cas de base
βT (i) = 1
End
For t’=T-1 down to t+1 do
For i=1 to N do
Calculer βt’ (i) = P (yt’:T|Xt’-1=i)
End
End
Return all βt (i)
End
11
 Complexité en O(TQ2N);
 Facile à implémenter;
 Pratique tant que le nombre de nœuds cachés est réduit;
 Variables discrètes.
12
L’algorithme Frontier
(Zweig 1996)
L F R
13
RBD-INFÉRENCE-FRONTIER(1)
 hF : les nœuds cachés dans F ;
 eF : les évidences dans F ;
 eL : les évidences dans L ;
 eR : les évidences dans R ;
14
Passage Avant:
 Ajouter un nœud N de R à F si tous ses parents sont
dans la F :
P(F)= P(hF, eF ,eL, N)

= P(hF, eF ,eL) * P(N | hF, eF) ?
 Supprimer un nœud N de F à L si tous ses enfants

sont dans F:
Marginalisation du N
L := L U{N} ; F := F \ {N} :
P (F) = P (hF-N, eF-N ,eL+N)?
15
Passage Arrière:
 Ajouter un nœud N de L à F :
P(F)= P(hF, eF ,eR, N)= P(hF, eF ,eR)
 Supprimer un nœud N de F à R :
R := R U {N} ; F := F \ {N}

P (F) = P (hF-N, eF-N ,eR+N)?
Multiplication par la CPT de N puis marginalisation
16
RBD-INFÉRENCE-FRONTIER-EXEMPLE
17
 Complexité en O(TNQN+2);
 Complexité exponentielle par rapport à la taille de la frontière.
18
L’algorithme Unrolled Junction Tree
 Dérouler le RBD sut T tranches de temps;
 Construire pour chaque tranche l’arbre de jonction

correspondant;
 Appliquer un algorithme d’inférence utilisé pour les réseaux

bayésiens statiques.
19
RBD-INFÉRENCE-UJT-PRINCIPE
 Définir les nœuds interface pour chaque tranche;

Les nœuds interface sont les nœuds destination d’un arc temporel et
les parents de ces nœuds.
L’ensemble des nœuds résultant correspond à un séparateur inter-tranches.

 Construire l’arbre de jonction pour chaque tranche de temps;
Jt :( It , It+1 , Nt )
Si t=T alors Jt = ( It , Nt )
20
RBD-INFÉRENCE-UJT-EXEMPLE(1) T=3
21
t=1 t=2 t=3

RBD-INFÉRENCE-UJT-EXEMPLE(2)
D1 C1 D2 C2 D3|C3
I1 I2 I2 I2 I3 I3 I3
N1 N2 N3
J1 J2 J3
 Pour chaque arbre de jonction

L’algorithme de
Jensen
 Le transfert inter-arbres
22
RBD-INFÉRENCE-UJT
 Les tailles des cliques larges;
 Construction des arbres de jonction est NP-Difficile.
23
 L’algorithme Interface(Murphy 2001)

Optimisation de l’algorithme Frontier.
 L’algorithme de filtrage et de lissage de

Kalman( Minka 1998)
Transformer un RBD linéaire gaussien à un modèle
de filtrage de Kalman;
Effectuer un Kalman filtering ou un Kalman
smoothing.
24
RBD-INFÉRENCE APPROCHÉE
Les algorithmes déterministes
RBD discrets:
Boyen-Koller (Boyen et Koller 1998);
Factored Frontier (Murphy et Weiss 2001);
Loopy Belief Propagation : une généralisation de
BK et FF;
RBD linéaire gaussien :
Generalized Pseudo Bayesian;
Interacting Multiple Models;
RBD mixte :
Viterbi Approximation;
Expectation Propagation;
Variational Methods;
RBD non linéaire / non gaussien
Extended Kalman Filter
25
Les algorithmes stochastiques
 Méthodes Offline :
Monte Carlo Markov Chain;
 Méthodes Online :
Particle Filtering;
Sequential Monte Carlo;
Bootstrap Filter ;
… 26
Comparatif
Stochastique Déterministe
Avantages  Facile à implémenter;  Rapide
 Capable de traiter des

modèles arbitraires;
Inconvénients  Plus lent  Adapté à des classes restreintes

de RBD
27
RBD-INFÉRENCE
 RaoBlackWellised Particle
Filtering(Murphy, 2002)
 Combinaison entre l’inférence exacte et

l’inférence approchée.
28
RBD-MANIPULATION BNT
Soit le réseau bayésien dynamique suivant:
X1 X2
Y1 Y2
29
RBD-Construction BNT
intra = zeros(2);% nbre de nœuds par tranche de temps "time-slice"
intra(1,2) = 1; % le nœud 1 est relié au nœud 2 dans chaque tranche t la structure est invariante au cours du temps
inter = zeros(2);% le nbre de nœuds liés pour 2 tranches consécutives t-1 et t
inter(1,1) = 1; % le nœud 1 dans la tranche t-1 est relié au nœud 1 dans la tranche t
%spécifications des paramètres (pour simplifier nous supposons que les nœuds observés sont discrets.)
H = 2; % la cardinalité des états cachés
O = 2; % la cardinalité des états observés(évidences)
ns = [H O]; %vecteur ligne enregistrant les cardinalités des nœuds "binaires"

dnodes = 1:2; %vecteur ligne enregistrant les nœuds discrets dans chaque tranche t
eclass1 = [1 2]; eclass2 = [3 2]; eclass = [eclass1 eclass2];
bnet = mk_dbn(intra, inter, ns, 'discrete', dnodes, 'eclass1', eclass1, 'eclass2', eclass2);
bnet.CPD{1} = tabular_CPD(bnet, 1, [0.5 0.5 ]); % P(X1)

bnet.CPD{2} = tabular_CPD(bnet, 2, [0.7 0.4 0.3 0.6]); %P(Y1|X1)= P(Y2|X2)
bnet.CPD{3} = tabular_CPD(bnet, 3, [0.5 0.7 0.5 0.3]);% P(X2|X1)
names = {'X1','Y1','X2','Y2'};
carre_rond = [1 1 1 1];
draw_graph(bnet.dag,names,carre_rond);
title('Reseau Bayesien Dynamique');
RBD-Inférence BNT
engine = smoother_engine(hmm_2TBN_inf_engine(bnet));%smoothing offline=

forwards-backwards algorithm
ss=2;% slice-size: le nbre de nœuds par tranche de temps
T=2;% nbre de tranche de temps
evidence = cell(ss,T); %on a 2 nœuds par tranche ,2 tranche de temps
% évidences pour les nœuds observés

evidence{1,1} = 1; evidence{1,2} = 1;
[engine, ll] = enter_evidence(engine, evidence);
for i=1:2 %afficher les résultants

for t=1:2
marg = marginal_nodes(engine, i, t);
bel_cdt = marg.T
end
end
Références
 Murphy, Dynamic Bayesian Networks: Representation, inference and

Learning. 2002;
 David Bellot. Fusion des données avec des réseaux baysiens pour la
modélisation des systèmes dynamiques et son application en
télémédecine. 2002;
 Tomas Singliar and Denver H.Dash, Efficient inference in

persistent Dynamic Bayesian Networks.
 G. Noizet and S. Guilmineau and Ph. Leray, http://bnt.insa-

rouen.fr, . 2007;
32

L'inférence Dans Les Réseaux Bayésiens Dynamiques

Transféré par

Droits d'auteur :

Formats disponibles

L'inférence Dans Les Réseaux Bayésiens Dynamiques

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

L'inférence Dans Les Réseaux Bayésiens Dynamiques

Transféré par

Droits d'auteur :

Formats disponibles

L’institut Supérieur de Gestion, Tunis

L’inférence dans les Réseaux

 Filtrer le bruit des observations;

 Garder une trace de l’état actuel pour une prise de décisions

 Evaluer l’effet de certaines actions possibles sur l’état futur.

 Obtenir la meilleur estimation d’un état passé.

 Pratique tant que le nombre de nœuds cachés est réduit;

 hF : les nœuds cachés dans F ;

 eF : les évidences dans F ;

 eL : les évidences dans L ;

 eR : les évidences dans R ;

P(F)= P(hF, eF ,eL, N)

 Supprimer un nœud N de F à L si tous ses enfants

P(F)= P(hF, eF ,eR, N)= P(hF, eF ,eR)

 Supprimer un nœud N de F à R :

R := R U {N} ; F := F \ {N}

 Complexité exponentielle par rapport à la taille de la frontière.

 Dérouler le RBD sut T tranches de temps;

 Construire pour chaque tranche l’arbre de jonction

 Appliquer un algorithme d’inférence utilisé pour les réseaux

 Définir les nœuds interface pour chaque tranche;

L’ensemble des nœuds résultant correspond à un séparateur inter-tranches.

t=1 t=2 t=3

 Pour chaque arbre de jonction

 Les tailles des cliques larges;

 Construction des arbres de jonction est NP-Difficile.

 L’algorithme Interface(Murphy 2001)

 L’algorithme de filtrage et de lissage de

Avantages  Facile à implémenter;  Rapide

 Capable de traiter des

Inconvénients  Plus lent  Adapté à des classes restreintes

 Combinaison entre l’inférence exacte et

Soit le réseau bayésien dynamique suivant:

ns = [H O]; %vecteur ligne enregistrant les cardinalités des nœuds "binaires"

bnet.CPD{1} = tabular_CPD(bnet, 1, [0.5 0.5 ]); % P(X1)

engine = smoother_engine(hmm_2TBN_inf_engine(bnet));%smoothing offline=

% évidences pour les nœuds observés

for i=1:2 %afficher les résultants

 Murphy, Dynamic Bayesian Networks: Representation, inference and

 Tomas Singliar and Denver H.Dash, Efficient inference in

 G. Noizet and S. Guilmineau and Ph. Leray, http://bnt.insa-

Vous aimerez peut-être aussi