Learning inclusion-optimal chordal graphs

Vincent Auvray, Louis Wehenkel
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:18-25, 2008.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-auvray08a, title = {Learning inclusion-optimal chordal graphs}, author = {Auvray, Vincent and Wehenkel, Louis}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {18--25}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/auvray08a/auvray08a.pdf}, url = {https://proceedings.mlr.press/r6/auvray08a.html}, abstract = {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.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Learning inclusion-optimal chordal graphs %A Vincent Auvray %A Louis Wehenkel %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-auvray08a %I PMLR %P 18--25 %U https://proceedings.mlr.press/r6/auvray08a.html %V R6 %X 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. %Z Reissued by PMLR on 09 October 2024.
APA
Auvray, V. & Wehenkel, L.. (2008). Learning inclusion-optimal chordal graphs. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:18-25 Available from https://proceedings.mlr.press/r6/auvray08a.html. Reissued by PMLR on 09 October 2024.

Related Material