Évaluation des algorithmes d'apprentissage de structure pour les réseaux bayésiens dynamiques.
Résumé
Les réseaux bayésiens (RB) sont connus comme l'un des formalismes les plus complets et cohérentes pour l'acquisition et la représentation des connaissances et du raisonnement à partir de données incomplètes et/ou incer-taines. L'apprentissage de la partie graphique de ces mod-èles à partir de données est un problème NP-difficile [?]. De nombreuses méthodes ont été proposées sur ce sujet [?]. L'évaluation de ces algorithmes passe classiquement par l'utilisation de métriques connues comparant un modèle appris et un modèle de référence ayant servi à générer les données d'apprentissage. Les réseaux bayésiens dynamiques (RBD) sont une classe de modèle générale et flexible permettant de représenter des processus temporels stochastiques complexes [?]. Certains algorithmes d'apprentissage de structure ont été proposés pour ces modèles, reprenant les principes des méthodes proposées dans le cas statique. Assez souvent, ces méthodes se concen-trent sur un cas particulier de RBD, les 2-TBN, réseaux à deux tranches de temps. Par contre, la comparaison de ces algorithmes est une tâche difficile car les métriques et/ou les réseaux de référence utilisés changent d'un article à un autre. De plus, l'évaluation de ces algorithmes est souvent limitée à des réseaux ayant un nombre limité de variables. Nous proposons dans ce travail deux contributions ayant pour objectif l'analyse comparative de n'importe quel algo-rithme d'apprentissage de structure pour les 2-TBN : (1) un algorithme de génération de grands 2-TBN s'appuyant sur une approche de tiling proposée dans le cas statique, et (2) une métrique pour évaluer la qualité de l'apprentissage adaptant la distance structurelle de Hamming (SHD) au cas dynamique, en prenant bien en compte toutes les spécificités liées à ces modèles. Un réseau bayésien dynamique (RBD) définit la distribution de probabilité d'une collection de variables aléatoires X[t] où X = {X 1. .. X n } est l'ensemble des variables observées au cours du temps discret t. Dans ce travail, nous considérons une classe spéciale de RBD, appelé réseaux bayésiens à deux tranche de temps (2-TBN). Un 2-TBN est un RBD qui satisfait la propriété de Markov d'ordre 1 X[t − 1] ⊥ X[t + 1] | X[t]. En conséquence, un 2-TBN est décrit par la paire (M 0 , M →). Les modèles de référence souvent utilisés dans l'évaluation des algorithmes d'apprentissage ont souvent un nombre limité de variables. Deux solutions sont possibles pour contrôler cette dimension. Il est tout d'abord possible de générer aléatoire-ment des modèles graphiques probabilistes de n'importe quelle taille [?]. Tsamardinos et al. [?] proposent de leur côté un algorithme pour la génération de grands RB par empilement (tiling) d'un premier modèle de référence. Une fois l'apprentissage réalisé, il faut ensuite appliquer une métrique comparant le modèle de référence et le modèle appris. Plusieurs mesures ont ainsi proposées dans la littéra-ture. Tsamardinos et al. [?] ont proposé une adaptation de la distance de Hamming entre les graphes tenant compte d'un problème d'identifiabilité statistique des modèles de dépendances. En effet, certains arcs d'un réseau bayésien peuvent être inversées sans changer les propriétés de dépen-dances/indépendances décrites par le modèle. Les réseaux bayésiens sont donc identifiables à une classe d'équivalence près, représentée par un graphe partiellement dirigé (PDAG) aussi appelé graphe essentiel. La métrique proposée par Tsamardinos et al. compare alors les PDAG du modèle de référence et du modèle appris afin de ne comparer que les orientations d'arcs qui sont réellement statistiquement distin-guables. L'apprentissage de structure étant une tâche difficile, cer-tains travaux proposent de réduire l'espace des solutions à l'aide de connaissances a priori, par exemple en déclarant le fait que certains arcs sont obligatoirement présents (ou ab-sents) dans le graphe final. Les classes d'équivalence décrites précédemment se doivent alors de prendre aussi cette information en compte. Meek [?] a ainsi proposé un algorithme permettant d identifier un graphe essentiel compatible avec ce type de connaissances a priori. Nous décrivons ici des nouveaux outils pour l'évaluation des algorithmes d'apprentissage de structure pour les RBD. La première contribution décrit un algorithme de génération de 2-TBN. La seconde contribution présente une nouvelle métrique pour comparer deux modèles de type 2-TBN. A. Génération de 2-TBN Dans le même état d'esprit que l'approche de tiling de Tsamardinos et al. nous proposons de générer les deux com
Domaines
Apprentissage [cs.LG]
Origine : Fichiers produits par l'(les) auteur(s)