Reference : Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algor...
Scientific congresses and symposiums : Paper published in a book
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/67683
Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algorithm
English
Ammar, Sourour mailto [Ecole Polytechnique de l’Université de Nantes > Laboratoire d’Informatique de Nantes Atlantique > Knowledge and Decision Team > >]
Leray, Philippe mailto [Ecole Polytechnique de l’Université de Nantes > Laboratoire d’Informatique de Nantes Atlantique > Knowledge and Decision Team > >]
Schnitzler, François mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Wehenkel, Louis mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Sep-2010
Proceedings of the Fifth European Workshop on Probabilistic Graphical Models (PGM-2010)
Myllymäki, Petri
Roos, Antoine
Jaakkola, Tommi
17-24
Yes
International
978-952-60-3314-3
The Fifth European Workshop on Probabilistic Graphical Models
from 13-09-2010 to 15-09-2010
Helsinki
Finland
[en] bayesian networks ; Markov Trees ; Chow-Liu algorithm ; mixture of trees
[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.
Systèmes et Modélisation
Fonds pour la formation à la Recherche dans l'Industrie et dans l'Agriculture (Communauté française de Belgique) - FRIA ; Biomagnet IUAP network of the Belgian Science Policy Office ; Pascal2 network of excellence of the EC
Researchers
http://hdl.handle.net/2268/67683

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
PGM210.pdfbefore reviewAuthor preprint496.78 kBRequest copy
Open access
PGM_2010.pdfAuthor postprint500.14 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.