Auvray, Vincent[Université de Liège - ULG > Département d'électricité, électronique et informatique - 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 >]
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI-08)
24th Conference on Uncertainty in Artificial Intelligence (UAI-08)
from 9-7-2008 to 12-7-2008
[en] Machine Learning ; Graphical Models
[en] Chordal graphs can be used to encode dependency models that are representable by both directed acyclic and undirected graphs. This paper discusses a very simple and efficient algorithm to learn the chordal structure of a probabilistic model from data. The algorithm is a greedy hill-climbing search algorithm that uses the inclusion boundary neighborhood over chordal graphs. In the limit of a large sample size and under appropriate hypotheses on the scoring criterion, we prove that the algorithm will find a structure that is inclusion-optimal when the dependency model of the data-generating distribution can be represented exactly by an undirected graph. The algorithm is evaluated on simulated datasets.