dc.contributor.author Pérez, A. dc.contributor.author Inza, I. dc.contributor.author Lozano, J.A. dc.date.accessioned 2016-06-13T13:31:22Z dc.date.available 2016-06-13T13:31:22Z dc.date.issued 2016-01-01 dc.identifier.issn 0888-613X dc.identifier.uri http://hdl.handle.net/20.500.11824/135 dc.description.abstract During the last decades several learning algorithms have been proposed to learn probability distributions based on decomposable models. Some of these algorithms can be used to search for a maximum likelihood decomposable model with a given maximum clique size, k. 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 the fractal tree family of algorithms which approximates this problem with a computational complexity of $\mathcal{O}(k \cdot n^2 \log n)$ in the worst case, where $n$ is the number of implied random variables and N is the size of the training set. The fractal tree algorithms construct a sequence of maximal $i$-order decomposable graphs, for $i=2,...,k,$ in $k - 1$ steps. At each step, the algorithms follow a divide-and-conquer strategy that decomposes the problem into a set of separate problems. Each separate problem is efficiently solved using the generalized Chow-Liu algorithm. Fractal trees can be considered a natural extension of the Chow-Liu algorithm, from $k = 2$ to arbitrary values of $k$, and they have shown a competitive behavior to deal with the maximum likelihood problem. Due to their competitive behavior, their low computational complexity and their modularity, which allow them to implement different parallelization strategies, the proposed procedures are especially advisable for modeling high dimensional domains. dc.format application/pdf dc.language.iso eng en_US dc.rights Reconocimiento-NoComercial-CompartirIgual 3.0 España en_US dc.rights.uri http://creativecommons.org/licenses/by-nc-sa/3.0/es/ en_US dc.subject Approximating probability distributions dc.subject Bounded clique size dc.subject Learning decomposable models dc.subject Maximum likelihood problem dc.subject The Chow-Liu algorithm dc.title Efficient approximation of probability distributions with k-order decomposable models dc.type info:eu-repo/semantics/article en_US dc.identifier.doi 10.1016/j.ijar.2016.03.005 dc.relation.publisherversion http://www.sciencedirect.com/science/article/pii/S0888613X16300329 dc.rights.accessRights info:eu-repo/semantics/openAccess en_US dc.type.hasVersion info:eu-repo/semantics/acceptedVersion en_US dc.journal.title International Journal of Approximate Reasoning en_US
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's license is described as Reconocimiento-NoComercial-CompartirIgual 3.0 España