Upload
aouatef2010
View
364
Download
2
Embed Size (px)
DESCRIPTION
les algorithmes exactes et approchés d'inférence dans les réseaux bayésiens dynamiques
Citation preview
1
L’inférence dans les Réseaux Bayésiens
Dynamiques
Rouahi [email protected]
2010 - 2011
L’institut Supérieur de Gestion, Tunis
2
RBD-INFÉRENCE
3
RBD-INFÉRENCE-OBJECTIF
4
RBD-INFÉRENCE-FILTRAGE
Filtrer le bruit des observations;
Garder une trace de l’état actuel pour une prise de décisions rationnelles.
5
RBD-INFÉRENCE-PRÉDICTION
Evaluer l’effet de certaines actions possibles sur l’état futur.
6
RBD-INFÉRENCE-LISSAGE
Obtenir la meilleur estimation d’un état passé.
7
RBD-INFÉRENCE-EXPLICATION
8
OFFLINEONLINE APPROCHEEEXACTE
RBD-INFÉRENCE
Inférence
9
RBD-INFÉRENCE EXACTE
Lissage hors ligne pour un HMM;
L’algorithme Forwards-Backwards (Baum et al. 1970)
10
RBD-INFÉRENCE-FB(1)
Passage Avant:Algorithme Forwards_Pass ()Input: HMM, Séquence d’observations Output: Probabilités Forwards αt (i)
DébutFor 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
11
Passage Arrière:Algorithme Backwards_Pass ()Input: HMM, Séquence d’observations Output: Probabilités Backwards βt (i)
DébutFor 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
RBD-INFÉRENCE-FB(2)
12
Complexité en O(TQ2N);
Facile à implémenter;
Pratique tant que le nombre de nœuds cachés est réduit;
Variables discrètes.
RBD-INFÉRENCE-FB(3)
13
RBD-INFÉRENCE EXACTEL’algorithme Frontier
(Zweig 1996)
F RL
14
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 ;
15
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:
L := L U{N} ; F := F \ {N} :P (F) = P (hF-N, eF-N ,eL+N)?
RBD-INFÉRENCE-FRONTIER(2)
Marginalisation du N
16
RBD-INFÉRENCE-FRONTIER(3)
Multiplication par la CPT de N puis marginalisation
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)?
17
RBD-INFÉRENCE-FRONTIER-EXEMPLE
18
RBD-INFÉRENCE-FRONTIER(4)
Complexité en O(TNQN+2);
Complexité exponentielle par rapport à la taille de la frontière.
19
RBD-INFÉRENCE EXACTE
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.
L’algorithme Unrolled Junction Tree
20
RBD-INFÉRENCE-UJT-PRINCIPE
Définir les nœuds interface pour chaque tranche;
L’ensemble des nœuds résultant correspond à un séparateur inter-tranches.
Construire l’arbre de jonction pour chaque tranche de temps;
Les nœuds interface sont les nœuds destination d’un arc temporel et les parents de ces nœuds.
Jt :( It , It+1 , Nt )Si t=T alors Jt = ( It , Nt )
RBD-INFÉRENCE-UJT-EXEMPLE(1)
21
t = 1
T = 3
t = 3t = 2
22
I2I1
Pour chaque arbre de jonction
Le transfert inter-arbres
N1
I3I2
N2
I3
N3
I2 I3
C1D1 D2 C2 D3|C3
J1 J2 J3
L’algorithme de Jensen
RBD-INFÉRENCE-UJT-EXEMPLE(2)
23
Les tailles des cliques larges;
Construction des arbres de jonction est NP-Difficile.
RBD-INFÉRENCE-UJT
24
RBD-INFÉRENCE EXACTE
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.
25
RBD-INFÉRENCE APPROCHÉE
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 gaussienExtended Kalman Filter
Les algorithmes déterministes
26
RBD-INFÉRENCE APPROCHÉE
Méthodes Offline :Monte Carlo Markov Chain;
Méthodes Online :Particle Filtering;Sequential Monte Carlo;Bootstrap Filter ;
Les algorithmes stochastiques
…
27
RBD-INFÉRENCE APPROCHÉE
Stochastique Déterministe
Avantages Facile à implémenter;
Capable de traiter des modèles arbitraires;
Rapide
Inconvénients
Plus lent Adapté à des classes restreintes de RBD
Comparatif
28
RBD-INFÉRENCE
RaoBlackWellised Particle Filtering(Murphy, 2002)
Combinaison entre l’inférence exacte et l’inférence approchée.
29
RBD-MANIPULATION BNT
X1
Y1
X2
Y2
Soit le réseau bayésien dynamique suivant:
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 tempsinter = zeros(2);% le nbre de nœuds liés pour 2 tranches consécutives t-1 et tinter(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ésO = 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 teclass1 = [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 tempsT=2;% nbre de tranche de tempsevidence = cell(ss,T); %on a 2 nœuds par tranche ,2 tranche de temps % évidences pour les nœuds observésevidence{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 endend
32
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;
Références