Mélanges d’arbres; Chow-Liu; apprentissage non-supervisé; perturb and combine; partitionnement approximatif
Abstract :
[fr] Dans cet article, nous comparons l’introduction d’heuristiques faibles (bootstrap, de
complexité quadratique) ou plus fortes (échantillonnage aléatoire) dans l’algorithme de Chow-
Liu en vue de l’apprentissage de densités de probabilité de type mélange d’arbres de Markov.
Nos expériences empiriques sur des problèmes de grande dimension montrent que, bien que
le bootstrap produise les résultats les plus précis en moyenne, d’autres heuristiques restent
compétitives en terme de précision, en particulier pour des ensembles d’apprentissage de petite
taille. [en] We consider randomization schemes of the Chow-Liu algorithm from weak (bagging,
of quadratic complexity) to strong ones (full random sampling, of linear complexity), for learn-
ing probability density models in the form of mixtures of Markov trees. Our empirical study
on high-dimensional synthetic problems shows that, while bagging is the most accurate scheme
on average, some of the stronger randomizations remain very competitive in terms of accuracy,
specially for small sample sizes.
Research center :
Systèmes et modélisation
Disciplines :
Computer science
Author, co-author :
Schnitzler, François ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Leray, Philippe; Ecole Polytechnique de l’Université de Nantes > Laboratoire d’Informatique de Nantes Atlantique > Knowledge and Decision Team
Wehenkel, Louis ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Language :
English
Title :
Vers un apprentissage subquadratique pour les mélanges d’arbres
Publication date :
10 May 2010
Event name :
5èmes Journées Francophones sur les Réseaux Bayésiens
Event organizer :
Philippe Leray
Event place :
Nantes, France
Funders :
FRIA - Fonds pour la Formation à la Recherche dans l'Industrie et dans l'Agriculture [BE] Wallonie-Bruxelles International, FNRS, Ministère Français des Affaires étrangères et Européennes, Ministère français de l'Enseignement supérieur et de la Recherche dans le cadre des partenariats Hubert Curien Biomagnet IUAP network of the Belgian Science Policy Office Pascal2 network of excellence of the EC
