Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Learning Inclusion-Optimal Chordal Graphs
Vincent Auvray, Louis Wehenkel
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.
Keywords: null
Pages: 18-25
PS Link:
PDF Link: /papers/08/p18-auvray.pdf
BibTex:
@INPROCEEDINGS{Auvray08,
AUTHOR = "Vincent Auvray and Louis Wehenkel",
TITLE = "Learning Inclusion-Optimal Chordal Graphs",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "18--25"
}


hosted by DSL   •   site info   •   help