Evaluation des algorithmes d’apprentissage de structure pour les réseaux Bayésiens dynamiques

Contexte Nos Propositions Conclusion et perspective

Evaluation des algorithmes d’apprentissagede structure pour les réseaux Bayésiens

dynamiques

Ghada Trabelsi12

Philippe Leray2– Mounir Ben Ayed1–Adel M.Alimi1

1REGIM (Ecole Nationale d’Ingénieur de Sfax )2LINA (Ecole Polytechnique de l’Université de Nantes)

G. Trabelsi, P. Leray, M. Ben Ayed and A.M. Alimi Benchmarking DBN 1/20


Plan

1 ContexteMotivationRéseaux BayésiensEvaluation de l’apprentissageEvaluation pour les DBN

2 Nos PropositionsGénération de grands 2-TBNSHD pour les 2-TBN

3 Conclusion et perspective



Motivation

Réseaux Bayésiens Dynamiques (DBN)

Extensions des BN pour la représentation de processusaléatoires

Généralisation d’autres modèles dynamiques: HMM, ...

Apprentissage de structure pour les DBN

Apprendre un DBN à partir de données⇒ Des algorithmesexistent

Evaluer un algorithme d’apprentissage⇒ Pas de cadrecommun

Notre objectif

Comment évaluer les algorithmes d’apprentissage destructure de (grands) DBNs?



Motivation







Notre objectif




Motivation







Notre objectif




Réseaux Bayésiens (statiques) (BN)

Définition (Pearl,85)Un réseau Bayésien (BN)=(G,Θ) est caracterisé par deuxcomposantes:

G : représentation graphique des relations de dépendanceentre les variables (directed acyclic graph (DAG))Θ : ensemble de distributions de probabilités conditionelles dechaque variable sacnaht ses parents dans G



Réseaux Bayésiens dynamiques (DBN)

BN à k tranches de temps (k-TBN) (Murphy,02)processus de Markov d’ordre k − 1

défini par un réseau initial M0 et un réseau de transition M�

exemple : 2-TBN (Dean and Kanazawa,89)



Réseaux Bayésiens dynamiques (DBN)

BN à k tranches de temps (k-TBN) (Murphy,02)

(k-TBN) simplifiék-TBN sans arcs intra-temporels (Dojer,06) (Vinh et al,12)



Evaluation de l’apprentissage

Des pratiques d’évaluation communes

Benchmarks

Métriques d’évaluation

Quelques détails surla génération de grands modèles par "tiling"

la distance structurelle de Hamming (SHD)





Benchmarksdes modèles simples ou complexes (en terme de nombre devariables)

des benchmarks standards

des modèles générés d’une manière aléatoire (Ide et al. 02)

des modèles arbitrairement grands générés par "tiling"(Tsamardinos,06)

Métriques d’évaluation


la distance structurelle de Hamming (SHD)G. Trabelsi, P. Leray, M. Ben Ayed and A.M. Alimi Benchmarking DBN 6/20




Benchmarks

Métriques d’évaluationdes métriques communesutilisation des données d’apprentissage

fonctions de score (AIC, BIC, BDeu, ...)= approximation du marginal (log)likelihood

comparaison à un modèle de référence(possible lorsque lesdonnées d’apprentissage sont générées à partir de cemodèle)






Benchmarks

Métriques d’évaluationdes métriques communes

utilisation des données d’apprentissagecomparaison à un modèle de référence(possible lorsque lesdonnées d’apprentissage sont générées à partir de cemodèle)

divergence de Kullback Leibler (KL)= comparaison des distributions de probabilité sous-jacentes






Benchmarks


utilisation des données d’apprentissagecomparaison à un modèle de référence(possible lorsque lesdonnées d’apprentissage sont générées à partir de cemodèle)

distance structurelle de Hamming (SHD)






Benchmarks


utilisation des données d’apprentissage

comparaison à un modèle de référence(possible lorsque lesdonnées d’apprentissage sont générées à partir de cemodèle)


la distance structurelle de Hamming (SHD)



Tiling (Tsamardinos,06)

génération de grands modèles par "tiling" (empilement) d’unmodèle de référence



Distance structurelle de Hamming

SHDcomparaison entre les graphes, mesure classique decomparaison de graphes

adaptée par (Tsamardinos et al. 06): comparaison des PDAGpour ne compter que les différences réellement distinguablesau sens de l’équivalence de Markov.



