Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks

Nicola Di Mauro, Antonio Vergari, Teresa M. A. Basile, Floriana Esposito

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Cutset Networks (CNets) are density estimators leveraging context-specific independencies recently introduced to provide exact inference in polynomial time. Learning a CNet is done by firstly building a weighted probabilistic OR tree and then estimating tractable distributions as its leaves. Specifically, selecting an optimal OR split node requires cubic time in the number of the data features, and even approximate heuristics still scale in quadratic time. We introduce Extremely Randomized Cutset Networks (XCNets), CNets whose OR tree is learned by performing random conditioning. This simple yet surprisingly effective approach reduces the complexity of OR node selection to constant time. While the likelihood of an XCNet is slightly worse than an optimally learned CNet, ensembles of XCNets outperform state-of-the-art density estimators on a series of standard benchmark datasets, yet employing only a fraction of the time needed to learn the competitors. Code and data related to this chapter are available at: https://github.com/nicoladimauro/cnet.
Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationBook Subtitle European Conference, ECML PKDD 2017, Skopje, Macedonia, September 18–22, 2017, Proceedings, Part I
EditorsMichelangelo Ceci, Jaakko Hollmén, Ljupčo Todorovski, Celine Vens, Sašo Džeroski
Place of PublicationCham
PublisherSpringer
Pages203-219
Number of pages17
Volume1
Edition1
ISBN (Electronic)978-3-319-71249-9
ISBN (Print)978-3-319-71248-2
DOIs
Publication statusPublished - 30 Dec 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
Volume1
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords / Materials (for Non-textual outputs)

  • Tractable probabilistic models
  • Cutset Networks

Fingerprint

Dive into the research topics of 'Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks'. Together they form a unique fingerprint.

Cite this