ORBi: Ammar Sourour - Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algorithm

Reference : Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algor...


	Document type :	Scientific congresses and symposiums : Paper published in a book
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/2268/67683

Title :	Sub-quadratic Markov tree mixture learning based on randomizations of the Chow-Liu algorithm
Language :	English
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 - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
	Wehenkel, Louis [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Publication date :	Sep-2010
Main document title :	Proceedings of the Fifth European Workshop on Probabilistic Graphical Models (PGM-2010)
Editor :	Myllymäki, Petri
	Roos, Antoine
	Jaakkola, Tommi
Pages :	17-24
Audience :	International
ISBN :	978-952-60-3314-3
Event name :	The Fifth European Workshop on Probabilistic Graphical Models
Event date :	from 13-09-2010 to 15-09-2010
Event place (city) :	Helsinki
Event country :	Finland
Keywords :	[en] bayesian networks ; Markov Trees ; Chow-Liu algorithm ; mixture of trees
Abstract :	[en] The present work analyzes diﬀerent 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 ﬁrst 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 units :	Systèmes et Modélisation
Funders :	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 Oﬃce ; Pascal2 network of excellence of the EC
Target :	Researchers
Permalink :	http://hdl.handle.net/2268/67683

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Restricted access	PGM210.pdf	before review	Author preprint	496.78 kB	Request copy
Open access	PGM_2010.pdf		Author postprint	500.14 kB	View/Open

All documents in ORBi are protected by a user license.

Dspace v1.5