Distance structurelle de Hamming

SHDcomparaison entre les graphes, mesure classique decomparaison de graphes

adaptée par (Tsamardinos et al. 06): comparaison des PDAGpour ne compter que les différences réellement distinguablesau sens de l’équivalence de Markov.



Evaluation pour les DBN

Pas de méthode d’évaluation standard

Benckmarkschaque étude utilise ses propres benchmarks

... avec des petits modèles de réference

mesures d’évaluation

Notre objectif

génération de benchmarks avec un grand nb de variables +une métrique d’évaluation correcte







mesures d’évaluation

Notre objectif








mesures d’évaluationutilisation des données d’apprentissage

fonctions de score (AIC, BIC, BDeu, ...)

comparaison à un modèle de référence

Notre objectif








mesures d’évaluationutilisation des données d’apprentissagecomparaison à un modèle de référence

sensitivity / specificity⇒ erreur à cause de l’équivalence de Markpv !

Notre objectif








mesures d’évaluationutilisation des données d’apprentissage

comparaison à un modèle de référence

Notre objectif




Plan






Génération de grands 2-TBN (Trabelsi,13b)

Entrée: un BN (statique) quelconque

génération du modèle initial (M0)

tiling de n copies du réseau original M.





génération du modèle de transition (M�)tiling de 2 copies de M0.





génération du modèle initial (M0)

tiling de n copies du réseau original M.

génération du modèle de transition (M�)tiling de 2 copies de M0.

généralisation possible pour les k-TBN

génération possible de k-TBN simplifiés



Résultats

Plusieurs 2-TBN (modèles et bases de données) sontdisponibles sur notre site web.(https://sites.google.com/site/dynamicbenchmarking/)

Réseaux #Vars #Arcs Arc temporel #n #kAsia_G0 8 8 3 0Asia_G� 24 31 5 3 2Alarm_G0 37 46 2 0Alarm_G� 74 110 18 2 2

Hailfinder_G0 56 66 2 0Hailfinder_G� 112 156 24 2 2Win95pts_G0 76 112 2 0Win95pts_G� 156 256 41 2 2

Andes_G0 223 338 2 0Andes_G� 446 820 144 2 2

Link_G0 724 1125 2 0Link_G� 1448 2530 280 2 2



SHD pour les 2-TBN

Définition (Trabelsi,13b)SHD(2-TBN) est une paire de

SHD entre les graphes initiaux des modèles théorique etappris

SHD entre les graphes de transition des modèles théorique etappris

SHD entre les graphes initiaux

SHD entre les graphes de transition



SHD pour les 2-TBN

Définition (Trabelsi,13b)


pas de problème: les modèles initiaux sont des BN "statiques"

solution: utilisation de SHD entre PDAG proposé parTsamardinos




SHD pour les 2-TBN

Définition (Trabelsi,13b)



problème: Des informations temporelles sont perdues encomparant les PDAGs

(Meek,95) propose PDAGK = PDAG compatible avec desconnaissances a priori K

Notre solution: adaptation du SHD entre PDAGK en utilisantles contraintes temporelles comme a priori



SHD sans correction temporelle









SHD avec correction temporelle












Plan






Conclusion et perspectives

Conclusionun algorithme pour la génération de (grands) 2-TBN

une mesure d’évaluation "correcte" dédiée à l’apprentissagedes 2-TBN

une application à l’évaluation d’un nouvel algorithmed’apprentissage de 2-TBN (dynamic MMHC)

Perspectivesextension aux k-TBNs

une mesure d’évaluation pour l’apprentissage des BN tenantcompte du fait que d’autres types de connaissances(présence/absence d’arcs, ...) ont pu être utilisées lors del’apprentissage.



Conclusion et perspectives

Conclusionun algorithme pour la génération de (grands) 2-TBN

une mesure d’évaluation "correcte" dédiée à l’apprentissagedes 2-TBN

une application à l’évaluation d’un nouvel algorithmed’apprentissage de 2-TBN (dynamic MMHC)

Perspectivesextension aux k-TBNs

une mesure d’évaluation pour l’apprentissage des BN tenantcompte du fait que d’autres types de connaissances(présence/absence d’arcs, ...) ont pu être utilisées lors del’apprentissage.


Science

Evaluation des algorithmes d’apprentissage de structure pour les réseaux Bayésiens dynamiques