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/Unit :
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 WBI - Wallonie-Bruxelles International BELSPO - Belgian Science Policy Office EC - European Commission
Funding text :
La recherche présentée ici a pu être réalisée grâce à une bourse F.R.I.A., ainsi que le soutien de Wallonie-Bruxelles International et du Fonds de la Recherche Scientifique, du Ministère Français des Affaires étrangères et européennes, du Ministère de l’Enseignement supérieur et de la Recherche dans le cadre des Partenariats Hubert Curien.
Il a également été soutenu par le réseau IUAP Biomagnet de l’office belge de la politique scientifique et le réseau d’excellence de la communauté européenne Pascal2.
