Paper published in a book (Scientific congresses and symposiums)
Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algorithm
Ammar, Sourour; Leray, Philippe; Schnitzler, François et al.
2010In Myllymäki, Petri; Roos, Antoine; Jaakkola, Tommi (Eds.) Proceedings of the Fifth European Workshop on Probabilistic Graphical Models (PGM-2010)
Peer reviewed
 

Files


Full Text
PGM_2010.pdf
Author postprint (512.14 kB)
Download
Full Text Parts
PGM210.pdf
Author preprint (508.7 kB)
before review
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
bayesian networks; Markov Trees; Chow-Liu algorithm; mixture of trees
Abstract :
[en] The present work analyzes different randomized methods to learn Markov tree mixtures for density estimation in very high-dimensional discrete spaces (very large number n of discrete variables) when the sample size (N ) is very small compared to n. Several sub- quadratic relaxations of the Chow-Liu algorithm are proposed, weakening its search proce- dure. We first study na¨ıve randomizations and then gradually increase the deterministic behavior of the algorithms by trying to focus on the most interesting edges, either by retaining the best edges between models, or by inferring promising relationships between variables. We compare these methods to totally random tree generation and randomiza- tion based on bootstrap-resampling (bagging), of respectively linear and quadratic com- plexity. Our results show that randomization becomes increasingly more interesting for smaller N/n ratios, and that methods based on simultaneously discovering and exploiting the problem structure are promising in this context.
Research center :
Systèmes et Modélisation
Disciplines :
Computer science
Author, co-author :
Ammar, Sourour;  Ecole Polytechnique de l’Université de Nantes > Laboratoire d’Informatique de Nantes Atlantique > Knowledge and Decision Team
Leray, Philippe;  Ecole Polytechnique de l’Université de Nantes > Laboratoire d’Informatique de Nantes Atlantique > Knowledge and Decision Team
Schnitzler, François ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
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 :
Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algorithm
Publication date :
September 2010
Event name :
The Fifth European Workshop on Probabilistic Graphical Models
Event place :
Helsinki, Finland
Event date :
from 13-09-2010 to 15-09-2010
Audience :
International
Main work title :
Proceedings of the Fifth European Workshop on Probabilistic Graphical Models (PGM-2010)
Editor :
Myllymäki, Petri
Roos, Antoine ;  Université de Liège - ULiège > Centres généraux > Centre interdisciplinaire de formation de formateurs de l'ULg (CIFFUL)
Jaakkola, Tommi
ISBN/EAN :
978-952-60-3314-3
Pages :
17-24
Peer reviewed :
Peer reviewed
Funders :
FRIA - Fonds pour la Formation à la Recherche dans l'Industrie et dans l'Agriculture [BE]
Biomagnet IUAP network of the Belgian Science Policy Office
Pascal2 network of excellence of the EC
Available on ORBi :
since 02 August 2010

Statistics


Number of views
65 (21 by ULiège)
Number of downloads
44 (4 by ULiège)

Scopus citations®
 
5
Scopus citations®
without self-citations
2

Bibliography


Similar publications



Contact ORBi