Dependency Trees in Sub-linear Time and Bounded Memory (2006)

Dan Pelleg, Andrew Moore

Tags

Cached Sufficient Statistics, Efficient Statistical Algorithms, Statistical Data Mining for Astrophysics

Abstract

We focus on the problem of efficient learning of dependency trees. Once grown, they can be used as a special case of a Bayesian network, for PDF approximation, and for many other uses. Given the data, a well-known algorithm can fit an optimal tree in time that is quadratic in the number of attributes and linear in the number of records. We show how to modify it to exploit partial knowledge about edge weights. Experimental results show running time that is near-constant in the number of records, without significant loss in accuracy of the generated trees.

Full text

Download (application/pdf, 312.5 kB)

Approximate BibTeX Entry

@article{pelleg-moore-deptree,
    Year = {2006},
    Journal = {VLDB Journal},
    Volume = {15},
    Number = {3},
    Pages = {250-262},
    Author = { Dan Pelleg, Andrew Moore },
    Title = {Dependency Trees in Sub-linear Time and Bounded Memory}
}