ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 29/2 - 2015  - pp.153-172  - doi:10.3166/ria.29.153-172
TITRE
Apprentissage de réseaux par agrégation bayésienne d’arbres couvrants

TITLE
Structure learning by bayesian averaging over spanning trees

RÉSUMÉ
Nous proposons dans cet article une méthode d’apprentissage de structure de modèle graphique basée sur les arbres couvrants. Étant donné un échantillon indépendant, Chow et Liu (1968) ont proposé un algorithme permettant de calculer l’arbre du maximum de vraisemblance. Cet algorithme consiste en une recherche d’arbre couvrant maximal où la matrice d’information mutuelle empirique entre les paires de variables est utilisée pour pondérer les arêtes. Nous présentons ici le pendant bayésien de cette approche fréquentiste. Une distribution a posteriori est calculée sur l’espace des arbres couvrants, ce qui nous permet ensuite de donner une probabilité a posteriori pour chacune des arêtes. L’intégration sur les paramètres de chacun des modèles est évitée en effectuant une approximation de type BIC. L’algorithme utilise un résultat d’algèbre appelé théorème arbre-matrice pour effectuer tous les calculs de manière exacte et rapide.


ABSTRACT
In this paper we present a network inference method based on spanning trees. Chow & Liu (1968) proposed an algorithm computing the best tree in terms of likelihood from an independent sample. This algorithm works out the solution by finding the maximal spanning tree when the empirical mutual information matrix is used to weight the edges. We developed a Bayesian version of this frequentist approach. We compute a posterior distribution on spanning trees. We can then give posterior probabilities for the edges. We use a BIC approximation to compute the marginal likelihood on parameters under all models. The backbone of our algorithm is an algebraic result called the Matrix-Tree theorem that allows fast and exact computations.


AUTEUR(S)
Loïc SCHWALLER, Stéphane ROBIN

MOTS-CLÉS
apprentissage de réseaux, arbre couvrant, Chow et Liu, modèle graphique

KEYWORDS
Chow & Liu, graphical model, network inference, spanning tree

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (671 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier