Vers un apprentissage subquadratique pour les mélanges d’arbres

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.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