Full Citation

Title: Efficient Learning of Decomposable Models With Bounded Clique Size

Citation Type: Miscellaneous

Publication Year: 2014

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: The learning of probability distributions from data is a ubiquitous problem in the fields of Statistics and Artificial Intelligence. During the last decades several learning algorithms have been proposed to learn probabilitydistributions based on decomposable models due to their advantageous theoretical properties. Some of these algorithms can be used to search for a maximum likelihood decomposable model with a given maximum clique size, k, which controls the complexity of the model. Unfortunately, the problem of learning a maximum likelihood decomposable model given a maximum clique size is NP-hard for k > 2. In this work, we propose a family of algorithms which approximates this problem with a computational complexity of O(k n2 log n) in the worst case, where n is the number of implied random variables.The structures of the decomposable models that solve the maximum likelihood problem are called maximal k-order decomposable graphs. Our proposals, called fractal trees, construct a sequence of maximal i-order decomposablegraphs, for i = 2; :::; k, in k

User Submitted?: No

Authors: Lozano, Jose A.; P'erez, Aritz; Inza, Inaki

Publisher: University of The Basque Country

Data Collections: IPUMS USA

Topics: Methodology and Data Collection

Countries: